Debian Codegraph @

documentation/manual/algorithm/transition.yo

raw
1 Once b() has successfully analyzed the grammar it generates the tables that
2 are used by the parsing function to parse input according to the provided
3 grammar. Each state results in a em(state transition table). For the example
4 grammar used so far there are five states. Each table consists of rows having
5 two elements. The meaning of the elements depends on their position in the
6 table.
7 itemization(
8 it() For the em(first) row,
9 itemization(
10 it() the first element indicates the em(type) of the
11 state. The following types are recognized:
12 table(2)(ll)(
13 row(cell(NORMAL)cell(Despite its name, it's not used))
14 row(cell(ERR_ITEM)cell(The state allows error recovery))
15 row(cell(REQ_TOKEN)cell(The state requires a token nl()
16 (which may already be available)))
17 row(cell(ERR_REQ)cell(combines ERR_ITEM and REQ_TOKEN))
18 row(cell(DEF_RED)cell(This state has a default reduction))
19 row(cell(ERR_DEF)cell(combines ERR_ITEM and DEF_RED))
20 row(cell(REQ_DEF)cell(combines REQ_TOKEN and DEF_RED))
21 row(cell(ERR_REQ_DEF)cell(combines ERR_ITEM, REQ_TOKEN and DEF_RED))
22 )
23 it() the second element indicates the index of the table's last
24 element.
25 )
26 it() For the em(last) row,
27 itemization(
28 it() the first element stores the current token (it is not used when
29 the option tt(--thread-safe) was specified)
30 it() the second element defines the action to perform. A positive
31 value indicates a shift to the indicated state; a negative value a reduction
32 according to the indicated rule number, disregarding its sign (note that it's
33 rule em(number), rather than rule em(offset); zero indicates the input is
34 accepted as correct according to the parser's grammar.
35 )
36 it() For all intermediate remaining rows:
37 the first element stores the value of a required token for the action
38 specified in the second element, similar to the way an action is specified in
39 the last row. Symbolic values (like tt(PARSE_ACCEPT) rather than 0) may be
40 used as well.
41 )
42 )
43 Here are the tables defining the five states of the example grammar
44 as they are generated by b() in the file containing the parsing function:
45 verb(
46 SR_ s_0[] =
47 {
48 { { DEF_RED}, { 2} },
49 { { 258}, { 1} }, // start
50 { { 0}, { -2} },
51
52 };
53
54 SR_ s_1[] =
55 {
56 { { REQ_TOKEN}, { 4} },
57 { { 259}, { 2} }, // expr
58 { { 257}, { 3} }, // NR
59 { { EOF_}, { PARSE_ACCEPT} },
60 { { 0}, { 0} },
61
62 };
63
64 SR_ s_2[] =
65 {
66 { { REQ_DEF}, { 2} },
67 { { 43}, { 4} }, // '+'
68 { { 0}, { -1} },
69
70 };
71
72 SR_ s_3[] =
73 {
74 { { DEF_RED}, { 1} },
75 { { 0}, { -3} },
76
77 };
78
79 SR_ s_4[] =
80 {
81 { { REQ_TOKEN}, { 3} },
82 { { 259}, { 5} }, // expr
83 { { 257}, { 3} }, // NR
84 { { 0}, { 0} },
85
86 };
87
88 SR_ s_5[] =
89 {
90 { { REQ_DEF}, { 1} },
91 { { 0}, { -4} },
92
93 };
94 )