Parser III, Adding the Lookaheads

Posted February  25
Due at the beginning of your lab period the following week

Objectives

• 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

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