Debian Codegraph @

documentation/manual/algorithm/states.yo

raw
1 Having determined the tt(FIRST) set, b() determines the
2 em(states) of the grammar. The analysis starts at the augmented grammar rule
3 and proceeds until all possible states have been determined.
4 In this analysis the concept of the em(dot) symbol is used. The em(dot) shows
5 the position we are at when analyzing production rules defined by a grammar.
6 Using the provided example grammar the analysis proceeds as follows:
7 itemization(
8 it() State 0: tt(start_$ -> . start)nl()
9 At this point we haven't seen anything yet. The em(dot) is before the
10 grammar's start symbol. The above is called an em(item) and the initial set of
11 items of a state is called the set of em(kernel items). Except for the start
12 rule, kernel items never have a dot before the very first symbol of a rule. In
13 this particular state there's only one kernel item. Items are indexed, so this
14 item receives index 0. Beyond, item indices are shown together with the items
15 themselves. If a nonterminal follows immediately to the right of the dot,
16 then all production rules of that nonterminal are added to the state as
17 non-kernel items. Non-kernel items always have their dots at the very first
18 position. Adding non-kernel items is a recursive process. If the rules of thus
19 added items also show nonterminals to the right of the dot, then the
20 production rules of those nonterminals are added too (unless they were
21 already added).
22
23 The above kernel item results in the addition of the following non-kernel
24 items:
25 itemization(
26 it() item 1: tt(start -> . start expr)
27 it() item 2: tt(start -> . )
28 )
29
30 From each of the items new states may be derived. New states are reached
31 when the symbol to the right of the dot has been recognized. In that case a
32 em(transition) (a em(goto)) to the next state takes place, where the dot has
33 moved one postition to the right, defining a kernel item of the new
34 state. Once the dot has reached the end of the rule, a em(reduction) may take
35 place. Following a reduction a transition based on rule's LHS is
36 performed. This procedure is discussed in more detail in section ref(PARSING).
37
38 Looking at the current state's items, two actions are possible:
39 itemization(
40 it() On tt(start), to a state in which tt(start) has been seen (state 1)
41 it() By default, a reduction by the rule tt(start -> . )
42 )
43
44 it() State 1: kernel items:
45 itemization(
46 it() item 0: tt(start_$ -> start .)
47 it() item 1: tt(start -> start . expr)
48 )
49 Since tt(expr) is a nonterminal to the right of the dot, we add
50 all tt(expr) rules as this state's non-kernel items:
51 itemization(
52 it() item 2: tt(expr -> . NR)
53 it() item 3: tt(expr -> . expr '+' expr)
54 )
55 This state becomes the em(accepting) state: if EOF is reached in this
56 state, the tt(start_$) rule has been recognized, and so the input was
57 syntactically correct. But in this state transitions to other states are also
58 possible:
59 itemization(
60 it() On tt(expr) to state 2
61 it() On NR to state 3
62 )
63
64 it() State 2: kernel items:
65 itemization(
66 it() item 0: tt(start -> start expr .)
67 it() item 1: tt(expr -> expr . '+' expr)
68 )
69 No nonterminal symbols appear to the right of the dots in these
70 items, so no non-kernel items are added to this state. Transitions from this
71 state are:
72 itemization(
73 it() On tt('+') to state 4
74 it() Or reduce to tt(start) according to its first item (removing
75 two elements from the parser's stack).
76 )
77
78 it() State 3: kernel items:
79 itemization(
80 it() item 0: tt(expr -> NR .)
81 )
82 In this state only one action is possible: a reduction to tt(expr)
83 (removing one element from the parser's stack).
84
85
86 it() State 4: kernel item:
87 itemization(
88 it() item 0: tt(expr -> expr '+' . expr)
89 )
90 Since tt(expr) is a nonterminal to the right of the dot, we add
91 all tt(expr) rules as this state's non-kernel items:
92 itemization(
93 it() item 1: tt(expr -> . NR)
94 it() item 2: tt(expr -> . expr '+' expr)
95 )
96 In this state the following transitions are possible:
97 itemization(
98 it() On tt(expr) to state 5
99 it() On tt(NR) we reach the situation tt(expr -> NR .) which has
100 already been encountered at state 3. That's OK, so on tt(NR) there is
101 a transition to state 3.
102 )
103 Note that in order to return to a previously defined state that state
104 must have exactly the required kernel items. So, if state 3 would contain
105 multiple kernel items, a new state would have been required, merely having the
106 tt(expr -> NR .) kernel item.
107
108 it() State 5: kernel items:
109 itemization(
110 it() item 0: tt(expr -> expr '+' expr .)
111 it() item 1: tt(expr -> expr . '+' expr)
112 )
113 In this state two actions are possible:
114 itemization(
115 it() On tt('+') to state 4
116 it() Or reduce to tt(expr) according to its first item (removing three
117 elements from the parser's stack).
118 )
119 As explained in the next section this state's first action is never
120 selected: in this state only the reduction is selected.
121 )