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.
0 comments:
Post a Comment