HW 2: Syntax AnalysisCSC 4351, Spring 2014Due: 26 February 20141. Context free grammars, LL and LR parsingConsider the following simple context free grammars:Grammar G1Grammar G2G → A$ G → A$A → ǫ A → ǫA → bAb A → AbbThe start symbols are G, the nonterminals are G and A, and the terminal symbols are b and $ (end offile). Note that these grammars generate the same language: strings consisting of even numbers of bsymbols (including zero of them).(a) Attempt to show a shift-reduce parse of the input string bbbb for a parser for grammar G1. Showthe contents of the stack, the input, and the actions (in the style of Figure 3.18 on Page 58 butwithout the subscripts for the parse states).Indicate any conflicts and describe why they are conflicts. Is G1LR(1)? Is it LR(0)?(b) Attempt to show a shift-reduce parse of the input string bbbb for a parser for grammar G2. Showthe contents of the stack, the input, and the actions (in the style of Figure 3.18 on Page 58 butwithout the subscripts for the parse states).Indicate any conflicts and describe why they are conflicts. Is G2LR(1)? Is it LR(0)?(c) Indicate whether G1and G2are LL(1). You don’t need to construct their LL(1) parse tables, butyou may argue from other properties.(d) Of the language classes we have discussed in class, what is the smallest category into whichL(G1) fits? Justify your answer. [Hint: This is a trick question!]12. Context free grammars, LL parsingConsider the following grammar:E → E + T | TT → id | id() | id(L)L → E, L | EThe nonterminals are E, T , and L. The terminals are +, id, (, ), ;. The start symbol is E.(a) Modify the grammar such that it can be parsed by an LL(1) parser.(b) Show Nullable, FIRST, and FOLLOW and derive the LL(1) parse table for the modified gram-mar.(c) Give the (non-abstract) parse tree produced by your grammar for the inputa + b(c,
View Full Document