Programming Project 2

The second programming assignment is to write a predictive parser for PSub, a subset of Pascal described in part below (based on a language described in the Appendix of Aho, Sethi, and Ullman, Compilers: Principles, Techniques, and Tools, Addison-Wesley, 1986). Your first step should be to convert the grammar given below into an equivalent LL(1) grammar by eliminating left-recursion and re-factoring some of the productions. You should submit a copy of this converted grammar with your assignment.

Next, based on this grammar, write a parser program with the following behavior:

• The input will be a PSub program, either in a file or on the standard input; you should use the function getlex from project 1 to provide tokens one at a time to the parser.
• Each procedure in your recursive-descent parser should start by printing out the name of the non-terminal it recognizes (relative to whatever you have named the non-terminals in your modified grammar); whenever a terminal is matched, print out its lexeme followed by a newline (if an epsilon is matched, just print a newline). The effect will be that the output of the parser will constitute a preorder traversal of the parse tree. For example, suppose that our grammar is

  S --> NP VP
  NP --> DET N | N
  VP --> V OBJ
  OBJ --> NP | epsilon

  and the input is ``John throws the ball'', corresponding to the following parse tree:

       S
      / \
     /   \
   NP     VP
    |    /  \
    |    |   \
    N    V    OBJ
    |    |     |
    |    |     |
  John throws  NP
              /  \
             /    \
           DET     N
            |      |
           the   ball

  (assume that N, V, and DET are tokens which each have an associated lexeme attribute such as ``John'' or ``throws''). Then the desired output of the parser for this project would be

  S NP N John
  VP V throws
  OBJ NP DET the
  N ball

• If an error is encountered in the input, the program should print out a brief error message plus the line containing the error, and then quit.

In addition to the LL(1) grammar, you should submit a printout containing the source code for your program, plus the result of running the parser on the example program given in the previous assignment (I have placed this program in the file /pub/cis606/pp1input on the cis machines. I will also place some other programs in this directory, plus their corresponding lexer and parser outputs, so that you may test your projects on some more extreme cases).

This assignment will be due at the start of class on Friday, October 14. To be fair to the other students, I will not grant extensions; if your program is not working by the deadline, submit what you have and I will try to assign partial credit. You may work in pairs (but not in larger groups); in fact, I would encourage this method if you are comfortable working with someone else, as it means less for me to grade!

As with all programming assignments, it will not be sufficient to simply produce code that works---it must also be adequately structured and documented. You may use any programming language you like on any machine you prefer, as long as there is a reasonable chance that I will be able to read your code. The program should be written ``from scratch''; that is, I do not want you to use compiler-building tools such as the Unix program yacc (at least, not yet).

Original Grammar for PSub