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