Về mặt trực quan có thể giải thích cho việc làm ở luật sinh 2 như sau: Khi luật sinh A •B Closure(I), điều này có thể dẫn đến trong quá trình phân tích, bộ phân tích có thể gặp xâu con B. Nếu B P thì hy vọng có thể gặp xâu con dẫn được từ , vì vậy ta đưa luật sinh B • vào Closure(I).
Ví dụ 3.28:
Xét văn phạm:
E‟ E;
E E+T;
E T ;
T T*F ; T F ;
F (E) ;
F id
Nếu I là tập chỉ có một mục I =E‟ •E, khi đó Closure sẽ gồm các mục sau:
E‟ •E
E •E+T E •T
T •T*F T •F
F •(E) F •id
Dưới đây sẽ đưa ra giải thuật tính Closure(I) ở dạng hàm như sau: Function Closure(I)
Begin
J:= I;
Repeat J‟:= J;
For mỗi A •B J Do
IF (B P) AND (B•J) THEN J:= J B •;
Chú ý:
Until J = J‟ End;
Nếu một B – luật sinh được thêm vào Closure(I) với dấu chấm ở cận trái thì
tất cả các B – luật sinh sẽ được thêm vào Closure(I). Vì vậy nói chung không cần liệt kê các B - mục dạng B • được thêm vào Closure(I) mà chỉ cần có một danh sách biến B và các luật sinh sẽ được bổ sung là đủ. Với nhận xét trên, rò ràng có thể chia tập các mục đó thành hai lớp:
1. Tập mục hạt nhân (Kernel item) gồm mục S‟ •S và các mục có dấu chấm không nằm ở cận trái.
2. Tập mục không phải là hạt nhân (Nonkernel) là các mục còn lại.
Với mỗi tập khi cần sử dụng, ta có thể lấy bao đóng từ các tập mục hạt nhân thuộc nó.
f) Phép toán goto
Giả sử I là tập các mục trên họ mục LR(0) và X V khi đó goto(I, X) là bao đóng của tập tất cả các mục A X• sao cho A •X I
goto(I, X) = closure(A X• A •X I)
Về mặt trực quan, nếu tập I gồm các mục với một khả tiền tố nào đó thì goto(I, X) sẽ chứa các mục có khả tiền tố X.
Cách tính goto(I, X):
1. Tạo một tập I' = ∅.
2. Nếu A → α•Xβ I thì đưa A→ αX•β vào I', tiếp tục quá trình này cho đến khi xét hết tập I.
3. Goto(I, X) = closure(I')
Ví dụ 3.29:
Xét văn phạm:
E‟ E E E+T
E T
T T*F
F F F (E)
F id
Giả sử I là tập chỉ có hai mục I = E‟ E• , E E•+T. Tính goto (I, +) ?
Ta có I' = { E→ E + • T }
( goto (I, +) = closure(I') bao gồm các mục : E → E + • T (Luật 1)
T → • T * F (Luật 2) T → • F (Luật 2)
F → • (E) (Luật 2) F → • id (Luật 2)
g) Kỹ thuật xây dựng tập mục LR(0)
Ở trên đã nói đến tập các mục LR(0), song làm thế nào để có nó chưa được đề cập đến. Sau đây sẽ mô tả ngắn gọn giải thuật xây dựng tập LR(0).
Gọi C là họ tập hợp các mục LR(0) của văn phạm gia tố G = (N, T, P, S).
Procedure Item (G) Begin
I := S‟ •S; C:= Closure(I); Repeat
C1:= C;
For I C AND X V Do
IF goto(I, X) < > AND goto(I, X) C then C:= C goto(I, X); until C1 = C
end;
Chú ý:
- Thủ tục trên cho ta tập kết quả C, đó chính là tập LR(0). Thủ tục được bắt đầu với tập có một mục S‟ •S, mục này được đưa vào LR(0), quá trình xây dựng
LR(0) là quá trình bổ sung dần bằng tập mới khác rỗng goto (I, X) cho đến khi nào không nhận thêm được mục mới.
- Có thể hình dung rằng có một Automat hữu hạn không đơn định N có các trạng thái là các mục của văn phạm. Automat N sẽ chuyển trạng thái từ trạng thái
A•X sang trạng thái AX• khi đọc X và từ trạng thái A•B sang trạng thái A • khi đọc từ rỗng . Khi đó một tập I các mục cũng chính là tập I các trạng thái của Automat N. Do vậy việc tính Closure(I) cũng chính là việc tính - Closure(I) khi chuyển Automat không đơn định về Automat đơn định. Cũng vì lý do trên nên goto(I,X) thực chất là phép chuyển trạng thái của Automat đơn định bằng cách xây dựng tập con từ Automat không đơn định N. Với cách nhìn này thì thủ tục item(G) chỉ là phép dựng tập con áp dụng cho Automat không đơn định N mà Automat này được xây dựng từ văn phạm gia tố G.
Ví dụ 3.30:
Xét văn phạm tăng cường E‟ E;
E E+T ; E T ;
T T*F ; T F ;
F id.
Ta xây dựng họ tập hợp mục LR(0) của văn phạm như sau: Closure({E'→ •E}):
I0 : E'→ • E
E → • E + T E → • T
T → • T * F T → • F
F → • (E) F → • id
Goto (I0, E) I1: E'→ E •
I : 2 | E → E • + T E → T • | |
Goto (I , F) 0 | I : 3 | T → T • * F T → F • |
Goto (I , ( ) 0 | I : 4 | F → (• E) |
Goto (I , id) 0 | I : 5 | E → • E + T E → • T T → • T * F T → • F F → • (E) F → • id F → id • |
Goto (I , +) 1 | I : 6 | E → E + • T |
Goto (I , *) 2 | I : 7 | T → • T * F T → • F F → • (E) F → • id T → T* • F |
Goto (I , E) 4 | I : 8 | F → • (E) F → • id T → (E •) |
Goto (I , T) 6 | I : 9 | E → E • + T E → E + T • |
Goto (I , F) 7 | I : 10 | T → T • * F T → T * F • |
Goto (I , ) ) 8 | I : 11 | F → (E) • |
Có thể bạn quan tâm!
-
Phân Tích Cú Pháp Cho Xâu Vào + Id * + Id Phục Hồi Lỗi -
A. Cây Phân Tích Cú Pháp Của Xâu Id+Id*id Được Xây Dựng Từ Dưới Lên Theo Phương Pháp Đẩy-Thu -
A. Cây Phân Tích Cú Pháp Của Xâu Id * Id + Id Được Xây Dựng Từ Dưới Lên Theo Phương Pháp Đẩy-Thu -
Chương trình dịch - 19 -
Chương trình dịch - 20 -
Chương trình dịch - 21
Xem toàn bộ 224 trang tài liệu này.
Hàm goto của các mục được biểu diễn ở dạng sơ đồ chuyển trạng thái của một Automat đơn định cho ở hình 3.15.
I0
E
I1 +
I6
T
I9
*
To I3 To I4
To I5
T
I1
*
I7
F
I10
F
I
3
(
To I4
To I5
(
I
E
)
4
I
8
I
11
+
T
To
id
id
I5
F
To I2
To I3
To I7
I6
Hình 3.15. Sơ đồ chuyển
h) Giải thuật xây dựng bảng phân tích cú pháp SLR
Bây giờ ta giới thiệu kỹ thuật xây dựng các hàm action và hàm goto cho bảng phân tích cú pháp SLR. Kỹ thuật xây dựng được mô tả bởi giải thuật sau:
- Input: Văn phạm tăng cường (gia tố) G.
- Output: Hàm action và hàm Goto cho bảng phân tích SLR
- Process:
1. Xây dựng C = { I0, I1, ..., In }, họ tập hợp các mục LR(0) của G'.
2. Trạng thái i được xây dựng từ Ii. Các action tương ứng với trạng thái i được xác định như sau:
2.1. Nếu A → α • aβ Ii và goto (Ii, a) = Ij thì action[i, a] ="shift j". Ở đây a là ký hiệu kết thúc.
2.2. Nếu A → α• Ii thì action[i, a] ="reduce (A → α)";
a FOLLOW(A). Ở đây A không phải là S'
2.3. Nếu S' → S• Ii thì action[i, $] ="accept".
Nếu một action đụng độ được sinh ra bởi các luật trên, ta nói văn phạm không phải là SLR. Giải thuật sinh ra bộ phân tích cú pháp sẽ thất bại trong trường hợp này.
3. Với mọi ký hiệu chưa kết thúc A, nếu goto (Ii,A) = Ij thì goto[i, A] = j
4. Tất cả các ô không xác định được bởi 2 và 3 đều là “error”
5. Trạng thái khởi đầu của bộ phân tích cú pháp được xây dựng từ tập các mục chứa S‟→ • S
Ví dụ 3.31:
Xây dựng bảng phân tích cú pháp SLR cho văn phạm gia tố G: E' → E;
E → E + T | T;
T → T * F | F;
F → (E) | id.
Ta có các luật sinh:
(0) E'→ E;
(1) E → E + T;
(2) E → T;
(3) T → T * F;
(4) T → F;
(5) F → (E);
(6) F → id.
1. C = { I0, I1, ... I11 }
2. FOLLOW(E) = {+, ), $}
FOLLOW(T) = {*, +, ), $}
FOLLOW(F) = {*, +, ), $}
Dựa vào họ tập hợp mục C đã được xây dựng trong ví dụ 3.28, ta thấy:
Trước tiên xét tập mục I0 : Mục F → • (E) cho action[0, ( ] ="shift 4", và mục F → • id cho action[0, id] ="shift 5". Các mục khác trong I0 không sinh được hành động nào.
Bây giờ xét I : Mục E'→ E • cho action[1, $] ="accept", mục E → E • + T cho
1
action[1, +] ="shift 6".
Tiếp theo xét I : E → T • ; T → T • * F
2
Vì FOLLOW(E) = {+, ), $}, mục đầu tiên làm cho action[2, $] = action[2,+] ="reduce (E ( T)". Mục thứ hai làm cho action[2, *] ="shift 7".
Tiếp tục theo cách này, ta thu được bảng phân tích cú pháp SLR đã trình bày trong bảng 3.13.
Action | Goto | ||||||||
id | + | * | ( | ) | $ | E | T | F | |
0 | s5 | s4 | 1 | 2 | 3 | ||||
1 | s6 | acc | |||||||
2 | r2 | s7 | r2 | r2 | |||||
3 | r4 | r4 | r4 | r4 | |||||
4 | s5 | s4 | 8 | 2 | 3 | ||||
5 | r6 | r6 | r6 | r6 | |||||
6 | s5 | s4 | 9 | 3 | |||||
7 | s5 | s4 | 10 | ||||||
8 | s6 | s11 | |||||||
9 | r1 | s7 | r1 | r1 | |||||
10 | r3 | r3 | r3 | r3 | |||||
11 | r5 | r5 | r5 | r5 |
Bảng 3.13. Bảng phân tích cú pháp LR(1)
Bảng phân tích xác định bởi giải thuật trên gọi là bảng SLR(1) của văn phạm G, bộ phân tích LR sử dụng bảng SLR(1) gọi là bộ phân tích SLR(1) và văn phạm có một bảng SLR(1) gọi là văn phạm SLR(1). Mọi văn phạm SLR(1) đều không mơ hồ. Tuy nhiên có những văn phạm không mơ hồ nhưng không phải là SLR(1).
Ví dụ 3.32:
Xét văn phạm G với tập luật sinh như sau: S → L = R ;
S → R ;
L → * R ; L → id ; R → L .