(20pt) Consider the following grammar for a declaration list: decl_list + decllist 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; 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 stmt read .id on id shift and reduce (pop 2 states, push stmt on input) 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 -.id = expr stmt . read id stmt to write expr 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 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 7. 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) 5. 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) 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 ./ factor (.expr ) on expr shift and goto 12 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. 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. on term shift and goto 13 on factor shift and reduce (pop 1 state, push term on input) expr expr addop. 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) 11. 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. on) shift and reduce (pop 3 states, push factor on input) on add op shift and goto 10 factor (expr.) expr -> expr. add op term add op +.+ add-op -.- on + shift and reduce (pop 1 state, push add op on input) on-shift and reduce (pop 1 state, push add op on input) 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_opt./ Figure 2.26 continued) 100 Chapter 2 Programming Language Syntax Parse stack Input stream Comment O read 1 O stmt list 2 0 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 O 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 O stmt list 2 id 3 := 5 expr 9 add-op 10 O 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 O stmt list 2 O 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 O stmt.list 2 write 4 expr 6 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 add-op 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 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 Ostmt list 2 write 4 term 7 O stmt list 2 write 4 O stmt list 2 write 4 expr 6 Ostmt list 2 $$ O stmt list 2 [done] 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 O again and pushing program onto the input stream. (20pt) Consider the following grammar for a declaration list: decl_list + decllist 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; 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 stmt read .id on id shift and reduce (pop 2 states, push stmt on input) 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 -.id = expr stmt . read id stmt to write expr 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 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 7. 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) 5. 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) 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 ./ factor (.expr ) on expr shift and goto 12 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. 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. on term shift and goto 13 on factor shift and reduce (pop 1 state, push term on input) expr expr addop. 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) 11. 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. on) shift and reduce (pop 3 states, push factor on input) on add op shift and goto 10 factor (expr.) expr -> expr. add op term add op +.+ add-op -.- on + shift and reduce (pop 1 state, push add op on input) on-shift and reduce (pop 1 state, push add op on input) 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_opt./ Figure 2.26 continued) 100 Chapter 2 Programming Language Syntax Parse stack Input stream Comment O read 1 O stmt list 2 0 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 O 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 O stmt list 2 id 3 := 5 expr 9 add-op 10 O 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 O stmt list 2 O 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 O stmt.list 2 write 4 expr 6 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 add-op 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 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 Ostmt list 2 write 4 term 7 O stmt list 2 write 4 O stmt list 2 write 4 expr 6 Ostmt list 2 $$ O stmt list 2 [done] 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 O again and pushing program onto the input stream
