1
Bài giảng 4 - Phân tích cú pháp
và các phương pháp phân tích cơ
bản
Nguyễn Phương Thái
Bộ môn Khoa học Máy tính
2
Bài toán

Đầu vào: câu vào chứa toàn các từ tố

Phân tách câu vào thành các phần theo
văn phạm và biểu diễn cấu trúc này
bằng một cây (gọi là cây phân tích)
hoặc theo một cấu trúc nào đó tương
đương với cây.
3
Bi toỏn (tip)
Phỏn tờch
tổỡ vổỷng
Phỏn tờch
cuù phaùp
cỏy
phỏn
tờch
Phỏn tờch
ngổợ
nghộa
Baớng kyù
hióỷu
yóu cỏửu

Thuật toán phân tích CYK (Coke-Younger-
Kasami).

Thuật toán phân tích Earley.
6
Các phương pháp phân tích
(tiếp)

Việc phân tích một câu là khôi phục
hoặc xây dựng suy dẫn sinh ra nó, do
đó ta sẽ dựng được cây suy dẫn.

Thông thường trong các thuật toán
phân tích, ta hay tiến hành từ một phía
của câu, kiểm tra lần lượt các thành
phần của câu đó cho đến hết (đa số từ
trái sang phải).
7
Hai chiến lược phân tích chính

Chiến lược phân tích top-down (trên xuống): cho một
văn phạm phi ngữ cảnh G = (Σ, ∆, P, S) và một câu
cần phân tích w. Ta xuất phát từ điểm khởi đầu,
nghĩa là từ S, áp dụng các suy dẫn trái, tiến từ trái
qua phải thử tạo ra câu đưa vào phân tích w.

Chiến lược phân tích bottom-up (dưới lên): Quá trình
ngược lại với phân tích top-down, xuất phát từ chính
câu vào phân tích w, bằng cách áp dụng thu gọn các
suy dẫn phải, tiến hành từ trái qua phải để đi tới ký

Giải quyết: có hai chiến lược:
1. Phân tích quay lui (backtrack): ta thử lần lượt các α
i

(1 ≤
i
≤
k
) để tìm α
i
thích hợp. Rất tốn thời gian.
2. Phân tích không quay lui (without-backtrack). Trong
việc tìm sản xuất thích hợp, ta biết cách xác định sản
xuất duy nhất thích hợp mà không cần phải thử các
sản xuất khác. Các phương pháp phân tích như vậy
gọi là phân tích tất định (deterministic parsing).
10
Phân tích Top-Down
Chuẩn bị:

Với một VPPNC cho trước, đánh dấu mọi lựa
chọn trong từng sản xuất. Ví dụ: nếu các sản
xuất dạng S→aSbS | aS | c thì aSbS là lựa
chọn thứ nhất, aS là lựa chọn thứ hai và c là
lựa chọn cuối của sản xuất S.

Dùng một con trỏ chỉ đến xâu vào. Ký hiệu
trên xâu vào do 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.

aSbS | aS | c

w =aacbc
13
Ví dụ

VPPNC
G=(Σ, ∆, P, S)

P:

S
→
aSbS | aS | c

w =aacbc
14
15
Phân tích Bottom-Up

Ngược lại với phương pháp top-down:
bắt đầu từ lá cố gắng xây dựng thành
cây bằng cách hướng lên gốc.

Phân tích bottom-up được gọi là phân
tích gạt thu gọn (shift-reduce parsing).
16
Ví dụ

S

phép xét từ tố mỗi giây, tổng thời gian cần để
phân tích mỗi một câu lệnh này là 3tỷ /
1000/60/60 > 80 giờ.

Nếu máy tính có khả năng xử lý gấp 10 lần
(10.000 từ tố mỗi giây) thì cũng cần đến 8 giờ để
xử lý xong câu lệnh đó.
18
Phát hiện lỗi

Nếu một chương trình dịch chỉ phải dịch các
chương trình máy tính viết đúng thì thiết kế
và hoạt động của nó sẽ rất đơn giản.

Một chương trình dịch tốt phải phát hiện,
định vị, phân loại được tất cả các lỗi để giúp
đỡ người viết.

Người thiết kế chương trình dịch phải tự
quyết định bắt và báo lỗi như thế nào
19
Phát hiện lỗi (tiếp)
Giai đoạn phân tích cú pháp phát hiện và khắc
phục được khá nhiều lỗi do:

Nhiều loại lỗi khác nhau đồng thời cũng là lỗi
cú pháp. Ví dụ lỗi do chuỗi từ tố từ bộ phân
tích từ vựng không theo thứ tự của luật văn
phạm của ngôn ngữ lập trình.
