Project 2: The Parser
General Description:
Implement the Parser for the Compiler as an LL(1) Push Down Automata using the Pascal Grammar 2
posted on the course website (published after Homework 2 is due).
We will implement a “Syntax Driven” compiler, meaning the Parser is the “main”. Use the code provided
on Multilab in pas.cpp as the actual main() to invoke parser p; p.compile(filename);
Given:
- pas.cpp provided main() program
- pas my solution, executable
- prints.h/.cpp print functions for the given grammar and token ids
- all of the files for my project 1.3 (the Scanner). You may use these or your own code.
- *.pas test pascal programs (more will be added by Nov 18)
- grammar.h contains MOST of the productions for our grammar as the 2-D array we worked
on in class. Finish this by adding the productions for TOK_STMT and TOK_N_VAL
as mentioned in the comments.
You may implement your own grammar, and not use this one, of course.
Required:
- use the pas.cpp provided for the test program.
- write a Parser class in parser.h and parser.cpp It will of course need to declare a Scanner object
as one of its data members.
- The Parser must use a Stack of tokens. The token.h from Project 1.3 has been extended to
include Non-Terminals of the given Pascal Grammar, if you wish to use that.
- You may use the C++ standard class, or write your own. If you write your own, the stack
must hold at least 100 tokens; a dynamic stack is preferable.
- The compile() method, and its sub-methods, MUST implement a PDA as described in the class
notes. Small variations are allowed, but the main loop must (each time through the loop):
o Pop the top off the stack
o Either consume a token or push the RHS of a production (or error)
Test Messages:
- Each time a Terminal is consumed by the PDA, print a message with the Token ID string of the
consumed token. Ex: TEST: tokenId consumed
- Each time a Non-Terminal is popped and a production selected to push, print the production
chosen. Ex: TEST: PROD: 15 TOK_N_TYPE --> INTEGER { INTEGER }
where 15 is the production number (array index) and { INTEGER } is the select set.
You do not have to print the select set, but it may be helpful.
- If you use the given token.h¸ test print functions have been provided in prints.h/.cpp
Error Messages:
- The compile() method returns any error message, or “” for no error (successful parse).
- If a method of the scanner finds an error, simply return the message from the scanner.
- Messages should include the Token ID (as a printable string) when appropriate. If you use the
given token.h, the TOKENID_STR[] constant array is provided for translating TOKENID to a
printable string.
- Parse errors would include:
o Token expected…
This would occur when a Terminal is popped off the stack that does not match the next
token from the source. Print both Token IDs in the message.
o No Production Found…
This would occur when a Non-Terminal is popped off the stack, and the next token from
the source does not match the select set of any production for that Non-Terminal. This
message will never appear if there is a DEFAULT select set for every Non-Terminal in the
grammar. If this message does occur, it should include the top token from the stack and
the next token from the source. Ex:
No production found for top=tokenId next token=tokenId
o Extra tokens at end of source.
This occurs when the stack goes empty, but there are more tokens in the source file.
o Unexpected end of source.
This occurs when the source returns TOK_EOS (end of source), but the stack is not
empty.
Submit in Canvas:
Submit a .zip file that contains all files needed to compile and execute your program. It should compile
by one of two methods:
1. if you have a make file, then just make
2. if you have no make file, then g++ -o pas *.cpp