| 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 |
|