| 1 |
This chapter describes the algorithm that is used by b(). Generating parsers |
| 2 |
of course begins with a grammar to be analyzed. The analysis consists of |
| 3 |
these steps: |
| 4 |
itemization( |
| 5 |
it() First, a set of tt(FIRST) tokens is determined. The tt(FIRST) set of |
| 6 |
a nonterminal defines all terminal tokens that can be encountered when |
| 7 |
beginning to recognize that nonterminal. |
| 8 |
it() Having determined the tt(FIRST) set, the grammar itself is |
| 9 |
analyzed. Starting from the start rule all possible syntactically correct |
| 10 |
derivations of the grammar are determined. |
| 11 |
it() At each state actions are defined that are eventually used by the |
| 12 |
parser to determine what to do in a particular state. These actions are based |
| 13 |
on the next available token and may either involve a transition to another |
| 14 |
state (called a em(shift), since it involves processing a token by `shifting' |
| 15 |
over the next part of the input) or it may involve a reduction (a em(reduce) |
| 16 |
action), in which the parser stack's size is somewhat reduced. In the latter |
| 17 |
case, if an em(action) is associated with a particular rule, the action is |
| 18 |
executed as a side effect of the reduction. |
| 19 |
it() Sometimes the analysis takes the parser generator to a state in which |
| 20 |
a choice between a em(shift) or a em(reduce) action must be made. This is |
| 21 |
called a em(shift-reduce) conflict. Sometimes the parser generator is able to |
| 22 |
solve these conflicts itself, by looking at the next available token (the |
| 23 |
em(look-ahead) token). If the next token is not a possible continuation for |
| 24 |
either a shift or a reduce action that particular continuation can be |
| 25 |
discarded. Likewise, two reductions may be encountered in a state (a |
| 26 |
em(reduce-reduce) conflict). Here the same reasoning can be applied, maybe |
| 27 |
resulting in discarding one of the possible reductions. In all other cases |
| 28 |
(i.e., if the look-ahead token is possible for both continuations) a true |
| 29 |
conflict is observed which somehow is solved by the grammar designer. If the |
| 30 |
designer doesn't select an particular action, the parser generator reports a |
| 31 |
conflict and selects a default action. By default a em(shift) is used, rather |
| 32 |
than a em(reduce). With a em(reduce-reduce) conflict the default action is to |
| 33 |
reduce by the rule listed first in the grammar. |
| 34 |
it() In cases where input is not structured according to the rules of the |
| 35 |
grammar, a em(syntactic error) is observed. Error recovery may be attempted, |
| 36 |
to allow the parser to continue parsing. This is a desirable characteristic |
| 37 |
since it provides the user of a program with a full syntactic error report, |
| 38 |
rather than one error at a time. |
| 39 |
it() Following the analysis of the grammar, code is generated and the |
| 40 |
parsing algorithm (implemented in the parser's tt(parse()) function) |
| 41 |
processes input according to the tables generated by the parser generator. |
| 42 |
) |
| 43 |
|
| 44 |
All the above phases are illustrated and discussed in the next |
| 45 |
sections. Additional details of the parsing process can be found in various |
| 46 |
books about compiler construction, e.g., in Aho, Sethi and Ullman's (2003) |
| 47 |
book bf(Compilers) (Addison-Wesley). |
| 48 |
|
| 49 |
In the sections below, the following grammar is used to illustrate the |
| 50 |
various phases: |
| 51 |
verb( |
| 52 |
%token NR |
| 53 |
|
| 54 |
%left '+' |
| 55 |
|
| 56 |
%% |
| 57 |
|
| 58 |
start: |
| 59 |
start expr |
| 60 |
| |
| 61 |
// empty |
| 62 |
; |
| 63 |
|
| 64 |
expr: |
| 65 |
NR |
| 66 |
| |
| 67 |
expr '+' expr |
| 68 |
; |
| 69 |
) |
| 70 |
The grammar is interesting as it has a rule containing an empty |
| 71 |
alternative and because it harbors a shift-reduce conflict. The shift-reduce |
| 72 |
conflict is solved by explictly assigning a priority and association to the |
| 73 |
tt('+') token. |
| 74 |
|
| 75 |
The analysis starts by defining an additional rule, which is recognized |
| 76 |
(reduced) at end of input. This rule and the rules specified in the grammar |
| 77 |
together define what is known as the em(augmented grammar). In the coming |
| 78 |
sections the symbol tt($) is used to indicate `end of input'. From the above |
| 79 |
grammar the following augmented grammar is derived: |
| 80 |
verb( |
| 81 |
1. start: start expr |
| 82 |
2. start: // empty |
| 83 |
3. expr: NR |
| 84 |
4. expr: expr '+' expr |
| 85 |
5. start_$: start (input ends here) |
| 86 |
) |
| 87 |
|
| 88 |
b() itself produces an extensive analysis of any grammar it is offered |
| 89 |
when the option tt(--construction) is provided. |