(20pt) Consider the following grammar for a declaration list: decl_list + decl_list decl ; | decl ; decl id : type type -> intreal char | array const .. const of type | record decl_list end Construct the characteristic finite state machine for this grammar (like the one in Fig.2.26, p.96-97 of textbook). Then use it to parse (like in Fig.2.30, p.100 of textbook) the program below: foo : record a : char; b: array 1 .. 2 of real; end; State Transitions 0. program - stmt_list $$ on stmt list shift and goto 2 stmt_list stmt_list stmt stmt stmt - . stmt_list stmt +. stmt . id :- expr . read id write expr on stmt shift and reduce (pop 1 state, push stmt list on input) on id shift and goto 3 on read shift and goto 1 on write shift and goto 4 1. stmt - read .id on id shift and reduce (pop 2 states, push stmt on input) 2. program stmt_list. $$ stmt_list stmt_list. stmt stmt - id := expr stmt -. read id stmt - . write expr on $$ shift and reduce (pop 2 states, push program on input) on stmt shift and reduce (pop 2 states, push stmt_list on input) on id shift and goto 3 on read shift and goto 1 on write shift and goto 4 3. stmt id . := expr on := shift and goto 5 4. stmt + write expr on expr shift and goto 6 on term shift and goto 7 on factor shift and reduce (pop 1 state, push term on input) expr +. term expr + expr add op term term factor term . term mult op factor factor . ( expr ) factor +. id factor - . number on shift and goto 8 on id shift and reduce (pop 1 state, push factor on input) on number shift and reduce (pop 1 state, push factor on input) stmt id :- . expr on expr shift and goto 9 on term shift and goto 7 on factor shift and reduce (pop 1 state, push term on input) expr . term expr +. expr add_op term term + factor term . term mult op factor factor . ( expr ) factor +.id factor + number on shift and goto 8 on id shift and reduce (pop 1 state, push factor on input) on number shift and reduce (pop 1 state, push factor on input) 6. stmt write expr. expr - expr. add op term on FOLLOW(stmt) = {id, read, write, $$ } reduce (pop 2 states, push stmt on input) on add op shift and goto 10 on + shift and reduce (pop 1 state, push addop on input) on - shift and reduce (pop 1 state, push add-op on input) add_op add_op 7. + 7.- Figure 2.26 CFSM for the calculator grammar (Figure 2.25). Basis and closure items in each state are Parse stack Input stream Comment O read 1 O stmt_list 2 O stmt_list 2 read 1 0 stmt_list 2 O stmt_list 2 O stmt list 2 id 3 O stmt list 2 id 3 := 5 O stmt list 2 id 3 := 5 O stmt_list 2 id 3 := 5 O stmt_list 2 id 3 :- 5 term 7 O stmt list 2 id 3 :- 5 0 stmt list 2 id 3 :- 5 expr 9 O stmt_list 2 id 3 := 5 expr 9 O stmt_list 2 id 3 :- 5 expr 9 add-op 10 O 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 term O stmt_list 2 id 3 := 5 O stmt_list 2 id 3 :- 5 expr 9 O stmt list 2 read A read B... A read B... shift read stmt read B... shift id (A) & reduce by stmt read id stmt list read B... shift stmt & reduce by stmt_list stmt read B sum ... shift stmt_list B sum := ... shift read stmt sum :-... shift id(B) & reduce by stmt + read id stmt list sum := ... shift stmt & reduce by stmt list stmt list stmt sum := A... shift stmt_list := A + ... shift id (sum) A + B... shift := factor + B... shift id (A) & reduce by factor id term + B... shift factor & reduce by term factor + B write... shift term expr + B write... reduce by expr term + B write... shift expr addop B write... shift + & reduce by add op + + B write sum... shift add-op factor write sum... shift id(B) & reduce by factor id term write sum ... shift factor & reduce by term factor 13 write sum... shift term expr write sum... reduce by expr expr add_op term write sum... shift expr stmt write sum... reduce by stmt id := expr stmt list write sum... shift stmt & reduce by stmt list stmt 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... shift expr 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 +/ 2 $$ shift mult op factor $$ shift number (2) & reduce by factor number term $$ shift factor & reduce by term ->term mult op factor shift term expr $$ reduce by expr term shift expr stmt $$ 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 $$ 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 O stmt list 2 write 4 expr 6 O stmt list 2 O stmt list 2 O stmt list 2 write 4 0 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 O stmt.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 $$ O stmt_list 2 $$ (done) 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 (20pt) Consider the following grammar for a declaration list: decl_list + decl_list decl ; | decl ; decl id : type type -> intreal char | array const .. const of type | record decl_list end Construct the characteristic finite state machine for this grammar (like the one in Fig.2.26, p.96-97 of textbook). Then use it to parse (like in Fig.2.30, p.100 of textbook) the program below: foo : record a : char; b: array 1 .. 2 of real; end; State Transitions 0. program - stmt_list $$ on stmt list shift and goto 2 stmt_list stmt_list stmt stmt stmt - . stmt_list stmt +. stmt . id :- expr . read id write expr on stmt shift and reduce (pop 1 state, push stmt list on input) on id shift and goto 3 on read shift and goto 1 on write shift and goto 4 1. stmt - read .id on id shift and reduce (pop 2 states, push stmt on input) 2. program stmt_list. $$ stmt_list stmt_list. stmt stmt - id := expr stmt -. read id stmt - . write expr on $$ shift and reduce (pop 2 states, push program on input) on stmt shift and reduce (pop 2 states, push stmt_list on input) on id shift and goto 3 on read shift and goto 1 on write shift and goto 4 3. stmt id . := expr on := shift and goto 5 4. stmt + write expr on expr shift and goto 6 on term shift and goto 7 on factor shift and reduce (pop 1 state, push term on input) expr +. term expr + expr add op term term factor term . term mult op factor factor . ( expr ) factor +. id factor - . number on shift and goto 8 on id shift and reduce (pop 1 state, push factor on input) on number shift and reduce (pop 1 state, push factor on input) stmt id :- . expr on expr shift and goto 9 on term shift and goto 7 on factor shift and reduce (pop 1 state, push term on input) expr . term expr +. expr add_op term term + factor term . term mult op factor factor . ( expr ) factor +.id factor + number on shift and goto 8 on id shift and reduce (pop 1 state, push factor on input) on number shift and reduce (pop 1 state, push factor on input) 6. stmt write expr. expr - expr. add op term on FOLLOW(stmt) = {id, read, write, $$ } reduce (pop 2 states, push stmt on input) on add op shift and goto 10 on + shift and reduce (pop 1 state, push addop on input) on - shift and reduce (pop 1 state, push add-op on input) add_op add_op 7. + 7.- Figure 2.26 CFSM for the calculator grammar (Figure 2.25). Basis and closure items in each state are Parse stack Input stream Comment O read 1 O stmt_list 2 O stmt_list 2 read 1 0 stmt_list 2 O stmt_list 2 O stmt list 2 id 3 O stmt list 2 id 3 := 5 O stmt list 2 id 3 := 5 O stmt_list 2 id 3 := 5 O stmt_list 2 id 3 :- 5 term 7 O stmt list 2 id 3 :- 5 0 stmt list 2 id 3 :- 5 expr 9 O stmt_list 2 id 3 := 5 expr 9 O stmt_list 2 id 3 :- 5 expr 9 add-op 10 O 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 term O stmt_list 2 id 3 := 5 O stmt_list 2 id 3 :- 5 expr 9 O stmt list 2 read A read B... A read B... shift read stmt read B... shift id (A) & reduce by stmt read id stmt list read B... shift stmt & reduce by stmt_list stmt read B sum ... shift stmt_list B sum := ... shift read stmt sum :-... shift id(B) & reduce by stmt + read id stmt list sum := ... shift stmt & reduce by stmt list stmt list stmt sum := A... shift stmt_list := A + ... shift id (sum) A + B... shift := factor + B... shift id (A) & reduce by factor id term + B... shift factor & reduce by term factor + B write... shift term expr + B write... reduce by expr term + B write... shift expr addop B write... shift + & reduce by add op + + B write sum... shift add-op factor write sum... shift id(B) & reduce by factor id term write sum ... shift factor & reduce by term factor 13 write sum... shift term expr write sum... reduce by expr expr add_op term write sum... shift expr stmt write sum... reduce by stmt id := expr stmt list write sum... shift stmt & reduce by stmt list stmt 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... shift expr 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 +/ 2 $$ shift mult op factor $$ shift number (2) & reduce by factor number term $$ shift factor & reduce by term ->term mult op factor shift term expr $$ reduce by expr term shift expr stmt $$ 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 $$ 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 O stmt list 2 write 4 expr 6 O stmt list 2 O stmt list 2 O stmt list 2 write 4 0 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 O stmt.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 $$ O stmt_list 2 $$ (done) 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