(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 b end; char; array 1 .. 2 of real; 96 Chapter 2 Programming Language Syntax State 0. program . stmt_list $$ 1. 2. stmt-list stmt-list stmt stmt list stmt stmt stmt id := expr read id stmt write expr stmt->read. id program stmt_list. $$ stmt list stmt list. stmt stmt id:expr read id write expr Transitions on stmt_list shift and goto 2 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 on id shift and reduce (pop 2 states, push stmt on input) 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 stmt stmt 3. stmt id := expr on := shift and goto 5 4. stmt write expr on expr shift and goto 6 expr expr - term term expr add.op term factor term mult_op factor (expr ) term term factor factor id factor number 5. stmt id : expr expr expr term term factor factor id factor number 6. stmt write expr. expr expr.add_op term add op add_op expr add-op term factor term mult.op factor (expr ) on term shift and goto 7 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) on expr shift and goto 9 on term shift and goto 7 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) 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) 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 7. expr term term term. mult.op factor mult.op mult_op . 8. factor expr ) expr expr 9. 10. term expr add op term term factor . term term mult.op factor factor (expr ) factor . id factor number stmtid := expr. expr expr.add_op term add op add op . expr expr add.op term term factor term term mult_op factor factor ( expr) factor .id factor number Transitions 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) on expr shift and goto 12 on term shift and goto 7 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) 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) on term shift and goto 13 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) 11. term term multop factor on factor shift and reduce (pop 3 states, push term on input) factor (expr ) factor id factor number expr.add.op term 12. factor (expr . ) expr add op add-op 13. expr expr add.op term. term mult.op mult_op Figure 2.26 (continued) term. mult-op factor 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) 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) 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) 100 Chapter 2 Programming Language Syntax Parse stack 0 0 read 1 0 0 0 stmt list 2 0 stmt list 2 read 1 0 stmt list 2 0 0 stmt list 2 0 stmt list 2 Input stream read A read B... A read B... stmt read B... stmt list read B... read B sum... B sum :-... stmt sum :5 stmt list sum ... sum : A... := A + ... A+ B... factor + B... term + B... + B write... expr + B write... + B write... add op B write... 0 stmt list 2 id 3 0 stmt-list 2 id 3 := 5 id 3 := 5 0 stmt list 2 id 3 := 5 0 stmt list 2 id 3 := 5 term 7 0 stmt list 2 id 3 := 5 0 stmt list 2 id 3 := 5 expr 9 0 stmt list 2 id 3 := 5 expr 9 0 stmt list 2 0 stmt list 2 id 3-5 expr 9 add.op 10 id 3:5 expr 9 add.op 10 id 3 := 5 expr 9 add-op 10 term 13 write sum... 0 stmt list 2 id 3 := 5 0 stmt list 2 id 3 := 5 expr 9 0 stmt list 2 0 stmt list 2 0 stmt list 2 0 0 stmt list 2 0 stmt-list 2 id 3-5 expr 9 add.op 10 write 4 0 stmt list 2 write 4 0 stmt list 2 write 4 0 stmt-list 2 write 4 term 7 0 stmt list 2 write 4 stmt list 2 write 4 0 stmt-list 2 0 0 stmt list 2 0 stmt list 2 write 4 0 stmt list 2 write 4 0 stmt list 2 0 stmt list 2 write 4 expr 6 write 4 term 7 0 stmt list 2 write 4 term 7 0 stmt list 2 write 4 term 7 mult.op 11 0 stmt list 2 write 4 term 7 mult-op 11 0 stmt-list 2 write 4 0 stmt list 2 write 4 term 7 0 stmt list 2 write 4 0 stmt-list 2 write 4 expr 6 0 stmt list 2 0 0 stmt-list 2 0 [done] B write sum... factor write sum term write sum expr write sum... write sum... stmt write sum... Comment shift read shift id(A) & reduce by stmt read id shift stmt & reduce by stmt-list shift stmt list shift read stmt 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