\input{/home/sc/yip/cs201-macro.tex}
\input{psfig}

\setlength{\textwidth}{6.25 in}
\setlength{\textheight}{10.0 in}
\setlength{\topmargin}{-.6 in}


\begin{document} 
\pagestyle{empty}

\psetheader{Fall Semester, 1996}{Practice Problems -- Oct 7, 1996}

\leftbold{Problem: Semantic Grammar}

In 1966 Daniel Bobrow received a PhD degree in AI from MIT for writing
a program that solved high school algebra word problems.  A small part
of the program was parsing the English version of simple arithmetic
expressions of the form:
\beginlisp
the sum of <x> and <y>
the product of <x> and <y>
<x> plus <y>
<x> times <y>
\endlisp
where $<x>$ and $<y>$ are either numbers or expressions involving numbers.

Your task is to write a semantic transition tree grammar for parsing
these expressions into lisp expressions.  For example:
\beginlisp
5 plus 3 times 6   $\longrightarrow$ (+ 5 (* 3 6))
5 times 3 plus 6   $\longrightarrow$ (+ (* 5 3) 6)
5 times the sum of 3 and 6 $\longrightarrow$ (* 5 (+ 3 6))
the product of 5 and 3 plus 6 $\longrightarrow$ (* 5 (+ 3 6))
\endlisp

Note that the usual operator precedence rules apply, i.e., {\tt times}
has higher precedence than {\tt plus}.

(Questions appear on the back of this page.)

\clearpage

Part A.

Label the transition links in the trees below to implement the
desired grammar. 

\bigskip

\centerline{\psfig{figure=transition-tree-grammar.ps,height=5in,width=5in}}


Part B.

Use the grammar in Part A to parse the expression:
\beginlisp
3 times 6
\endlisp
Indicate the sequence of numbers corresponding to the order of tree
traversal by an interpreter.  We will assume the interpreter tries
the topmost branch first in each subtree.  For paths ending in a failure,
indicate what causes the failure.
\beginlisp
1  Fails looking for "the"
12 ...
   ...
\endlisp



\end{document}