## 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
```