1. (40pt) Consider the language: P= {w|w{(,), [,]}*$$, all parentheses in ware properly balanced} . (a) (10pt) Construct a grammar, G, for P that is LL(1). Build its LL(1) parse table (as in Fig. 2.20) to prove that it is LL(1). (b) (10pt) Construct a grammar, G2, for P that is SLR(1) but not LL(1). Build its SLR(1) parse table (as in Fig. 2.28) to prove that it is SLR(1). Prove also that it is not LL(1). (c) (4pt) Construct a grammar, G3, for P that is not SLR(1). Prove that it is not SLR(1). (d) (4pt) Show the parse tree and the left derivation for the string [([]) ()] $$ in G. (e) (4pt) Show the trace of the table-driven LL(1) parse (as in Fig. 2.21) using G for the same string. (f) (4pt) Show the parse tree and the right derivation for the string [([]) ) ( )] $$ in G2. (g) (4pt) Show the trace of the table-driven SLR(1) parse (as in Fig. 2.30) using G2 for the same string. The grammars G1..3 above must have a production P S$$, with P not appearing anywhere else in the grammar. The parse tables are built as done in the textbook, not as done by jflap. You can use jflap to help but you need to modify its output. Do not upload screenshots from jflap. Write your own tables. Top-of-stack nonterminal id program stmt list 1 2 number read write Current input token ) 921 125192 stmt 4 expr 7 7 term_tail 9 - term 10 10 factor tail 12 factor 14 15 add.op mult.op 7 1 1 1 1 02 1111001216 11119 12 21 $$ 11111 6381 18 19 FIGURE 2.20 LL(I) parse table for the calculator language. Table entries indicate the production to predict (as numbered in Figure 2.23). A dash indicates an error When the top-of-stack symbol is a terminal, the appropriate action is always to match it against an incoming token from the scanner. An auxiliary table, not shown here, gives the right-hand-side symbols for each production. Parse stack program stmt list $$ stmt stmt list $$ read id stmt-list $$ id stmt list $$ stmt list $$ stmt stmt list $$ read id stmt.list $$ id stmt list $$ stmt list $$ stmt stmt list $$ id:expr stmt list $$ expr stmt list $$ expr stmt list $$ term term tail stmt.list $$ factor factor-tail term-tail stmt-list $$ id factor tail term.tail stmt.list $$ factor tail term.tail stmt.list $$ term tail stmt list $$ add_op term term_tail stmt list $$ +term term tail stmt list $$ term term tail stmt.list $$ factor factor-tail term-tail stmt list $$ id factor tail term.tail stmt.list $$ factor tail term tail stmt.list $$ term tail stmt.list $$ stmt list $$ stmt stmt list $$ write expr stmt-list $$ Input stream read A read B read A read B read A read B read A read B A read B... read B sum: read B sum: read B sum: B sum := sum: A+B sum: A+B... sum: A+B. := A + B... A+B... A+B. A+ B... A+B. + B write sum.. + B write sum. + B write sum +B write sum. B write sum... B write sum B write sum... write sum... write sum write... write sum write... write sun write... Comment initial stack contents predict program predict stmt-list predict stmt match read match id predict stmt.list predict stmt match read match id stmt Jist $$ stmt stmt. list read id stmt stmt list read id predict stmt.list stmt stmt.list predict stmtid : expr match id match :- predict expr term term.tail predict term factor factor-tail predict factor id match id predict factor_tail predict term Jail add.op term term tail predict add.op + match + predict term factor factor-tail predict factor id match id predict factor_tail predict term taile predict stmt.list stmt stmt list write sum write... predict stmt write expr expr stmt list $$ term term tail stmt.list $$ factor factor_tail term tail stmt list $$ id factor tail term.tail stmt.list $$ factor tail term tail stmt.list $$ term_tail stmt-list $$ stmt-list $$ stmt stmt list $$ write expr stmt list $$ sum write sum / 2 sum write sum / 2 sum write sum/2 sum write sum / 2 write sum/2 write sun / 2 term term tail match write predict expr predict term predict factor id match id factor factor tail predict factor-tail e predict term-taile predict stmt.list-stmt stmt list predict stmt write expr write sum / 2 write sun / 2 write sum / 2 expr stmt list $$ sum/2 match write term term tail stmt.list $$ sum / 2 predict expr term term.tail factor factor tail term.tail stmt-list $$ sum / 2 predict term factor factor-tail id factor-tail term_tail stmt-list $$ sum / 2 predict factor id factor tail term.tail stmt.list $$ 12 match id mult.op factor factor.tail term.tail stmt.list $$ /2 I factor factor tail term tail stmt.list $$ /2 factor factor tail term tail stmt list $$ 2 number factor tail term.tail stmt.list $$ factor tail term.tail stmt-list $$ 2 predict factor tailmult.op factor factor tail predict mult.op/ match/ predict factor number match number term tail stmt.list $$ stmt list $$ $$ Figure 2.21 Trace of a table-driven LL(I) parse of the sum-and-average program of Example 2.24. predict factor-tail predict term tail predict stmt.liste figure Top-of-stack state sl 0 $2 b3 Current input symbol et f ao mo id lit rw :- sl s4 b2 12 CIFFIT 11 2 3 4 5 6 7 8 9 10 11 / $$ + ( ) 233gi bl 11111 11 b14 b15 16 17 17 r7 b16 b17 17 31 " b14 b15 111211 111199 353 $7 b9 $7 b9 $10 16 sll r b12 b13 b12 b13 16 r6 17 17 s12 s7 b9 29 b12 b13 $10 14 32111SIS 2133122 14 14 $13 b9 b10 b12 b13 b12 b13 $10 r8 111 1112 I T 12 13 bil b14 b15 r8 r8 b16 b17 18 FIGURE 2.28 SLR(I) parse table for the calculator language. Table entries indicate whether to shift (s), reduce (r), or shift and then reduce (b). The accompanying number is the new state when shifting, or the production that has been recognized when (shifting and) reducing. Production numbers are given in Figure 2.25. Symbol names have been abbreviated for the sake of formatting. A dash indicates an error An auxiliary table, not shown here, gives the left-hand-side symbol and right-hand-side length for each production. Parse stack 0 0 read 1 0 0 0 stmt-list 2 0 stmt list 2 read 1 0 stmt list 2 0 0 stmt list 2 0 stmt list 2 id 3 0 stmt list 2 id 3 := 5 0 stmt list 2 id 3 := 5 0 stmt list 2 id 3 := 5 0 stmt list 2 id 3 - 5 term 7 0 stmt list 2 id 3 := 5 0 stmt-list 2 id 3 := 5 expr 9 0 stmt list 2 id 3 := 5 expr 9 0 stmt list 2 id 3:5 expr 9 add.op 10 0 stmt list 2 id 3:5 expr 9 add.op 10 0 stmt list 2 id 3 := 5 expr 9 add.op 10 Input stream read A read B... A read B... stmt read B... stmt-list read B... read B sum... B sum:... stmt sum ... stmt list sum :... sum A... := A+... A+B... factor + B... term + B... + B write... expr+B write... + B write... add.op B write... B write sum... factor write sum... term write sum... 0 stmt list 2 id 3-5 expr 9 add_op 10 term 13 write sum... 0 stmt list 2 id 3 := 5 0 stmt-list 2 id 3 := 5 expr 9 0 stmt. list 2 0 0 stmt list 2 0 stmt list 2 write 4 0 stmt list 2 write 4 0 stmt-list 2 write 4 0 stmt-list 2 write 4 term 7 0 stmt list 2 write 4 0 stmt list 2 write 4 expr 6 0 stmt list 2 0 expr write sum... write sum... stmt write sum... Comment shift read shift id (A) & reduce by stmt shift stmt & reduce by stmt-list shift stmt.list shift read shift id (B) & reduce by stmt shift stmt & reduce by stmt.list shift stmt.list shift id (sum) shift := read id stmt read id stmt list stmt shift id (A) & reduce by factor id shift factor & reduce by term shift term reduce by expr term shift expr shift + & reduce by add-op shift add.op factor shift id (B) & reduce by factor id shift factor & reduce by term shift term factor reduce by exprexpr add_op term shift expr reduce by stmtid := expr stmt. list write sum... shift stmt & reduce by stmt.list stmt write sum... sum write sum... factor write sum... term write sum... write sum... expr write sum... write sum... stmt write sum... shift stmt.list shift write shift id (sum) & reduce by factor id shift factor & reduce by term shift term reduce by expr term shift expr reduce by stmt write expr factor stmt list write sum... shift stmt & reduce by stmt list stmt list stmt 0 stmt list 2 0 stmt list 2 write 4 0 stmt list 2 write 4 0 stmt-list 2 write 4 0 stmt list 2 write 4 term 7 0 stmt list 2 write 4 0 stmt list 2 write 4 expr 6 0 stmt list 2 0 0 stmt-list 2 0 stmt-list 2 write 4 0 stmt.list 2 write 4 0 stmt list 2 write 4 0 stmt list 2 write 4 term 7 0 stmt list 2 write 4 term 7 0 stmt-list 2 write 4 term 7 mult-op 11 0 stmt-list 2 write 4 term 7 mult-op 11 0 stmt-list 2 write 4 0 stmt list 2 write 4 term 7 0 stmt list 2 write 4 0 stmt list 2 write 4 expr 6 0 stmt list 2 write sum... sum write sum... factor write sum. term write sum... write sum... expr write sum... write sum... stmt write sum... stmt list write sum... write sum/... sum/2... factor/2... term/2... / 2 $$ mult.op 2 $$ 2 $$ factor $$ term $$ $$ expr $$ $$ stmt $$ stmt list $$ $$ program shift stmt.list shift write shift id (sum) & reduce by factor id shift factor & reduce by term shift term reduce by exprterm shift expr reduce by stmt write expr factor shift stmt & reduce by stmt list stmt_list stmt shift stmt-list shift write shift id (sum) & reduce by factor id shift factor & reduce by term factor shift term shift/ & reduce by mult.op / shift mult-op number term mult-op factor 0 0 stmt-list 2 0 [done] shift number (2) & reduce by factor shift factor & reduce by term shift term reduce by expr term shift expr reduce by stmt->write expr shift stmt & reduce by stmt-list stmt-list stmt shift stmt-list shift $$ & reduce by program stmt.list $s Figure 2.30 Trace of a table-driven SLR(I) parse of the sum-and-average program. States in the parse stack are shown in boldface type. Symbols in the parse stack are for clarity only; they are not needed by the parsing algorithm. Parsing begins with the initial state of the CFSM (State 0) in the stack. It ends when we reduce by program stmt_list $$, uncovering State 0 again and pushing program onto the input stream