Parser Specifications (Abbreviated)

Students are to implement a recursive descent parser. They do this through the following.

EBNF, LL(1) Grammars, and LL(1) Table Construction

Students refresh their knowledge of EBNF and context-free grammars. They then learn about LL(1) grammars, the construction of LL(1) tables by way of First, Follow, and Predict set calculations, and how to resolve LL(1) table conflicts. They create their own LL(1) table for microPascal, but are then given a correct version for comparison and use in constructing the parser.

Parser Construction

From the LL(1) table teams are to construct a recursive descent parser for microPascal based on this table as follows.

• The nonterminal symbols of the microPascal grammar are divided among the team members.
• For each non terminal, the responsible student is to write a method in which that nonterminal symbol expands itself as follows:
  • The lookahead token is obtained from the scanner
  • The entry in the LL(1) table for the non-terminal (row) of this method and the current lookahead token (column) is examined. If the entry is non-empty it contains the number of a rule in the grammar that has the nonterminal of this method on the left
  • A case statement that switches on the rule number found in the LL(1) table selects the correct case for expanding the nonterminal according to its rule number (if the LL(1) table has no entry in it for this nonterminal-lookahead pair, the default case is to register an error)
  • Each non-default case in the case statement represents the expansion of one of the rules in the grammar with the nonterminal of this method on the left. The case expands the nonterminal according to this rule by handling each symbol on the right hand side of this rule by (for each token on the right hand side) calling a method to match the token and calling the relevant method for each nonterminal.
  • If the case statement in the implementation language cannot switch one or the other type of value (the state or the lookahead token) an if-then-elseif-else construct can be used.