IT4073:NGÔN NG và Ữ
PH NG PHÁP D CHƯƠ Ị
Ph m Đăng H iạ ả
haipd@soict.hut.edu.vn
05/29/13 2
Ch ng 3: Phân tích cú phápươ
1. Bài toán phân tích cú pháp
2. Ph ng pháp phân tích cú pháp quay luiươ
3. Ph ng pháp phân tích b ngươ ả
4. Ph ng pháp phân tích cú pháp t t đ nhươ ấ ị
5. Phân tích cú pháp cho PL/0
05/29/13 3
Bài toán đ t raặ
Cho
–Văn ph m phi ng c nh Gạ ữ ả
G = (VT, VN, P, S)
–Xâu ω V*T
H i ỏ
– ω∈ L(G)?
N u ếω ∈ L(G)
–Ch ra các s n xu t đã s d ng đ sinh ra ỉ ả ấ ử ụ ể
ω
–C u trúc nên cây suy d nấ ẫ
1. Bài toán phân tích cú pháp
Trong ch ng trình d ch, ươ ị
xâu ω là chu i các token ỗ
thu đ c t giai đo n ượ ừ ạ
tr c – ướ phân tích t v ngừ ự
Program Vidu;
Begin
X := 10
End.
PROGRAM IDENT
SEMICOLON BEGIN IDENT
ASSIGN NUMBER END
PERIOD
05/29/13 4
Ph ng pháp phân tíchươ
•Ki m tra xâu phân tích t trái qua ph iể ừ ả
–Ki m tra ký hi u trái nh t c a xâu c n phân tíchể ệ ấ ủ ầ
–T i ký hi u ti p,.. Cho t i ký hi u cu i cùngớ ệ ế ớ ệ ố
•Ph ng pháp xây d ng cây phân tíchươ ự
–Trên xu ng (ốTop-down): S ⇒* ω?
–D i lên (ướ Bottom-up): ω *⇐ S?
•Ph ng pháp l a ch n s n xu t (ươ ự ọ ả ấ A→α1|…|αn)
–Quay lui (backtracking)
•Th l n l t các s n xu tử ầ ượ ả ấ
–T t đ nh (ấ ị deterministic)
•Xác đ nh đ c duy nh t m t s n xu t thích h pị ượ ấ ộ ả ấ ợ
1. Bài toán phân tích cú pháp
05/29/13 5
Phân tích trái
•Phân tích trái c a xâu ủα là dãy các s n xu t ả ấ
đ c s d ng trong ượ ử ụ suy d n tráiẫ t S ra ừα
•Các s n xu t đ c đánh s th t 1,..pả ấ ượ ố ứ ự
–Phân tích là danh sách các s t 1 đ n pố ừ ế
•Ví d cho văn ph mụ ạ
1. E → T+E
2. E → T
3. T → F* T
4. T → F
5. F → (E)
6. F → a
Phân tích trái c a xâu ủa*(a+a) là 23645146246
1. Bài toán phân tích cú pháp
Xét xâu a*(a+a)
E ⇒
2 T ⇒
3 F*T ⇒
6 a*T
⇒
4 a*F ⇒
5a*(E)
⇒
1 a*(T+E) ⇒
4 a*(F+E)
⇒
6 a*(a+E) ⇒
2 a*(a+T)
⇒
4 a*(a+F) ⇒
6 a*(a+a)