COM 3351 Out: April 29, 1993 Dr. Wand Due: May 6, 1993

Problem Set 4: Interactive Parsing Using Streams

For this problem set, you will modify the scanner and parser found in

/course/com3351/pub/mp4.s.

1. Write a procedure check-parser that will take a Scheme list and check to see if it is a legal parser according to the list-of-frames representation.

2. Modify the parser driver in /course/com3351/pub/mp4.s to create an interactive read-parse-print loop using the scanner automaton-1 and the parser parser-2. Your program should print a prompt, accept characters until a command is found, and pretty-print the resulting parse tree. It should finish when a parse error occurs or when the token end is found as the first token of a command. A typical session with the read-parse-print loop might look something like:

> (read-parse-print-loop)
rpp> x := y
(assignment x (var-expression y))
rpp> exit
#f
> (test2)
rpp> x:=y
(assignment x (var-expression y))
rpp> begin x:=y ; u := (v + u) end
(compound-command
   ((assignment x (var-expression y))
    (assignment
       u
       (addition-expression
          (var-expression v)
          (var-expression u)))))
rpp> begin x:=y ; uu
        := ((x + v) + u) end

(compound-command
   ((assignment x (var-expression y))
    (assignment
       uu
       (addition-expression
          (addition-expression (var-expression x) (var-expression v))
          (var-expression u)))))
rpp> exit
#f

This is the same as Exercise 11.3.3 in EOPL. Hints: You will have to use your standard-input stream from the preceding machine problem, write a procedure to convert a parser into a stream transducer (like automaton->stream-transducer) and then hook everything together.

3. Arithmetic expressions using the usual rules of precedence may be parsed using the following grammar:

⟨arithmetic expression⟩ ::= ⟨term⟩ {⟨additive operator⟩ ⟨term⟩}^{∗}
⟨term⟩  ::= ⟨factor⟩ {⟨multiplicative operator⟩ ⟨factor⟩}^{∗}
⟨factor⟩  ::= ⟨number⟩ | ( ⟨arithmetic expression⟩)
⟨additive operator⟩  ::= + | -
⟨multiplicative operator⟩ ::= * | /

This question has two parts:

(a) Extend parser-2 to allow ordinary arithmetic expressions as expressions, using the grammar above.

(b) Why would the following grammar not work?

⟨arithmetic expression⟩ ::= ⟨term⟩ ⟨additive operator⟩ ⟨arithmetic expression⟩
⟨term⟩  ::= ⟨factor⟩ ⟨multiplicative operator⟩ ⟨term⟩
⟨factor⟩  ::= ⟨number⟩ | ( ⟨arithmetic expression⟩)
⟨additive operator⟩  ::= + | -
⟨multiplicative operator⟩ ::= * | /