Assignment 2:  Parser Generator

Your task in this assignment is to implement, in C++, an LL(1) parser generator and driver, as sketched in the lecture notes, or in Figures 2.23 and 2.18 in the text.  (I recommend the version in the lecture notes, which separates EPS from FIRST and FOLLOW; it’s a little easier to understand.) 

Your parser generator should accept as input any LL(1) grammar conforming to the format described below.  It should output initialized C++ data structures which, if linked to your driver and an appropriate scanner, will produce a working parser for strings in the language.  Your parser, in turn, should accept any string in the language defined by the CFG given to the parser generator.  To demonstrate that it works correctly, it should print a trace of its predictions and matches. 

If the grammar given to the parser generator is malformed, or not LL(1), the parser generator should print a helpful error message and quit.  If the string given to the parser contains syntax errors, the parser should recover gracefully and keep on parsing (more on this below). 

To simplify your task, we are providing a basic scanner; it accepts a variety of common tokens, with which you can construct a variety of sample grammars. 

Grammar format

Input to your parser generator should consist of

  1. A list of token names and numbers, one per line.  Token names are strings of printable, non-whitespace characters.  Token numbers are small nonnegative integers, not necessarily contiguous or in any particular order.  (This will make it easier for you to use the same scanner for several different grammars.  You may assume that all token numbers are less than 128, that the value 0 is not used, and that the value 1 is reserved for end-of-file.) 

  2. A blank line. 

  3. A list of productions, one per line.  Each production should consist of a symbol name, the metasymbol “->”, and a sequence of zero or more symbol names.  We will test your code with only pure BNF:  no alternation, no Kleene closure.  You may assume that productions with the same left-hand side will be consecutive, and that the start symbol is the left-hand side of the first production. 

A simple example

The calculator grammar from class might be input to your parser generator as follows. 

    tok_eof     1
    ident       2
    rw_read    13
    rw_write   18
    lit_int    19
    becomes    21
    op_add     22
    op_sub     23
    op_mul     24
    op_div     25
    lparen     26
    rparen     27

    program    ->  stmt_list tok_eof
    stmt_list  ->  stmt stmt_list
    stmt_list  ->
    stmt       ->  ident becomes expr
    stmt       ->  rw_read ident
    stmt       ->  rw_write expr
    expr       ->  term term_tail
    term_tail  ->  add_op term term_tail
    term_tail  ->
    term       ->  factor fact_tail
    fact_tail  ->  mult_op factor fact_tail
    fact_tail  ->
    factor     ->  lparen expr rparen
    factor     ->  ident
    factor     ->  lit_int
    add_op     ->  op_add
    add_op     ->  op_sub
    mult_op    ->  op_mul
    mult_op    ->  op_div 

When you run this through your parser generator, it should produce C++ versions of the tables used in Figure 2.18 in the text (page 71).  In addition, it should produce tables giving the FIRST and FOLLOW sets of every nonterminal, and an indication of which of these can generate epsilon; you’ll need these tables for error recovery.  The exact format of these tables is up to you.  One possible format might look something like the following.  It uses row-pointer layout for right-hand sides and FOLLOW sets, and contiguous two-dimensional layout for the main parse table.  (NB:  I generated this by hand, starting from Figures 2.19 and 2.22 in the text; please let me know if you spot any typos.) 

static const int max_terminal = 27;
static const int num_nonterminals = 10;
static const int num_productions = 19;
char *non_terminal_names[] = {
    "program",      // 1
    "stmt_list",    // 2
    "stmt",         // 3
    "expr",         // 4
    "term_tail",    // 5
    "term",         // 6
    "fact_tail",    // 7
    "factor",       // 8
    "add_op",       // 9
    "mult_op"       // 10
};

// Right-hand sides, in reverse order.  Negative numbers indicate tokens.
int rhs1[] = {-1, 2, 0};           // eof, stmt_list
int rhs2[] = {2, 3, 0};            // stmt_list, stmt
int rhs3[] = {0};                  // epsilon
int rhs4[] = {4, -21, -2, 0};      // expr, becomes, ident
int rhs5[] = {-2, -13, 0};         // ident, read
int rhs6[] = {4, -18, 0};          // expr, write
int rhs7[] = {5, 6, 0};            // term_tail, term
int rhs8[] = {5, 6, 9, 0};         // term_tail, term, add_op
int rhs9[] = {0};                  // epsilon
int rhs10[] = {7, 8, 0};           // factor_tail, factor
int rhs11[] = {7, 8, 10, 0};       // factor_tail, factor, mult_op
int rhs12[] = {0};                 // epsilon
int rhs13[] = {-27, 4, -26, 0};    // rparen, expr, lparen
int rhs14[] = {-2, 0};             // ident
int rhs15[] = {-19, 0};            // lit_int
int rhs16[] = {-22, 0};            // op_add
int rhs17[] = {-23, 0};            // op_sub
int rhs18[] = {-24, 0};            // op_mul
int rhs19[] = {-25, 0};            // op_div

int* right_hand_sides[] = {0,
    rhs1, rhs2, rhs3, rhs4, rhs5, rhs6, rhs7, rhs8, rhs9, rhs10,
    rhs11, rhs12, rhs13, rhs14, rhs15, rhs16, rhs17, rhs18, rhs19};

int parse_tab[][max_terminal] = {
// See Figure 2.19 in the text, but note that tokens in this example are ordered differently, and have gaps.
// Index table as parse_tab[top-of-stack_nonterminal-1, input_token-1];
   1,  1,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  1,  0,  0,  0,  0,  1,  0,  0,  0,  0,  0,  0,  0,  0,  0,
   3,  2,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  2,  0,  0,  0,  0,  2,  0,  0,  0,  0,  0,  0,  0,  0,  0,
   0,  4,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  5,  0,  0,  0,  0,  6,  0,  0,  0,  0,  0,  0,  0,  0,  0,
   0,  7,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  7,  0,  0,  0,  0,  0,  0,  7,  0,
   9,  9,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  9,  0,  0,  0,  0,  9,  0,  0,  0,  8,  8,  0,  0,  0,  9,
   0, 10,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0, 10,  0,  0,  0,  0,  0,  0, 10,  0,
  12, 12,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0, 12,  0,  0,  0,  0, 12,  0,  0,  0, 12, 12, 11, 11,  0, 12,
   0, 14,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0, 15,  0,  0,  0,  0,  0,  0, 13,  0,
   0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0, 16, 17,  0,  0,  0,  0,
   0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0, 18, 19,  0,  0
};

bool generates_epsilon[] = {false, true, false, false, true, false, true, false, false, false};

int first1[]  /* program */    = {2, 13, 18, 1, 0};  // ident, rw_read, rw_write, tok_eof
int first2[]  /* stmt_list */  = {2, 13, 18, 0};     // ident, rw_read, rw_write
int first3[]  /* stmt */       = {2, 13, 18, 0};     // ident, rw_read, rw_write
int first4[]  /* expr */       = {26, 2, 19, 0};     // lparen, ident, lit_int
int first5[]  /* term_tail */  = {22, 23, 0};        // op_add, op_sub
int first6[]  /* term */       = {26, 2, 19, 0};     // lparen, ident, lit_int
int first7[]  /* fact_tail */  = {24, 25, 0};        // op_mul, op_div
int first8[]  /* factor */     = {26, 2, 19, 0};     // lparen, ident, lit_int
int first9[]  /* add_op */     = {22, 23, 0};        // op_add, op_sub
int first10[] /* mult_op */    = {24, 25, 0};        // op_mul, op_div

int* first_sets[] = {first1, first2, first3, first4, first5, first6, first7, first8, first9, first10};

int follow1[]  /* program */    = {0};                                    // empty
int follow2[]  /* stmt_list */  = {1, 0};                                 // tok_eof
int follow3[]  /* stmt */       = {2, 13, 18, 1, 0};                      // ident, rw_read, rw_write, tok_eof
int follow4[]  /* expr */       = {27, 2, 13, 18, 1, 0};                  // rparen, ident, rw_read, rw_write, tok_eof
int follow5[]  /* term_tail */  = {27, 2, 13, 18, 1, 0};                  // rparen, ident, rw_read, rw_write, tok_eof
int follow6[]  /* term */       = {22, 23, 27, 2, 13, 18, 1, 0};          // op_add, op_sub, rparen, ident, rw_read, rw_write, tok_eof
int follow7[]  /* fact_tail */  = {22, 23, 27, 2, 13, 18, 1, 0};          // op_add, op_sub, rparen, ident, rw_read, rw_write, tok_eof
int follow8[]  /* factor */     = {22, 23, 24, 25, 27, 2, 13, 18, 1, 0};  // op_add, op_sub, op_mul, op_div, rparen, ident, rw_read, rw_write, tok_eof
int follow9[]  /* add_op */     = {26, 2, 19, 0};                         // lparen, ident, lit_int
int follow10[] /* mult_op */    = {26, 2, 19, 0};                         // lparen, ident, lit_int

int* follow_sets[] = {follow1, follow2, follow3, follow4, follow5, follow6, follow7, follow8, follow9, follow10}; 

Given the input

    read A
    read B
    sum := A + B
    write sum
    write sum / 2
your driver should print the right-hand column of Figure 2.20 in the text. 

Syntax error recovery

Your parser must implement phrase-level recovery from syntax errors.  This should allow it to continue to parse a program (and find more syntax errors) after it encounters an instance of invalid syntax.  Specifically,

  1. If the input token is tok_error or some other token not used in the given grammar, you should print an error message and consume the token before inspecting the top-of-stack symbol. 
  2. If you have a terminal at the top of the parse stack and the input token doesn’t match it, you should pop the expected token, print an error message, and leave the current input token unconsumed. 
  3. If you have a nonterminal N at the top of the parse stack for which there is no prediction (zero in the parse table), you should consume input tokens until you find a token T in FIRST(N) or FOLLOW(N).  If T is in FOLLOW(N), you should pop N from the stack and continue; otherwise you should continue with N still in place. 

Hints

Division of labor and writeup

As in all assignments this semester, you may work alone or in teams of two.  This particular assignment works very well for a team:  one of you should write the parser generator; the other should write the driver with error recovery.  Be sure to follow all the rules on the Grading page.  As with all assignments, use the turn-in script:  ~cs254/bin/TURN_IN.  Put your write-up in a README.txt or README.pdf file in the directory in which you run the script.  Be sure to describe any features of your code that the TA might not immediately notice. 

Extra credit suggestions

Trivia Assignment

Before the beginning of class on Thursday, Sept. 18, send email to the TA containing answers to the following questions.

MAIN DUE DATE: 

Monday September 29, at 11:59 pm; no extensions. 
Last Change:  29 September 2008 / Michael Scott's email address