Bài giảng Đặc tả ngôn ngữ lập trình - Từ vựng, cú pháp

ĐẶC TẢ NGÔN NGỮ LẬP TRÌNH
TỪ VỰNG – CÚ PHÁP
TS. Nguyễn Hứa Phùng
Khoa CNTT-ĐHBK TPHCM
2007
Từ vựng - Cú Pháp Khoa CNTT-ĐHBK TPHCM2
GIỚI THIỆU
z Đặc tả hình thức cung cấp một mô tả chính 
xác về một ngôn ngữ lập trình(nnlt)
Chương 
trình
Bộ dịch
Đặc tả
NNLT
Từ vựng - Cú Pháp Khoa CNTT-ĐHBK TPHCM3
GIỚI THIỆU (tt)
z Đặc tả hình thức cho phép:
– Người học có thể tiếp thu nnlt dễ dàng
– Bộ dịch có thể sinh mã đúng đắn
– Bộ dịch có thể kiểm tra lỗi tự động
– Có thể chứng minh được tính đúng đắn của chương trình
z Đặc tả hình thức:
– Từ vựng
– Văn phạm
– Ngữ nghĩa
ĐẶC TẢ TỪ VỰNG
Từ vựng - Cú Pháp Khoa CNTT-ĐHBK TPHCM5
NGÔN NGỮ
z Chuỗi và ngôn ngữ
– Tập hợp các ký tự Σ
– Một chuỗi S trên Σ là 1 dãy hữu hạn các ký tự thuộc Σ
– Chuỗi rỗng ∈
– Một ngôn ngữ L trên Σ là tập hợp các chuỗi trên Σ
z Tác vụ trên ngôn ngữ
– Hợp L1 ∪ L2
– Kết nối L1 L2 
– Đóng bao Li
z L0 = {∈}
z L2 = LL
z Li = LLi-1
L* = ∪ Lii = ∞
i = 0
Từ vựng - Cú Pháp Khoa CNTT-ĐHBK TPHCM6
BIỂU THỨC CHÍNH QUI
z Biểu thức chính qui r diễn tả ngôn ngữ L(r)
– ∈ ⇒ {∈}
– a ∈ Σ ⇒ {a}
– Giả sử r và s lần lượt diễn tả ngôn ngữ L(r) và
L(s) thì
z (r) | (s) ⇒ L(r) ∪ L(s)
z (r)(s) ⇒ L(r) L(s)
z (r)* ⇒ (L(r))*
z (r) ⇒ L(r)
Từ vựng - Cú Pháp Khoa CNTT-ĐHBK TPHCM7
ĐỊNH NGHĨA CHÍNH QUI
z Định nghĩa chính qui
d1Æ r1
d2Æ r2
…
dnÆ rn
Từ vựng - Cú Pháp Khoa CNTT-ĐHBK TPHCM8
TOÁN TỬ CHÍNH QUI
z Độ ưu tiên
– *
– concat
– |
z Một số toán tử mở rộng
(a)? == a | ∈
(a)+ == a(a)*
ĐẶC TẢ VĂN PHẠM
Từ vựng - Cú Pháp Khoa CNTT-ĐHBK TPHCM10
ĐẶC TẢ VĂN PHẠM
z Cú pháp trừu tượng (abstract syntax)
z Cú pháp cụ thể (concrete syntax)
– Văn phạm phi ngữ cảnh (context-free grammar) 
và BNF (Backus-Naur Form)
– Sơ đồ cú pháp
z Cú pháp cảm ngữ cảnh (context-sensitive 
syntax)
Từ vựng - Cú Pháp Khoa CNTT-ĐHBK TPHCM11
CÚ PHÁP TRỪU TƯỢNG
z Phân các yếu tố NN thành các lớp văn phạm
z Liệt kê tất cả các dạng của mỗi lớp
z Ví dụ:
– Lớp cú pháp:
C Hằng (constant)
O Toán tử (operator)
E Biểu thức (expression)
– Dạng cú pháp:
E ::= C | E O E | ( E )
8 – 4 – 2 
E O E
8 – 4 – 2 
E O E
Từ vựng - Cú Pháp Khoa CNTT-ĐHBK TPHCM12
VĂN PHẠM PHI NGỮ CẢNH 
z Noam Chomsky, 1957
z Là 1 bộ gồm 4 thành phần:
– Tập các ký hiệu kết thúc Σ
– Tập các ký hiệu không kết thúc N
– Ký hiệu bắt đầu S ∈ N
– Tập các luật sinh ρ có dạng
A Æ ω với A ∈ N và ω là 1 chuỗi các ký hiệu kết thúc và
không kết thúc
Từ vựng - Cú Pháp Khoa CNTT-ĐHBK TPHCM13
SƠ ĐỒ CÚ PHÁP
Term
Exp Term
Exp
-
Từ vựng - Cú Pháp Khoa CNTT-ĐHBK TPHCM14
Ví dụ: Biểu thức
z Σ = { 0,1,2,3,4,5,6,7,8,9,(,),-,* }
z N = { , , }
z S = 
z ρ = { Æ | - 
 Æ | * 
 Æ 0|1|2|3|4|5|6|7|8|9| ()
}
Từ vựng - Cú Pháp Khoa CNTT-ĐHBK TPHCM15
CHUỖI DẪN XUẤT
 Æ - 
⇒ - 
⇒ - 
⇒ * - 
⇒ * - 
⇒ 3 * - 
⇒ 3 * 5 - 
⇒ 3 * 5 - 
⇒ 3 * 5 - 2 
 Æ 
Æ*
 Æ 
 Æ 3
 Æ 5
 Æ 
 Æ 2
Từ vựng - Cú Pháp Khoa CNTT-ĐHBK TPHCM16
CÂY PHÂN TÍCH CÚ PHÁP
5 2 4
*
-
Từ vựng - Cú Pháp Khoa CNTT-ĐHBK TPHCM17
CÂY CÚ PHÁP
5 2
*
-
4