CS331 Compilers Project--phase 3

CS331 Compilers Project--phase 3

PARSER

This phase of the project implements an LL(1) parser for the language described by this grammar. The parse table is stored in

~cs331/parser/parsetable-2const.dat

The file

~cs331/parse_table.xls

provides the table as an Excel file with the terminals and non-terminals given as headers to the rows and columns.

The parser consists of the following:

the parse_driver, which calls the lexical analyzer for the next token and manipulates the stack;
the parse table, which is a matrix indexed by stack symbol (non-terminals from the grammar) and current input symbol (terminal symbol from the grammar), and which contains in each cell either an integer code representing a production number, an accept action indicator, or an error indicator;
right-hand-side table, containing the right hand sides for each production in the grammar.

The parser works by examining the symbol on top of the stack and the current input symbol, which is the token most recently passed to the parser by the lexical analyzer. If the stack symbol is a terminal and matches the current input symbol, the top symbol is popped from the stack and the parser calls for the next input token. If the stack symbol is a non-terminal, the parser consults the cell in the parse table corresponding to the stack symbol and the current input symbol. If the entry in the table is accept, the parse has successfully completed. If the entry is error, the error routine is called. If the entry is a production number, the parser does the following: the top symbol on the stack is popped. The production number from the parse table is used as an index into the right-hand side table. This table can be set up as an array with integer indeces that correspond to the production numbers in the grammar. Each cell should point to a list containing the actual symbols in the right hand side for that production. You may want to store the symbols in reverse order--i.e., last one at the front of the list, etc.--since this is the order in which you will push them on the stack.

The parse starts by initializing the stack to contain the distinguished symbol of the grammar () with the ENDOFFILE terminal symbol underneath. It then proceeds as described above, repeatedly comparing stack top and current input and pushing and popping symbols from the stack as required, until an error is detected or the input string is successfully parsed. The actual code for the parser will be quite short; an outline is given here.

Parse Errors

When an error is detected, call the error routine and print an appropriate message, together with the current token, the current line number, and the current line up to the problem token, with an indication of the point of failure. Your messages cannot be very explicit, because your parser doesn't have any way of knowing what it was looking for--but you are encouraged to attempt to provide as informative messages as you can.

You should also implement a dump_stack function that can be called during debugging. which prints the current contents of the parse stack. Be sure this can be turned on and off, since the compiler will ultimately not generate this kind of internal information for the user.

Once an error is detected the parse should stop. Error recovery in a parser is tricky; if you want to try to implement some type of error recovery, do that after you get the basic parser working. An outine of one accepted method is here

Notes

The right-hand-side table will ultimately contain markers that indicate that a call to semantic action routines is in order, interspersed within the right-hand-side symbols themselves. Your semantic routines will not be implemented until later, so at this point you can either use the grammar with actions and include code to just ignore semantic actions when they appear on the stack; or use the grammar without actions , and modify it later to include the actions.

Here are some resources for the project:

There is a test file you can use to test your parser in ~cs331/parsetest.dat.

You should create a main driver for the compiler and use this to call the parser. Its body should consist of statements to do all setup (instantiate the lexical analyzer, parser, symbol table, plus any other setup required), then it should call the parser. If the parse completes successfully, control returns to this main driver routine and it prints a message the compilation was completed successfully.