##
CPSC425 Spring 2008

Extra Credit: Parsing Infix Expressions

In class we looked at a top-down parser for a simple expression grammar
(the code). Recall that this parser is simply
a recognizer in that it terminates and returns and empty list if it is given
a legal expression in the language, and throws a somewhat meaningful exception
otherwise.
Your assignment is to modify this parser so that it returns an expression tree
for the given expression. Note that the grammar doesn't change -- you'll be
parsing strings in the exact
same language of infix expressions as in the code we looked at in class.

To build your expression tree use the same tree type that we defined in
class and you used in HW 10. **Your top-level function should be
***parse: string -> unit*; it will take the expression to be parsed as a string
with no spaces and
print (not return) the parse tree. This function will need to convert the
expression string
to a list of tokens (also strings) before passing it off to the function
that parses a math expression. This conversion is easy with *map* and
*explode*.

For example, the following input should produce the output shown. Note that
in our grammar * and /
have higher precedence than + and - and all operators are right associative. This
is particularly evident in the third example below.

-parse "a+b*c";
(Node +
(Node a Empty Empty)
(Node *
(Node b Empty Empty)
(Node c Empty Empty)))
val it = () : unit
- parse "(a+b)*(c-a)";
(Node *
(Node +
(Node a Empty Empty)
(Node b Empty Empty))
(Node -
(Node c Empty Empty)
(Node a Empty Empty)))
val it = () : unit
- parse "a+b*c-a-b-c/((c-b))";
(Node +
(Node a Empty Empty)
(Node -
(Node *
(Node b Empty Empty)
(Node c Empty Empty))
(Node -
(Node a Empty Empty)
(Node -
(Node b Empty Empty)
(Node /
(Node c Empty Empty)
(Node -
(Node c Empty Empty)
(Node b Empty Empty)))))))
val it = () : unit