4. (20pt) Consider the following grammar for a declaration list: decl_list + decl_list decl ; | decl ; decl + id : type type + int | real | 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; 100 Chapter 2 Programming Language Syntax Parse stack Input stream Comment read A read B... 0 read 1 A read B... shift read stmt read B... shift id(A) & reduce by stmt ->read id samt list read B... shift stmt & reduce by stmt_list stmt O stmt list 2 read B sum... shift stmt list O stmt list 2 read 1 Baum: ... shift read O stmt list 2 simt sum =... shift id(B) & reduce by stmt read id stmt_list sum := ... shift stmt & reduce by stmt list stmt_list stmt O stmt list 2 sum := A... shift stmt list O stmt.list 2 id 3 := A +... shift id (gum) O stmt_list 2 id 3 := 5 A+B... shift := O stmt list 2 id 3 := 5 factor + B... shift id (A) & reduce by factor id 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 0 stmt_list 2 id 3 :- 5 expr 9 + B write... shift expr 0 stmt list 2 id 3 :- 5 expr 9 add op B write... shift + & reduce by add op + + 0 stmt list 2 id 3 :- 5 expr 9 add-op 10 B write sum... shift add_op 0 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 O stmt 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 nt list write sum... shift stmt & reduce by stmt list- stmt O stmt_list 2 write sum.. shift stmt list 0 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 simt list 2 write 4 expr 6 write sum... shift expr O simt list 2 stmt write sum... reduce by stmt ->write expr stmt_list write sum... shift stmt & reduce by stmt list stmt_list stmt 0 stmt list 2 write sum/... shift stmt list O stmt list 2 write 4 sum / 2... shift write O stmt_list 2 write 4 factor / 2... shift id (aum) & reduce by factor id O stmt list 2 write 4 term / 2... shift factor & reduce by term factor O stmt list 2 write 4 term 7 / 2 $$ shift term Ostmt list 2 write 4 term 7 mult op 2 $$ shift / & reduce by mult op / O stmt_list 2 write 4 term 7 mult op 11 2 $$ shift mult_op O stmt list 2 write 4 term 7 mult op 11 factor $$ shift number(2) & reduce by factor number O stmt list 2 write 4 term $$ shift factor & reduce by term term mult op factor O stmt_list 2 write 4 term 7 shift term O stmt_list 2 write 4 expr $$ reduce by expr term O stmt_list 2 write 4 expr 6 shift expr O stmt list 2 stmt $$ reduce by stmt write expr stmt.list $$ shift stmt & reduce by stmt list stmt_list stmt O stmt_list 2 $$ shift stmt list program shift $$ & reduce by program stmt.list $$ (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 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 O again and pushing program onto the input stream. 4. (20pt) Consider the following grammar for a declaration list: decl_list + decl_list decl ; | decl ; decl + id : type type + int | real | 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; 100 Chapter 2 Programming Language Syntax Parse stack Input stream Comment read A read B... 0 read 1 A read B... shift read stmt read B... shift id(A) & reduce by stmt ->read id samt list read B... shift stmt & reduce by stmt_list stmt O stmt list 2 read B sum... shift stmt list O stmt list 2 read 1 Baum: ... shift read O stmt list 2 simt sum =... shift id(B) & reduce by stmt read id stmt_list sum := ... shift stmt & reduce by stmt list stmt_list stmt O stmt list 2 sum := A... shift stmt list O stmt.list 2 id 3 := A +... shift id (gum) O stmt_list 2 id 3 := 5 A+B... shift := O stmt list 2 id 3 := 5 factor + B... shift id (A) & reduce by factor id 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 0 stmt_list 2 id 3 :- 5 expr 9 + B write... shift expr 0 stmt list 2 id 3 :- 5 expr 9 add op B write... shift + & reduce by add op + + 0 stmt list 2 id 3 :- 5 expr 9 add-op 10 B write sum... shift add_op 0 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 O stmt 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 nt list write sum... shift stmt & reduce by stmt list- stmt O stmt_list 2 write sum.. shift stmt list 0 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 simt list 2 write 4 expr 6 write sum... shift expr O simt list 2 stmt write sum... reduce by stmt ->write expr stmt_list write sum... shift stmt & reduce by stmt list stmt_list stmt 0 stmt list 2 write sum/... shift stmt list O stmt list 2 write 4 sum / 2... shift write O stmt_list 2 write 4 factor / 2... shift id (aum) & reduce by factor id O stmt list 2 write 4 term / 2... shift factor & reduce by term factor O stmt list 2 write 4 term 7 / 2 $$ shift term Ostmt list 2 write 4 term 7 mult op 2 $$ shift / & reduce by mult op / O stmt_list 2 write 4 term 7 mult op 11 2 $$ shift mult_op O stmt list 2 write 4 term 7 mult op 11 factor $$ shift number(2) & reduce by factor number O stmt list 2 write 4 term $$ shift factor & reduce by term term mult op factor O stmt_list 2 write 4 term 7 shift term O stmt_list 2 write 4 expr $$ reduce by expr term O stmt_list 2 write 4 expr 6 shift expr O stmt list 2 stmt $$ reduce by stmt write expr stmt.list $$ shift stmt & reduce by stmt list stmt_list stmt O stmt_list 2 $$ shift stmt list program shift $$ & reduce by program stmt.list $$ (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 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 O again and pushing program onto the input stream