ĐẶ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 TPHCM

2

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 TPHCM

3

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 TPHCM

5

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

L

1

∪ L

2

–

Kết nối

L

1

L

2

 

–

Đóng bao

L

i

z

L

0

= {

∈}

z

L

2

= LL

z

L

i

= LL

i-1

L* = 

∪

L

i

i = 

∞

i = 0

Từ vựng - Cú Pháp

Khoa CNTT-ĐHBK TPHCM

6

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 TPHCM

7

ĐỊNH NGHĨA CHÍNH QUI

z

Định nghĩa chính qui

d

1

Æ

r

1

d

2

Æ

r

2

…
d

n

Æ

r

n

Từ vựng - Cú Pháp

Khoa CNTT-ĐHBK TPHCM

8

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 TPHCM

10

ĐẶ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 TPHCM

11

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 TPHCM

12

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 TPHCM

13

SƠ ĐỒ CÚ PHÁP

Term

Exp

Term

Exp

-

Từ vựng - Cú Pháp

Khoa CNTT-ĐHBK TPHCM

14

Ví dụ: Biểu thức

z

Σ = { 0,1,2,3,4,5,6,7,8,9,(,),-,* }

z

N = { <Exp>, <Term>, <Factor>}

z

S = <Exp>

z

ρ = { <Exp> Æ <Term> | <Exp> - <Term>

<Term> Æ <Factor> | <Term> * <Factor> 
<Factor> Æ 0|1|2|3|4|5|6|7|8|9| (<Exp>)

}

Từ vựng - Cú Pháp

Khoa CNTT-ĐHBK TPHCM

15

CHUỖI DẪN XUẤT

<Exp> Æ <Exp> - <Term>

<Exp>

⇒

<Exp> - <Term>

⇒

<Term> - <Term>

⇒

<Term> * <Factor> - <Term>

⇒

<Factor> * <Factor> - <Term>

⇒

3 * <Factor> - <Term>

⇒

3 * 5 - <Term>

⇒

3 * 5 - <Factor>

⇒

3 * 5 - 2 

<Exp> Æ <Term>

<Term>Æ<Term>*<Factor>

<Term> Æ <Factor>

<Factor> Æ 3

<Factor> Æ 5

<Term> Æ <Factor>

<Factor> Æ 2

Từ vựng - Cú Pháp

Khoa CNTT-ĐHBK TPHCM

16

CÂY PHÂN TÍCH CÚ PHÁP

<Exp>

5

2

4

<Factor>

<Factor>

<Term>

*

<Term>

<Factor>

-

<Exp>

<Term>

Từ vựng - Cú Pháp

Khoa CNTT-ĐHBK TPHCM

17

CÂY CÚ PHÁP

5

2

*

-

4