Consider the following LL(1) grammar for a simplified subset of Lisp:
P → E $$
E → atom
   → ’ E
   → ( E Es )
Es → E Es
   →

(a) What is FIRST(Es)? FOLLOW(E)? PREDICT(Es → ∈)?

(b) Give a parse tree for the string (cdr ‚(a b c)) $$.

(c) Show the left-most derivation of (cdr ‚(a b c)) $$.

(d) Show a trace, in the style of Figure 2.21, of a table-driven top-down parse of this same input.

(e) Now consider a recursive descent parser running on the same input.

At the point where the quote token (’) is matched, which recursive descent routines will be active (i.e., what routines will have a frame on the parser’s run-time stack)?

Figure 2.21:

Transcribed Image Text:

Parse stack Input stream Comment program read A read B ... initial stack contents predict program stmt list $$ predict stmtJist stmt stmt list stmt list $$ read A read B stmt stmt list $$ read A read B read id stmnt Jist $$ read A read B predict stmt + read id id stmt-list $$ A read B... match read stmt list $$ read B sum : match id stmt stmt Jist $$ predict stmt Jist – stmt stmt Jist read B sum: read id stmtlist $$ read B sum : predict stmt + read id id stmtlist $$ B sum :=... match read stmtlist $$ sum := A + B match id ... stmt stmt list $$ id := expr stmt_list $$ predict stmt Jist → stmt stmtlist predict stmt - id := expr sum := A + B sum := A + B := expr stmtlist $$ expr stmt list $$ term term_tail stmt list $$ factor factor_tail term.tail stmt.list $$ id factor_tail term_tail stmtlist $$ factor_tail term tail stmt list $$ := A + B... match id A + B... match := A + B predict expr + term term_tail predict term factor factor.tail predict factor id ... A + B A + B + B write sum match id + B write sum + B write sum + B write sum predict factor_tail € predict term tail + add_op term term tail predict add_op -+ term tail stmt list $$ add_op term term.tail stmt list $$ + term term tail stmtlist $$ term term_tail stmt.list $$ B write sum match + factor factor_tail term tail stmt.list $$ id factor_tail term_tail stmtlist $$ factor_tail term tail stmtlist $$ term tail stmt list $$ predict term + factor factor.tail predict factor +id B write sum B write sum write sum. write sum write .. predict factor_tail € match id predict term tail € predict stmtJist stmt stmt list predict stmt write expr stmtlist $$ write sum write ... write sum write... write sum write... stmt stmtlist $$ write expr stmt Jist $$ expr stmt list $$ term term_tail stmt.list $$ factor factor_tail term_tail stmt list $$ id factor_tail term tail stmt list $$ factor_tail term tail stmtlist $$ termtail stmt.list $$ sum write sum / 2 match write predict expr - term term tail predict term factor factor.tail predict factor id sum write sum / 2 sum write sum / 2 sum write sum / 2 write sum / 2 write sum / 2 write sum / 2 match id predict factor_tail € predict term tail € stmt list $$