Bài 6
Phân tích cú pháp
trên xuống có quay lui
1
Bài toán phân tích cú pháp
Bài toán đặt ra
Cho văn phạm phi ngữ cảnh G và xâu w
w
Î
L(G) đúng hay sai?
Phân tích trên xuống (top down)
S Þ* w?
2
w đúng cú pháp Þcây PT cú pháp
E -> E + T
E -> T
T -> T * F
T -> F
F -> ( E )
F -> ident
3
Biểu diễn cây PT cú pháp bằng cách nào?
Phân tích trái
•Phân tích trái của a là dãy các sản xuất được sử dụng
trong suy dẫn trái ra a từ S
•Phân tích phải của a là nghịch đảo của dãy các sản
xuất được sử dụng trong suy dẫn phải ra a từ S
•Phân tích là danh sách các số từ 1 đến p
4
Ví dụ
Xét văn phạm G, các sản xuất được đánh số như sau
1. E T+E
2. E T
3. T F* T
4. T F
5. F (E)
6. F a
Suy dẫn trái: E ÞT ÞF*T Þa*T Þa* F Þa*(E) Þ
a* (T+ E) Þa * (F + E) Þa* (a + E) Þa* (a+T) Þ
a* (a + F) Þa* (a+a)
•Phân tích trái của xâu a*(a+a) là 23645146246
•Phân tích phải của xâu a*(a+a) là 66464215432
5