PLI Tutorial 5
Bottom-up parsing and simple Scheme evaluators 

(Lm.n refers to Louden, Exercise m.n.)

Complete Tutorial 4.

Part A.  LALR(1) parsing.

1. (L5.1) Consider the following grammar:

   E -> "(" L ")" | id
   L -> L "," E | E

   a. Construct the SLR(1) parsing table for this grammar.
   b. Show the parsing stack and the actions of an SLR(1) 
      parser for the input string
      ((a),b,(a,b))
   c. Is the grammar LR(0)?  If not, describe the LR(0) conflict.

2. (L5.3) Consider the following grammar:

   A -> A "(" A ")" | empty

   a. Construct the SLR(1) parsing table for this grammar.
   b. Show the parsing stack and the actions of an SLR(1)
      parser for the input string
      (()()) 
   c. Is the grammar LR(0)?  If not, describe the LR(0) conflict.

3. (L5.12) Show that the following grammar is not LALR(1):

   S -> a A d | b B d | a B e | b A e
   A -> c
   B -> c

4. The following ambiguous grammar generates the same strings
   as the grammar of L5.3 above (namely, all strings of nested
   parentheses):

   A -> A A | "(" A ")" | empty

   Will a Yacc-generated parser using this grammar recognize
   all legal strings?  Why or why not?

5. (L5.28 and 5.33) Rewrite the Yacc calculator specification 
   given in the Resources page so that:
   a. It avoids the exp/term/factor distinction but instead uses 
      associativity and precedence declarations to specify these
      properties of operators, and also handles unary minus.
   b. Generates the following useful error messages:
      "missing right parenthesis", e.g., for the string (2+3
      "missing left parenthesis", e.g., for the string 2+3)
      "missing operator", e.g., for the string 2 3
      "missing operand", e.g., for the string (2+)

6. (L5.34) The following grammar represents simple arithmetic 
   expressions in a Scheme-like prefix notation:

   lexp -> number | "(" op lexp-seq ")"
   op -> "+" | "-" | "*" | "/"
   lexp-seq -> lexp-seq lexp | lexp

   For example, the expression (* (- 2) 3 4) has value -24.
   Wrote a Yacc specification for a program that will compute
   and print the value of expressions in this syntax.
   (Hint: This will require rewriting the grammar, and a method
   to apply an operator to the values of an lexp-seq.

Part B. Simple Scheme evaluators.

1. Study evaluators eval5.s (definitions with dynamic scope rules
   and eval6.s (definitions with static scope rules) and use some 
   "diff" tool to find all differences between the two files.

2. Load evaluator eval6.s, run (mc-scheme), and enter each of the 
   following expressions in turn:

   (define (f x)
      (define (g y) (+ x y))
      g)
   f
   (f 2)

   Carefully explain what you see in each case.

3. Extend evaluator eval6.s so that it implements let and let* 
   expressions.

4. Read about letrec expressions, and modify eval4.s (or your 
   answer to question 3) so that it also implements letrec 
   expressions.