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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
|
Once b() has successfully analyzed the grammar it generates the tables that
are used by the parsing function to parse input according to the provided
grammar. Each state results in a em(state transition table). For the example
grammar used so far there are five states. Each table consists of rows having
two elements. The meaning of the elements depends on their position in the
table.
itemization(
it() For the em(first) row,
itemization(
it() the first element indicates the em(type) of the
state. The following types are recognized:
table(2)(ll)(
row(cell(NORMAL)cell(Despite its name, it's not used))
row(cell(ERR_ITEM)cell(The state allows error recovery))
row(cell(REQ_TOKEN)cell(The state requires a token nl()
(which may already be available)))
row(cell(ERR_REQ)cell(combines ERR_ITEM and REQ_TOKEN))
row(cell(DEF_RED)cell(This state has a default reduction))
row(cell(ERR_DEF)cell(combines ERR_ITEM and DEF_RED))
row(cell(REQ_DEF)cell(combines REQ_TOKEN and DEF_RED))
row(cell(ERR_REQ_DEF)cell(combines ERR_ITEM, REQ_TOKEN and DEF_RED))
)
it() the second element indicates the index of the table's last
element.
)
it() For the em(last) row,
itemization(
it() the first element stores the current token (it is not used when
the option tt(--thread-safe) was specified)
it() the second element defines the action to perform. A positive
value indicates a shift to the indicated state; a negative value a reduction
according to the indicated rule number, disregarding its sign (note that it's
rule em(number), rather than rule em(offset); zero indicates the input is
accepted as correct according to the parser's grammar.
)
it() For all intermediate remaining rows:
the first element stores the value of a required token for the action
specified in the second element, similar to the way an action is specified in
the last row. Symbolic values (like tt(PARSE_ACCEPT) rather than 0) may be
used as well.
)
)
Here are the tables defining the five states of the example grammar
as they are generated by b() in the file containing the parsing function:
verb(
SR_ s_0[] =
{
{ { DEF_RED}, { 2} },
{ { 258}, { 1} }, // start
{ { 0}, { -2} },
};
SR_ s_1[] =
{
{ { REQ_TOKEN}, { 4} },
{ { 259}, { 2} }, // expr
{ { 257}, { 3} }, // NR
{ { EOF_}, { PARSE_ACCEPT} },
{ { 0}, { 0} },
};
SR_ s_2[] =
{
{ { REQ_DEF}, { 2} },
{ { 43}, { 4} }, // '+'
{ { 0}, { -1} },
};
SR_ s_3[] =
{
{ { DEF_RED}, { 1} },
{ { 0}, { -3} },
};
SR_ s_4[] =
{
{ { REQ_TOKEN}, { 3} },
{ { 259}, { 5} }, // expr
{ { 257}, { 3} }, // NR
{ { 0}, { 0} },
};
SR_ s_5[] =
{
{ { REQ_DEF}, { 1} },
{ { 0}, { -4} },
};
)
|
