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