4.4 Recursive-Descent Parsing 183Notice that the expr function includes tracing output statements, which are
included to produce the example output shown later in this section.
Recursive-descent parsing subprograms are written with the convention
that each one leaves the next token of input in nextToken. So, whenever
a parsing function begins, it assumes that nextToken has the code for the
leftmost token of the input that has not yet been used in the parsing process.
The part of the language that the expr function parses consists of one or
more terms, separated by either plus or minus operators. This is the language
generated by the nonterminal
that parses terms (term). Then it continues to call that function as long as it
finds ADD_OP or SUB_OP tokens (which it passes over by calling lex). This
recursive-descent function is simpler than most, because its associated rule
has only one RHS. Furthermore, it does not include any code for syntax error
detection or recovery, because there are no detectable errors associated with
the grammar rule.
A recursive-descent parsing subprogram for a nonterminal whose rule has
more than one RHS begins with code to determine which RHS is to be parsed.
Each RHS is examined (at compiler construction time) to determine the set of
terminal symbols that can appear at the beginning of sentences it can generate.
By matching these sets against the next token of input, the parser can choose
the correct RHS.
The parsing subprogram for
/* term
Parses strings in the language generated by the rule:
*/
void term() {
printf("Enter
/ Parse the first factor /
factor();
/ As long as the next token is or /, get the
next token and parse the next factor /
while (nextToken == MULT_OP || nextToken == DIV_OP) {
lex();
factor();
}
printf("Exit
} /
The function for the
grammar must choose between its two RHSs. It also includes error detection.
In the function for
to call the error function. In a real parser, a diagnostic message must be