Compiler Construction using Flex and Bison Anthony A. Aaby Walla Walla College cs.wwc.edu [email protected] Version of April 22, 2005 Copyright (cid:13)c 2003 Anthony A. Aaby Walla Walla College 204 S. College Ave. College Place, WA 99324 E-mail: [email protected] LaTeX sources available by request. This material may be distributed only subject to the terms and conditions set forth in the Open Publication License, v1.0 or later (the latest version is presently available at http://www.opencontent.org/openpub This book is distributed in the hope it will be useful, but without any war- ranty; without even the implied warranty of merchantability or fitness for a particular purpose. The author encourages wide distribution of this book for personal and com- mercialuse,providedtheabovecopyrightnoticeremainsintactandthemethod adheres to the provisions of the Open Publication Liscense located at http://www.opencontent.org/openpub In summary, you may copy and distribute this book free of charge or for a profit. No explicit permission is required from the author for reproduction of this book in any medium, physical or electronic. Note, derivative works and translations of this document must include the original copyright notice must remain intact. To Pamela Aaby i ii Contents 1 Introduction 1 2 The Parser 5 3 The Scanner 9 4 The Context 13 5 Optimization 19 6 Virtual Machines 21 7 Code Generation 27 8 Peephole Optimization 37 9 Exercises 39 A Simple - The complete implementation 47 A.1 The parser: Simple.y . . . . . . . . . . . . . . . . . . . . . . . . . 47 A.2 Directions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 A.3 The scanner: Simple.lex . . . . . . . . . . . . . . . . . . . . . . . 52 A.4 The symbol table: ST.h . . . . . . . . . . . . . . . . . . . . . . . 53 A.5 The code generator: CG.h . . . . . . . . . . . . . . . . . . . . . . 54 A.6 The stack machine: SM.h . . . . . . . . . . . . . . . . . . . . . . 55 A.7 Sample program: test simple . . . . . . . . . . . . . . . . . . . . 57 B Lex/Flex 59 B.1 Lex/Flex Examples . . . . . . . . . . . . . . . . . . . . . . . . . . 59 B.2 The Lex/Flex Input File . . . . . . . . . . . . . . . . . . . . . . . 61 B.3 The Generated Scanner . . . . . . . . . . . . . . . . . . . . . . . 66 B.4 Interfacing with Yacc/Bison . . . . . . . . . . . . . . . . . . . . . 67 iii C Yacc/Bison 69 C.1 An Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 C.2 A Yacc/Bison Example . . . . . . . . . . . . . . . . . . . . . . . 71 C.3 The Yacc/Bison Input File . . . . . . . . . . . . . . . . . . . . . 72 C.4 Yacc/Bison Output: the Parser File . . . . . . . . . . . . . . . . 86 C.5 Parser C-Language Interface. . . . . . . . . . . . . . . . . . . . . 87 C.6 Debugging Your Parser . . . . . . . . . . . . . . . . . . . . . . . 90 C.7 Stages in Using Yacc/Bison . . . . . . . . . . . . . . . . . . . . . 95 iv Chapter 1 Introduction Alanguagetranslatorisaprogramwhichtranslatesprogramswritteninasource languageintoanequivalentprograminanobjectlanguage. Thesourcelanguage isusuallyahigh-levelprogramminglanguageandtheobjectlanguageisusually themachinelanguageofanactualcomputer. Fromthepragmaticpointofview, thetranslatordefinesthesemanticsoftheprogramminglanguage,ittransforms operationsspecifiedbythesyntaxintooperationsofthecomputationalmodelto somerealorvirtualmachine. Thischaptershowshowcontext-freegrammarsare usedintheconstructionoflanguagetranslators. Sincethetranslationisguided bythesyntaxofthesourcelanguage,thetranslationissaidtobesyntax-directed. Acompilerisatranslatorwhosesourcelanguageisahigh-levellanguageand whose object language is close to the machine language of an actual computer. The typical compiler consists of several phases each of which passes its output to the next phase • The lexical phase (scanner) groups characters into lexical units or tokens. The input to the lexical phase is a character stream. The output is a streamoftokens. Regularexpressionsareusedtodefinethetokensrecog- nized by a scanner (or lexical analyzer). The scanner is implemented as a finite state machine. Lex and Flex are tools for generating scanners: programs which recognize lexical patterns in text. Flex is a faster version of Lex. In this chapter Lex/Flex refers to either of the tools. The appendix on Lex/Flex is a condensation of the manual page “flexdoc” by Vern Paxon. • The parser groups tokens into syntactical units. The output of the parser is a parse tree representation of the program. Context-free grammars are used to define the program structure recognized by a parser. The parser is implemented as a push-down automata. 1 YaccandBisonaretoolsforgeneratingparsers: programswhichrecognize thestructuregrammaticalstructureofprograms. Bisonisafasterversion of Yacc. In this chapter, Yacc/Bison refers to either of these tools. The sectionsonYacc/Bisonareacondensationandextensionofthedocument “BISONtheYacc-compatibleParserGenerator”byCharlesDonnellyand Richard Stallman. • The semantic analysis phase analyzes the parse tree for context-sensitive information often called the static semantics. The output of the semantic analysis phase is an annotated parse tree. Attribute grammars are used to describe the static semantics of a program. This phase is often combined with the parser. During the parse, infor- mation concerning variables and other objects is stored in a symbol table. The information is utilized to perform the context-sensitive checking. • The optimizer applies semantics preserving transformations to the anno- tated parse tree to simplify the structure of the tree and to facilitate the generation of more efficient code. • The code generator transforms the simplified annotated parse tree into objectcodeusingruleswhichdenotethesemanticsofthesourcelanguage. The code generator may be integrated with the parser. • The peep-hole optimizer examines the object code, a few instructions at a time, and attempts to do machine dependent code improvements. In contrast with compilers an interpreter is a program which simulates the execution of programs written in a source language. Interpreters may be used either at the source program level or an interpreter may be used it interpret an objectcodeforanidealizedmachine. Thisisthecasewhenacompilergenerates code for an idealized machine whose architecture more closely resembles the source code. Thereareseveralothertypesoftranslatorsthatareoftenusedinconjunction with a compiler to facilitate the execution of programs. An assembler is a translatorwhosesourcelanguage(anassemblylanguage)representsaone-to-one transliteration of the object machine code. Some compilers generate assembly code which is then assembled into machine code by an assembler. A loader is a translator whose source and object languages are machine language. The sourcelanguageprogramscontaintablesofdataspecifyingpointsintheprogram which must be modified if the program is to be executed. A link editor takes collectionsofexecutableprogramsandlinksthemtogetherforactualexecution. A preprocessor is a translator whose source language is an extended form of somehigh-levellanguageandwhoseobjectlanguageisthestandardformofthe high-level language. Forillustrationpurposes,wewillconstructacompilerforasimpleimperative programming language called Simple. The context-free grammar for Simple is 2 program::=LET[declarations]INcommand sequenceEND declarations::=INTEGER[id seq]IDENTIFIER. id seq::=id seq... IDENTIFIER, command sequence::=command... command command::=SKIP; |IDENTIFIER:=expression; |IFexpTHENcommand sequenceELSEcommand sequenceFI; |WHILEexpDOcommand sequenceEND; |READIDENTIFIER; |WRITEexpression; expression::=NUMBER|IDENTIFIER|’(’expression’)’ |expression+expression|expression−expression |expression∗expression|expression/expression |expressionˆ expression |expression=expression |expression<expression |expression>expression Figure 1.1: Simple given in Figure 1.1 where the non-terminal symbols are given in all lower case, the terminal symbols are given in all caps or as literal symbols and, where the literal symbols conflict with the meta symbols of the EBNF, they are enclosed with single quotes. The start symbol is program. While the grammar uses upper-case to high-light terminal symbols, they are to be implemented in lower case. There are two context sensitive requirements; variables must be declared before they are referenced and a variable may be declared only once. 3 4