Once the items of all the grammar's states have been determined the LA sets for the states' items are computed. Starting from the LA set of the kernel item of state 0 (representing the augmented grammar's production rule tt(S_$: . S), where tt(S) is the grammar's start rule) the LA sets of all items of all of the grammar's states are determined. By definition, the LA set of state 0's kernel item equals tt($), representing end-of-file. Starting from the function tt(State::determineLAsets), which is called for state 0, the LA sets of all items of all states are computed. For each state, the LA sets of its items are computed first. Once they have been computed, the LA sets of items from where transitions to other states are possible are then propagated to the matching kernel items of those destination states. When the LA sets of kernel items of those destination states are enlarged then their state indices are added to a set tt(todo). LA sets of the items of states whose indices are stored in the tt(todo) set are (re)computed (by calling tt(determineLAsets) for those states) until tt(todo) is empty, at which point all LA sets have been computed. Initially tt(todo) only contains 0, the index of the initial state, representing the augmented grammar's production rule. To compute the LA sets of a state's items the LA set of each of its kernel items is distributed (by the member tt(State::distributeLAsetOf)) over the items which are implied by the item being considered. E.g., for item tt(X: a . Y z), where tt(a) and tt(z) are any sequence of grammar symbols and tt(X) and tt(Y) are nonterminal symbols, all of tt(Y's) production rules are added as new items to the current state. Then the member tt(distributeLAsetOfItem(idx)) matches the item's rule specification with the specification tt(a.Bc), where tt(a) and tt(c) are (possibly empty) sequences of grammatical symbols, and tt(B) is a (possibly empty) nonterminal symbol appearing immediately to the right of the item's dot position. if tt(B) is empty then there are no additional production rules and tt(distributeLAsetOf) may return. Otherwise, the set tt(b = FIRST(c)) is computed. This set holds all symbols which may follow tt(B). If tt(b) contains epsilon() (i.e., the element representing the empty set), then the currently defined LA set of the item can also be observed. In that case epsilon() is removed, and the currently defined LA set is added to tt(b). Finally, the LA sets of all items representing a production rule for tt(B) are inspected: if tt(b) contains unique elements compared to the LA sets of those items, then the unique elements of tt(b) are added to the LA sets of those items. Finally, tt(distributeLAsetOfItem) is recursively called for those items whose LA sets were enlarged. Once the LA sets of the items of a state have thus been computed, tt(inspectTransitions) is called to propagate the LA sets of items from where transitions to other states are possible to the affected (kernel) items of those other (destination) states. The member tt(inspectTransitions) inspects all tt(Next) objects of the current state's tt(d_nextVector). Next objects provide itemization( it() the state index of a state to transfer to from the current state; it() a size_t vector of item transitions. Each element is the index of an item in the current state (the source-item), its index is the index of a (kernel) item of the state to transfer to (the destination index). ) If the LA set of a destination item can be enlarged from the LA set of the source item then the LA sets of the destination state's items must be recomputed. This is realized by inserting the destation state's index into the `todo' set. To illustrate an LA-set computation we will now compute the LA sets of (some of) the items of the states of the grammar introduced at the beginning of this chapter. Its augmented grammar consists of the following production rules: verb( 1. start: start expr 2. start: // empty 3. expr: NR 4. expr: expr '+' expr 5. start_$: start ) When analyzing this grammar, we found the following five states, consisting of several items and transitions (kernel items are marked with K following their item indices). Next to the items, where applicable, the goto-table is shown: the state to go to when the mentioned grammatical symbol has been recognized: verb( Goto table ----------- State 0: start 0K: start_$ -> . start 1 1: start -> . start expr 1 2: start -> . State 1: expr NR 0K: start_$ -> start . 1K: start -> start . expr 2 2: expr -> . NR 3 3: expr -> . expr '+' expr State 2: '+' 0K: start -> start expr . 1K: expr -> expr . '+' expr 4 State 3: 0K: expr -> NR . State 4: expr NR 0K: expr -> expr '+' . expr 5 1: expr -> . NR 3 2: expr -> . expr '+' expr 5 State 5: '+' 0K: expr -> expr '+' expr . 1K: expr -> expr . '+' expr 4 ) Item 0 of state 0 by definition has LA symbol $, and LA computation therefore always starts at item 0 of state 0. The interesting part of the LA set computation is encountered in the recursive member tt(distributeLAsets): verb( distributeLAsetsOfItem(0) start_$ -> . start: LA: {$}, B: start, c: {}, so b: {$} items 1 and 2 refer to production rules of B (start) and are inspected: 1: LA(1): {}: b contains unique elements. Therefore: LA(1) = {$} distributeLAsetsOfItem(1): start -> . start expr: LA: {$}, B: start, c: {expr}, so b: {NR} inspect items 1 and 2 as they refer to production rules of B (start): 1: LA(1): {}: b contains unique elements. Therefore: LA(1) = {$,NR} distributeLAsetsOfItem(1) start -> . start expr: LA: {$,NR}, B: start, c: {expr}, so b: {NR} inspect items 1 and 2 as they refer to prod. rules of B (start): 1: LA(1): {$,NR}, so b does not contain unique elements: done 2: LA(2): {}, b contains unique elements LA(2) = {NR} distributeLAsetsOfItem(2) start -> .: LA: {NR}, B: -, c: {}, so b: {NR} inspect items 1 and 2 as they refer to prod. rules of B (start): 1: LA(1): {$,NR}, b does not contain unique elements: done 2: LA(2): {NR}, so b does not contain unique elements: done 2: LA(2): {NR}, so b does not contain unique elements: done 2: LA(2): {NR}: b contains unique elements. Therefore: LA(2) = {$,NR} distributeLAsetsOfItem(2) start -> .: LA: {$,NR}, B: -, c: {} B empty, so return. ) So, item 0 has LA set tt({$}), items 1 and 2 have LA sets tt({$,NR}). The next step involves propagating the LA sets to kernel items of the states to where transitions are possible: itemization( it() Item 0, state 0 transits to item 0 state 1. Item 0 of state 1's current LA set is empty, so it receives LA set tt({$}), and 1 (state 1's index) is inserted into the tt(todo) set. it() Item 1, state 0 transits to item 1 state 1. Item 1 of state 1's current LA set is empty, so it receives LA set tt({$,NR}), and 1 (state 1's index) is inserted into the tt(todo) set. ) Following this LA set propagation the LA sets of all items of state 1 are computed, which in turn is followed by LA propagation to other states (states 2 and 3), etc. etc. In this grammar there are no transitions to the current state (i.e., transitions from state x to state x). If such transitions are encountered then they can be ignored by tt(inspectTransitions) as the LA sets of the items of a state have already be computed by the time tt(inspectTransitions) is called.