Parser III, Adding the Lookaheads
Posted February 25
Due at the beginning of your lab period the following week
Objectives
The objectives of this assignment are
- to have you interface your parser with your scanner
- to have you finish an LL(1) table for mPascal
- to have you complete much of the parser to the point that it parses an input string.
To Do
Continue working on your parser to the point that it actually parses an input string
- Finish construction of the LL(1) table for mPascal
that you started in lab. The empty LL(1) table you must use for this
task can be found on the resources page. Complete the
procedures that you created as stubs for the last assignment. This means that you
must determine which lookahead symbols cause which rules to be expanded (see the Special
Notes below). These two things should be done in parallel. That is, as you are
determining how to finish off a procedure for a particular nonterminal by determining
which lookaheads cause which rule to be expanded in that procedure, you should fill in the
row of the LL(1) table corresponding to that nonterminal. There may be
conflicts in the table that you will need to resolve.
- Complete the nonterminal subs that will allow you to parse programs that
consist of a single program (no procedures or functions), assignment
statements, read statements, and write statements. That is, your
parser should be able to correctly parse any correct program that has no
procedures or functions, but does contain assignment, read, and write
statements. Of course, if you really get to cranking, you can do as many as
you want. Next week's assignment will have you completing the parser
to parse any mPascal program.
- Complete the procedure called Match. It should match the token supplied as its
parameter with the current lookahead token. If they match, the scanner should be
called to get the next lookahead token and Match should return. If they do not
match, the Syntax_Error procedure should be called (see the Special Notes below).
- Complete the procedure called Syntax_Error. For now, this procedure should
just print the message "Syntax error found on line 5, column 20", for example,
where the line number and column number are those computed by the scanner. Then the
entire program should terminate (see the Special Notes below).
- After matching the end of file marker in the <system_goal> rule of
the grammar, your parser should print the message "The input program
parses!" As noted above, the parser will not even get this far if
a parsing error is encountered earlier. Instead, it will print a syntax
error.
Special Notes
- You may find it helpful to use the grammar animator in this process, to help you trace through
derivations to see, for example, if a token really could follow a particular nonterminal.
The grammar animator should have the latest microPascal context free grammar loaded for you to
play with. You can also select a particular nonterminal to act as the start symbol instead
of the usual start symbol, so that, for example, you can start your parses with <statement> rather
than the usual start symbol. You can access the grammar animator on the Resources page.
- At this point, your compiler should be able to input some mPascal
programs and parse them correctly, as described above. As usual, you should complete and
test your program a bit at a time. That is, try to parse programs with
no statements, then with READ statements, then with WRITE statements, then
with assignment statements, and so forth. This form of incremental
implementation and testing is much more rewarding and quicker than trying to
get the whole project running at once.
- You will be given a correct LL(1) table next week that you can use to correct any
errors you make this week in the LL(1) table. Give it your best shot
on your own this week.
- It should be easy to share responsibilities among team members this time. We
suggest that you assign each member a set of the nonterminals and make that team member
responsible for completing both the procedures and the LL(1) table entries for that
nonterminal, so that you each have experience with both aspects of the project.
- Depending on how your programming language supports exceptions, this is the ideal
time to incorporate them into your program for handling syntax errors (that is, use
exceptions to manage syntax errors instead of, or in addition to, a procedure as described
above). The basic idea is this:
- At the point where a syntax error is detected, raise a special exception that you
define, called, say, Syntax_Error.
- Create a handler for that exception that, in this case, prints the message described
above and then gracefully terminates the program.
- In later assignments, the handler can be modified to recover from the error and
continue, rather than terminating the program.
To Turn In
- Turn in your complete program, both the source and executable files, using the
usual electronic submission procedure. Do not turn in a printed copy.
- Turn in your printed LL(1) table. Be sure your team names and
group number are in the upper left corner as usual.