Consider the language: P= {w | WE{(,), [,]}*$$, all parentheses in w are properly balanced} . (a) (10pt) Construct a grammar, G1, 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 G1. (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 Current input token ) id number read write $$ 1 1 2 1 3 2 5 6 7 7 1 2 4 7 9 10 12 14 9 9 8 12 12 12 12 program simt list simt expr term_tail term 10 10 factor tail factor 15 13 add.cop 16 mult.op 18 19 FIGURE 2.20 LL() 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. 17 Parse stack Input stream Comment 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 $s stmt.list $$ stmt stmt list $$ id := expr stmt list $$ :- expr stmt.list $$ expr stmt.list $s 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 fail stmt.list $$ term term fail stmt.list $$ factor factor-tail term-tail stmt list ss id factor-tail term tail stmt.list $$ factor.tail term fail stmt.list $$ term tail stmt.list $$ stmt.list $$ stmt stmt list $$ write expr stmt.list $$ read A read B initial stack contents read A read B predict program stmt list $$ read A read B predict stmt_list stmt stmt list read A read B predict stmt read id A read B... match read read B sum :- match id read B sum :- predict stmt.list stmt stmt.list read B sum :- predict stmt read id B sum := match read sum := A + B match id sum := A + B predict stmt.list stmt stmt.list sum := A + B predict stmt id := expr := A + B.. match id A + B match :- A + B predict expr term term_tail A + B predict term factor factor-tail A B... predict factorid + B write sum match id + B write sum predict factor-taile + B write sum predict term fail add-op term term fail + B write sum predict add-op-++ B write sum match + Bwrite sum predict term + factor factor-tail B write sum predict factor id write sum... match id write sum write... predict factor.tail write sum write predict term tail + write sum write... predict stmt_list stmt stmt list write sum write predict stmt ->write expr expr stmt.list $$ sum write sum / 2 term term.tail stmt.list $$ sum write sum / 2 factor factor-tail term.tail stmt list $$ sum write sum / 2 id factor-tail term tail stmt.list $$ sum write sum / 2 factor-tail term fail stmt.list $$ write sum / 2 term-tail stmt list $$ write sum/ 2 stmt list $$ write sum/ 2 stmt stmt list $$ write sum/ 2 write expr stmt list $$ write sum / 2 expr stmt.list $8 sum / 2 term term fail stmt.list $$ sum / 2 factor factor-tail term-tail stmt-list $$ sum/ 2 id factor-tail term-tail stmt-list $$ sum / 2 factor-tail term-tail stmt.list $$ / 2 mult.op factor factor-tail term tail stmt.list $$ / 2 / factor factor tail term fail stmt.list $$ / 2 factor factor tail term.tail stmt list $$ 2 number factor-tail term fail stmt.list $$ 2 factor-tail term tail stmt.list $$ term-tail stmt.list $$ stmt.list $$ $$ match write predict expr term term-tail predict term => + factor factor tail predict factor id match id predict factor-taile predict term-tail - predict stmt.list-stmt stmt.list predict stmt write expr match write predict expr term term_tail predict term + factor factor-tail predict factor id match id predict factor-tail + mult.op factor factor fail predict mult.op +/ match/ predict factor number match number predict factor-tail +E predict term fail te predict stmt.list  Figure 2.21 Trace of a table-driven LL(1) parse of the sum-and-average program of Example 2.24. figure Top-of-stack state Current input symbol mo id lit I 2 3 1 do ( ) . / $$ 58 6 6 17 IIIIIII r6 17 11 s8 s10 14 14 0 $2 b3 53 sl s4 1 b5 2. b2 33 sS4 b1 3 55 4 s6 s7 b9 b12b13 5 59 $7 b9 b12b13 6 s10 6 b14 b15 7 sil 17 17 17 b16b17 8 s12 s7 b9 b12b13 9 14 b14 b15 10 $13 b9 b12 613 11 b10 b12 613 12 s10 bil b14b15 13 s11 18 616 b17 FIGURE 2.28 SLR(1) 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. 14 1 18 r8 Parse stack Input stream Comment shift expr 0 read A read B... 0 read 1 A read B... shift read 0 stmt read B... shift id(A) & reduce by stmt read id 0 stmt-list read B... shift stmt & reduce by stmt_list stmt O stmt.list 2 read B sum... shift stmt-list 0 stmt.list 2 read 1 B sum :-... shift read O stmt.list 2 stmt sum :... shift id(B) & reduce by stmt + read id 0 stmt.list sum :- ... shift stmt & reduce by stmt.list + stmt_list stmt 0 stmt.list 2 sum := A... shift stmt.list O stmt.list 2 id 3 :- A+ shift id (sum) 0 stmt.list 2 id 3 := 5 A+B... shift := O stmt.list 2 id 3 :- 5 factor + B... shift id (A) & reduce by factorid O stmt.list 2 id 3 :- 5 term + B... shift factor & reduce by term + factor O stmt_list 2 id 3 :- 5 term 7 + B write... shift term O stmt.list 2 id 3 :- 5 expr+ B write... reduce by expr term O stmt-list 2 id 3 :- 5 expr 9 + B write... O stmt.list 2 id 3 :- 5 expr 9 add-op B write... shift + & reduce by add-op ++ O stmt.list 2 id 3 :- 5 expr 9 add-op 10 B write sum... shift add op O stmt.list 2 id 3 :- 5 expr 9 add-op 10 factor write sum... shift id (B) & reduce by factor id O stmt.list 2 id 3 := 5 expr 9 add-op 10 term write sum... shift factor & reduce by term + factor Ostmt_list 2 id 3 :- 5 expr 9 add-op 10 term 13 write sum... shift term O stmt_list 2 id 3 := 5 expr write sum... reduce by expr + expr add_op term O stmt_list 2 id 3 :- 5 expr 9 write sum... shift expr O stmt.list 2 stmt write sum... reduce by stmt + id := expr 0 stmt.list write sum... shift stmt & reduce by stmt.list-stmt O stmt.list 2 write sum... shift stmt.list O stmt.list 2 write 4 sum write sum... shift write O stmt.list 2 write 4 factor write sum... shift id (sum) & reduce by factor id O stmt.list 2 write 4 term write sum... shift factor & reduce by term  factor O stmt.list 2 write 4 term 7 write sum... shift term O stmt.list 2 write 4 expr write sum... reduce by expr term O stmt.list 2 write 4 expr 6 write sum... O stmt list 2 stmt write sum... reduce by stmt - write expr 0 stmt.list write sum... shift stmt & reduce by stmt.list - stmt_list stmt shift expr shift expr O stmt.list 2 O stmt.list 2 write 4 O stmt.list 2 write 4 0 stmt.list 2 write 4 O stmt.list 2 write 4 term 7 O 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 O stmt.list 2 write 4 O stmt.list 2 write 4 O stmt.list 2 write 4 term 7 O stmt.list 2 write 4 term 7 O stmt-list 2 write 4 term 7 mult op 11 Ostmt-list 2 write 4 term 7 mult-op 11 O stmt list 2 write 4 O stmt.list 2 write 4 term 7 O stmt.list 2 write 4 O stmt.list 2 write 4 expr 6 O stmt_list 2 0 O stmt-list 2 0 [done] write sum... shift stmt.list sum write sum... shift write factor write sum... shift id (sum) & reduce by factor id term write sum.. shift factor & reduce by term factor write sum... shift term expr write sum reduce by expr term write sum... stmt write sum... reduce by stmt - write expr stmt_list write sum... shift stmt & reduce by stmt_list-+ stmt_list stmt write sum/... shift stmt-list sum / 2... shift write factor / 2... shift id (sum) & reduce by factor id term / 2... shift factor & reduce by term + factor / 2 $$ shift term mult.op 2 $$ shift / & reduce by mult.op +1 2 $$ shift mult-op factor $$ shift number (2) & reduce by factor + number term $$ shift factor & reduce by term  term mult-op factor $$ shift term reduce by expr - term $s shift expr stmt $s reduce by stmt + write expr stmt_list $$ shift stmt & reduce by stmt-list stmt_list stmt $$ shift stmt.list program shift $$ & reduce by program stmt.list $s expr $$ Figure 2.30 Trace of a table-driven SLR(1) 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.