Bài giảng Chương trình dịch (Phần 2)
Chƣơng 3. Phân tích cúa pháp
Chƣơng 3
PHÂN TÍCH CÚ PHÁP
Mục tiêu:
Giúp sinh viên có khả năng:
- Biết đƣợc vị trí, nhiệm vụ của giai đoạn phân tích cú pháp
- Biết đƣợc các phƣơng pháp phân tích cú pháp.
- Hiểu đƣợc các kỹ thuật biến đổi văn phạm.
- Hiểu đƣợc các kỹ thuật trong phƣơng pháp phân tích top - down.
- Hiểu đƣợc các kỹ thuật trong phƣơng pháp phân tích bottom - up .
- Vận dụng các kỹ thuật vào phân tích cú cho một số văn phạm đơn giản
Nội dung chính:
- Vị trí, nhiệm vụ của giai đoạn phân tích cú pháp và các phƣơng pháp phân
tích cú pháp.
- Các kỹ thuật biến đổi văn phạm: khử đệ quy trái, thừa số hoá bên trái, khử
nhập nhằng.
- Phƣơng pháp phân tích top – down: phân tích cú pháp đệ quy xuống, phân
tích cú pháp dự đoán.
- Phƣơng pháp phân tích bottom – up: phân tích cú pháp đẩy thu, phân tích
cú pháp LR(k).
3.1. Giai đoạn phân tích cú pháp
3.1.1. Vị trí, chức năng, nhiệm vụ của giai đoạn phân tích cú pháp
Giai đoạn phân tích cú pháp là giai đoạn tiếp theo của giai đoạn phân tích từ
vựng và trƣớc giai đoạn phân tích ngữ nghĩa.
Chức năng của giai đoạn phân tích cú pháp là phân tích chƣơng trình nguồn
về mặt cú pháp: Xây dụng cây phân tích cú pháp hoặc báo lỗi. Nhiệm vụ chính của
giai đoạn này là nhận vào dòng các thẻ từ (token) có đƣợc từ giai đoạn phân tích từ
vựng và xác nhận rằng nó có thể đƣợc sinh ra từ văn phạm của ngôn ngữ nguồn
bằng cách tạo ra cây phân tích cú pháp cho dòng thẻ từ này và đầu ra của nó là cây
phân tích cú pháp (parsing tree). Ngoài ra, bộ phân tích cú pháp còn có cơ chế ghi
nhận các lỗi cú pháp theo một phƣơng thức linh hoạt và có khả năng phục hồi đƣợc
76
Chƣơng 3. Phân tích cúa pháp
các lỗi thƣờng gặp để có thể tiếp tục xử lý phần còn lại của xâu vào. Có thể chỉ ra vị
trí của giai đoạn này với các giai đoạn liên quan ở hình 3.1.
Cây phân tích
cú pháp
(Parsing tree)
Chƣơng
trình nguồn
Thẻ từ
Bộ phân tích
từ vựng
Bộ phân tích
Phần còn lại
của front end
cú pháp
Yêu cầu
Thẻ từ mới
Bảng
ký hiệu
Hình 3.1. Vị trí của bộ phân tích cú pháp
3.1.2. Xử lý lỗi cú pháp
Chƣơng trình nguồn có thể chứa các lỗi ở nhiều mức độ khác nhau:
- Lỗi từ vựng: nhƣ tên, từ khóa, toán tử viết không đúng.
- Lỗi cú pháp: nhƣ ghi một biểu thức toán học với các dấu ngoặc đóng và mở
không cân bằng, thiếu dấu chấm phảy (;), thiếu từ khoá.
- Lỗi ngữ nghĩa: nhƣ một toán tử áp dụng vào một toán hạng không tƣơng thích,
sai kiểu dữ liệu.
- Lỗi logic: nhƣ thực hiện một lời gọi đệ quy không thể kết thúc.
Phần lớn việc phát hiện và phục hồi lỗi trong một chƣơng chƣơng trình biên
dịch tập trung vào giai đoạn phân tích cú pháp. Vì thế, bộ xử lý lỗi (error handler)
trong quá trình phân tích cú pháp phải đạt đƣợc mục đích sau:
- Ghi nhận và thông báo lỗi một cách rõ ràng và chính xác.
- Phục hồi lỗi một cách nhanh chóng để có thể xác định các lỗi tiếp theo.
- Không làm chậm tiến trình của một chƣơng trình đúng.
3.1.3. Các chiến lƣợc phục hồi lỗi
Phục hồi lỗi là kỹ thuật vƣợt qua các lỗi để tiếp tục quá trình dịch. Nhiều
chiến lƣợc phục hồi lỗi có thể dùng trong bộ phân tích cú pháp. Mặc dù không có
chiến lƣợc nào đƣợc chấp nhận hoàn toàn nhƣng một số trong chúng đã đƣợc áp
dụng rộng rãi. Ở đây sẽ giới thiệu một số chiến lƣợc:
1) Phương thức "hoảng sợ" (panic mode recovery)
77
Chƣơng 3. Phân tích cúa pháp
Đây là phƣơng pháp đơn giản nhất cho cài đặt và có thể dùng cho hầu hết
các phƣơng pháp phân tích. Khi một lỗi đƣợc phát hiện thì bộ phân tích cú pháp bỏ
qua từng ký hiệu một cho đến khi tìm thấy một tập hợp đƣợc chỉ định của các token
đồng bộ (synchronizing tokens), các token đồng bộ thƣờng là dấu chấm phẩy (;)
hoặc end.
2) Chiến lược mức ngữ đoạn (phrase_level recovery)
Khi phát hiện một lỗi, bộ phân tích cú pháp có thể thực hiện sự hiệu chỉnh
cục bộ trên phần còn lại của xâu vào. Cụ thể là thay thế phần đầu còn lại bằng một
chuỗi ký tự có thể tiếp tục. Chẳng hạn, dấu phẩy (,) bởi dấu chấm phẩy (;), xóa một
dấu phẩy lạ hoặc thêm vào một dấu chấm phẩy.
3) Chiến lược dùng các luật sinh sửa lỗi (error production)
Thêm vào văn phạm của ngôn ngữ những luật sinh lỗi và sử dụng văn
phạm này để xây dựng bộ phân tích cú pháp, giúp có thể sinh ra bộ đoán lỗi thích
hợp để chỉ ra cấu trúc lỗi đƣợc nhận biết trong xâu vào.
4) Chiến lược hiệu chỉnh toàn cục (global correction)
Một cách lý tƣởng là chƣơng trình biên dịch tạo ra một số thay đổi trong khi xử
lý một lỗi. Có những giải thuật để lựa chọn một số tối thiểu các thay đổi để đạt đƣợc một
hiệu chỉnh có chi phí toàn cục nhỏ nhất. Cho một xâu vào có lỗi x và một văn phạm G,
các giải thuật này sẽ tìm đƣợc một cây phân tích cú pháp cho xâu y mà số lƣợng các thao
tác chèn, xóa và thay đổi token cần thiết để chuyển x thành y là nhỏ nhất. Nói chung,
hiện nay kỹ thuật này vẫn còn ở dạng nghiên cứu lý thuyết.
3.1.4. Các phƣơng pháp phân tích cú pháp
Hiện tại có nhiều phƣơng pháp phân tích cú pháp khác nhau; tuy nhiên,
ngƣời ta có thể phân chúng thành 3 loại: phƣơng pháp phân tích tổng hợp, phƣơng
pháp phân tích top – down và phƣơng pháp phân tích bottom – up.
1) Phương pháp phân tích tổng hợp (Universal parsing)
Tiêu biểu cho phƣơng pháp phân tích tổng hợp là giải thuật Cooke – Young
Kasami và giải thuật Earley; Ngƣời ta gọi chúng là giải thuật tổng hợp hay giải
thuật vạn năng vì chúng phân tích cú pháp cho văn phạm bất kỳ. Tuy nhiên do tính
vạn năng của chúng cho nên nói chung phƣơng pháp này không hiệu quả với một
78
Chƣơng 3. Phân tích cúa pháp
văn phạm cụ thể; vì lý do trên, ngƣời ta ít sử dụng chúng để viết các chƣơng trình
dịch (Compiler).
2) Phương pháp phân tích Top – Down
Về mặt trực giác có thể coi phƣơng pháp phân tích Top – Down là phƣơng
pháp xây dựng cây phân tích cú pháp từ trên xuống hay có thể xem nhƣ một nỗ lực
xây dựng cây phân tích cú pháp bắt đầu từ nút gốc và phát sinh dần xuống lá (Root
– Leaves).
3) Phương pháp phân tích Bottom – Up
Về mặt trực giác có thể coi phƣơng pháp phân tích Bottom – Up là xây dựng
cây phân tích cú pháp từ dƣới lên trên hay hay có thể xem nhƣ một nỗ lực xây dựng
cây phân tích cú pháp bắt đầu từ các nút lá và thu gọn dần về gốc (Leaves – root).
3.2. Biến Ðổi văn phạm phi ngữ cảnh
Nhiều ngôn ngữ lập trình có cấu trúc đệ quy mà nó có thể đƣợc định nghĩa
bằng các văn phạm phi ngữ cảnh (context-free grammar) G với 4 thành phần
G = (N, T, P, S), trong đó:
- N : là tập hữu hạn các ký hiệu chƣa kết thúc hay các biến (variables)
- T : là tập hữu hạn các ký hiệu kết thúc (terminals) với N T = .
- P : là tập luật sinh của văn phạm (productions) có dạng:
A với A N và V* = (NT)*
- S N: là ký hiệu bắt đầu của văn phạm (start symbol).
Ví dụ: Văn phạm với các luật sinh sau cho phép định nghĩa các biểu thức số học
đơn giản (với E là một biểu thức - expression) :
E → EAE | (E) | - E | id ;
A → + | - | * | / | ↑ .
3.2.1. Cây phân tích cú pháp (Parsing tree) và dẫn xuất
Ta nói rằng αAβ dẫn xuất ra αγβ (ký hiệu: αAβ αγβ) nếu A → γ là một
luật sinh, α và β là các chuỗi tùy ý các ký hiệu văn phạm.
Nếu α α ... α ta nói α dẫn xuất ra (suy ra) α
1
2
n
1
n
Ký hiệu : dẫn xuất ra qua 1 bƣớc
79
Chƣơng 3. Phân tích cúa pháp
*
: dẫn xuất ra qua 0, 1 hoặc nhiều bƣớc.
+ : dẫn xuất ra qua 1 hoặc nhiều bƣớc.
i : dẫn xuất ra qua i bƣớc.
Ta có tính chất:
*
1. α α với α
*
*
*
2. α β và β γ thì α γ
+
Cho một văn phạm G với ký hiệu bắt đầu S. Ta dùng quan hệ để định
nghĩa L(G) một ngôn ngữ đƣợc sinh ra bởi G. Xâu các ký hiệu kết thúc w thuộc
+
L(G) nếu và chỉ nếu S w và xâu w đƣợc gọi là một câu của G. Một ngôn ngữ
đƣợc sinh ra bởi một văn phạm phi ngữ cảnh gọi là ngôn ngữ phi ngữ cảnh. Nếu hai
văn phạm cùng sinh ra cùng một ngôn ngữ thì chúng đƣợc gọi là hai văn phạm
tƣơng đƣơng.
*
Nếu S α, trong đó α có thể chứa một ký hiệu chƣa kết thúc thì ta nói rằng
α là một dạng câu (sentential form) của G. Một câu là một dạng câu chứa toàn các
ký hiệu kết thúc.
Cây phân tích cú pháp là hình ảnh minh họa cho ký hiệu bắt đầu của một văn
phạm dẫn đến một xâu trong ngôn ngữ.
Nếu ký hiệu chƣa kết thúc A có luật sinh A XYZ thì cây phân tích cú
pháp có thể có một nút trong có nhãn A và có 3 nút con có nhãn tƣơng ứng từ trái
qua phải là X, Y, Z.
A
X
Z
Y
Hình 3.2. Minh họa một cây phân tích cú pháp
Một cách hình thức, cho một văn phạm phi ngữ cảnh thì cây phân tích cú pháp
là một cây có các tính chất sau đây:
1. Nút gốc có nhãn là ký hiệu bắt đầu.
80
Chƣơng 3. Phân tích cúa pháp
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
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 α ta xây dựng một cây phân tích cú pháp. Ví dụ với dẫn xuất:
i
81
Chƣơng 3. Phân tích cúa pháp
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
+
+
id
E
(
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.
82
Chƣơng 3. Phân tích cúa pháp
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
E
+
E
E
*
E
E
id
*
E
+
id
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 :
<sttm> IF <expr> THEN <sttm>
<sttm> IF <expr> THEN <sttm> ELSE <sttm>
<sttm> Other
Các luật sinh trên định nghĩa câu lện IF, ở đây <sttm> ứng với biến chỉ câu
lệnh; <epxr> - biến chỉ biểu thức; other chỉ câu lệnh khác.
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
83
Chƣơng 3. Phân tích cúa pháp
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
sttm
S2
else
expr
E2
E1
if
then
sttm
S1
a)
sttm
if
expr then sttm
else
sttm
S2
expr
E2
E1
if
then
sttm
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:
<sttm> <sttm1> <sttm2>
<sttm1> IF <expr> THEN <sttm1> ELSE <sttm1> other
<sttm2> IF <expr> THEN <sttm>
<sttm2> IF <expr> THEN <sttm1> ELSE <sttm2>
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
84
Chƣơng 3. Phân tích cúa pháp
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α ;
- Gián tiếp: A i 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.
85
Chƣơng 3. Phân tích cúa pháp
Á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
86
Chƣơng 3. Phân tích cúa pháp
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:
87
Chƣơng 3. Phân tích cúa pháp
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.
88
Chƣơng 3. Phân tích cúa pháp
1) Ý tưởng
Ý tƣởng cơ bản của kỹ thuật này là viết lại các A – luật sinh của văn phạm
nhằm “hoãn” lại việc quyết định cho đến khi đủ thông tin cho một lựa chọn đúng
với quá trình phân tích.
Ví dụ 3.6:
Xét văn phạm có các luật sinh sau cho câu lệnh IF:
<sttm> IF <expr> THEN <sttm> ELSE <sttm>
<sttm> IF <expr> THEN <sttm>
Khi nhận ra từ IF thì không biết sử dụng luật sinh nào trong hai luật sinh
trên.
Một cách tổng quát, khi có các A - luật sinh dạng:
A 1;
A 2
Ta đƣa thêm vào biến A‟ và thay các A - luật sinh trên về dạng:
A A‟;
A‟ 1 ;
A‟ 2
Quá trình thêm biến và thay thế các A - luật sinh nhƣ trên gọi là quá trình
thừa số hoá bên trái. Quá trình thừa số hoá bên trái cho phép ta nhận đƣợc văn phạm
mới tƣơng đƣơng với văn phạm đã cho. Rõ ràng nhờ quá trình thừa số hoá giúp cho
ta nhận biết luật sinh cần sử dụng chính xác và nhanh chóng hơn.
2) Giải thuật thừa số hoá bên trái
Input: Văn phạm G
Output: Văn phạm tƣơng đƣơng đã thừa số hoá bên trái
Process:
Bƣớc 1: Với mỗi biến A thực hiện
- Tìm tiền tố chung dài nhất cho tất cả các vế phải của các luật sinh có
vế trái là A;
- Nếu tìm thấy A 1| 2 | … | n | ; trong đó: là các vế phải
không có tiền tố chung với các vế phải khác thì
89
Chƣơng 3. Phân tích cúa pháp
+ Bổ sung vào một biến mới A‟;
+ Thay tập luật sinh tìm đƣợc bằng A A‟|
và A‟ 1| 2| …| n .
Bƣớc 2: Với mỗi biến A‟ mới bổ sung thực hiện bƣớc 1 cho đến khi không
còn một biến có hai luật sinh có chung một tiền tố
Ví dụ 3.7:
a) Xét văn phạm với các luật sinh sau:
<sttm> IF <expr> THEN <sttm>
<sttm> IF <expr> THEN <sttm> ELSE <sttm>
<sttm> <sttm 1>.
Nếu ký hiệu = IF <expr> THEN <sttm> khi đó ta có:
<sttm> | ELSE <sttm>
<sttm> <sttm 1>
Sau khi thừa số hoá bên trái ta có:
<sttm> A1
A1 ELSE <sttm> |
<sttm> <sttm 1>
b) Cho văn phạm với các luật sinh:
S aaaAcBd | aaaAcDE | aaaFe | bbS| cD;
A bbCd | bbb;
B bbD;
C abc;
D aba;
E dbaa;
F e | .
Áp dụng giải thuật trên:
1. -Với biến S, ta thay S aaaAcBd | aaaAcDE | aaaFe | bbS| cD bằng
S aaaS1 | bbS| cD;
S1 AcBd | AcDE | Fe
90
Chƣơng 3. Phân tích cúa pháp
- Với biến A, ta thay A bbCd | bbb bằng A bbA1 và A1 Cd | b
- Với các biến B, C, D, E, F: không có tiền tố chung
2. - Với biến S1, ta thay S1 AcBd | AcDE | Fe bằng
S1 AcS2 | Fe;
S2 Bd | DE .
- Với biến A1: không có tiền tố chung
3. Với biến S2: Không có tiền tố chung
Kết quả ta thu đƣợc văn phạm tƣơng đƣơng với tập các luật sinh:
S aaaS1 | bbS| cD;
S1 AcS2 | Fe;
S2 Bd | DE;
A bbA1 ;
A1 Cd | b;
B bbD;
C abc;
D aba;
E dbaa;
F e | .
c) Cho văn phạm với các luật sinh:
S aaaAcBd | aaaAcde | bbbBe | bbS| cC;
A aba;
B bba;
C abc.
Áp dụng giải thuật trên:
1. Với biến S, thay S aaaAcBd | aaaAcde | bbbBe | bbSdd| cD bằng
S aaaAcS‟| bbS‟‟| cC;
S‟ Bd| de;
S‟‟ Be| Sdd.
Kết quả ta thu đƣợc văn phạm tƣơng đƣơng với tập các luật sinh:
91
Chƣơng 3. Phân tích cúa pháp
S aaaAcS‟| bbS‟‟| cC;
S‟ Bd| de;
S‟‟ Be| Sdd.
A aba;
B bba;
C abc.
Ta có thể viết lại giải thuật trên nhƣ sau:
Với mỗi biến A thực hiện
Bƣớc 1:
- Tìm tiền tố chung dài nhất cho tất cả các vế phải của các luật sinh có
vế trái là A;
- Nếu tìm thấy A 1| 2 | … | n | ; trong đó: là các vế phải
không có tiền tố chung với các vế phải khác thì
+ Bổ sung vào một biến mới A‟;
+ Thay tập luật sinh tìm đƣợc bằng A A‟|
và A‟ 1| 2| …| n
Bƣớc 2: Với mỗi biến A‟ mới bổ sung thực hiện bƣớc 1 cho đến khi không
còn một biến có hai luật sinh có chung một tiền tố .
Khi đó thừa số hoá bên trái cho văn phạm trong ví dụ 3.7b có thể trình bày lại
nhƣ sau:
Áp dụng giải thuật trên:
-Với biến S, ta thay S aaaAcBd | aaaAcDE | aaaFe | bbS| cD bằng
S aaaS1 | bbS| cD;
S1 AcBd | AcDE | Fe
- Với biến S1, ta thay S1 AcBd | AcDE | Fe bằng
S1 AcS2 | Fe;
S2 Bd | DE
- Với biến S2: không có tiền tố chung
- Với biến A, ta thay A bbCd | bbb bằng A bbA1 và A1 Cd | b
- Với biến A1: không có tiền tố chung
92
Chƣơng 3. Phân tích cúa pháp
- Với các biến B, C, D, E, F: không có tiền tố chung.
Kết quả ta thu đƣợc văn phạm tƣơng đƣơng với tập các luật sinh:
S aaaS1 | bbS| cD;
S1 AcS2 | Fe;
S2 Bd | DE;
A bbA1 ;
A1 Cd | b;
B bbD;
C abc;
D aba;
E dbaa;
F e | .
3.3. Phân tích cú pháp từ trên xuống
Kỹ thuật phân tích cú pháp từ trên xuống dựa vào ý tƣởng cơ bản là cố gắng
tìm một dẫn xuất trái nhất cho xâu vào, xuất phát từ ký tự bắt đầu của văn phạm.
Hay nói một cách khác là xây dựng một cây phân tích cho xâu vào, bắt đầu từ nút
gốc phát sinh dần xuống nút lá. Kỹ thuật phân tích cú pháp từ trên xuống đƣợc chia
thành hai loại:
- Phân tích cú pháp từ trên xuống có quay lui - gọi là phân tích cú pháp đệ
quy xuống.
- Phân tích cú pháp từ trên xuống theo nguyên tắc dự đoán (Preditive parse)
3.3.1. Phân tích cú pháp đệ quy xuống
1) Ý tưởng
Ý tƣởng của kỹ thuật này đƣợc minh hoạ qua ví dụ cụ thể sau:
Cho văn phạm với các luật sinh:
1. S cAd.
2. A ab.
3. A a.
93
Chƣơng 3. Phân tích cúa pháp
Cần xây dựng cây phân tích cú pháp cho từ w = cad.
S
S
S
c
d
c
d
d
c
A
A
a)
A
a
b
a
b)
c)
Hình 3.7 a, b, c. Mô tả quá trình phân tích xâu w = cad
Bắt đầu với gốc có nhãn S, con trỏ trỏ vào ký tự đầu tiên của xâu w là c; áp
dụng luật sinh 1 ta đƣợc cây ở hình a). Đối chiếu với lá của cây trong hình a) từ bên
trái ta thấy nhãn của nút lá trái nhất là c trùng với ký tự mà con trỏ đang trỏ trên xâu
vào; Vì vậy, con trỏ trỏ đến ký tự thứ 2 là a. Xét nút lá thứ 2 cây a), nút có nhãn A,
sử dụng luật sinh thứ 2 ta đƣợc cây b). So sánh nhãn nút lá cực trái của cây con này
với ký tự mà con trỏ trỏ trên xâu w; chúng giống nhau, đó là ký tự a. Con trỏ trên
xâu w trỏ sang ký tự d. So sánh nhãn của nút lá tiếp theo của cây con gốc A với ký
tự mà con trỏ đang trỏ trên xâu w; ta thấy chúng khác nhau. Việc sử dụng luật
sinh 2 coi nhƣ thất bại; ta cần phải quay lui lại nút gốc có nhãn A và con trỏ trên
xâu w cũng lui lại ký tự thứ 2 là a. Bây giờ, ta lại thử sử dụng luật sinh 3; kết quả ta
có cây dẫn xuất hình 3.7c. So sánh nhãn của nút lá trong cây gốc A với ký tự con trỏ
đang trỏ, chúng trùng nhau. Khi đó con trỏ trên w dịch đến ký tự thứ 3 và việc so
sánh lại đƣợc tiến hành với nút lá có nhãn d. Kết quả ta xây dựng xong cây phân
tích cho w; giải thuật kết thúc.
2) Giải thuật phân tích cú pháp đệ quy xuống
Trƣớc tiên, để đảm bảo có thể phân tích cú pháp đệ quy xuống; ta cần thực
hiện các bƣớc chuẩn bị sau:
- Loại bỏ đệ quy trái;
- thực hiện thừa số hoá bên trái
Input: Văn phạm đã loại bỏ đệ quy trái, thừa số hoá bên trái, Xâu vào
Output: Cây phân tích cú pháp
Process:
94
Chƣơng 3. Phân tích cúa pháp
Bƣớc 1: - Sử dụng một con trỏ trỏ đến xâu vào. Ký hiệu trên xâu vào đang đƣợc
con trỏ chỉ đến gọi là ký hiệu vào hiện tại. Ví trí đầu tiên của con trỏ là ký hiệu bên
trái nhất của xâu vào.
- Khởi tạo cây với nút gốc là ký tự khởi đầu S của văn phạm; nút đang
xét là S.
Bƣớc 2: Nếu nút đang xét là:
- Ký hiệu không kết thúc A thì tìm luật sinh đầu tiên có vế trái là A. Giả sử là
A X1X2…Xk thì bổ sung vào cây các nút X1, X2, …, Xk làm con của A và lấy X1
làm nút đang xét. Trƣờng hợp k = 0 tức là A thì bổ sung nút có nhãn là làm
con của A và lấy nút ngay bên phải A làm nút đang xét.
- Ký hiệu kết thúc a thì so sánh a với ký hiệu vào hiện tại
+ Nếu trùng nhau thì lấy nút bên phải a làm nút đang xét và dịch chuyển con
trỏ trên xâu vào sang ký tự tiếp theo.
+ Nếu khác nhau thì quay lại nút do luật sinh ngay trƣớc đó tạo ra; điều
chỉnh lại con trỏ trên xâu vào và lựa chọn luật sinh tiếp theo. Nếu không còn lựa
chọn nào nữa thì quay lui.
Bƣớc 3: Nếu đã duyệt hết xâu vào và cây không còn nút nào chƣa xét thì ta thu
đƣợc cây phân tích cú pháp. Ngƣợc lại, nếu đã quay lui lại tất cả các trƣờng hợp mà
không thu đƣợc cây phân tích cú pháp thì thông báo lỗi.
Chú ý:
Phƣơng pháp này thƣờng rất ít gặp. Lý do là với kết cấu các ngôn ngữ lập
trình hiếm khi dùng đến nó.
Ví dụ 3.8:
Cho văn phạm với các luật sinh:
S cAd bbABd;
A ab a b;
B bac bad.
Hãy phân tích cú pháp cho các xâu:
a) w = bbabacd.
b) w = bbbbad.
95
Tải về để xem bản đầy đủ
143 trang
22220
Free
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Chương trình dịch (Phần 2)", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- bai_giang_chuong_trinh_dich_phan_2.pdf
