Bài giảng Chương trình dịch - Chương 3: Phân tích cú pháp
CHƯƠNG III
Phân tích cú pháp
Mục tiêu:
Nắm được vai trò của giai đoạn phân tích cú
pháp
- Văn phạm phi ngữ cảnh (contexfree
grammar),cách phân tích cú pháp từ dưới
lêtừ trên xuống (todown and bottomup
parsing)
Bộ phân tích cú pháp LR
1
Vai trò của bộ phân tích cú pháp
• Đây là giai đoạn thứ 2 của quá trình biên dịch
• Nhiệm vụ chính: Nhận chuỗi các token từ bộ
phân tích từ vựng và xác định chuỗi đó có
được sinh ra bởi văn phạm của ngôn ngữ
nguồn không
Token
Source
Lexical
Parser
Rest of
Parse
tree
program
analyzer
front end
Get next
token
Symbol
table
2
• Các phương pháp phân tích cú pháp
(PTCP) chia làm hai loại: Phân tích từ trên
xuống (todown parsing) và phân tích từ
dưới lên (bottomup parsing)
• Trong quá trình biên dịch xuất hiện nhiều
lỗi trong giai đoạn PTCP do đó bộ phân
tích cú pháp phải phát hiện và thông báo
lỗi chính xác cho người lập trình đồng thơi
không làm chậm những chương trình được
viết đúng
3
Văn phạm phi ngữ cảnh
• Để định nghĩa cấu trúc của ngôn ngữ lập
trình ta dùng văn phạm phi ngữ cảnh
(Contexfree grammars) hay gọi tắt là
một văn phạm
• Một văn phạm bao gồm:
- Các kí hiệu kết thúc terminal): Chính là các
token
- Các kí hiệu chưa kết thúc nonterminal): Là
các biến kí hiệu tập các xâu kí tự
- Các luật sinh production): Xác định cách
thức hình thành các xâu từ các kí hiệu kết thúc
và chưa kết thúc
4
Ví dụ 3.1Văn phạm sau định nghĩa các
biểu thức số học đơn giản
E → E A E | (E) | E | id
A → + | * | /
Trong đó E, A là các kí tự chưa kết thúc (E
còn là kí tự bắt đầu), các kí tự còn lại là
các kí tự kết thúc
5
• Dẫn xuất (derivation): Ta nó
nếu A → là một luật sinh đọc là dẫn
xuất hoặc suy ra)
• Nếu .... thì ta nói rằng
dẫn xuấn
• Kí hiệulà dẫn xuấ0 bướclà
dẫn xuấ1 bước
• Cho văn phạm G với kí tự bắt đầu là S,
L(G) là ngôn ngữ được sinh bởi G. Mọi xâu
trong L(G) chỉ chứa các kí hiệu kết thúc
của G
6
• Ta nói một xâu L(G) nếu và chỉ nếu S +
w, w được gọi là một câu (sentence) của văn
phạm G
• Một ngôn ngữ được sinh bởi văn phạm phi
ngữ cảnh được gọi là ngôn ngữ phi ngữ cảnh
(contex- free language)
• Hai văn phạm được gọi là tương đương nếu
sinh ra cùng một ngôn ngữ
• Nếu S * có thể chứa kí hiệu chưa kết
thúc) thí ta nó là một dạng câu (sentence
form) của G. Một câu là một dạng câu không
7
chứa kí hiệu chưa kết thúc
Ví dụ 3.2Xâu (id+id) là một câu của văn
phạm trong ví dụ 3.1 vì
E E (E) (E+E (id+E)
(id+id)
• Một dẫn xuất được gọi là trái nhất
(leftmost) nếu tại mỗi bước kí hiệu chưa
kết thúc ngoài cùng bên trái được thay
thế, kí hiệu l. Nếu S *lm th được
gọi là dạng câu trái
• Tương tự ta có dẫn xuất phải nhất
(rightmost) hay còn gọi là dẫn xuất chính
tắc, kí hiệu rm
8
• Cây phân tích cú pháp (parse tree) là
dạng biểu diễn hình học của dẫn xuất. Ví
dụ parse tree cho biểu thức (id+id) là:
E
E
E
-
)
(
+
E
|
id
E
|
id
9
• Tính mơ hồ của văn phạm (ambiguity):
Một văn phạm sinh ra nhiều hơn một
parse tree cho một câu được gọi là văn
phạm mơ hồ. Nói cách khác một văn
phạm mơ hồ sẽ sinh ra nhiều hơn một dẫn
xuất trái nhất hoặc dẫn xuất phải nhất cho
cùng một câu.
• Loại bỏ sự mơ hồ của văn phạm: Ta xét ví
dụ văn phạm sau
Stmt → if expr then stmt
| if expthen stmelse stmt
| other
10
• Văn phạm trên là mơ hồ vì với cùng một câu
lệnh iE1 then iE2 then S1 else S2" sẽ
có hai parse tree:
11
• Ðể loại bỏ sự mơ hồ này ta đưa ra qui tắc
"Khớp mỗelse với mộthen chưa khớp gần
nhất trước đó". Với qui tắc này, ta viết lại
văn phạm trên như sau :
Stm→ matched_stmt | unmatched_stmt
matched_stm→ if expr then
matched_stmt else
matched_stmt
| other
unmatched_stmt → if expthen Stmt
| if expr then
matched_stmelse
12
unmatched_stmt
• Loại bỏ đệ qui trái: Một văn phạm được
gọi là đệ qui trái (left recursion) nếu tồn
tại một dẫn xuất có dạng A + (A là 1
kí hiệu chưa kết thúc là một xâu).
• Các phương pháp phân tích từ trên xuống
không thể xử lí văn phạm đệ qui trái, do
đó cần phải biến đổi văn phạm để loại bỏ
các đệ qui trái
• Ðệ qui trái có hai loại :
Loại trực tiếp: Có dạng A +
Loại gián tiếp: Gây ra do dẫn xuất của hai
13
hoặc nhiều bước
• Với đệ qui trái trực tiếp: Ta nhóm các luật
sinh thành
A → | |..... | m | 2 |.....|
n
Thay luật sinh trên bởi các luật sinh sau:
A → A' | A|..... A'
A→ A| A|..... | A|
Ví dụ 3.3Thay luật sinh A → | bởi
A → A'
A→ A|
14
• Với đệ qui trái gián tiếp: Ta dùng thuật toán
sau
1Sắp xếp các ký hiệu không kết thúc theo thứ tự
A1, A2, ..., An
for i:=1 to n do
begin
for j:=1 to 1 do
begin
Thay luật sinh dạng A→ A bởi luật sinh
A→ |..... trong đó
A→ |.....| k là tất cả các luật
sinh hiện tại
end;
• Tạo ra nhân tố trái (left factoring) là một
phép biến đổi văn phạm rất có ích để có
được một văn phạm thuận tiện cho việc
phân tích dự đoán
• Ý tưởng cơ bản là khi không rõ luật sinh
nào trong hai luật sinh khả triển có thể
dùng để khai triển một ký hiệu chưa kết
thúc A, chúng ta có thể viết lại các luật
sinh nhằm "hoãn" lại việc quyết định cho
đến khi thấy đủ yếu tố cho một lựa chọn
đúng.
16
Ví dụ 3.3Ta có hai luật sinh
stmt → if expr then stmt else stmt
if expr then stmt
Sau khi đọc token if, ta không thể ngay lập
tức quyết định sẽ dùng luật sinh nào để
mở rộng stmt
• Cách tạo nhân tố trái: Giả sử có luật sinh
A → | |..... | là tiền
tố chung dài nhất của các luật sinh
không bắt đầu bở)
Luật sinh trên được biến đổi thành:
17
A → A
Phân tích cú pháp từ trên xuống
• Phân tích cú pháp (PTCP) từ trên xuống
được xem như một cố gắng tìm kiếm một
dẫn xuất trái nhất cho chuỗi nhập. Nó
cũng có thể xem như một cố gắng 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á
• PTCP từ trên xuống đơn giản hơn PTCP từ
dưới lên nhưng bị giới hạn về mặt hiệu
quả
• Có một số kĩ thuật PTCP từ trên xuống
18
như: PTCP đệ qui lùi, PTCP đoán trước,
• PTCP đoán trước không đệ qui
(nonrecursive predictive parsing) hoạt
động theo mô hình sau:
INPUT
a + b $
Predictive parsing
OUTPUT
X
Y
Z
$
program
STACK
Parsing table
M
19
• INPUT là bộ đệm chứa chuỗi cần phân
tích, kết thúc bởi ký hiệu $
• STACK chứa một chuỗi các ký hiệu văn
phạm với ký hiệu $ nằm ở đáy STACK.
Khởi đầu STACK chứa kí hiệu bắt đầu S
trên đỉnh
• Parsing table M là một mảng hai chiều
dạng M[A,a], trong đó A là ký hiệu chưa
kết thúc, a là ký hiệu kết thúc hoặc $.
• Bộ phân tích cú pháp được điều khiển bởi
Predictive parsing program
20
Tải về để xem bản đầy đủ
60 trang
13/04/2022
4520
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Chương trình dịch - Chương 3: Phân tích cú pháp", để 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_chuong_3_phan_tich_cu_phap.ppt
