\documentstyle [11pt,mysecs,course]{article}
\input local
\pagestyle{empty}
\problemset 4
\date{April 29, 1993}
\due{May 6, 1993}
\title{Interactive Parsing Using Streams}

\begin{document}
\maketitle

For this problem set, you will modify the scanner and parser found in
{\tt {/course/com3351/pub/mp4.s}}.

\problem
Write a procedure {\tt 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.

\problem
Modify the parser driver in {\tt {/course/com3351/pub/mp4.s}} to create an
interactive read-parse-print loop using the scanner {\tt automaton-1} and the
parser {\tt 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 {\tt end} is found
as the first token of a command.

A typical session with the read-parse-print loop might look something like:

\ttnoi
> (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
\endtt

This is the same as Exercise 11.3.3 in {\em 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 {\tt
automaton->stream-transducer}) and then hook everything together.

\problem 
Arithmetic expressions using the usual rules of precedence may be parsed using
the following grammar:

$$\gramalign{
\nt{arithmetic expression} &\nt{term}\ \st{\nt{additive operator}\ \nt{term}}\\
\nt{term}      &\nt{factor}\ \st{\nt{multiplicative operator}\ \nt{factor}}\\
\nt{factor}    &\nt{number} \alt \term( \nt{arithmetic expression} \term) \\
\nt{additive operator} &\term+ \alt \term- \\
\nt{multiplicative operator} &\term* \alt \term/ \\
}$$


This question has two parts:

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

(b) Why would the following grammar not work?

$$\gramalign{
\nt{arithmetic expression} &\nt{term}\ {\nt{additive operator}\ \nt{arithmetic
expression}}\\
\nt{term}      &\nt{factor}\ {\nt{multiplicative operator}\ \nt{term}}\\
\nt{factor}    &\nt{number} \alt \term( \nt{arithmetic expression} \term) \\
\nt{additive operator} &\term+ \alt \term- \\
\nt{multiplicative operator} &\term* \alt \term/ \\
}$$

\end{document}
