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 #40, the design and implementation of the tokens and their corresponding visitors remain the same!
Note to Labbies: Explain the tokenizer (Tokenizer3.java), AToken, ITokVisitor, IdToken, NumToken to the students.
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.
Note To Labbies: explain the above UML class diagrams to the students.
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/18/2007 11:41:28 AM
Dung X. Nguyen at dxnguyen at rice dot edu
