Nguyễn Phương Thái
Bộ môn Khoa học Máy tính
/>
Cú pháp
•
Là khuôn dạng hay cấu trúc của chương trình
•
Không liên quan đến ý nghĩa chương trình
•
Được mô tả bằng văn phạm phi ngữ cảnh

Tại sao chúng ta sử dụng văn phạm phi ngữ cảnh
(VPPNC) cho phân tích cú pháp
•
Cho phép mô tả rõ ràng và dễ hiểu cú pháp một
ngôn ngữ lập trình
•
Dễ sửa đổi và mở rộng ngôn ngữ lập trình
•
Dễ tạo ra các bộ parser
•
Cho phép dịch dựa vào cú pháp
22/10/14
2
Nguyễn Phương Thái - Coltech - Compiler 2009

Văn phạm

Phân loại văn phạm của Chomsky

Cây phân tích, dẫn xuất, và văn phạm nhập nhằng

Ví dụ phân tích
văn phạm
22/10/14
6
Nguyễn Phương Thái - Coltech -
Compiler 2009
Định nghĩa
Một văn phạm là một hệ thống G = (
Σ
,
∆
, P, S) trong
đó:

Σ
là tập hữu hạn các ký hiệu, gọi là ký hiệu kết thúc
(terminal)

∆
là tập hữu hạn các ký hiệu, gọi là ký hiệu không kết
thúc (nonterminal)

S
∈∆
gọi là ký hiệu khởi đầu

P là tập hữu hạn các cặp xâu (
α
,
β

Nguyễn Phương Thái - Coltech - Compiler 2009
Các qui ước:

Dùng các chữ in hoa A, B, C, D, E hoặc cụm từ trong cặp ngoặc
nhọn (như <chủ ngữ>) để trỏ các ký hiệu không kết thúc;

Dùng các chữ thường a, b, c, d, e và các con số, các phép toán +,
-, *, /, cặp ngoặc đơn để trỏ các ký hiệu kết thúc. Trong một số
trường hợp dùng qui ước là một từ được in đậm (như số và chữ)
hoặc cụm từ trong cặp ngoặc kép (như "bò");

Dùng các chữ in hoa X, Y, Z để trỏ các ký hiệu có thể là kết thúc
hoặc không kết thúc;

Dùng các chữ thường u, v, w, x, y, z để trỏ các xâu ký hiệu cuối;

Dùng các chữ thường Hy lạp
α
,
β
,
χ
để trỏ các xâu gồm các biến
và ký hiệu cuối;

Nếu có các sản xuất cùng vế trái A
→

α
và A

| | là ký hiệu độ dài xâu (ví dụ |
α
| là độ dài của xâu
α
);

Ký hiệu
ε
là một kí hiệu đặc biệt, chỉ xâu rỗng hoặc
kí hiệu rỗng
22/10/14
10
Nguyễn Phương Thái - Coltech - Compiler 2009

Định nghĩa suy dẫn (derivation): Cho văn phạm G = (
Σ
,
∆
, P,
S) như trên, ta gọi suy dẫn trực tiếp là một quan hệ hai ngôi ký
hiệu
⇒
trên tập V* nếu
αβγ
là một xâu thuộc V* và
β→δ
là
một sản xuất trong P, thì
αβγ


phân tích (đoán nhận) về S:

L(G) = { w | w
∈

Σ
* và S
⇒
* w }
hoặc:

L(G) = { w | w
∈

Σ
* và w
⇒
* S }
22/10/14
12
Nguyễn Phương Thái - Coltech - Compiler 2009

Định nghĩa: Hai văn phạm G
1
và G
2
(sản sinh hoặc đoán nhận)
là tương đương khi và chỉ khi L(G
1
) = L(G

thỏa mãn điều kiện |
α
|
≤
|
β
|
22/10/14
16
Nguyễn Phương Thái - Coltech - Compiler 2009

Lớp 2, văn phạm phi ngữ cảnh (context free - viết tắt là
VPPNC) nếu sản xuất có dạng:
A → α trong đó A ∈ ∆, α ∈V*
22/10/14
17
Nguyễn Phương Thái - Coltech - Compiler 2009

Lớp 3, văn phạm chính quy (regular - viết tắt là VPCQ) nếu
sản xuất có dạng:
A
→
a, A
→
Ba trong đó A, B
∈

∆
, a
∈

định);

Ngôn ngữ loại 3 (chính qui - viết tắt là NNCQ) được
đoán nhận bởi một ôtômát hữu hạn (sai khác xâu
rỗng).
22/10/14
20
Nguyễn Phương Thái - Coltech - Compiler 2009
Dạng BNF (Backus - Naur Form): thực chất chỉ là một cách biểu
diễn khác của VPPNC. Quy ước:

Các ký tự viết hoa biểu diễn các ký hiệu không kết thúc
(nonterninal), cũng có thể thay bằng một xâu đặt trong cặp
dấu < > hoặc một từ in nghiêng;

Các ký tự viết chữ nhỏ và dấu toán học biểu diễn các ký hiệu
kết thúc (terninal), cũng có thể thay bằng một xâu đặt trong
cặp dấu nháy kép " " hoặc một từ in đậm;

Ký hiệu
→
hoặc = là ký hiệu chỉ phạm trù cú pháp ở vế trái
được giải thích bởi vế phải;

Ký hiệu | chỉ sự lựa chọn.
22/10/14
21
Nguyễn Phương Thái - Coltech - Compiler 2009
Định nghĩa toán hạng: có thể là một biến (tên), số hoặc một biểu
thức ở trong cặp dấu ngoặc đơn

Nhãn của gốc là S

Nếu một nút có nhãn X là một nút trong thì X
∈

∆

Nếu nút n có nhãn là X và các nút n
1
, n
2
, , n
k
là các
con của nút n, theo thứ tự từ trái sang phải, và lần
lượt mang các nhãn X
1
,X
2
, X
k
thì X
→
X
1
X
2
…X
k
phải

Hai thứ tự dẫn xuất thường dùng:
•
Suy dẫn trái: chọn kí hiệu bên trái nhất
•
Suy dẫn phải: chọn kí hiệu bên phải nhất

Ví dụ: Dẫn xuất trái nhất và dẫn xuất phải nhất của cây
cú pháp trên
22/10/14
25
Nguyễn Phương Thái - Coltech - Compiler 2009