Bài giảng Chương trình dịch - Phân tích từ vựng

 NFA Định nghĩa REs, DFA và NFA REs ⇒NFA (Thompson’s construction, Algorithm 3.3, Red Dragon/Algorithm 3.23, Purple Dragon) NFA ⇒DFA (subset construction, Algorithm 3.2, Red Dragon/Algorithm 3.20, Purple Dragon) DFA ⇒minimal-state DFA (state minimisation, Algorithm 3.6, Red Dragon/Algorithm 3.39, Purple Dragon) * * Nguyễn Phương Thái - Coltech - Compiler 2009 Ứng dụng của biểu thức chính qui Bất cứ nơi nào mà mẫu văn bản cần được mô tả Hệ thống, cơ sở dữ liệu và quản trị mạng Unix: grep, fgrep, egrep, sed, awk Các văn bản HTML: Javascript và VBScript Perl: J. Friedl, Mastering Regular Expressions, O’reilly, 1997 Mô tả từ tố cho các chương trình sinh hệ phân tích từ vựng (lex, JLex, v.v.)  * * Nguyễn Phương Thái - Coltech - Compiler 2009 Ứng dụng của ôtômát hữu hạn Thiết kế phần cứng (tối thiểu hóa trạng thái ⇒ tối thiểu hóa giá thành) Lý thuyết ngôn ngữ Độ phức tạp tính toán Các chương trình sinh hệ phân tích từ vựng (lex and JLex) JCT: //humboldt.sunyit.edu/JCT * * Nguyễn Phương Thái - Coltech - Compiler 2009 Bộ chữ cái, xâu ký tự và ngôn ngữ Bộ chữ cái ∑: tập hữu hạn ký hiệu Bộ chữ cái nhị phân {0,1} (cho ngôn ngữ máy) Bộ chữ cái ASCII (cho các ngôn ngữ bậc cao) Xâu ký tự: chuỗi hữu hạn ký hiệu thuộc ∑ Độ dài |s| của xâu s: số lượng ký hiệu trong s ε: xâu rỗng (| ε | = 0) Ngôn ngữ: tập các xâu trên ∑; hai trường hợp đặc biệt: ∅: tập rỗng {ε} * * Nguyễn Phương Thái - Coltech - Compiler 2009 Ví dụ về ngôn ngữ ∑= {0, 1} – mỗi xâu là một chỉ thị Tập chỉ thị của M68K Tập chỉ thị của Pentium Tập chỉ thị của MIPS ∑ = tập ASCII – mỗi xâu ký tự là một chương trình Tập các chương trình Haskell Tập các chương trình C Tập các chương trình VC * * Nguyễn Phương Thái - Coltech - Compiler 2009 Các thuật ngữ về xâu ký tự (Figure 3.7 of Text) * * Nguyễn Phương Thái - Coltech - Compiler 2009 Ghép xâu Nếu x và y là các xâu, xy là xâu tạo bởi phép bổ xung y vào x Ví dụ: x y xy key word keyword java script javascript ε is the identity: εx = xε = x * * Nguyễn Phương Thái - Coltech - Compiler 2009 Các phép toán trên ngôn ngữ (Figure 3.8 of Text) * * Nguyễn Phương Thái - Coltech - Compiler 2009 Ví dụ về các phép toán trên ngôn ngữ * * Nguyễn Phương Thái - Coltech - Compiler 2009 Ví dụ về các phép toán trên ngôn ngữ * * Nguyễn Phương Thái - Coltech - Compiler 2009 Các biểu thức chính qui – Regular Expressions (REs) – trên bộ chữ cái ∑ Cơ sở qui nạp: 	1. ε là một RE, khi đó ngôn ngữ chính qui – regular language (RL) – RL là {ε} 	2. a ∈ ∑ là một RE, khi đó RL là {a} Bước qui nạp: Giả sử r và s là các RE, các RL tương ứng là L(r) and L(s). Khi đó: 	1. (r)|(s) là một RE, RL là L(r) ∪ L(s) 	2. (r)(s) là một RE, RL là L(r)L(s) 	3. (r)∗ là một RE, RL là L(r)∗ 	4. (r) là một RE, RL là L(r) 	 	Chú ý: ngôn ngữ chính qui cũng có thể được gọi là tập chính qui * * Nguyễn Phương Thái - Coltech - Compiler 2009 Thứ tự ưu tiên và tính kết hợp của các toán tử “chính qui” Thứ tự ưu tiên: “∗” có độ ưu tiên cao nhất “ghép” có độ ưu tiên thứ nhì “|” có độ ưu tiên thấp nhất Tính kết hợp: — tất cả các toán tử đều có tính kết hợp trái Ví dụ: 	(a)|((b)∗(c)) ≡ a|b∗c 	Không cần sử dụng các dấu ngoặc thừa! * * Nguyễn Phương Thái - Coltech - Compiler 2009 Một ví dụ về RE và RL Bộ chữ cái: ∑ = {0, 1} RE: 0(0|1)∗ Câu hỏi: RE trên định nghĩa ngôn ngữ nào? Trả lời: L(0(0|1)∗) = L(0)L((0|1)∗) 	 = {0}L(0|1)∗ 	 = {0}(L(0) ∪ L(1))∗ 	 = {0}({0} ∪ {1})∗ 	 = {0}{0, 1}∗ 	 = {0}{ε, 0, 1, 00, 01, 10, 11, . . . } 	 = {0, 00, 01, 000, 001, 010, 011, . . . } 	RE trên mô tả tập các xâu ký tự nhị phân bắt đầu với một số 0 * * Nguyễn Phương Thái - Coltech - Compiler 2009 Các ví dụ khác: ∑ = {0, 1} * * Nguyễn Phương Thái - Coltech - Compiler 2009 Giải thích một số ký hiệu Một hay nhiều instance +: r+ = rr∗ Ngôn ngữ (L(r))+ Có cùng thứ tự ưu tiên và tính kết hợp như ∗ Không hay một instance ?: r? = r|ε Ngôn ngữ L(r) ∪ {ε} Viết (r)? để chỉ nhóm (vd (12)?) Các lớp ký tự: [A − Za − z ][A − Za − z0 − 9 ]∗ * * Nguyễn Phương Thái - Coltech - Compiler 2009 Các biểu thức chính qui cho VC (hay C) Trong đặc tả của VC, chữ cái gồm cả “_” Trong Java, chữ cái và chữ số thuộc tập Unicode. Do đó các định danh có thể là: * * Nguyễn Phương Thái - Coltech - Compiler 2009 Các văn phạm chính qui cho số nguyên và số thực trong VC * * Nguyễn Phương Thái - Coltech - Compiler 2009 Ôtômát hữu hạn (hay máy hữu hạn trạng thái) 	Một ôtômát hữu hạn là một bộ 5: (∑, S, T, F, I) 	trong đó ∑ là bộ chữ cái S là tập hữu hạn trạng thái T là hàm chuyển trạng thái: T : S × ∑ → S F là tập hữu hạn các trạng thái kết thúc hay còn gọi là trạng thái nhận I là trạng thái bắt đầu: I ∈ S. * * Nguyễn Phương Thái - Coltech - Compiler 2009 Biểu diễn và chấp nhận Đồ thị chuyển: Chấp nhận: Một Ôtômát hữu hạn chấp nhận một xâu vào x nếu và chỉ nếu có đường đi nào đó trong đồ thị chuyển từ trạng thái bắt đầu đến trạng thái chấp nhận nào đó, đồng thời các nhãn trên đường đi đó tạo thành x * * Nguyễn Phương Thái - Coltech - Compiler 2009 Ôtômát hữu hạn này đoán nhận ngôn ngữ nào? * * Nguyễn Phương Thái - Coltech - Compiler 2009 Ví dụ 1 * * Nguyễn Phương Thái - Coltech - Compiler 2009 Trạng thái lỗi ẩn * * Nguyễn Phương Thái - Coltech - Compiler 2009 Ôtômát hữu hạn đơn định (DFA) và ôtômát hữu hạn không đơn định (NFA) Một FA là một DFA nếu Không trạng thái nào có một chuyển-ε, và Với mỗi trạng thái s và ký hiệu vào a, có không quá một cung nhãn a ra khỏi s Một FA là một NFA nếu nó không phải một DFA: Không đơn định: ứng với một ký hiệu vào có thể có vài chuyển * * Nguyễn Phương Thái - Coltech - Compiler 2009 DFA hay NFA? Các ngôn ngữ được đoán nhận là gì? * * Nguyễn Phương Thái - Coltech - Compiler 2009 Hai ví dụ Cùng ngôn ngữ: tập các xâu ký tự của a mà chiều dài của chúng là bội số của 2 hay 3 (gồm cả ε) * * Nguyễn Phương Thái - Coltech - Compiler 2009 Nội dung Phân tích từ vựng: từ tố, từ vị, mẫu REs, FA (DFA, NFA) Nâng cao: REs  NFA; NFA  DFA; DFA  minimal-state DFA Một số bài tập * * Nguyễn Phương Thái - Coltech - Compiler 2009 Thuật toán Thompson để xây dựng NFA từ các RE Điều khiển bởi cú pháp Quy nạp: Các trường hợp (case) trong xây dựng NFA tương ứng với các trường hợp trong định nghĩa RE Điều quan trọng: nếu một ký hiệu xuất hiện vài lần trong một RE r, một NFA riêng biệt được tạo cho mỗi lần xuất hiện Thuật toán Thompson là một trong nhiều thuật toán đã được đưa ra * * Nguyễn Phương Thái - Coltech - Compiler 2009 Thuật toán Thompson Cơ sở qui nạp: 	1. Với ε, tạo NFA 	2. Với a ∈ ∑, tạo NFA Bước qui nạp: giả sử N(r) và N(s) là các NFA của các RE r và s. Khi đó * * Nguyễn Phương Thái - Coltech - Compiler 2009 Thuật toán Thompson (Cont’d) * * Nguyễn Phương Thái - Coltech - Compiler 2009 Ví dụ: RE ⇒NFA Chuyển đổi (0|10∗1)∗10∗ thành một NFA * * Nguyễn Phương Thái - Coltech - Compiler 2009 Ví dụ: RE ⇒ NFA * * Nguyễn Phương Thái - Coltech - Compiler 2009 Ví dụ: DFA (Cont’d) Thuật toán này được biết đến như là thuật toán xây dựng tập con bởi vì trạng thái của DFA tương ứng với tập con các trạng thái của NFA Có tối đa 2n trạng thái DFA, trong đó n là tổng số trạng thái NFA * * Nguyễn Phương Thái - Coltech - Compiler 2009 Xây dựng tập con: các toán tử được sử dụng * Nguyễn Phương Thái - Coltech - Compiler 2009 * Thuật toán xây dựng tập con Gọi s0 là trạng thái bắt đầu của NFA; DFAstates chứa duy nhất trạng thái chưa được đánh dấu ε-closure(s0) while có một trạng thái không được đánh dấu T trong DFAstates do begin 	đánh dấu T 	for mỗi ký hiệu vào a do begin 	U := ε-closure(move(T, a)); 	if U không có trong DFAstates then 	Thêm U vào DFAstates như một trạng thái chưa được đánh dấu; 	DFATrans[T, a] := U; 	end; end; * * Nguyễn Phương Thái - Coltech - Compiler 2009 Xây dựng tập con: Định nghĩa của DFA Giả sử (∑, S, T, F, s0) là NFA ban đầu. DFA sẽ là: Bộ chữ cái: ∑ Các trạng thái: tất cả các trạng thái có trong DFAstates Trạng thái bắt đầu: ε-closure(s0) Các trạng thái chấp nhận: tất cả các trạng thái trong DFAstates mà chứa ít nhất một trạng thái chấp nhận trong F của NFA Các chuyển: DFATrans * * Nguyễn Phương Thái - Coltech - Compiler 2009 Thuật toán cực tiểu hóa trạng thái DFA Ban đầu, giả sử ∏ gồm hai nhóm (1) Tập tất cả các trạng thái kết thúc (2) Tập các trạng thái không kết thúc Khởi tạo ∏new = ∏ for mỗi nhóm G trong ∏new { Chia G thành các nhóm con sao cho hai trạng thái s và t thuộc cùng nhóm nếu và chỉ nếu với mọi ký hiệu vào a các trạng thái s và t có chuyển nhãn a tới các trạng thái trong cùng nhóm của ∏new Thay G trong ∏new bằng tập các tập con được tạo ra } * Nguyễn Phương Thái - Coltech - Compiler 2009 * Ví dụ (Cont’d): Các trạng thái được gán nhãn lại Kết quả lý thuyết: tất cả các ngôn ngữ chính qui có thể được nhận dạng bởi một DFA trạng thái cực tiểu mà là duy nhất (theo tên trạng thái) * * Nguyễn Phương Thái - Coltech - Compiler 2009 Nội dung Phân tích từ vựng: từ tố, từ vị, mẫu REs, FA (DFA, NFA) Nâng cao: REs  NFA; NFA  DFA; DFA  minimal-state DFA Một số bài tập * * Nguyễn Phương Thái - Coltech - Compiler 2009 A. 4 Phân loại Chomsky * * Nguyễn Phương Thái - Coltech - Compiler 2009 Phân loại văn phạm của Chomsky Chúng ta đang làm việc với lớp 3: ngôn ngữ chính qui * * Nguyễn Phương Thái - Coltech - Compiler 2009 Bài tập Bài 1. Viết biểu thức chính qui cho các ngôn ngữ có mô tả như sau (∑ = {0,1}): (a) Tất cả các xâu có thể (b) Không có xâu nào (c) Xâu rỗng (d) Xâu 011 (e) Các xâu 0 và 011 (f) Tất cả các xâu bắt đầu với một 1 (g) Tất cả các xâu bắt đầu với một ký hiệu 1 và kết thúc với một ký hiệu 0 (h) Tất cả các xâu chứa đúng ba ký hiệu 1 (i) Tất cả các xâu mà mỗi ký hiệu 0 đều có ký hiệu 1 đi trước và đi sau * Nguyễn Phương Thái - Coltech - Compiler 2009 * Bài tập Bài 2. Thiết kế các ôtômát hữu hạn đơn định (DFA) để đoán nhận các ngôn ngữ sau (∑ = {0,1}): (a) Mọi xuất hiện của xâu con 11 được theo sau bởi ký hiệu 0. (b) Ký hiệu thứ ba (nếu có) là 1. (c) Số lượng ký hiệu 0 phải là chẵn và số lượng ký hiệu 1 cũng chẵn (kể cả xâu rỗng). Bài 3. Thiết kế các ôtômát hữu hạn không đơn định (NFA) từ các biểu thức chính qui sau: (a) (a|b)* (b) a*|b* (c) a|(b|c)* (d) a(a|b)*b * Nguyễn Phương Thái - Coltech - Compiler 2009 *