Compilers (CS362 2004S)

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.


Related Files:

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 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.



Monday, 16 February 2004 [Samuel A. Rebelsky]


Disclaimer: I usually create these pages on the fly, which means that I rarely proofread them and they may contain bad grammar and incorrect details. It also means that I tend to update them regularly (see the history for more details). Feel free to contact me with any suggestions for changes.

This document was generated by Siteweaver on Mon Apr 26 13:19:33 2004.
The source to the document was last modified on Wed Feb 18 09:34:14 2004.
This document may be found at

You may wish to validate this document's HTML ; Valid CSS! ; Check with Bobby

Samuel A. Rebelsky,