Debian Codegraph @

documentation/manual/algorithm/determine.yo

raw
1 Once the items of all the grammar's states have been determined the LA sets
2 for the states' items are computed. Starting from the LA set of the kernel
3 item of state 0 (representing the augmented grammar's production rule
4 tt(S_$: . S), where tt(S) is the grammar's start rule) the LA sets of all
5 items of all of the grammar's states are determined. By definition, the LA set
6 of state 0's kernel item equals tt($), representing end-of-file.
7
8 Starting from the function tt(State::determineLAsets), which is called for
9 state 0, the LA sets of all items of all states are computed.
10
11 For each state, the LA sets of its items are computed first. Once they have
12 been computed, the LA sets of items from where transitions to other states are
13 possible are then propagated to the matching kernel items of those destination
14 states. When the LA sets of kernel items of those destination states are
15 enlarged then their state indices are added to a set tt(todo). LA sets of the
16 items of states whose indices are stored in the tt(todo) set are (re)computed
17 (by calling tt(determineLAsets) for those states) until tt(todo) is empty, at
18 which point all LA sets have been computed. Initially tt(todo) only contains
19 0, the index of the initial state, representing the augmented grammar's
20 production rule.
21
22 To compute the LA sets of a state's items the LA set of each of its kernel
23 items is distributed (by the member tt(State::distributeLAsetOf)) over the
24 items which are implied by the item being considered. E.g., for item tt(X: a
25 . Y z), where tt(a) and tt(z) are any sequence of grammar symbols and tt(X)
26 and tt(Y) are nonterminal symbols, all of tt(Y's) production rules are added
27 as new items to the current state.
28
29 Then the member tt(distributeLAsetOfItem(idx)) matches the item's rule
30 specification with the specification tt(a.Bc), where tt(a) and tt(c) are
31 (possibly empty) sequences of grammatical symbols, and tt(B) is a (possibly
32 empty) nonterminal symbol appearing immediately to the right of the item's
33 dot position. if tt(B) is empty then there are no additional production rules
34 and tt(distributeLAsetOf) may return. Otherwise, the set tt(b = FIRST(c)) is
35 computed. This set holds all symbols which may follow tt(B). If tt(b) contains
36 epsilon() (i.e., the element representing the empty set), then the currently
37 defined LA set of the item can also be observed. In that case epsilon() is
38 removed, and the currently defined LA set is added to tt(b). Finally, the LA
39 sets of all items representing a production rule for tt(B) are inspected: if
40 tt(b) contains unique elements compared to the LA sets of those items, then
41 the unique elements of tt(b) are added to the LA sets of those items. Finally,
42 tt(distributeLAsetOfItem) is recursively called for those items whose LA sets
43 were enlarged.
44
45 Once the LA sets of the items of a state have thus been computed,
46 tt(inspectTransitions) is called to propagate the LA sets of items from where
47 transitions to other states are possible to the affected (kernel) items of
48 those other (destination) states. The member tt(inspectTransitions) inspects
49 all tt(Next) objects of the current state's tt(d_nextVector). Next objects
50 provide
51 itemization(
52 it() the state index of a state to transfer to from the current state;
53 it() a size_t vector of item transitions. Each element is the index of an
54 item in the current state (the source-item), its index is the index
55 of a (kernel) item of the state to transfer to (the destination
56 index).
57 )
58 If the LA set of a destination item can be enlarged from the LA set of the
59 source item then the LA sets of the destination state's items must be
60 recomputed. This is realized by inserting the destation state's index into the
61 `todo' set.
62
63
64 To illustrate an LA-set computation we will now compute the LA sets of (some
65 of) the items of the states of the grammar introduced at the beginning of this
66 chapter. Its augmented grammar consists of the following production rules:
67 verb(
68 1. start: start expr
69 2. start: // empty
70 3. expr: NR
71 4. expr: expr '+' expr
72 5. start_$: start
73 )
74 When analyzing this grammar, we found the following five states, consisting of
75 several items and transitions (kernel items are marked with K following their
76 item indices). Next to the items, where applicable, the goto-table is shown:
77 the state to go to when the mentioned grammatical symbol has been recognized:
78 verb(
79 Goto table
80 -----------
81 State 0: start
82 0K: start_$ -> . start 1
83 1: start -> . start expr 1
84 2: start -> .
85
86 State 1: expr NR
87 0K: start_$ -> start .
88 1K: start -> start . expr 2
89 2: expr -> . NR 3
90 3: expr -> . expr '+' expr
91
92 State 2: '+'
93 0K: start -> start expr .
94 1K: expr -> expr . '+' expr 4
95
96 State 3:
97 0K: expr -> NR .
98
99 State 4: expr NR
100 0K: expr -> expr '+' . expr 5
101 1: expr -> . NR 3
102 2: expr -> . expr '+' expr 5
103
104 State 5: '+'
105 0K: expr -> expr '+' expr .
106 1K: expr -> expr . '+' expr 4
107 )
108
109 Item 0 of state 0 by definition has LA symbol $, and LA computation therefore
110 always starts at item 0 of state 0. The interesting part of the LA set
111 computation is encountered in the recursive member tt(distributeLAsets):
112 verb(
113 distributeLAsetsOfItem(0)
114 start_$ -> . start: LA: {$}, B: start, c: {}, so b: {$}
115
116 items 1 and 2 refer to production rules of B (start) and are inspected:
117
118 1: LA(1): {}: b contains unique elements. Therefore:
119 LA(1) = {$}
120 distributeLAsetsOfItem(1):
121 start -> . start expr: LA: {$}, B: start, c: {expr}, so b: {NR}
122 inspect items 1 and 2 as they refer to production rules of B (start):
123
124 1: LA(1): {}: b contains unique elements. Therefore:
125 LA(1) = {$,NR}
126 distributeLAsetsOfItem(1)
127 start -> . start expr: LA: {$,NR}, B: start, c: {expr}, so b: {NR}
128 inspect items 1 and 2 as they refer to prod. rules of B (start):
129
130 1: LA(1): {$,NR}, so b does not contain unique elements: done
131
132 2: LA(2): {}, b contains unique elements
133 LA(2) = {NR}
134 distributeLAsetsOfItem(2)
135 start -> .: LA: {NR}, B: -, c: {}, so b: {NR}
136 inspect items 1 and 2 as they refer to prod. rules of B (start):
137
138 1: LA(1): {$,NR}, b does not contain unique elements: done
139
140 2: LA(2): {NR}, so b does not contain unique elements: done
141
142 2: LA(2): {NR}, so b does not contain unique elements: done
143
144 2: LA(2): {NR}: b contains unique elements. Therefore:
145 LA(2) = {$,NR}
146 distributeLAsetsOfItem(2)
147 start -> .: LA: {$,NR}, B: -, c: {}
148 B empty, so return.
149 )
150 So, item 0 has LA set tt({$}), items 1 and 2 have LA sets tt({$,NR}).
151
152 The next step involves propagating the LA sets to kernel items of the states
153 to where transitions are possible:
154 itemization(
155 it() Item 0, state 0 transits to item 0 state 1. Item 0 of state 1's
156 current LA set is empty, so it receives LA set tt({$}), and 1 (state 1's
157 index) is inserted into the tt(todo) set.
158 it() Item 1, state 0 transits to item 1 state 1. Item 1 of state 1's
159 current LA set is empty, so it receives LA set tt({$,NR}), and 1 (state 1's
160 index) is inserted into the tt(todo) set.
161 )
162
163 Following this LA set propagation the LA sets of all items of state 1 are
164 computed, which in turn is followed by LA propagation to other states (states
165 2 and 3), etc. etc.
166
167 In this grammar there are no transitions to the current state (i.e.,
168 transitions from state x to state x). If such transitions are encountered then
169 they can be ignored by tt(inspectTransitions) as the LA sets of the items of a
170 state have already be computed by the time tt(inspectTransitions) is called.
171
172
173