2. Mỗi một lá có nhãn là một ký hiệu kết thúc hoặc ε.
3. Mỗi nút trong có nhãn là một ký hiệu chưa kết thúc.
4. Nếu A là một ký hiệu chưa kết thúc được dùng làm nhãn cho một nút trong nào đó và X1, ..., Xn là nhãn của các con của nó theo thứ tự từ trái sang phải thì A → X1X2 ... Xn là một luật sinh. Ở đây X1, ..., Xn có thể là ký hiệu kết thúc hoặc chưa kết thúc. Ðặc biệt, nếu A → ε thì nút có nhãn A có thể có một con có nhãn ε.
Một cây phân tích cú pháp có thể xem như một biểu diễn cho một dẫn xuất.
Ðể hiểu được bộ phân tích cú pháp làm việc ta cần xét dẫn xuất trong đó chỉ có ký hiệu chưa kết thúc trái nhất trong bất kỳ dạng câu nào được thay thế tại mỗi bước, dẫn xuất như vậy được gọi là dẫn xuất trái nhất. Nếu α β trong đó ký hiệu
chưa kết thúc trái nhất trong α được thay thế, ta viết α * β .
l m
Nếu S * α thì ta nói α là dạng câu trái nhất của văn phạm.
l m
Có thể bạn quan tâm!
-
Biểu Diễn Automat Bằng Đồ Thị -
Automat Đoán Nhận R=(A B) * Abb -
Vị Trí, Chức Năng, Nhiệm Vụ Của Giai Đoạn Phân Tích Cú Pháp -
A, B, C. Mô Tả Quá Trình Phân Tích Xâu W = Cad -
Mô Tả Hình Tổ Chức Dữ Liệu Của Kỹ Thuật Dự Đoán -
Cây Phân Tích Cú Pháp Cho Xâu Vào Id + Id * Id Được Xây Dựng Từ Dưới Lên
Xem toàn bộ 224 trang tài liệu này.
Tương tự, ta có dẫn xuất phải nhất - còn gọi là dẫn xuất chính tắc (canonical derivations).
Ví dụ 3.1:
Cho văn phạm G = ( N, T, P, S); Tập P gồm các quy tắc:
E E + E; E E * E; E (E); E - E; E id
Khi đó cây phân tích cú pháp cho xâu - (id + id) có dạng ở hình 3.2 E
E
-
( E )
E E
+
id id
Hình 3.3. Minh họa một cây phân tích cú pháp
Ðể thấy mối quan hệ giữa cây phân tích cú pháp và dẫn xuất, ta xét một dẫn xuất: α1 α2 ... αn .
Với mỗi αi ta xây dựng một cây phân tích cú pháp. Ví dụ với dẫn xuất:
E -E - (E) - (E + E) - (id + E) - (id + id) Quá trình xây dựng cây phân tích cú pháp như sau:
E E
E E
- E -
( )
E
E E
E E
- -
( E ) ( E )
E E E E
+ +
E id
E
-
( E )
E E
+
id id
Hình 3.4. Xây dựng cây phân tích cú pháp từ dẫn xuất
3.2.2. Ngôn ngữ nhập nhằng (Ambiguity)
Trong lý thuyết ngôn ngữ hình thức đã đề cập đến tính nhập nhằng của văn phạm; để tiện cho việc trình bày, ta đưa ra khái niệm tương tự về văn phạm nhập nhằng.
Văn phạm được gọi là nhập nhằng nếu tồn tại một xâu có hai cây phân tích cú pháp khác nhau. Nói cách khác văn phạm được gọi là nhập nhằng nếu tồn tại một xâu có nhiều hơn một cây phân tích cú pháp cho dẫn xuất trái nhất hay phải nhất.
Ngôn ngữ được sinh bởi văn phạm nhập nhằng gọi là ngôn ngữ nhập nhằng.
Ví dụ 3.2:
Cho văn phạm: G = ( N, T, P, E)
Tập P gồm các quy tắc:
E E + E; E E * E; E (E); E - E; E id
Xét xâu id + id * id, xâu này có hai dẫn xuất trái nhất là:
a) E E + E id + E id + E * E id + id * E id + id * id
b) E E * E E + E * E id + E * E id + id * E id + id * id Hình 3.5a và 3.5b là hai cây phân tích cú pháp của xâu trên.
E
E
E
+ E
id E
E
E * E E
* id E
id id
+ id id
a) b)
Hình 3.5. Hai cây phân tích cú pháp của xâu id + id * id
Vậy văn phạm trên là văn phạm nhập nhằng.
3.2.3. Kỹ thuật khử nhập nhằng
Nếu một văn phạm là nhập nhằng thì khi gặp một xâu có nhiều hơn một cây phân tích cú pháp; ta không thể xác định được cây phân tích cú pháp nào sẽ được chọn. Vì vậy, ta phải viết lại văn phạm nhằm loại bỏ sự nhập nhằng của nó. Chẳng hạn, xét văn phạm với các luật sinh :
Các luật sinh trên định nghĩa câu lện IF, ở đây
Ký hiệu E là biểu thức; S là câu lệnh và xét câu lệnh sau:
IF E1 THEN IF E2 THEN S1 ELSE S2
Văn phạm trên là văn phạm nhập nhằng vì câu lệnh trên có hai cây phân tích cú pháp trái nhất ở hình 3.6a và hình 3.6b
sttm
if expr then sttm
E1 if expr
E2
then
sttm
S1
else
sttm
S2
a)
sttm
if expr then
sttm
else
sttm
E1 if expr
E2
then
sttm S2
S1
b)
Hình 3.6. Hai cây phân tích cú pháp của cùng một xâu
Để khử tính nhập nhằng của văn phạm nêu trên, người ta thường khắc phục bằng cách cho mỗi ELSE ứng với THEN gần nhất trước đó. Theo nguyên tắc này, ta sửa lại các luật sinh như sau:
3.2.4. Kỹ thuật khử đệ quy trái
Trong lý thuyết ngôn ngữ hình thức, khi xét dạng chuẩn Greibach đã đề cập đến các A - luật sinh. Các A - luật sinh thường làm cho văn phạm trở thành đệ quy
trái. Ở đây, ta sẽ nhắc lại khái niệm và kỹ thuật khử đệ quy trái đã nêu trong các bổ đề của Greibach.
1) Khái niệm
Một văn phạm phi ngữ cảnh được gọi là đệ quy trái nếu tồn tại một dẫn xuất dạng: A + A với AN; V+ = (NT)+
Phương pháp phân tích Top – Down không khắc phục được trường hợp văn phạm đệ quy trái. Vì vậy, để có thể sử dụng được phương pháp phân tích Top – Down cần phải khử tính đệ quy trái của văn phạm.
Ðệ quy trái có hai loại :
- Trực tiếp: Dạng A Aα ;
i
- Gián tiếp: A Aα với i ≥ 2.
Ví dụ 3.3:
Xét văn phạm như sau: S → Aa | b;
A→ Ac | Sd | a.
Biến A là biến đệ quy trái (trực tiếp) vì A Ac nhờ áp dụng luật sinh A→ Ac Biến S, A cũng là các biến đệ quy trái (gián tiếp);
Vì S Aa Sda nhờ áp dụng các luật sinh S → Aa; A→ Sd và A Sd Aad nhờ áp dụng các luật sinh A→ Sd; S → Aa .
2) Kỹ thuật khử đệ quy trái
a) Khử đệ quy trái trực tiếp
Nếu luật sinh có dạng: A → Aα1 | Aα2 | ... | Aαm | β1 | β2 | ... | βn
thì thêm vào một biến mới A‟ và thay luật sinh đó bởi các luật sinh: A → β1A‟ | β2A‟ | ... | βnA‟
Và A‟ → α1A‟| α2A‟ | ... | αm A‟ | ε
Ví dụ 3.4:
- Xét văn phạm sinh ra biểu thức số học có các luật sinh sau: E E + T; E T ;
T T*F; T F ; F (E); F id.
Áp dụng kỹ thuật nêu trên, ta có:
+ Với các luật sinh E E + T; E T có thể viết lại là E E + T | T và nó được thay thế bằng các luật sinh E TE1 và E1 + TE1| .
+ Với các luật sinh T T*F; T F có thể viết lại là T T*F | F và nó
được thay thế bằng các luật sinh T FT1 và T1 *FT1 | .
Sau khi khử đệ quy trái, ta thu được văn phạm không đệ quy trái với tập các luật sinh:
E TE1 ; E1 + TE1| ;
T FT1 và T1 *FT1 | ; F (E) | id.
- Xét văn phạm S → Aa | b;
A→ Ac | Sd | a
Ta có A Ac | Sd | a; nên nó sẽ được thay thế bằng các luật sinh A SdA‟ | aA‟ ;
A‟ cA'| .
b) Khử đệ quy trái gián tiếp
- Ý tưởng
Với mỗi biến đệ quy trái gián tiếp:
+ Biến đổi và thay thế để đưa nó về đệ quy trái trực tiếp.
+ Khử đệ quy trái trực tiếp.
- Giải thuật loại bỏ đệ quy trái gián tiếp
Input: Văn phạm không tuần hoàn và không có các – luật sinh (nghĩa là văn phạm không chứa các dẫn xuất dạng A + A và A )
Output: Văn phạm tương đương không đệ quy trái Process:
1. Sắp xếp các ký hiệu không kết thúc theo thứ tự A1, A2, ..., An ;
2. For i := 1 to n do Begin
- for j:=1 to i -1 do
if luật sinh Ai Aj then
begin
+ Tìm các luật sinh dạng Aj δ1 | δ2 | ... | δk ;
+ Thay luật sinh dạng Ai Aj bởi luật sinh Ai δ1 | δ2 | ... | δk;
{Trong đó các A - luật sinh và A - luật sinh là các luật sinh hiện tại}
i j
end;
- Loại bỏ đệ quy trái trực tiếp trong số các Ai - luật sinh; End;
Ví dụ 3.5:
a) Khử đệ quy trái cho văn phạm có các luật sinh S → Aa | b;
A→ Ac | Sd | a.
Áp dụng giải thuật trên
1. Sắp xếp các ký hiệu chưa kết thúc theo thứ tự S, A.
2. - Với i = 1:
+ j = 0 nên vòng lặp theo j bị bỏ qua;
+ Không có đệ quy trái trực tiếp nên không có điều gì xảy ra.
- Với i = 2:
+ j = 1:
Có luật sinh A Sd và tìm được S Aa | b nên phải thay thế luật sinh này và sau khi thay ta thu được: A Ac | Aad | bd | a.
+ Loại bỏ đệ quy trái trực tiếp cho các A luật sinh, ta được: A bdA' | aA';
A' cA' | adA' | ε
b) Khử đệ quy trái cho văn phạm có các luật sinh: S Sc| Aa| b;
A Ac| Bd| b; B Bb| Sa| d
1. Sắp xếp các ký hiệu chưa kết thúc theo thứ tự S, A, B.
2. - Với i = 1:
+ j = 0 nên vòng lặp theo j bị bỏ qua;
+ Khử đệ quy trái trực tiếp cho S- luật sinh:
Bổ sung thêm biến S‟;
Thay S Sc| Aa| b bằng S AaS‟| bS‟ ; S‟ cS‟| .
-Với i = 2:
+ j =1:
Không tồn tại luật sinh dạng Ai Aj nên việc thay thế bị bỏ qua.
+ Khử đệ quy trái trực tiếp cho A - luật sinh: Bổ sung thêm biến A‟;
Thay A Ac| Bd| b bằng A BdA‟ | bA‟ ; A‟ cA‟| .
- Với i = 3; ta có:
+ j =1:
Tồn tại luật sinh B Sa và tìm được S AaS‟| bS‟ nên sau khi thay thế ta thu được: B Bb| AaS‟a | bS‟a | d.
+ j = 2:
Tồn tại luật sinh B AaS‟a và tìm được A BdA‟ | bA‟ nên sau khi thay thế ta thu được: B Bb| BdA‟aS‟a | bA‟aS‟a | bS‟a | d.
+ Loại bỏ đệ quy trái trực tiếp cho các B - luật sinh: Bổ sung thêm B‟;
Thay luật sinh B Bb| BdA‟aS‟a | bA‟aS‟a | bS‟a | d bằng
B bA‟aS‟a B‟| bS‟aB‟ | dB‟ và B‟ bB‟| dA‟aS‟aB‟| .
Vậy sau khi khử đệ quy trái ta thu được văn phạm với các luật sinh sau: S AaS‟| bS‟; S‟ cS‟| ;
A BdA‟ | bA‟ ; A‟ cA‟| ;
B bA‟aS‟a B‟| bS‟aB‟ | dB‟; B‟ bB‟| dA‟aS‟aB‟| .
3.2.5. Kỹ thuật thừa số hoá bên trái
Trong quá trình phân tích từ trên xuống (Top – Down); ta có thể thay một biến ở vế trái bằng một xâu ở vế phải. Vấn đề nảy sinh là ở mỗi bước phân tích trong tập P có thể có nhiều luật sinh có thể sử dụng được nhưng ta không biết chọn luật sinh nào là thích hợp cho các bước tiếp theo. Để khắc phục tình trạng trên, người ta sử dụng kỹ thuật thừa số hoá bên trái.