|
|
Assignment 2: Parser GeneratorYour 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 formatInput to your parser generator should consist of
A simple exampleThe 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.
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,
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.
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.
Before the beginning of class on Thursday, Sept. 18, send email to the TA containing answers to the following questions.
hash_map page at SGI's on-line
copy of the documentation for the C++ Standard Template
Library?
How many constructors are documented on that page?
