1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
|
+ Intro
Miniyacc, generates LALR(1) tables for LR parsers.
It is trivial to port to a new language and has
a smooth implementation (no optimizations).
+ Space saving strategy
The compression scheme used to store the actions
is a single displacement table. It is described
in the dragon book and in
R. Tarjan and A. Yao, "Storing a Sparse Table"
CACM Vol. 22 No. 11, 1979, pp. 606-611
Before applying this compression scheme, we
remove the most common reduce from every row
and store it in a "default" table. Error
actions become the default reduce, it is a
well-known harmless optimization: the error
will be detected later when no shift is
possible.
+ Tables generated by miniyacc
- yyr1 rule -> arity of rhs
- yyr2 rule -> lhs symbol
- yyadef state -> default reduce (-1 if none)
- yygdef symbol -> default goto
- yyadsp displacements for actions in yyact
- yygdsp displacements for gotos in yyact
- yyact state ⨉ tok -> action
symbol ⨉ state -> state
- yychk validation table for yyact
A non-negative action is a shift action, the
value of the action is the destination state.
An action <= -2 is a reduce by the rule whose
number is the opposite of the action minus two.
A missing action in yyact is the default action.
This one is either -1, indicating an error state,
or a rule number to reduce. A -1 in the action
table marks an explicit parsing error.
The action and the goto tables are all merged in
yyact. The action table is indexed first on state
and second on tokens. The checking for the actions
is performed on tokens to be able to merge several
rows. The checking for gotos is performed on the
symbols.
+ Notes
++ About reduces
Even though it is fairly obvious that in a
single state their can be shifts towards
different states. It is also true that,
depending on the lookahead, their can be
multiple reduces. For an example, consider
the following grammar:
S -> A c | B
A -> c
B -> c
While possible, this case happens extremely
rarely in practice, even on large languages.
++ About goto
It is impossible that a goto on two different
symbols yields to the same state, so if the
goto table is indexed by states first and then
non-terminal, there is no point in having a
default action.
The dragon book recommends to index the table
first by symbol, and then by state. In this
case, a default goto is helpful.
|
