15-411 Compiler Design: Lab 3Fall 2008Instructor: Frank PfenningTAs: Rob Arnold and Eugene MarinelliTest Programs Due: 11:59pm, Tuesday, October 7, 2008Compilers Due: 11:59pm, Tuesday, October 14, 20081 IntroductionThe goal of the lab is to implement a complete compiler for the language L3 . This language extendsL2 by functions. This means you will have to change all phases of the compiler from the secondlab. One can write some interesting rec ursive and iterative functions over integers in this language.Correctness is still paramount, but performance starts to become an issue because the code yougenerate will be executed on a set of test cases with preset time limits. These limits are set so thata correct and straightforward c ompiler without optimizations should receive full credit.2 RequirementsAs for Lab 2, you are required to hand in test programs as well as a complete working compiler thattranslates L3 source programs into correct target programs written in x86-64 assembly language.When encountering an error in the input program (which can be a lexical, grammatical, or staticsemantics error) the compiler should terminate with a non-zero exit code and print a helpful errormessage. To test the target programs, we will assemble and link them using gcc on the lab machinesand run them under fixed but generous time limits.3 L3 SyntaxThe syntax of L3 is defined by the context-free grammar in Figure 1. Ambiguities in this grammarare resolved according to the operator precedence table in Figure 2 and the rule that an elseprovides the alternative for the most recent eligible if.CommentsL2 source programs may contain C-style comments of the form /* ... */ for multi-line commentsand // for single-line comm ents. Multi-line comments may be nested (and of course the delimitersmust be balanced). Also, # should be considered as starting a single-line comment as such lineswill be used as directives for testing and possibly other uses later in the class.1hprogrami ::= hgdecli∗hfunctioni∗hgdecli ::= extern htypei hidenti ( hparamlisti ) ;hfunctioni ::= htypei hidenti ( hparamlisti ) hbodyihparamlisti ::= ε | hidenti : htypei [ , hidenti : htypei ]∗hbodyi ::= { hdecli∗hstmti∗}hdecli ::= var hidenti [ , hidenti ]∗: htypei ;htypei ::= inthstmti ::= hsimpi ; | hcontroli | ;hsimpi ::= hidenti hasopi hexpihcontroli ::= if ( hexpi ) hblocki [ else hblocki ] |while ( hexpi ) hblocki | for ( [ hsimpi ] ; hexpi ; [ hsimpi ] ) hblocki |continue ; | break ; | return hexpi ;hblocki ::= hstmti | { hstmti∗}hexpi ::= ( hexpi ) | hintconsti | hidenti | hunopi hexpi | hexpi hbinopi hexpi |hidenti ( [ hexpi [ , hexpi ]∗] )hidenti ::= [A-Za-z][0-9A-Z a-z]∗hintconsti ::= [0-9][0-9]∗(in the range 0 ≤ intconst < 232)hasopi ::= = | += | -= | *= | /= | %= | &= | ^= | |= | <<= | >>=hbinopi ::= + | - | * | / | % | < | <= | > | >= | == | !=| && | || | & | ^ | | | << | >>hunopi ::= ! | ~ | -The precedence of unary and binary operators is given in Figure 2.Non-terminals are in hangle bracketsi, optional constituents in [brackets].Terminals are in bold.Figure 1: Grammar of L32Operator Associates Meaning() n/a function call, explicit parentheses! ~ - right logical not, bitwise not, unary minus* / % left integer times, divide, modulo+ - left integer plus, minus<< >> left (arithmetic) shift left, right< <= > >= left integer comparison== != left integer equality, disequality& left bitwise and^ left bitwise exclusive or| left bitwise or&& left logical and|| left logical or= += -= *= /= %= &= ^= |= <<= >>= right assignment operatorsFigure 2: Precedence of operators, from highest to lowest4 L3 Static SemanticsThe L3 language has two kinds of identifiers: those standing for functions and those standingfor integers. These are in separate name spaces, so a function and a variable may have the samename without conflict. Reserved words of the grammar (extern, var, int, if, else, while, for,continue, break, return) cannot b e used as function or variable names.Regarding functions, several properties must be checked.• Every function that is called must be declared somewhere in the file, either using extern orwith a definition. The order of the defined functions in the file is irrelevant, but a functionmay not be declared more than once.• Functions must be called with the correct number of arguments. Since there is only one basictype in the language, namely int, this is the extent of type-checking required.• Each function must explicit return with a value. This is checked by verifying that everyfinite c ontrol flow path originating at the top of a function ends in a return statement. Aprecise specification of this condition is given in Lab 2.• There must be a function main() which returns an integer as the result of the overall com-putation (and not an exit status).• Each break or continue statement must occur inside a for or while loop.Regarding variables, we need to check two properties.3• Every variable must be declared, either as a function parameter or an explicit local variablewith a var declaration. Function parameters and local variables are local to a function andhave nothing to do with parameters or local variables in other functions. Variables may notbe redeclared, that is, names of parameters to a given function and its local variables mustall be pairwise distinct. There are no global variables.• Each local variable must be defined by an assignment before it is used. This is checked byverifying that along all control flow paths originating at the beginning of the function, eachlocal variable is assigned to before it is used. This ensures that there will be no references touninitialized variables. A precise specification of this condition is given in Lab 2.The restriction on return statements and initializing variables guarantee that the meaning ofevery valid program is deterministic: it will either return a unique value, raise a div exception, orfail to terminate.5 L3 Dynamic SemanticsIn most cases, statements have the familiar operational semantics from C. Conditionals, for, andwhile loops execute as in C. continue skips the res t of the statements in a loop body and breakjumps to the first statement after a loop. As in C, when encountering a continue inside a forloop, we jump to the step statement.The meanings of the special assignment operators are as in L2, where x op= e is the same asx = x op e.Integer Oper ato rsSince expressions contain division and modulus operations and function
View Full Document
Unlocking...