The textbook's name is Programming Language Pragmatics 4th.
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; 96 Chapter 2 Programming Language Syntax State Transitions program stmt.list $$ on stmt_list shift and goto 2 stmt list - stmt_list stmt stmt-list - stmt stmt . id :- expr stmt . read id stmt -> 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 on $$ shift and reduce (pop 2 states, push program on input) on stmt shift and reduce (pop 2 states, push stmt_list on input) stmt stmt stmt . id := expr . read id write expr on id shift and goto 3 on read shift and goto 1 on write shift and goto 4 simt 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 2 . 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 expr term - term factor factor factor - . term . expr add op term factor . term mult op factor . ( expr ) .id 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 add op on input) on-shift and reduce (pop 1 state, push add op on input) add_op add_op . + .- Figure 2.26 CFSM for the calculator grammar (Figure 2.25). Basis and closure items in each state are separated by a horizontal rule. Trivial reduce-only states have been eliminated by use of shift and reduce" transitions. (continued) 2.3 Parsing 97 State Transitions 7. expr ->term . term term. mult op factor on FOLLOW(expr) = {id, read, write, $$, ), +, - } reduce (pop 1 state, push expr on input) on mult-op shift and goto 11 on * shift and reduce (pop 1 state, push mult op on input) on / shift and reduce (pop 1 state, push mult op on input) mult op mult.op .* / 8. on expr shift and goto 12 on term shift and goto 7 factor (.expr ) expr . term expr . expr add op term term - factor term +. term mult op factor factor expr ) factor . id factor . number on factor shift and reduce (pop 1 state, push term on input) 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) 9. stmt expr id := expr. expr. add op term on FOLLOW (stmt) = {id, read, write, $$ } reduce (pop 3 states, push stmt on input) on add op shift and goto 10 on + shift and reduce (pop 1 state, push add op on input) on-shift and reduce (pop 1 state, push add op on input) add_op add_op . + - 10. expr expr add_op. term on term shift and goto 13 on factor shift and reduce (pop 1 state, push term on input) term - term - factor factor - factor factor . term mult op factor (expr) .id . 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) term - term mult op factor factor factor factor (expr ) id . number on factor shift and reduce (pop 3 states, push term on input) 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) 12. factor expr (expr.) expr. add op term on ) shift and reduce (pop 3 states, push factor on input) on add-op shift and goto 10 on + shift and reduce (pop 1 state, push add op on input) on - shift and reduce (pop 1 state, push add op on input) add_op add_op . + .- 13. expr term expr add-op term term . mult op factor on FOLLOW(expr) = {id, read, write, $$, ), +, - } reduce (pop 3 states, push expr on input) on mult_op shift and goto 11 on * shift and reduce (pop 1 state, push mult op on input) on / shift and reduce (pop 1 state, push mult op on input) mult op mult op *.* ./ Figure 2.26 (continued) 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; 96 Chapter 2 Programming Language Syntax State Transitions program stmt.list $$ on stmt_list shift and goto 2 stmt list - stmt_list stmt stmt-list - stmt stmt . id :- expr stmt . read id stmt -> 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 on $$ shift and reduce (pop 2 states, push program on input) on stmt shift and reduce (pop 2 states, push stmt_list on input) stmt stmt stmt . id := expr . read id write expr on id shift and goto 3 on read shift and goto 1 on write shift and goto 4 simt 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 2 . 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 expr term - term factor factor factor - . term . expr add op term factor . term mult op factor . ( expr ) .id 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 add op on input) on-shift and reduce (pop 1 state, push add op on input) add_op add_op . + .- Figure 2.26 CFSM for the calculator grammar (Figure 2.25). Basis and closure items in each state are separated by a horizontal rule. Trivial reduce-only states have been eliminated by use of shift and reduce" transitions. (continued) 2.3 Parsing 97 State Transitions 7. expr ->term . term term. mult op factor on FOLLOW(expr) = {id, read, write, $$, ), +, - } reduce (pop 1 state, push expr on input) on mult-op shift and goto 11 on * shift and reduce (pop 1 state, push mult op on input) on / shift and reduce (pop 1 state, push mult op on input) mult op mult.op .* / 8. on expr shift and goto 12 on term shift and goto 7 factor (.expr ) expr . term expr . expr add op term term - factor term +. term mult op factor factor expr ) factor . id factor . number on factor shift and reduce (pop 1 state, push term on input) 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) 9. stmt expr id := expr. expr. add op term on FOLLOW (stmt) = {id, read, write, $$ } reduce (pop 3 states, push stmt on input) on add op shift and goto 10 on + shift and reduce (pop 1 state, push add op on input) on-shift and reduce (pop 1 state, push add op on input) add_op add_op . + - 10. expr expr add_op. term on term shift and goto 13 on factor shift and reduce (pop 1 state, push term on input) term - term - factor factor - factor factor . term mult op factor (expr) .id . 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) term - term mult op factor factor factor factor (expr ) id . number on factor shift and reduce (pop 3 states, push term on input) 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) 12. factor expr (expr.) expr. add op term on ) shift and reduce (pop 3 states, push factor on input) on add-op shift and goto 10 on + shift and reduce (pop 1 state, push add op on input) on - shift and reduce (pop 1 state, push add op on input) add_op add_op . + .- 13. expr term expr add-op term term . mult op factor on FOLLOW(expr) = {id, read, write, $$, ), +, - } reduce (pop 3 states, push expr on input) on mult_op shift and goto 11 on * shift and reduce (pop 1 state, push mult op on input) on / shift and reduce (pop 1 state, push mult op on input) mult op mult op *.* ./ Figure 2.26 (continued) 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
