Write an LL(1) parser generator in purely functional Scheme. If you consult Figure 2.24, remember that you will need to use tail recursion in place of iteration. Assume that the input CFG consists of a list of lists, one per nonterminal in the grammar. The first element of each sublist should be the nonterminal; the remaining elements should be the right-hand sides of the productions for which that nonterminal is the left-hand side. You may assume that the sublist for the start symbol will be the first one in the list. If we use quoted strings to represent grammar symbols, the calculator grammar of Figure 2.16 would look like this:

Your output should be a parse table that has this same format, except that every right-hand side is replaced by a pair (a 2-element list) whose first element is the predict set for the corresponding production, and whose second element is the right-hand side. For the calculator grammar, the table looks like this:

You may want to define a right_context function that takes a nonterminal B as argument and returns a list of all pairs (A, β), where A is a nonterminal and β is a list of symbols, such that for some potentially different list of symbols α, A → α B β. This function is useful for computing FOLLOW sets. You may also want to build a tail-recursive function that recomputes FIRST and FOLLOW sets until they converge. You will find it easier if you do not include ∈ in either set, but rather keep a separate estimate, for each nonterminal, of whether it may generate ∈.

Figure 2.24

Figure 2.16

Transcribed Image Text:

'(("program" ("stmt_list" "$$")) ("stmt_list" ("stmt" "stmt_list") ()) ("stmt" ("id" ":=" "expr") ("read" "id") ("write" "expr")) ("expr" ("term" "term_tail")) ("term" ("factor" "factor_tail")) ("term_tail" ("add_op" "term" "term_tail") ()) ("factor_tail" ("mult_op" "factor" "FT") ()) ("add_op" ("+") ("-")) ("mult_op" ("*") ("/")) ("factor" ("id") ("number") ("(" "expr" ")")))