|
|
Assignment 2: Parser GeneratorYour task in this assignment is to implement an LL(1) parser generator and driver, as sketched in the lecture notes, or in Figures 2.23 and 2.18 in the text. The parser generator may be written in any language you like. The parser driver should be written in C++. 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 it 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.
$$ 1
ident 2
read 13
write 18
integer 19
:= 21
+ 22
- 23
* 24
/ 25
( 26
) 27
program -> stmt_list $$
stmt_list -> stmt stmt_list
stmt_list ->
stmt -> ident := expr
stmt -> read ident
stmt -> 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 -> ( expr )
factor -> ident
factor -> integer
add_op -> +
add_op -> -
mult_op -> *
mult_op -> /
|
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
77). 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 *terminal_names[] = {
0,
"$$", // 1
"ident", // 2
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
"read", // 13
0, 0, 0, 0,
"write", // 18
"integer", // 19
0,
":=", // 21
"+", // 22
"-", // 23
"*", // 24
"/", // 25
"(", // 26
")" // 27
};
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}; // $$, stmt_list
int rhs2[] = {2, 3, 0}; // stmt_list, stmt
int rhs3[] = {0}; // epsilon
int rhs4[] = {4, -21, -2, 0}; // expr, :=, 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}; // ), expr, (
int rhs14[] = {-2, 0}; // ident
int rhs15[] = {-19, 0}; // integer
int rhs16[] = {-22, 0}; // +
int rhs17[] = {-23, 0}; // -
int rhs18[] = {-24, 0}; // *
int rhs19[] = {-25, 0}; // /
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, read, write, $$
int first2[] /* stmt_list */ = {2, 13, 18, 0}; // ident, read, write
int first3[] /* stmt */ = {2, 13, 18, 0}; // ident, read, write
int first4[] /* expr */ = {26, 2, 19, 0}; // (, ident, integer
int first5[] /* term_tail */ = {22, 23, 0}; // +, -
int first6[] /* term */ = {26, 2, 19, 0}; // (, ident, integer
int first7[] /* fact_tail */ = {24, 25, 0}; // *, /
int first8[] /* factor */ = {26, 2, 19, 0}; // (, ident, integer
int first9[] /* add_op */ = {22, 23, 0}; // +, -
int first10[] /* mult_op */ = {24, 25, 0}; // *, /
int* first_sets[] = {first1, first2, first3, first4, first5, first6, first7, first8, first9, first10};
int follow1[] /* program */ = {0}; // empty
int follow2[] /* stmt_list */ = {1, 0}; // $$
int follow3[] /* stmt */ = {2, 13, 18, 1, 0}; // ident, read, write, $$
int follow4[] /* expr */ = {27, 2, 13, 18, 1, 0}; // ), ident, read, write, $$
int follow5[] /* term_tail */ = {27, 2, 13, 18, 1, 0}; // ), ident, read, write, $$
int follow6[] /* term */ = {22, 23, 27, 2, 13, 18, 1, 0}; // +, -, ), ident, read, write, $$
int follow7[] /* fact_tail */ = {22, 23, 27, 2, 13, 18, 1, 0}; // +, -, ), ident, read, write, $$
int follow8[] /* factor */ = {22, 23, 24, 25, 27, 2, 13, 18, 1, 0};
// +, -, *, /, ), ident, read, write, $$
int follow9[] /* add_op */ = {26, 2, 19, 0}; // (, ident, integer
int follow10[] /* mult_op */ = {26, 2, 19, 0}; // (, ident, integer
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. 17, 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?
