21/1/2010
1
Bài 6
Phân tích cú pháp
tê ốóli
1
t
r
ê
n xu
ố
ng c
ó
quay
l
u
i
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
L(G) đúh i?
2
w
∈
L(G)
đú
ng
h
ay sa
i?
Phân tích trên xuống (top down)
S ⇒* w?
w đúng cú pháp ⇒cây cú pháp
E -> E + T
E -> T
T
>T
*
F
3
T
-
>
T
F
T -> F
F -> ( E )
F -> ident
Biểu diễn cây cú pháp bằng cách nào?
Phân tích trái
Phân tích trái củaαlà dãy các sảnxuất
được
sử
dụng
suy
dẫn
trái
ra
α
từ
S
4
được
sử
dụng
suy
dẫn
trái
ra
α
từ
S
Phân tích là danh sách các sốtừ1đếnp
21/1/2010
2
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
5
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à 23645124646
Giải thuật phân tích top down quay lui
Tưtưởng chủyếucủagiảithuậtlàxây
dựngcâyphântíchcúpháp(câysuydẫn)
cho xâu w
6
Đánh sốthứtựcác sảnxuất có cùng vế
phải, nhưvậy, các A - sảnxuấtcủavăn
phạmsẽđượcxếpthứtự
A→α1|α2|....|αn
Mô tả giải thuật
Bắtđầutừnút gốcS
Nút S được coi là nút hoạtđộng
7
Tạo ra các nút con mộtcáchđệ quy
Nút hoạt động là ký hiệu
không kết thúc A
ChọnvếphảiđầutiêncủaA-sảnxuất:X
1X2....X
k.
Tạo k nút con trựctiếpcủaAvới nhãn X1,X
2,....X
k.
Nút
hoạt
động
là
nút
nhãn
X
1
8
Nút
hoạt
động
là
nút
nhãn
X
1
.
Nếuk=0,(sảnxuấtA→ε) thì nút hoạtđộng sẽlà nút
bên phải (ngay sau) A khi duyệt cây theo thứtựtrái
21/1/2010
3
Nút được xét có nhãn là ký hiệu
kết thúc a
So sánh vớikýhiệuđang xét.
Nếu trùng vớikýhiệuđang xét thì chuyểnđầu
đọc sang phải 1 ô, chuyển sang xét nút bên phải.
Nếu
a
không
trùng
với
ký
hiệu
đang
xét
thì
quay
9
Nếu
a
không
trùng
với
ký
hiệu
đang
xét
thì
quay
lui tới nút mà tạiđóđãsửdụng sảnxuấttrước
(Thay thếmộtkýhiệu không kết thúc (chẳng hạn
A) bằng vếphảimộtsảnxuất).
Chuyểnđầuđọc sang trái (nếucần) và thửvớilựa
chọntiếp theo. Nếu không còn lựachọn nào khác
thì quay lui tớibướctrướcđó
NếuđãquayluitớiSvàkhôngcònlựachọn
khác:câu sai cú pháp
Điều kiện để thực hiện giải thuật
Văn
phạm
G
cần
thoả
điều
kiện
1 0
Văn
phạm
G
cần
thoả
điều
kiện
không đệ quy trái để tránh rơivào
chu trình
Ví dụ
Cho văn phạm
S
→
aSb | c
Các sảnxuấtsẽđượcđánh sốtừ1đến2
1 1
Các
sản
xuất
sẽ
được
đánh
số
từ
1
đến
2
.
Xét xâu vào aacbb
Dựng cây phân tích cú pháp
1 2
21/1/2010
4
Thử lựa chọn khác
1 3
Giải thuật phân tích cú pháp quay lui
Vào
Văn phạm G phi ngữ cảnh không đệ quy trái,
xâu w = a1. . . .an, n ≥0
Các sản xuất của G được đánh số 1,. . . . q
Ra
Mộthâtíhtáih (ếó)
1 4
Một
p
hâ
n
tí
c
h
t
r
ái
c
h
o w
(
n
ế
u c
ó)
Thông báo lỗi nếu ngược lại
Phương pháp
(Xây dựng 2 stack D1và D2.
D
2
biểu diễn d
ạ
n
g
câu trái hi
ệ
n t
ạ
i có đư
ợ
c bằn
g
1 5
ạgệ ạ ợ g
cách thay thế các ký hiệu không kết thúc bởi vế
phải tương ứng
D1 ghi lại lịch sử những lựa chọn đã sử dụng và
những ký hiệu vào trên đó đầu đọc đã đổi vị trí
(1)
∀A ∈N , giả sử có các A-sản xuất
A →α1 | α2| . . . .| αn
Coi các sảnxuấttrênlà
1 6
Coi
các
sản
xuất
trên
là
A1→α1
. . . .
An→αn
21/1/2010
5
Hình trạng của giải thuật
Bộbốn(s,i,α, β)
s∈Q: Trạng thái hiệnthời
q: Trạng thái bình thường
b
Q
li
1 7
b
:
Q
ua
y
l
u
i
t: Kết thúc
i:Vịtrí đầuđọc(Băng vào có dấuhiệukết thúc #)
α:Nội dung stack thứnhất
β:Nội dung stack thứhai
Thực hiện giải thuật
Bắtđầutừhình trạng đầu, tính liên tiếp
các hình trạng tiếp theo cho đếnkhi
khôn
g
tính đư
ợ
cnữa.
1 8
g
ợ
Nếuhìnhtrạng cuối là (t,n+1,γ,ε), đưa
ra h(γ)vàdừng. Ngượclạiđưa ra thông
báo sai
Ví dụ
Xét xâu vào aacbb và văn phạm G với
các sản xuất
1 9
S →aSb
S →c
Đánh số lại các sản xuất
1. S1→aSb
2
S
→
c
2 0
2
.
S
2
→
c