Nhắc Lại Một Số Kiến Thức Về Văn Phạm – Ngôn Ngữ - Automat

Mục tiêu:

Chương 2

PHÂN TÍCH TỪ VỰNG

Giúp sinh viên có khả năng:

- Củng cố được một số kiến thức về văn phạm, ngôn ngữ và automat.

- Hiểu được các khái niệm: thẻ từ, mẫu từ vựng, trị từ vựng. Biểu diễn và nhận biết được các thẻ từ.

- Biết được vị trí, nhiệm vụ của giai đoạn phân tích từ vựng.

- Hiểu được kỹ thuật đọc chương trình nguồn.

Có thể bạn quan tâm!

• Chương trình dịch - 1
• Chương trình dịch - 2
• Phân Tích Ngữ Nghĩa (Semantic Analysis)
• Thẻ Từ, Mẫu Từ Vựng Và Trị Từ Vựng (Từ Vị)
• Kỹ Thuật Sử Dụng Automat Để Phân Tích Từ Vựng
• Mô Tả Quá Trình Đoán Nhận Xâu

Xem toàn bộ 224 trang tài liệu này.

- Chuyển được automat hữu hạn không đơn định về automat hữu hạn đơn định.

- Xây đựng được automat hữu hạn không đơn định đoán nhận một biểu thức chính quy.

- Nhận biết được từ vị bằng automat hữu hạn.

Nội dung chính:

- Nhắc lại một số kiến thức về văn phạm – ngôn ngữ - Automat.

- Thẻ từ, mẫu từ vựng và trị từ vựng (từ vị).

- Giai đoạn phân tích từ vựng.

- Kỹ thuật đọc chương trình nguồn.

- Kỹ thuật sử dụng Automat để phân tích từ vựng.

2.1. Nhắc lại một số kiến thức về văn phạm – ngôn ngữ - Automat

2.1.1. Một số khái niệm cơ sở

- Bảng chữ cái (bộ chữ cái) là một tập hợp hữu hạn, khác rỗng các phần tử, ký hiệu là . Các phần tử của một bảng chữ cái  được gọi là các chữ cái hoặc các ký tự (character) hay ký hiệu (symbol).

- Xâu (string) hay từ (word) trên một bảng chữ cái  là một dãy hữu hạn gồm một số lớn hơn hay bằng không các ký tự của bảng chữ cái đó; Trong đó, một ký tự có thể xuất hiện nhiều lần.

- Xâu rỗng là xâu không có chữ cái nào, độ dài của xâu rỗng bằng không. Xâu rỗng được ký hiệu là  hoặc e .

Ví dụ 2.1:

+ Tập hợp các chữ cái La tinh {a, b, c, …, A, B, …, Z } là một bảng chữ cái và a, b, ..., A, ... là các chữ cái hay các ký tự.

+  = {0, 1} là một bảng chữ cái nhị phân. 0, 1 là các chữ cái của bảng chữ cái .

+ Aaab, bbbbb là các từ trên bảng chữ cái La Tinh.

+ , 0, 1, 00101, 000011 là các từ trên bảng chữ cái nhị phân  = {0, 1}.

- Xâu con của xâu w là xâu x  được tạo từ các ký tự nằm liền kề nhau trong xâu w.

- Tiền tố của xâu w là một xâu con bất kỳ nằm ở đầu xâu w.

- Hậu tố của xâu w là một xâu con bất kỳ nằm ở cuối xâu w.

- Ngôn ngữ: Cho  là một bảng chữ cái.

+ * là tập hợp tất cả các xâu trên  kể cả xâu rỗng.

+ + là tập hợp tất cả các xâu trên  trừ xâu rỗng.

+ Tập con bất kỳ của tập hợp * được gọi là ngôn ngữ trên bảng chữ cái .

Ví dụ 2.2:

Cho bảng chữ cái nhị phân  = {0, 1} thì:

+ * = {, 0, 1, 00, 01, 10, 11, ...}.

+ + = {0, 1, 00, 01, 10, 11, ...}.

+  , + , * , {}, {0}, {1}, {, 0, 1}, { 1, 00, 01, 10}, {0, 1, 00, 01,

10, 11, 0001}, ... là các ngôn ngữ trên bảng chữ cái  . Và w = 001 là một từ trên bảng chữ cái  thì:

+ 0, 1, 00, 01, 011 là các xâu con của xâu w.

+ 0, 00, 001 là các tiền tố của xâu w.

+ 1, 01, 001 là các hậu tố của xâu w.

2.1.2. Biểu diễn ngôn ngữ

- Liệt kê:

+ Liệt kê hết: Đối với một ngôn ngữ hữu hạn, số lượng xâu của nó có ít, để biểu diễn nó, một cách đơn giản, ta chỉ cần liệt kê tất cả các xâu thuộc vào ngôn ngữ đó.

Ví dụ 2.3: L1 = {ε};

L2 = { a, ba, aaba, bbbbb}.

+ Liệt kê không hết:

Đối với một ngôn ngữ, số lượng xâu của nó có nhiều, các xâu thường tuân theo một quy luật; để biểu diễn nó, một cách đơn giản, ta chỉ cần liệt kê một số xâu và ám chỉ cách xác định các xâu khác thuộc vào ngôn ngữ đó.

Ví dụ 2.4: L1 = {ε, a, aa, aaa, …};

L2 = { ab, aabb, aaabbb, aaaabbbb, ...}.

- Chỉ ra tính chất đặc trưng: Trong trường hợp một ngôn ngữ là vô hạn, ta không thể liệt kê được tất cả các xâu thuộc vào ngôn ngữ đó. Trong những trường

hợp không phức tạp lắm, người ta thường phải tìm ra tính chất đặc trưng chung của các xâu và xác định các xâu bằng cách chỉ rò tính chất đặc trưng của các xâu đó. Tính chất đặc trưng này thường được mô tả thông qua một vị từ.

Ví dụ 2.5:

L3 = { ai | i là một số nguyên tố }; L4 = { ai bj | i ≥ j ≥ 0 }.

- Trong phần lớn các trường hợp, người ta thường biểu diễn ngôn ngữ một cách tổng quát thông qua một văn phạm hoặc một automat. Văn phạm là cơ chế hay công cụ cho phép sản sinh ra mọi xâu của một ngôn ngữ; trong khi đó automat lại là cơ chế hay công cụ cho phép đoán nhận một xâu bất kỳ có thuộc ngôn ngữ hay không. Về mặt hình thức, cả văn phạm và automat đều là cách biểu diễn khác nhau của cùng một quan niệm.

2.1.3. Văn phạm

1) Định nghĩa

Văn phạm là một hệ thống gồm bốn thành phần G = (N, T, P, S) trong đó:

N – Là một tập hữu hạn các ký hiệu không kết thúc (Nonterminal) hay tập các biến (variables).

T – Là tập hữu hạn các ký hiệu kết thúc hay ký hiệu cuối (Terminal) với N T = .

P – Là tập hữu hạn các quy tắc sinh hay còn được gọi là luật sinh.

P: (N  T)+ → (N  T)*

α β

SN - là ký hiệu chưa kết thúc đặc biệt dùng làm ký hiệu bắt đầu (start)

2) Phân loại

Chomsky dựa vào các luật sinh đã phân văn phạm thành bốn loại:

- Văn phạm loại 0 (văn phạm ngữ cấu – Phrase Grammar) là văn phạm mà các luật sinh của nó không có bất kỳ một điều kiện ràng buộc nào hay nói cách khác các luật sinh của nó có dạng: α  β với α  (N  T)+; β  (N  T)*

- Văn phạm loại 1 (phạm cảm ngữ cảnh - Context Sensitive Grammar) là văn phạm mà các luật sinh của nó có dạng: α  β với α  (N  T)+; β  (N  T)* và



- Văn phạm loại 2 (văn phạm phi ngữ cảnh - Context free Grammar) là văn phạm mà các luật sinh của nó có dạng: A  α với AN; α  (NT)*

- Văn phạm loại 3 (văn phạm chính quy - Regular Grammar) là văn phạm mà các luật sinh của nó có một trong hai dạng:

1. A  Ba hoặc A  a (văn phạm tuyến tính trái);

2. A  aB hoặc A  a (văn phạm tuyến tính phải). Với điều kiện A, B  N; a T.

2.1.4. Văn phạm phi ngữ cảnh

Ðể xây dựng cú pháp của một ngôn ngữ lập trình bậc cao, người ta dùng văn phạm phi ngữ cảnh CFG (Context Free Grammar) hay còn gọi là văn phạm BNF (Backus Naur Form).

Văn phạm này bao gồm bốn thành phần:

1. Một bảng chữ cái - Tập hợp các ký hiệu kết thúc (terminal symbols).

2. Một tập hợp các ký hiệu chưa kết thúc (nonterminal symbols), còn gọi là các biến (variables).

3. Một tập hợp các luật sinh (productions) trong đó mỗi luật sinh bao gồm một ký hiệu chưa kết thúc - gọi là vế trái, một mũi tên và một chuỗi các token và hoặc các ký hiệu chưa kết thúc, kết thúc gọi là vế phải.

4. Một trong các ký hiệu chưa kết thúc đặc biệt được dùng làm ký hiệu bắt đầu của văn phạm.

Quy ước:

- Mô tả văn phạm bằng cách liệt kê các luật sinh.

- Luật sinh chứa ký hiệu bắt đầu sẽ được liệt kê đầu tiên.

- Nếu có nhiều luật sinh có cùng vế trái thì nhóm lại thành một luật sinh duy nhất, trong đó các vế phải cách nhau bởi ký hiệu “|” và đọc là “hoặc”.

Ví dụ 2.6:

Nếu xem biểu thức là một danh sách của các số phân biệt nhau bởi dấu + và dấu thì văn phạm với các luật sinh sau sẽ xác định cú pháp của biểu thức.

list → list + digit; list → list – digit; list → digit;

digit → 0 | 1 | 2 | ...| 9

và ta có thể nhóm lại thành các luật sinh: list → list + digit | list - digit | digit ; digit → 0 | 1 | 2 ...| 9

Như vậy văn phạm phi ngữ cảnh ở đây là:

- Tập hợp các ký hiệu kết thúc: 0, 1, 2, ..., 9, +, -

- Tập hợp các ký hiệu chưa kết thúc: list, digit.

- Các luật sinh:

list → list + digit | list - digit | digit ; digit → 0 | 1 | 2 ...| 9

- Ký hiệu chưa kết thúc bắt đầu: list.

2.1.5. Biểu thức chính quy (Regular Expression)

Văn phạm chính quy đơn giản và đủ dùng cho biểu diễn và phân tích từ vựng. Ngoài cách biểu diễn bằng các luật sinh, văn phạm chính quy còn có cách biểu diễn tương đương bằng biểu thức chính quy.

Chẳng hạn có thể viết:

id = (letter | _ ) (letter | digit | _ )* hoặc id  letter (letter | digit)*; (letter | _ ) (letter | digit | _ )* là một biểu thức chính quy.

Biểu thức chính quy được xây dựng trên một tập hợp các quy tắc xác định.

Mỗi biểu thức chính quy r đặc tả một ngôn ngữ L(r).

Sau đây là các quy tắc xác định biểu thức chính quy trên bảng chữ cái Σ.

1. ε là một biểu thức chính quy đặc tả cho một chuỗi rỗng {ε }.

2. Nếu a  Σ thì a là biểu thức chính quy r đặc tả tập hợp các chuỗi {a}

3. Giả sử r và s là các biểu thức chính quy đặc tả các ngôn ngữ L(r) và L(s) ta có:

a. (r) | (s) là một biểu thức chính quy đặc tả L(r)  L(s)

b. (r) (s) là một biểu thức chính quy đặc tả L(r)L(s).

c. (r)* là một biểu thức chính quy đặc tả (L(r))*

d. (r)+ là một biểu thức chính quy đặc tả (L(r))+

Quy ước:

Toán tử bao đóng *, + có độ ưu tiên cao nhất và kết hợp trái. Toán tử ghép có độ ưu tiên thứ hai và kết hợp trái.

Toán tử hợp | có độ ưu tiên thấp nhất và kết hợp trái.

Ví dụ 2.7:

Cho bảng chữ cái Σ = {a, b}.

1. Biểu thức chính quy a | b đặc tả {a, b}

2. Biểu thức chính quy (a | b) (a | b) đặc tả tập hợp {aa, ab, ba, bb}. Tập hợp này có thể được đặc tả bởi biểu thức chính quy tương đương sau: aa | ab | ba | bb.

3. Biểu thức chính quy a* đặc tả { ε, a, aa, aaa, ... }

4. Biểu thức chính quy (a | b)* đặc tả {(, a, b, aa,bb, ...}. Tập này có thể đặc tả bởi (a*b* )*.

5. Biểu thức chính quy a | a* b đặc tả {a, b, ab, aab,... }

Hai biểu thức chính quy r và s cùng đặc tả một tập hợp thì ta nói rằng chúng tương đương và viết là r = s.

2.1.6. Automat hữu hạn đơn định

1) Định nghĩa

Automat hữu hạn đơn định là một hệ thống gồm 5 thành phần; ký hiệu là M = , , q0, F>, trong đó:

Q - Tập hữu hạn khác rỗng các trạng thái.

 - Tập hữu hạn khác rỗng các ký hiệu vào (gọi tắt là bảng chữ cái vào).

 - Ánh xạ còn gọi là hàm chuyển trạng thái có dạng:

: Q  Q (q, a) p

q0 - Là trạng thái bắt đầu; q0 Q.

F - Tập con của Q ( F  Q) là tập các trạng thái kết thúc.

2) Hàm chuyển trạng thái mở rộng

1. δ*(q, ε) = q

2. δ*(q, wa) = δ(δ*(q, w), a); với q  Q; w  Σ* và a  Σ.

= δ(δ( ... δ(q, a)...))

 δ*(q, a1a2…an-1an) = δ(δ( ... (δ(δ(q, a1),a2), ...),an-1), an)

3) Ngôn ngữ đoán nhận bởi automat hữu hạn đơn định

L(M) = w * *(q0,w) = qF

2.1.7. Automat hữu hạn không đơn định - NFA (Nondeterministic Finite Automata)

1) Định nghĩa

Automat hữu hạn không đơn định là một hệ thống gồm 5 thành phần, ký hiệu là M = , , q0, F> trong đó:

Q - Tập hữu hạn khác rỗng các trạng thái.

 - Tập hữu hạn khác rỗng các ký hiệu vào (gọi tắt là bảng chữ cái vào).

 - Ánh xạ còn gọi là hàm chuyển trạng thái có dạng:

: Q  2Q (q, a) p

q0 - Là trạng thái bắt đầu; q0 Q.

F - Tập con của Q là tập các trạng thái kết thúc.

2) Hàm chuyển trạng thái mở rộng

1. δ*(q, ε) = {q} ;

2. δ*(q, wa) = δ(δ*(q, w), a) với q  Q; w  Σ* và a  Σ

 δ*(q, a1a2…an-1an) = δ(δ( ... (δ(δ(q, a1),a2), ...),an-1), an) 3. - δ(T, a) =  δ(q, a) với  T  Q.

q  T

- δ*(T, a) =  δ*(q, a) với  T  Q.

q  T

3) Ngôn ngữ đoán nhận bởi automat không đơn định

N(M) = w* *(q0,w) = q  F 

Hay N(M) = {w * | δ*(q , w) có chứa một trạng thái trong F }

0

2.1.8. Automat hữu hạn không đơn định với ε-dịch chuyển (NFAε)

1) Định nghĩa

Automat hữu hạn không đơn định với ε-dịch chuyển (NFA với ε-dịch chuyển) là một hệ thống gồm 5 thành phần; ký hiệu là M = , , q0, F> trong đó:

Q - Tập hữu hạn khác rỗng các trạng thái.

 - Tập hữu hạn khác rỗng các ký hiệu vào (gọi tắt là bảng chữ cái vào).

 - Ánh xạ còn gọi là hàm chuyển trạng thái có dạng:

: Q  ( {})  2Q

(q, a) p

q0 - Là trạng thái bắt đầu; q0 Q.

F - Tập con của Q là tập các trạng thái kết thúc.

2) Hàm chuyển trạng thái mở rộng

a) Hàm -CLOSURE

1. -CLOSURE(q) là tập hợp các trạng thái p sao cho có đường đi từ trạng thái q tới p khi M nhận vào từ rỗng  (gồm không, một hoặc nhiều cung mang nhãn ).

2. ε-CLOSURE(T) = qT ε-CLOSURE(q) với qQ ; T Q

Chú ý: ε-CLOSURE() = 

Ví dụ 2.8: