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