COP 4620/5625PROGRAMMING LANGUAGETRANSLATORSInstructor: Manuel BermudezFALL 2005FINAL EXAMTake-home, Drop-dead deadline: 12 noon Friday Dec. 16Turn in at my office or at E301 CSEProblem 1 (10p.)Problem 2 (20p.)Problem 3 (15p.)Problem 4 (15p.)Problem 5 (15p.)Problem 6 (15p.)Problem 7 (15p.)SCORE (105p.)NAMEFall 2002 COP-4640/5625 Final Page 2 of 21PROBLEM 1. (10 points)Write a string-to-tree transduction grammar,with the following characteristics.1. The language is composed of expressions, with operators and the atomic symbol ’a’.2. The language has the following operator precedence hierarchy.LevelOperator Type of Op. AssociativityLeast binding ’&’,’*’ Binary Infix Left’ˆ’,’%’,’˜’ Binary Infix Right’#’,’+’ Binary Infix Left’|’ Unary Prefix None’@’ Unary Postfix NoneMost binding ’(’ ’)’ Embedding NoneShowthe derivation tree and the abstract syntax tree of the following expression:a&a*|a#aˆ||a@+a%a˜aFall 2002 COP-4640/5625 Final Page 3 of 21PROBLEM 2. (20 points)The following string-to-tree transduction grammar describes the language of regularexpressions overalphabet {a, b, c}.E0 -> E0 ’|’ E1 => ’|’-> E1E1 -> E1 E2 => ’cat’-> E2E2 -> E2 ’list’ E3 => ’list’-> E3E3 -> E4 ’+’ => ’+’-> E4 ’*’ => ’*’-> E4 ’?’ => ’?’-> E4E4 -> ’(’ E0 ’)’-> ’a’ => ’a’-> ’b’ => ’b’-> ’c’ => ’c’This language consists of regular expressions. Here are a couple of sample regularexpressions:1) (a | b)* c? (b a)+2) (a* | b)* list c a+The language has the following operator precedence hierarchy.Level Operator Type of Op. AssociativityLeast binding ’|’ Binary Infix Left’’ Binary Infix Left’list’ Binary Infix Left’+’,’*’,’?’Unary Postfix NoneMost binding ’(’ ’)’ Embedding NoneFall 2002 COP-4640/5625 Final Page 4 of 211) Showthat the above gramamr is not LL(1).2) Transform the grammar to makeitLL(1), calculate Select sets and showthe modi-fied grammar is LL(1).3) Showthe parse table for the modified grammar.4) Write arecursive descent parser (in pseudo-code) for this language, adding’BuildTree’ statements to build the Abstract Syntax Tree for the original grammar.5) Showastep-by-step parse for each of the twosample regular expressions shownabove.Ineach step, showthe stack, the remaining input, and anyBuildTree invoca-tions.6) Construct the LR(0) item sets, and build the ACTION and GOTO tables of theLR(0) parser.7) Showthat the grammar is NOTLR(0).8) Is the grammar SLR(1) ? Showthe necessary analysis.9) Is the grammar LALR(1) ? Showthe necessary analysis.10) Using your ACTION and GOTO tables, showastep-by-step LR parse for each ofthe twosample regular expressions shown above.Ineach step, showthe stack, theremaining input, and the action taken (shift/reduce). Then takethe sequence ofreductions performed by the parser,and use them to build (bottom-up) the AbstractSyntax tree for the input string.Fall 2002 COP-4640/5625 Final Page 5 of 21PROBLEM 3. (15 points)Consider the following context-free grammar.S → QQ → RrT→ RR → sT→ tT → R1) Showthat the grammar is NOTLL(1).2) Modify the grammar to makeitLL(1).3) Construct First, Followand Select sets (as necessary) to prove that the newgrammaris LL(1).4) Construct the corresponding LL(1) (a.k.a. OPF) parse table.5) Hand-simulate the execution of the classical top-down parsing algorithm, using yourparse table, for the input string "sstrst ". For each step, showthe stack, the input,and the result of OPF.Then takethe sequence of productions produced by OPF anduse them to build (top-down) the derivation tree for the input string.Fall 2002 COP-4640/5625 Final Page 6 of 21PROBLEM 4. (15 points)Consider the same grammar as in Problem 3:S → QQ → RrT→ RR → sT→ tT → Ra) Construct the LR(0) item sets, and build the ACTION and GOTO tables of theLR(0) parser.b) Showthat the grammar is NOTLR(0).c) Is the grammar SLR(1) ? Showthe necessary analysis.d) Is the grammar LALR(1) ? Showthe necessary analysis.e) Hand-simulate the execution of the LR parsing algorithm, using your ACTION andGOTO tables (modified in c), for the input string "sstrst". For each step, showthestack, the input, and the action taken (shift/reduce). Then takethe sequence ofreductions performed by the parser,and use them to build (bottom-up) the derivationtree for the input string.Fall 2002 COP-4640/5625 Final Page 7 of 21PROBLEM 5. (15 points)Youare about to (partially) write a compiler-interpreter for roman numerals. Belowis a (slightly incomplete) grammar that recognizes a list of roman numerals, separated bycommas. Each numeral is between 1 and 3999. In case you don’tremember howromannumerals work, the following rules should refresh your memory:1) Roman numerals are composed of symbols I (one), V (five), X (ten), L (fifty),C(one hundred), D (fivehundred), and M (one thousand).2) A smaller number placed in front of a larger number is subtracted from it. (e.g.IV means four). Only one such smaller number can be subtracted at a time(e.g. IIV does not mean 3). Other restrictions apply (see the grammar).3) A number placed after a greater or equal number is added to it (e.g. DC means600, XIII means 13, and MMM means 3000). Again, other restrictions apply.Romans → Roman ( ’,’Roman)* => ’romans’Roman → Thous Hunds Tens Ones => ’ ’Thous → M? M? M? => ’ ’Hunds → CC?C?=>’ ’→ C(D+M)=>’ ’→ DC?C?C?=>’ ’→Tens → XX?X?=>’ ’→ X(L+C)=>’ ’→ LX?X?X?=>’ ’→Ones → II?I?=>’ ’→ I(V+X)=>’ ’→ VI?I?I?=>’ ’→M → ’M’ => ’1000’D → ’D’ => ’500’C → ’C’ => ’100’L → ’L’=>’50’X → ’X’ => ’10’V → ’V’ => ’5’I → ’I’ => ’1’a) Is the above language of Roman numerals a context-free language, or is it aregular language ? Justify your answer.b) Some of the tree transduction parts are blank. Each one should be either "+" or"-". YOU FILL THEM IN.Fall 2002 COP-4640/5625 Final Page 8 of 21Now, assume someone has already undertaken the task of developing a recursivedescent parser for this grammar.c) Showthe derivation tree and the abstract syntax tree for the following input:DLVII, MI, MCMXCIVd) Belowisa(slightly incomplete) roman compiler back-end program, written inpseudo code. The code for cases "Plus" and "Minus" is missing. YOUFILLTHEM IN.program RomanBackEnd(input,output);constOne = ’1’;Five = ’5’;Ten=’10’;Fifty =