Comp 212 Lab 13: Parsing Scheme Expressions


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