Here is Figure 2.26:
Here is Figure 2.30:
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; 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 stint_list stmt_list . $$ stmt_list . stmt on $$ shift and reduce (pop 2 states, push program on input) on simt 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 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 . 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 .* ./ 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) 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- .- 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) 11 term term mult op factor on factor shift and reduce (pop 3 states, push term on input) factor factor - 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) factor expr add_op add_op (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) 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 0 read 1 O stmt_list 2 0 stmt.list 2 read 1 O 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 Ostmt_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 0 stmt.list 2 id 3 := 5 expr 9 O stmt_list 2 read A read B... A read B... stmt read B... stmt_list read B... read B sum... B sum :... stmt sum := ... stmt_list sum := .. sum := A... = A +... A + B... factor + B... term + B... + B write... expr + B write... + B write... add op B write... B write sum... factor write sum... term write sum... 13 write sum... expr write sum... write sum. stmt write sum... stmt_list write sum... write sum... sum write sum... factor write sum... term write aum... write sum... expr write sum... write sum... stmt write sum... stmt.list write sum.. write sum / ... sum / 2... factor / 2... term /2... / 2 $$ mult_op 2 $$ 2 $$ factor $$ term $$ Ostmt.list 2 O stmt_list 2 write 4 O stmt_list 2 write 4 O stmt_list 2 write 4 0 stmt_list 2 write 4 term 7 0 stmt_list 2 write 4 O stmt_list 2 write 4 expr 6 O stmt_list 2 shift read shift id (A) & reduce by stmt read id shift stmt & reduce by stmt_list stmt shift stmt_list shift read shift id(B) & reduce by stmt read id shift stmt & reduce by stmt_list stmt.list stmt shift stmt_list shift id (sum) shift := shift id (A) & reduce by factor id shift factor & reduce by term factor shift term reduce by expr term shift expr shift + & reduce by add-op + shift add op shift id(B) & reduce by factor id shift factor & reduce by term factor shift term reduce by expr expr add-op term shift expr reduce by stmt - id := expr shift stmt & reduce by stmt_list stmt shift stmt.list shift write shift id (sum) & reduce by factor id shift factor & reduce by term factor shift term reduce by expr term shift expr reduce by stmt ->write expr shift stmt & reduce by stmt.list stmt.list stmt shift stmt_list shift write shift id (sum) & reduce by factor id shift factor & reduce by term factor shift term shift / & reduce by mult op / shift mult_op shift number (2) & reduce by factor number shift factor & reduce by term term mult op factor shift term reduce by expr ->term shift expr reduce by stmt write expr shift stmt & reduce by stmt.list stmt.list stmt shift stmt.list shift $$ & reduce by program stmt.list $$ O stmt_list 2 O stmt_list 2 write 4 Ostmt_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 $$ expr $$ stmt $$ stmt_list SS Ostmtlist 2 program 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 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; 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 stint_list stmt_list . $$ stmt_list . stmt on $$ shift and reduce (pop 2 states, push program on input) on simt 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 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 . 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 .* ./ 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) 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- .- 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) 11 term term mult op factor on factor shift and reduce (pop 3 states, push term on input) factor factor - 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) factor expr add_op add_op (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) 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 0 read 1 O stmt_list 2 0 stmt.list 2 read 1 O 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 Ostmt_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 0 stmt.list 2 id 3 := 5 expr 9 O stmt_list 2 read A read B... A read B... stmt read B... stmt_list read B... read B sum... B sum :... stmt sum := ... stmt_list sum := .. sum := A... = A +... A + B... factor + B... term + B... + B write... expr + B write... + B write... add op B write... B write sum... factor write sum... term write sum... 13 write sum... expr write sum... write sum. stmt write sum... stmt_list write sum... write sum... sum write sum... factor write sum... term write aum... write sum... expr write sum... write sum... stmt write sum... stmt.list write sum.. write sum / ... sum / 2... factor / 2... term /2... / 2 $$ mult_op 2 $$ 2 $$ factor $$ term $$ Ostmt.list 2 O stmt_list 2 write 4 O stmt_list 2 write 4 O stmt_list 2 write 4 0 stmt_list 2 write 4 term 7 0 stmt_list 2 write 4 O stmt_list 2 write 4 expr 6 O stmt_list 2 shift read shift id (A) & reduce by stmt read id shift stmt & reduce by stmt_list stmt shift stmt_list shift read shift id(B) & reduce by stmt read id shift stmt & reduce by stmt_list stmt.list stmt shift stmt_list shift id (sum) shift := shift id (A) & reduce by factor id shift factor & reduce by term factor shift term reduce by expr term shift expr shift + & reduce by add-op + shift add op shift id(B) & reduce by factor id shift factor & reduce by term factor shift term reduce by expr expr add-op term shift expr reduce by stmt - id := expr shift stmt & reduce by stmt_list stmt shift stmt.list shift write shift id (sum) & reduce by factor id shift factor & reduce by term factor shift term reduce by expr term shift expr reduce by stmt ->write expr shift stmt & reduce by stmt.list stmt.list stmt shift stmt_list shift write shift id (sum) & reduce by factor id shift factor & reduce by term factor shift term shift / & reduce by mult op / shift mult_op shift number (2) & reduce by factor number shift factor & reduce by term term mult op factor shift term reduce by expr ->term shift expr reduce by stmt write expr shift stmt & reduce by stmt.list stmt.list stmt shift stmt.list shift $$ & reduce by program stmt.list $$ O stmt_list 2 O stmt_list 2 write 4 Ostmt_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 $$ expr $$ stmt $$ stmt_list SS Ostmtlist 2 program 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
