Constructing CLR Parsing Table:
The parsing table has two fields
associate with each state in the DFA known as ACTION and GOTO. These are
computed using the following algorithm:
Construct C = { I0, I1,……… In}
the collection of sets of LR(1) items for G’
State ‘i’ of the parser is
constructed form Ii. The parsing actions for state ‘i’ are determined as
follows
- If [A → α.aβ, b] is in Ii and goto(Ii, a) = Ij then set action[i, a] to “shift j”. Here ‘a’ is required to be a terminal
- If [A → α, a] is in Ii, A ≠ S’, then set action [i, a] to “reduce A → α”
- \[If~\left[ S~\to ~S.,~\$\right]~~is\text{}in\text{}Ii,\text{}then\text{}the\text{}set\text{}action~\left[i,~\$\right]\text{}~~~to\text{}accept\]
If a conflict results from the
above rules, the grammar is said not to be LR(1), and the algorithm is said to
fail
The goto transitions for state ‘i'
are determined as follows: if goto(Ii, A) = Ij, then goto[i, A] = j
All entries not defined by rules
(2) and (3) are made “error”
The initial state of the parser
is the one constructed from the set containing item [S’ → .S, $]
Example 1:
State
|
Action
|
Goto
|
|||
c
|
d
|
$
|
S
|
C
|
|
0
|
s3
|
s4
|
1
|
2
|
|
1
|
ACC
|
||||
2
|
s6
|
s7
|
5
|
||
3
|
s3
|
s4
|
8
|
||
4
|
r3
|
r3
|
|||
5
|
r1
|
||||
6
|
s6
|
s7
|
9
|
||
7
|
r3
|
||||
8
|
r2
|
r2
|
|||
9
|
r2
|
||||
- si means shift state ‘i'
- Acc means Accept
- n means reduce by using production number ‘i’
- Blank means Error
LR(1) Items Construction:
Example 2: A
The augmented grammar is A’ →
A A →
(A) A → a and the sets of LR(1) items
are:
I0:
A’ → .A,$
A → .(A),$
A → .a,$
I1:
A’→A.,$
I2:
A→(.A),$
A→.(A),$
A→.a,)
I3:
A→a.,$
I4:
A→(A.),$
|
I5:
A→(.A),)
A→.(A),)
A→.a,)
I6:
A→a.,)
I7:
A→(A).,$
I8:
A→(A.),)
I9:
A→(A).,)
|
The goto function of the LR(1) collection of set of items
defines a DFA that recognizes the viable prefixes of the grammar. Each set of
item becomes a state in the DFA. The DFA for the example 2 from its items is as
shown in the image.
