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 #39, the design
and implementation of the
tokens and their corresponding visitors *remain the same*!

: Explain the tokenizer (Tokenizer3.java), AToken, ITokVisitor, IdToken, NumToken to the students.Note to Labbies

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. In case you are stuck, click here for the UML class diagrams.

: explain the above UML class diagrams to the students.Note To Labbies

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. In case you are stuck, click here for the UML class diagrams.

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 04/24/2006 02:58:00 PM

Dung X. Nguyen at dxnguyen at rice dot edu