Bài 10: Cho văn phm
E E op E | (E) | true | false
op and | or
a. Xây dng bng phân tích pháp LR chính tc cho văn phm trên.
Văn phạm tăng cường:
E’ E
[1] E E op E
[2] E → (E)
[3] E true
[4] E false
[5] op and
[6] op or
Xây dựng họ tập mục
I’
(Nếu
[A
α
•X ,
a]
I
thì
đưa
[A
α
X• ,
a]
vào
I')
Closure(I’)
closure({E'
E,
$})
E'
E,
$
E'
E,
$
E
E
op
E,
$
/
and/or
E
(E),
$
/
and/or
E
true
,
$
/
and/or
E
false
,
$
/
and/or
I
0
Goto(I
0
,E)
E'
E
•,
$
E
→E
op
E,
$
/
and/or
E'
E
•,
$
E
E
op
E,
$
/
and/or
op
and
,
(/true/false
op
or
,
(/true/false
I
1
Goto(I
0
,
(
)
E
(•
E),
$
/
and/or
E
(•
E),
$
/
and/or
E
E
op
E,
)/and/or
E
(E),
)/and/or
E
true
,
)/and/or
E
false
,
)/and/or
I
2
Goto(I
0
,
true
)
E
true
•,
$
/
and/or
E
true
•,
$
/
and/or
I
3
Goto(I
0
,
false
)
E
false
•,
$
/
and/or
E
false
•,
$
/
and/or
I
4
Goto(I
1
,op)
E
E
op
E,
$
/
and/or
E
E
op
E,
$
/
and/or
E
E
op
E,
$
/
and/or
E
(E),
$
/
and/or
E
true
,
$
/
and/or
E
false
,
$
/
and/or
I
5
Goto(I
1
,
and
)
op
and
•,
(/true/false
op
and
•,
(/true/false
I
6
Goto(I
1
,
or
)
op
or
•,
(/true/false
op
or
•,
(/true/false
I
7
Goto(I
2
,
E)
E
(E
•),
$
/
and/or
E
E
op
E,
)/and/or
E
(E
•),
$
/
and/or
E
E
op
E,
)/and/or
op
and
,
(/true/false
op
or
,
(/true/false
I
8
Goto(I
2
,
(
)
E
(•
E),
)/and/or
E
(•
E),
)/and/or
E
E
op
E,
)/and/or
E
(E),
)/and/or
E
true
,
)/and/or
E
false
,
)/and/or
I
9
Goto(I
2
,
true
)
E
true
•,
)/and/or
E
true
•,
)/and/or
I
10
Goto(I
2
,
false
)
E
false
•,
)/and/or
E
false
•,
)/and/or
I
11
Goto(I
5
,
E)
E
E
op
E
•,
$
/
and/or
E
E
op
E,
$
/
and/or
E
E
op
E
•,
$
/
and/or
E
E
op
E,
$
/
and/or
op
and
,
(/true/false
op
or
,
(/true/false
I
12
Goto(I
5
,
(
)
E
(•E),
$
/
and/or
≡I
2
Goto(I
5
,
true
)
E
true
•,
$
/
and/or
≡I
3
Goto(I
5
,
false
)
E
false
•,
$
/
and/or
≡I
4
Goto(I
8
,
)
)
E
(E)
•,
$
/
and/or
E
(E)
•,
$
/
and/or
I
13
Goto(I
8
,op
)
E
E
op
E,
)/and/or
E
E
op
E,
)/and/or
E
E
op
E,
)/and/or
E
(E),
)/and/or
E
true
,
)/and/or
E
false
,
)/and/or
I
14
Goto(I
8
,
and
)
op
and
•,
(/true/false
≡I
6
Goto(I
8
,
or
)
op
or
•,
(/true/false
≡I
7
Goto(I
9
,
E)
E
(E•),
)/and/or
E
E
op
E,
)/and/or
E
(E•),
)/and/or
E
E
op
E,
)/and/or
op
and
,
(/true/false
op
or
,
(/true/false
I
15
Goto(I
9
,
(
)
E
(•
E),
)/and/or
I
9
Goto(I
9
,
true
)
E
true
•,
)/and/or
I
10
Goto(I
9
,
false
)
E
false
•,
)/and/or
I
11
Goto(I
12
,op)
E
E
op
E,
$
/
and/or
≡I
5
Goto(I
12
,
and
)
op
and
•,
(/true/false
≡I
6
Goto(I
12
,
or
)
op
or
•,
(/true/false
≡I
7
Goto(I
14
,E)
E
E
op
E•,
)/and/or
E
E
op
E,
)/and/or
E
E
op
E•,
)/and/or
E
E
op
E,
)/and/or
op
and
,
(/true/false
op
or
,
(/true/false
I
16
Goto(I
14
,
(
)
E
(•
E),
)/and/or
≡I
9
Goto(I
14
,
true
)
E
true
•,
)/and/or
≡I
10
Goto(I
14
,
false
)
E
false
•,
)/and/or
≡I
11
Goto(I
15
,
)
)
E
(E)
•,
)/and/or
E
(E)
•,
)/and/or
I
17
Goto(I
15
,op
)
E
E
op
E,
)/and/or
≡I
14
Goto(I
15
,
and
)
op
and
•,
(/true/false
≡I
6
Goto(I
15
,
or
)
op
or
•,
(/true/false
≡I
7
Goto(I
16
,
op)
E
E
op
E,
)/and/or
≡I
14
Goto(I
16
,
and
)
op
and
•,
(/true/false
≡I
6
Goto(I
16
,
or
)
op
or
•,
(/true/false
≡I
7
Trng
thái
action
and
or
true
false
(
)
$
E
op
0
S3
S4
S2
1
1
S6
S7
acc
5
2
S10
S11
S9
8
3
R3
R3
R3
4
R4
R4
R4
5
S3
S4
S2
12
6
R5
R5
R5
7
R6
R6
R6
8
S6
S7
S13
14
9
S10
S11
S9
15
10
R3
R3
R3
11
R4
R4
R4
12
S6/
R1
S7/R1
R1
5
13
R2
R2
R2
14
S10
S11
S9
16
15
S6
S7
S17
14
16
S6/
R1
S7/R1
14
17
R2
R2
R2

Preview text:


Bài 10: Cho văn phạm
E → E op E | (E) | true | false
op → and | or
a. Xây dựng bảng phân tích cú pháp LR chính tắc cho văn phạm trên.
• Văn phạm tăng cường: E’ → E [1] E → E op E [2] E → (E) [3] E → true [4] E → false [5] op → and [6] op → or
• Xây dựng họ tập mục
I’ (Nếu [A ⟶ α•X , a] ∈ Closure(I’)
I thì đưa [A ⟶ αX• , a] vào I') closure({E' ⟶ E' ⟶ • E, $ E' ⟶ • E, $ • E, $})
E → • E op E, $/and/or
E → • (E), $/and/or I0
E → • true, $/and/or
E → • false, $/and/or Goto(I 0,E) E' ⟶ E •, $ E' ⟶ E •, $
E →E • op E, $/and/or
E → E • op E, $/and/or op → • and, I1 (/true/false
op → • or, (/true/false Goto(I 0,( )
E → (• E), $/and/or
E → (• E), $/and/or
E → • E op E, )/and/or
E → • (E), )/and/or I2
E → • true, )/and/or
E → • false, )/and/or Goto(I0, true)
E → true •, $/and/or
E → true •, $/and/or I3 Goto(I0, false)
E → false •, $/and/or
E → false •, $/and/or I4 Goto(I 1,op)
E → E op • E, $/and/or
E → E op • E, $/and/or
E → • E op E, $/and/or
E → • (E), $/and/or I5
E → • true, $/and/or
E → • false, $/and/or Goto(I1, and) op → and •, op → and •, (/true/false I (/true/false 6 Goto(I1, or)
op → or •, (/true/false
op → or •, (/true/false I7 Goto(I 2, E)
E → (E •), $/and/or
E → (E •), $/and/or
E → E • op E, )/and/or
E → E • op E, )/and/or op → • and, I8 (/true/false
op → • or, (/true/false Goto(I 2, ( )
E → (• E), )/and/or
E → (• E), )/and/or
E → • E op E, )/and/or
E → • (E), )/and/or I9
E → • true, )/and/or
E → • false, )/and/or Goto(I2, true)
E → true •, )/and/or
E → true •, )/and/or I10 Goto(I2, false)
E → false •, )/and/or
E → false •, )/and/or I11 Goto(I 5, E)
E → E op E •, $/and/or
E → E op E •, $/and/or
E → E • op E, $/and/or
E → E • op E, $/and/or op → • and, I12 (/true/false
op → • or, (/true/false Goto(I5,( )
E → (•E), $/and/or ≡I2 Goto(I5, true)
E → true •, $/and/or ≡I3 Goto(I5, false)
E → false •, $/and/or ≡I4 Goto(I8,) )
E → (E) •, $/and/or
E → (E) •, $/and/or I13 Goto(I 8,op )
E → E op • E, )/and/or
E → E op • E, )/and/or
E → • E op E, )/and/or
E → • (E), )/and/or I14
E → • true, )/and/or
E → • false, )/and/or Goto(I 8, and) op → and •, ≡I (/true/false 6 Goto(I8, or)
op → or •, (/true/false ≡I7 Goto(I 9, E) E → (E•), )/and/or E → (E•), )/and/or
E → E • op E, )/and/or
E → E • op E, )/and/or op → • and, I15 (/true/false
op → • or, (/true/false Goto(I9, ( )
E → (• E), )/and/or ≡ I9 Goto(I9, true)
E → true •, )/and/or ≡I10 Goto(I9, false)
E → false •, )/and/or ≡I11 Goto(I12,op)
E → E op • E, $/and/or ≡I5 Goto(I 12, and) op → and •, ≡I (/true/false 6 Goto(I12, or)
op → or •, (/true/false ≡I7 Goto(I 14,E)
E → E op E•, )/and/or
E → E op E•, )/and/or
E → E • op E, )/and/or
E → E • op E, )/and/or op → • and, I16 (/true/false
op → • or, (/true/false Goto(I14,( )
E → (• E), )/and/or ≡I9 Goto(I14, true)
E → true •, )/and/or ≡I10 Goto(I14, false)
E → false •, )/and/or ≡I11 Goto(I15, ) )
E → (E) •, )/and/or
E → (E) •, )/and/or I17 Goto(I15,op )
E → E op • E, )/and/or ≡I14 Goto(I 15, and) op → and •, ≡I (/true/false 6 Goto(I15, or)
op → or •, (/true/false ≡I7 Goto(I16, op)
E → E op • E, )/and/or ≡I14 Goto(I 16, and) op → and •, ≡I (/true/false 6 Goto(I16, or)
op → or •, (/true/false ≡I7 Trạng action goto thái and or true false ( ) $ E op 0 S3 S4 S2 1 1 S6 S7 acc 5 2 S10 S11 S9 8 3 R3 R3 R3 4 R4 R4 R4 5 S3 S4 S2 12 6 R5 R5 R5 7 R6 R6 R6 8 S6 S7 S13 14 9 S10 S11 S9 15 10 R3 R3 R3 11 R4 R4 R4 12 S6/ S7/R1 R1 5 R1 13 R2 R2 R2 14 S10 S11 S9 16 15 S6 S7 S17 14 16 S6/ S7/R1 14 R1 17 R2 R2 R2