Debian Codegraph @

documentation/manual/algorithm/intro.yo

raw
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.