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