Project, Phase 2: Parser

Warning: This assignment is currently under development.

Assigned: Monday, 16 February 2004
Due: Monday, 8 March 2004

Summary: In this stage of the project, you will design and build a hand-coded recursive-descent parser for your Pascal compilers. The output from your parser should be a parse tree that uses my Node class.

Contents:

• Some Guidelines
• Recursive-Descent Parsing
• Steps in Building the Parser

Related Files:

• Node.java: The building block of parse trees.
• Symbol.java: The values that go in nodes.
• Nonterminal.java: A new kind of symbol.
• Parser.java: The interface for parsers.
• StupidParser.java: An example parser.

Some Guidelines

Warning: You may be required to use each others' parsers at the next stage of the project.

Group Work: You should continue to work in your group from Phase 1 of the project.

Code Reuse: You may use any of the lexers created for this class (or you may create a new one).

Libraries: You should continue to use my libraries. Unless you have a strong reason to modify my code, you should not make copies of those libraries. (If there are changes you'd like made, send me a rationale for the changes, and I'll consider making them.)

Recursive-Descent Parsing

As you will see in the coming weeks, there are a number of techniques for turning a grammar (which describes a language) into a parser (which reads input strings and builds parse trees for them). Some of these techniques are automatic: They take as input a grammar and produce as output a parser.

In my experience, you learn a bit more and gain a bit more freedom by hand-coding your parser. That is, you write a program that reads input and returns a parse tree. The easiest kind of hand-coded parser to write is a recursive-descent parser. Recursive descent parsers typically have one parse procedure for each nonterminal. Each such procedure looks at the next input symbol (or symbols) and determines which right-hand side for that nonterminal is likely to match. They then call appropriate procedures for the right-hand side.

As you will soon see, we sometimes need to modify our grammars to make them amenable to recursive-descent parsing.

Steps in Building the Parser

1. Begin by deciding on the natural grammar for Pascal. You should do this in the next day or so. You can certainly rely on the grammar that appears in the Pascal User Manual and Report.

2. Read through the StupidParser.java class to understand your goals.

3. Rewrite the Pascal grammar so that it is unambiguous and has no left recursion.

4. Design the nonterminal constants.

5. Implement the parser. It should read input (probably passed as a parameter) and return a parse tree.

6. Test your parser on some interesting cases.