This lab will lead you to write a recursive descent parser to parse scheme-like arithmetic expressions in pre-fix format, such as (* 3 (+ 4 5)). We shall restrict ourselves to arithmetic expressions containing numbers, strings (representing variables), and binary operations such as addition and multiplication. The syntax of the Scheme-like arithmetic expression can be expressed as an LL(1) grammar with the following rules.

E
::= Leaf | BinOp

Leaf ::= VarLeaf | NumLeaf

VarLeaf ::= **id**

NumLeaf ::= **num**

BinOp ::= **(**
Ops

Ops ::= Add | Mul

Add ::= **+** E E **)**

Mul ::= *** ** E E ** )**

Though the above LL(1) grammar is *completely different* from the one
given in lecture #36, the design
and implementation of the
tokens and their corresponding visitors *remain the same*!

A. Design an appropriate object model for the above LL(1) grammar by creating the UML class diagrams for the appropriate classes with all the methods and fields. Put your classes in the “scheme” package.

B. Design the corresponding object model for the factories of token visitors that will parse the grammar by creating the UML class diagrams for the appropriate classes with all the methods and fields. Put your code in the “parser” package.

C. Now that the object model for the grammar and the visitor factories are in place, write the code for the complete parser.

Solution (no peeking before completing the lab!).

Last revised 05/09/2005 12:53:24 AM

Dung X. Nguyen at dxnguyen at rice dot edu