fig2.26 and fig 2.30 are below
mm 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; State Transitions 0. program stilist $$ on stil.list shift and goto 2 S t .Jist Statlist stra St.Jist - St Str . id :- expr Str . read id Str .write expr on star shift and reduce (pop 1 state, push statlist on input) on id shift and goto 3 on read shift and goto 1 on write shift and goto 4 1. Sant read. id on id shift and reduce (pop 2 states, push stron input) s program strit.list list . $$ Sit.list Smit on s shift and reduce (pop 2 states, push program on input) on sm shift and reduce (pop 2 states, push smt.list on input) - stm Str str .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. Stil i d . - expr on :-shift and goto 5 1. str 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 expr term termi - factor factor factor terme . expr add-op term factor term made 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) 5. sit 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 term term factor factor factor . expr add op term factor . ferm 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. st expr write expr. expr. add op terme on FOLLOW(sm) = {id, read, write, 38 } reduce pop 2 states, push sten 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_opo 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) expr id term Start read id , add op 12 add_op read stmt_list-2 term vrite writes t term write mult op mult op 13 expr__ add_op mm 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; State Transitions 0. program stilist $$ on stil.list shift and goto 2 S t .Jist Statlist stra St.Jist - St Str . id :- expr Str . read id Str .write expr on star shift and reduce (pop 1 state, push statlist on input) on id shift and goto 3 on read shift and goto 1 on write shift and goto 4 1. Sant read. id on id shift and reduce (pop 2 states, push stron input) s program strit.list list . $$ Sit.list Smit on s shift and reduce (pop 2 states, push program on input) on sm shift and reduce (pop 2 states, push smt.list on input) - stm Str str .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. Stil i d . - expr on :-shift and goto 5 1. str 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 expr term termi - factor factor factor terme . expr add-op term factor term made 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) 5. sit 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 term term factor factor factor . expr add op term factor . ferm 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. st expr write expr. expr. add op terme on FOLLOW(sm) = {id, read, write, 38 } reduce pop 2 states, push sten 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_opo 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) expr id term Start read id , add op 12 add_op read stmt_list-2 term vrite writes t term write mult op mult op 13 expr__ add_op
