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

1Bài 3. PHÂN TÍCH TỪ VỰNG Hoàng Anh Việt Viện CNTT&TT - ĐHBKHN Kiểm tra bài trước • Bài tập 2.1: Cho văn phạm phi ngữ cảnh: S → S S + | S S * | a Xây dựng cây PTCP cho câu nhập: aa+a* • Bài 2.2 Đâu là văn phạm mơ hồ: 2 3Mục đích • Sau khi học xong chương này, sinh viên sẽ nắm được: – Các kỹ thuật xác định và cài đặt bộ PTTV. – Xây dựng các lược đồ cho các biểu thức chính quy mô tả ngôn ngữ. – DFA và NFA. Các automata hữu hạn xác định và không xác định dùng để nhận dạng chính xác ngôn ngữ. – Sử dụng công cụ có sẵn Lex để sinh ra bộ PTTV Điều kiện • Kiến thức cần có: – Kiến thức cơ bản về NFA và DFA – Cách chuyển đổi giữa các Automata. 4 Tài liệu tham khảo [1] Slide bài giảng [2] Compilers : Principles, Technique and Tools - Alfred V.Aho, Jeffrey D.Ullman - Addison - Wesley Publishing Company, 1986. [3] Automata and Formal Language, An Introduction- Dean Kelley- Prentice Hall, Englewood Cliffs, New Jersey 07632 [4] Compilers course, CS 143 summer 2010, Standford University. 5 6Nội dung 1. Vai trò của bộ phân tích từ vựng 2. Lữu trữ tạm chương trình nguồn 3. Đặc tả Token 4. Nhận dạng Token 5. Sơ đồ dịch 6. Automat hữu hạn 7. Từ biểu thức chính quy đến NFA 8. Tổng kết quá trình PTTV 9. Thiết kế bộ sinh bộ PTTV 7Nội dung 1. Vai trò của bộ phân tích từ vựng 2. Lữu trữ tạm chương trình nguồn 3. Đặc tả Token 4. Nhận dạng Token 5. Sơ đồ dịch 6. Automat hữu hạn 7. Từ biểu thức chính quy đến NFA 8. Tổng kết quá trình PTTV 9. Thiết kế bộ sinh bộ PTTV 1. Vai trò của bộ phân tích từ vựng 1.1 Ý nghĩa của giai đoạn PTTV 1.2 Các khái niệm 1.3 Thuộc tính của Token 1.4 Lỗi từ vựng 8 1. Vai trò của bộ phân tích từ vựng 9 1.1 Ý nghĩa của giai đoạn PTTV • Làm cho việc thiết kế đơn giản và dễ hiểu hơn • Hiệu quả của trình biên dịch được cải thiện nhờ một số chương trình xử lý chuyên dụng. • Tính đa tương tích của trình biên dịch được cải thiện. 10 1.2 Các khái niệm • Từ tố (Token): là các ký hiệu kết thúc trong văn phạm đối với ngôn ngữ nguồn. Ví dụ: từ khóa, toán tử, dấu câu, hằng, định danh • Trị từ vựng (Lexeme) của một token là một chuỗi ký tự biểu diễn cho token đó • Mẫu từ vựng (pattern) là qui luật mô tả một tập các trị từ vựng kết hợp với một token nào đó. 11 1.2 Các khái niệm 12 1.3 Thuộc tính của Token • Khi có nhiều mẫu từ vựng khớp với trị từ vựng, bộ PTTV phải cung cấp thêm thông tin và cất chúng vào bảng danh biểu (Ví dụ trị từ vựng). Token luôn mang trong mình một thuộc tính duy nhất là con trỏ để chỉ đến vị trí của nó trong bảng danh biểu. Khi một token được chuyển đến bộ phân tích cú pháp nó sẽ có dạng. 13 1.3 Thuộc tính của Token • Ví dụ 3.1: Câu lệnh: X=Y*2, được viết như một dãy các bộ: – – – – – 14 Chú ý: Một số bộ không cần giá trị thuộc tính, thành phần đầu tiên là đủ nhận dạng trị từ vựng 1.4 Lỗi từ vựng • Chỉ một số ít lỗi được phát hiện tại bước PTTV. • Ví dụ: fi (i>=m) fi lỗi viết sai từ khóa if ? Hay một id (danh biểu) chưa được khai báo? • Các chiến lược khắc phục lỗi: • Xóa đi 1 ký tự dư • Xen thêm 1 ký tự bị mất • Thay thế ký tự sai bằng ký tự đúng • Chuyển đổi hai ký tự kề nhau 15 16 Nội dung 1. Vai trò của bộ phân tích từ vựng 2. Lữu trữ tạm chương trình nguồn 3. Đặc tả Token 4. Nhận dạng Token 5. Sơ đồ dịch 6. Automat hữu hạn 7. Từ biểu thức chính quy đến NFA 8. Thiết kế bộ sinh bộ PTTV 2. Lưu trữ tạm chương trình nguồn 2.1 Cặp bộ đệm 2.2 Khóa canh 17 2. Lưu trữ tạm chương trình nguồn • Vấn đề: Đọc từng ký tự chương trình nguồn tốn nhiều thời gian và ảnh hưởng tốc độ dịch • Giải quyết: Đọc một lúc một chuỗi ký tự và lưu vào bộ đệm buffer. • Thế nào cho trọn vẹn Token? 18 2.1 Cặp bộ đệm • Vùng đệm chia làm 2 nửa với kích thước N (1024 hoặc 4096) • Sử dụng 2 con trỏ P1, P2 để dò tìm. – P1 đặt tại vị trí đầu của 1 trị từ vựng – P2 dịch chuyển để xác định trị từ vựng cho token. 19 Vấn đề? 2.1 Cặp bộ đệm Giải thuật: if p2 ở ranh giới một nửa bộ đệm then begin lấp đầy N ký hiệu nhập mới vào nửa bên phải. p2 := p2 + 1; end else if p2 ở tận cùng bên phải bộ đệm then begin lấp đầy N kỳ hiệu nhập vào nửa bên trái bộ đệm. chuyển p2 về ký tự tận cùng bên trái của bộ đệm. end else p2 := p2 + 1; 20 2.2 Khóa canh • Chỉ đọc N-1 ký tự vào mỗi nửa buffer. • Ký tự N là eof. 21 Hình 3.4- Khóa canh oef tại cuối mỗi vùng đệm 2.2 Khóa canh Giải thuật: p2 := p2 + 1; If p2 ^ eof then if p2 ở ranh giới một nửa bộ đệm then begin chất đầy N kỳ hiệu nhập vào nửa bên phải bộ đệm ; p2 := p2 + 1 end 22 2.2 Khóa canh else if p2 ở tận cùng bên phải bộ đệm then begin lấp đầy N ký hiệu vào nửa bên trái bộ đệm; chuyển p2 về đầu bộ đệm end else /* dừng sự phân tích từ vựng*/ end 23 24 Nội dung 1. Vai trò của bộ phân tích từ vựng 2. Lữu trữ tạm chương trình nguồn 3. Đặc tả Token 4. Nhận dạng Token 5. Sơ đồ dịch 6. Automat hữu hạn 7. Từ biểu thức chính quy đến NFA 8. Thiết kế bộ sinh bộ PTTV 3. Đặc tả token 3.1 Chuỗi và ngôn ngữ 3.2 Các phép toán trên ngôn ngữ 3.3 Biểu thức chính quy 3.4 Các tính chất đại số của biểu thức chính quy 3.5 Định nghĩa chính quy 3.6 Ký hiệu viết tắt. 25 3.1 Chuỗi và ngôn ngữ • Chuỗi: – Tập hợp hữu hạn các ký tự – Độ dài chuỗi là số ký tự trong chuỗi – Chuỗi rỗng ε là chuỗi có độ dại 0. • Ngôn ngữ: – Là tập hợp các chuỗi – Có thể chỉ bao gồm 1 chuỗi rỗng ký hiệu là Ø 26 3.2 Các phép toán trên ngôn ngữ • Xét 2 ngôn ngữ L và M: – Hợp: của L và M là L υ M = {s|s ∈ L hoặc s ∈ M} – Ghép: của L và M là: LM= {st| s ∈L và t ∈ M} – Bao đóng Kleen của L: L*= {ghép của 0 hoặc nhiều L} – Bao đóng dương của L={ghép của 1 hoặc nhiều L} 27 3.2 Các phép toán trên ngôn ngữ • Ví dụ 3.2 L={A,B,.Z,a,b,z} D={0,1,9} - L ∪ D là tập hợp các chữ cái và số. - LD là tập hợp các chuỗi bao gồm một chữ cái và một chữ số. - L4 là tập hợp tất cả các chuỗi có 4 chữ cái - L* là tập hợp các chuỗi của các chữ cái và rỗng. - L(L ∪ D)* là tập hợp tất cả các chuỗi mở đầu bằng 1 chữ cái và theo sau là chữ cái hoặc số. - D+ là tập hợp các chuỗi gồm 1 hoặc nhiều chữ số. 28 3.3 Biểu thức chính quy (regular Expression) • Nhắc lại: Trong NNLT, 1 biến (danh biểu) là một phần tử của tập hợp L(L ∪ D)* => có thể viết: biến=letter(letter|digit)* 29 Đây biểu thức chính quy! 3.3 Biểu thức chính quy (regular Expression) • Biểu thức chính quy: – Được xây dựng trên một tập hợp các luật xác định. – Mỗi BTCQ r đặc tả cho một ngôn ngữ L(r). – 2 BTCQ là tương đương nếu cùng đặc tả một tập hợp 30 Các luật xác định BTCQ trên tập Alphabet ∑: 1. ε là một biểu thức chính quy đặc tả 1 chuỗi rỗng {ε} 2. Nếu a ∈ ∑ thì a là BTCQ r đặc tả tập hợp các chuỗi {a} 3. r và s là các BTCQ đặc tả các ngôn ngữ L(r) và L(s) 1. (r)|(s) là một btcq đặc tả L(r) ∪ L(s) 2. (r)(s) là 1 btcq đặc tả L(r)L(s). 3. (r)* là 1 btcq đặc tả (L(r))* 3.3 Biểu thức chính quy (regular Expression) • Ví dụ 3.3 Cho ∑ = { a, b} – BTCQ a|b đặc tả {a,b} – BTCQ (a|b)(a|b) đặc tả tập hợp {aa,ab,ba,bb} – BTCQ a* đặc tả { ε, a, aa, aaa, ... } – BTCQ (a | b)* đặc tả {a, b, aa,bb, ...}. Tập này có thể đặc tả bởi (a*b* )*. – BTCQ a | a* b đặc tả {a, b, ab, aab,... } 31 3.4 Các tính chất đại số của BTCQ Tính chất Mô tả r | s = s | r | có tính chất giao hoán r | (s | t) = (r | s ) | t | có tính chất kết hợp (rs) t = r (st) Phép ghép có tính chất kết hợp r (s | t) = rs | rt (s | t) r = sr | tr Phép ghép phân phối đối với phép | εr = r rε = r ε là phần tử đơn vị của phép ghép r* = ( r | ε )* Quan hệ giữa r và ε r* * = r * * có hiệu lực như nhau 32 Hình 3.5 - Một số tính chất đại số của biểu thức chính quy 3.5 Định nghĩa chính quy • Định nghĩa chính quy là chuỗi định nghĩa có dạng: d1 → r1 dn → rn Trong đó: di là 1 tên còn ri là 1 BTCQ • Ví dụ 3.4: Tập hợp các danh biểu trong Pascal 33 3.5 Định nghĩa chính quy • Ví dụ 3.5:Các số không dấu trong Pascal là các chuỗi 5280, 39.37, 6.336E4 hoặc 1.894E- 4. Ðịnh nghĩa chính quy sau đặc tả tập các số này là : 34 3.6 Ký hiệu viết tắt 1. Một hoặc nhiều: dùng dấu + 2. Không hoặc một: dùng dấu ? – Ví dụ 3.6: r | ε được viết tắt là r ? – Ví dụ 3.7: Viết tắt cho định nghĩa chính quy tập hợp số num trong ví dụ 3.5 3. Lớp ký tự 35 3.6 Ký hiệu viết tắt Sử dụng lớp ký hiệu chúng ta có thể mô tả danh biểu như là một chuỗi sinh ra bởi biểu thức chính quy : [A - Z a - z] [A - Z a - z 0 – 9] * 36 37 Nội dung 1. Vai trò của bộ phân tích từ vựng 2. Lữu trữ tạm chương trình nguồn 3. Đặc tả Token 4. Nhận dạng Token 5. Sơ đồ dịch 6. Automat hữu hạn 7. Từ biểu thức chính quy đến NFA 8. Tổng kết quá trình PTTV 9. Thiết kế bộ sinh bộ PTTV 4. Nhận dạng Token • Cho văn phạm G: stmt -> if exp then stmt | if exp then stmt else stmt | € exp -> term relop term |term term -> id |num • Các ký hiệu kết thúc: if, then, else, relop, id, num được cho bởi định nghĩa chính quy. 38 4. Nhận dạng Token • Định nghĩa chính quy khoảng trắng 39 4. Nhận dạng Token Biểu thức chính quy Token Trị thuộc tính ws - - If if - Then Then - Else Else - Id Id Con trỏ trong bảng ký hiệu Num Num Giá trị số < Relop LT (Less than) <= Relop LE (Less or Equal) = Relop EQ (Equal) Relop NE (not equal) > Relop GT (Greater than) >= Relop GE (Greater or Equal) 40 Hình 3.6: Mẫu biểu thức chính quy cho 1 số token 41 Nội dung 1. Vai trò của bộ phân tích từ vựng 2. Lữu trữ tạm chương trình nguồn 3. Đặc tả Token 4. Nhận dạng Token 5. Sơ đồ dịch 6. Automat hữu hạn 7. Từ biểu thức chính quy đến NFA 8. Thiết kế bộ sinh bộ PTTV 5. Sơ đồ dịch • Để dễ nhận dạng Token • Mỗi nhóm Token có một sơ đồ dịch • Nếu xảy ra thất bại khi đang theo một SDD thì lui con trỏ lại vị trí đầu và kích hoạt SDD tiếp theo. • Nếu thất bại trong mọi SDD=> lỗi từ vựng và cần khởi động thủ tục khắc phục • Mỗi SDD gồm: trạng thái, các cạnh nối. 42 5. Sơ đồ dịch • Sơ đồ dịch nhận dạng cho Token relop: 43 Chú ý: ký tự * chỉ trạng thái đọc quá 1 ký tự, cần quay lui con trỏ 5. Sơ đồ dịch • Sơ đồ dịch nhận dạng Token Id • gettoken( ) và install_id( ) tương ứng để nhận token và các thuộc tính trả về. 44 5. Sơ đồ dịch • Sơ đồ dịch nhận dạng num 45 Hình 3.9 - Sơ đồ dịch cho các số không dấu trong Pascal 5. Sơ đồ dịch • Sơ đồ dịch nhận dạng khoảng trắng ws 46 Có gì đặc biệt? 47 Nội dung 1. Vai trò của bộ phân tích từ vựng 2. Lữu trữ tạm chương trình nguồn 3. Đặc tả Token 4. Nhận dạng Token 5. Sơ đồ dịch 6. Automat hữu hạn 7. Từ biểu thức chính quy đến NFA 8. Thiết kế bộ sinh bộ PTTV 6. Automat hữu hạn • Kiến thức nền: – Lý thuyết Văn phạm – Lý thuyết ngôn ngữ – Lý thuyết tập hợp – Các kỹ thuật chứng minh: Quy nạp, phản chứng. • Tài liệu tham khảo: 1. Bài giảng lý thuyết ngôn ngữ hình thức và Automat- Hồ Văn Quân [2002] 2. An Introduction to Formal Languages and Automat- Peter Linz [1990] 48 6. Automat hữu hạn 6.1 Các khái niệm Automat 6.2 Phân loại và ứng dụng 6.3 Automat hữu hạn đơn định (DFA) 6.4 Automat hữu hạn không đơn định (NFA) 6.5 Chuyển từ NFA sang DFA 49 6.1 Các khái niệm Automat • Automat là gì? – Dịch là máy tự động, là thiết bị có thể thực hiện công việc mà không cần sự can thiệp của con người. – Nó hoạt động dựa trên một số quy tắc và dựa vào các quy tắc này con người lập trình cho nó hoạt động theo ý muốn của mình. – Máy tính số ngày nay là một máy tư động điển hình và mạnh nhất. 50 6.1 Các khái niệm Automat • Là một mô hình trừu tượng của máy tính số bao gồm các thành phần chủ yếu sau: 51 6.1 Các khái niệm Automat • Thiết bị đầu vào (input file): là nơi mà chuỗi nhập (input string) được ghi lên, và được automat đọc nhưng không thay đổi được nội dung. Nó được chia thành các ô, mỗi ô giữ một ký hiệu. • Cơ cấu nhập (input mechanism): là bộ phận có thể đọc input file từ trái sang phải, một ký tự tại một thời điểm. Nó cũng có thể dò tìm được điểm kết thúc của chuỗi nhập (oef, #). 52 6.1 Các khái niệm Automat • Bộ nhớ tạm (temporary storage): là thiết bị gồm một số không giới hạn ô nhớ (cell), mỗi ô có thể giữ 1 ký hiệu từ một bảng chữ cái (không cần giống bảng chữ cái nhập). Automat có thể đọc và thay đổi nội dung của các ô nhớ này. • Đơn vị điều khiển (Control Unit): mỗi automat có một đơn vị điều khiển, cái mà có thể ở trong 1 trạng thái bất kỳ trong một số hữu hạn các trạng thái nội, và có thể chuyển đổi trạng thái trong một kiểu được định nghĩa sẵn có nào đó.53 6.1 Các khái niệm Automat • Hoạt động của Automat: – Tại một thời điểm bất kỳ đã cho, đơn vị điều khiển đang ở trong một trạng thái nội (internal state) nào đó, và cơ cấu nhập là đang quét (scanning) một ký hiệu cụ thể nào đó trên Input file. – Trạng thái nội của đơn vị điều khiển tại thời điểm kế tiếp được xác định bởi trạng thái kế (next state) hay bởi hàm chuyển trạng thái (transition function). – Trong suốt quá trình chuyển trạng thái từ khoảng thời gian này đến khoảng thời gian kế, kết quả (output) có thể được sinh ra và thông tin trong bộ nhớ lưu trữ có thể được thay đổi. 54 6.1 Các khái niệm Automat • Một số định nghĩa khác: – Trạng thái nội: là một trạng thái của đơn vị điều khiển mà nó có thể đạt được. – Trạng thái kế: là một trạng thái nội của đơn vị điều khiển mà nó sẽ đạt tới ở thời điểm kế tiếp. – Hàm chuyển trạng thái: là hàm gởi ra trạng thái kế của automat dựa trên trạng thái hiện hành, ký hiệu nhập hiện hành được quét, và thông tin hiện hành trong bộ nhớ tạm. 55 6.1 Các khái niệm Automat • Một số định nghĩa khác: – Cấu hình (configuration): được sử dụng để tham khảo đến bộ thông tin: » Trạng thái cụ thể mà đơn bị điều khiển đang có » Vị trí của cơ cấu nhập trên thiết bị nhập. » Nội dung hiện hành của bộ nhớ tạm – Di chuyển (move): là sự chuyển trạng thái của automat từ một cấu hình này sang cấu hình kế tiếp. 56 6.2 Phân loại và ứng dụng • Dựa vào hoạt động của Automat, có đơn định hay không: – Automat đơn định (Deterministic Automat): là automat trong đó mỗi di chuyển (move) được xác định duy nhất bởi cấu hình hiện tại. Sự duy nhất này thể hiện tính đơn định. – Automat không đơn định (non-deterministic automat): là automat mà tại mỗi thời điểm có một vài khả năng lựa chọn để di chuyển. Việc có một vài khả năng lựa chọn thể hiện tính không đơn định. 57 6.2 Phân loại và ứng dụng • Dựa vào kết quả xuất ra của automat: – Accepter: là automat mà đáp ứng ở ngõ ra của nó được giới hạn trong hai trạng thái đơn giả “yest” hay “no”. “yes” tương ứng với việc chấp nhận chuỗi nhập, “no” tương ứng với việc từ chối, không chấp nhận chuỗi nhập. – Transducer: là automat tổng quát hơn, có khả năng sinh ra các chuỗi ký tự ở đầu ra. Máy tính số là một transducer điển hình. 58 6.2 Phân loại và ứng dụng • Một vài ứng dụng: – Cung cấp kiến thức nền tảng cho việc xây dựng các ngôn ngữ lập trình, chương trình dịch. – Ứng dụng vào các lĩnh vực xử lý chuỗi: • Các chức năng tìm kiếm, thay thế trong các trình soạn thảo • Sửa lỗi chính tả, chú thích từ loại – Ứng dụng vào lĩnh vực thiết kế số. – 59 6.3 Automat hữu hạn đơn định (DFA) • Định nghĩa: – Một Automat hữu hạn đơn định (deterministic finite state accepter) hay DFA được định nghĩa bởi bộ năm: M= (Q,Σ, δ , q0 ,F).  Q là một tập hữu hạn các trạng thái nội  Σ là một tập hữu hạn các ký hiệu được gọi là bảng chữ cái nhập.  δ: Q x Σ -> Q là hàm chuyển trạng thái.  q0 Є Q là trạng thái khởi đầu.  F Є Q là một tập trạng thái kết thúc, hay còn gọi là trạng thái chấp nhận. 60 Chú ý: Automat hữu hạn không có bộ nhớ so với mô hình tổng quát 6.3 Automat hữu hạn đơn định (DFA) • Hoạt động của một DFA: – Tại thời điểm khởi đầu, nó được giả thiết ở trong trạng thái khởi đầu q0 với cơ cấu nhập đang ở ký hiệu đầu tiên bên trái của chuỗi nhập. – Mỗi lần di chuyển, cơ cấu nhập tiến về phía phải 1 ký hiệu và lấy ra. – Khi gặp ký hiệu kết thúc, chuỗi được chấp nhận nếu automat đang ở vào 1 trong các trạng thái chấp nhận được của nó. Ngược lại thì chuỗi nhập bị từ chối. 61 6.3 Automat hữu hạn đơn định (DFA) • Để biểu diễn trực quan cho DFA, dùng đồ thị chuyển trạng thái: – Các đỉnh biểu diễn các trạng thái – Các cạnh biểu diễn các chuyển trạng thái – Các nhãn trên các định là tên các trạng thái – Các nhãn trên các cạnh là giá trị hiện tại của ký hiệu nhập – Trạng thái khởi đầu sẽ được nhận biết rằng một mũi tên đi vào không mang nhãn mà không xuất phát từ định nào. – Các trạng thái kết thúc được vẽ bằng vòng tròn đôi 62 6.3 Automat hữu hạn đơn định (DFA) • Cho DFA: M= (Q,Σ, δ , q0 ,F). Q={ q0,q1,q2}, Σ={0,1}, F{q1}, δ được cho bởi: δ (q0,0) = q0, δ (q0,1) = q1 δ (q1,0) = q0 δ (q1,0) = q2 δ (q2,0) = q2 δ (q2,0) = q1 • Đồ thị chuyển trạng thái tương ứng 63 6.3 Automat hữu hạn đơn định (DFA) • Hàm chuyển trạng thái mở rộng δ* được định nghĩa đệ quy như sau: • δ* (q, λ) =q, • δ* (q, wa) = δ(δ*(q, w),a) , với q Є Q, w Є Σ* và a Є Σ • Ví dụ: • Nếu δ (q0, a) =q1 và δ (q1, b) =q2 • Thì δ*(q0, ab) =q2 64 6.3 Automat hữu hạn đơn định (DFA) • Định nghĩa 2: – Ngôn ngữ được chấp nhận bởi DFA M= (Q,Σ, δ , q0 ,F). Là tập tất cả các chuỗi trên Σ được chấp nhận bởi M. – L(M)= {w Є Σ*: δ*(q0 ,w) Є F}. 65 6.3 Automat hữu hạn đơn định (DFA) • Ví dụ: – Xét DFA M sau: – DFA trên chấp nhận ngôn ngữ sau: L(M)= {anb: n>=0} – Trạng thái bẫy: là trạng thái mà sau khi automat đi vào thì sẽ không bao giờ thoát ra được. 66 6.3 Automat hữu hạn đơn định (DFA) • Bảng truyền (transition table) – Là bảng trong đó các nhãn của hàng biểu diễn cho trạng thái hiện tại, còn nhãn của cột biểu diễn cho ký hiệu nhập hiện tại. Các điểm nhập trong bảng định nghĩa cho trạng thái kế tiếp. 67 6.3 Automat hữu hạn đơn định (DFA) • Ví dụ: Tìm DFA chấp nhận ngôn ngữ – Tìm DFA M1 chấp nhận tập tất cả các chuỗi trên Σ={a,b} được bắt đầu bằng chuỗi ab. – Tìm DFA M2 chấp nhận tất cả các chuỗi trên Σ={0,1}, ngoại trừ những chuỗi chứa chuỗi con 001. 68 6.3 Automat hữu hạn đơn định (DFA) • Bài tập 1: chuỗi nào được đón nhận: 0001, 01001, 0000110 • Bài tập 2: Xây dựng DFA sao cho – Tất cả các chuỗi chỉ có 1 ký tự a – Tất cả các chuỗi có ít nhất 1 ký tự a – Tất cả các chuỗi không có nhiều hơn 3 ký tự a 69 0 q 0 0 1 q 1 1 1 0 q 2 6.4 Automat hữu hạn không đơn định (NFA) • Định nghĩa: Một Automat hữu hạn không đơn định (nondeterministic finite state accepter) hay NFA được định nghĩa bằng bộ năm: M= (Q,Σ, δ , q0 ,F). Trong đó Q,Σ, q0 ,F được định nghĩa như đối với Accepter hữu hạn đơn định còn δ được định nghĩa là: δ : Q x (Σ υ {λ}) → 2Q 70 6.4 Automat hữu hạn không đơn định • Nhận xét: – Miền giá trị của δ là tập 2Q , vì vậy giá trị của nó không còn là 1 phần tử đơn của Q mà là tập con của Q. Ví dụ: δ(q1, a) = {q0 , q2}. Đặc biệt tập con này có thể là rỗng -> cấu hình chết. – λ được coi như đối số thứ 2 của δ nên NFA có thể thực hiện dịch chuyển mà không cần có ký tự nhập. – NFA cũng được biểu diễn bằng đồ thị chuyển trạng thái. 71 6.4 Automat hữu hạn không đơn định • Ví dụ: • Hàm chuyển trạng thái mở rộng: – Cho một NFA, hàm chuyển trạng thái mở rộng được định nghĩa sao cho δ*(qi,w) chứa qj nếu và chỉ nếu có một con đường trong đồ thị đi từ qi đến qj mang nhãn w. Điều này đúng với mọi qi, qj ЄQ và w Є Σ* 72 6.4 Automat hữu hạn không đơn định • Ví dụ hàm chuyển mở rộng: • Với T là tập con của Q, định nghĩa: 73 6.4 Automat hữu hạn không đơn định • Bảng truyền NFA: – Tập trạng thái S = {0, 1,2, 3}; Σ = {a, b}; Trạng thái bắt đầu so = 0; tập trạng thái kết thúc F = {3}. 74 6.4 Automat hữu hạn không đơn định • Ngôn ngữ của NFA: Ngôn ngữ được chấp nhận bởi NFA M= (Q,Σ, δ , q0 ,F), được định nghĩa như một tập các chuỗi được chấp nhận bởi NFA trên. Một cách hình thức: • Ví dụ: – Ngôn ngữ được chấp nhận bởi automat dưới là L={(10)n :n>=0} 75 6.4 Automat hữu hạn không đơn định • Bài tập NFA: Biểu diễn NFA N bằng sơ đồ chuyển và bảng truyền. N chấp nhận ngôn ngữ L={w|w Є {0, 1}* và kết thúc bởi 01} Σ={q0,q1,q2}, q0, F{q2}. 76 6.5 Chuyển từ NFA sang DFA 6.5.1 Sự tương đương giữa NFA và DFA 6.5.2 Chuyển từ NFA sang DFA 77 6.5.1 Sự tương đương giữa NFA và DFA • Sự tương đương giữa hai automat – Hai automat được gọi là tương đương nhau nếu chúng cùng chấp nhận một ngôn ngữ như nhau. • Ví dụ: – DFA và NFA sau là tương đương nhau vì cùng chấp nhận ngôn ngữ {(10)n : n>=0} 78 6.5.1 Sự tương đương giữa NFA và DFA • Nhận xét: – DFA bản chất là một loại của NFA. – Một NFA thì sẽ có một DFA tương đương với nó. – Mọi ngôn ngữ được chấp nhận bởi NFA thì cũng sẽ được chấp nhận bởi DFA. – Xây dựng NFA thường dễ dàng hơn. – Trong thực tế, số trạng thái của DFA xấp xỉ NFA, nhưng thường có nhiều hàm truyền hơn. – Trong trường hợp xấu nhất, nếu cùng chấp nhận một ngôn ngữ: NFA có n trạng thái thì DFA có 2n trạng thái. 79 6.5.1 Sự tương đương giữa NFA và DFA • Định lý về sự tương đương: – Cho L là ngôn ngữ được chấp nhận bởi một Automat hữu hạn không đơn định MN = (QN, Σ, δN, q0, FN) thì tồn tại một automat hữu hạnh đơn định MD = (QD, Σ, δD, {q0}, FD) sao cho L=L(MD). • Chú ý: – Một trạng thái của NFA là một tập trạng thái của DFA – Trạng thái kết thúc của NFA là trạng thái mà có chứa trạng thái kết thúc của DFA. 80 6.5.2 Chuyển từ NFA sang DFA • Thủ tục chuyển NFA thành DFA: – Input: nfa MN = (QN, Σ, δN, q0, FN) – Output: ĐTCTT GD của DFA MD • B1: Tạo một đồ thị GD với định khởi đầu là tập δN * (q0 λ) • B2: Lặp lại Bước 3 đến Bước 6 cho đến khi không còn cạnh nào thiếu. • B3: Lấy một đỉnh bất kỳ {qi, qj,qk } của GD mà có 1 cạnh còn chưa được định nghĩa đối với một a nào đó của Σ. • B4: Tính δN * ({qi, qj,qk } , a) = {ql, qm,qn }. • B5: Tạo một đỉnh cho GD có nhãn {ql, qm,qn } nếu nó chưa tồn tại. • B6: Thêm vào GD một cạnh từ {qi, qj,qk } đến {ql, qm,qn } và gán nhãn cho nó bằng a. • B7: Mỗi trạng thái của GD mà nhãn của nó chứa một qf bất kỳ thuộc FN thì được coi là một đỉnh kết thúc. 81 6.5.2 Chuyển từ NFA sang DFA • Ví dụ: Hãy biến đổi NFA dưới thành DFA tương đương 82 6.5.2 Chuyển từ NFA sang DFA 83 6.5.2 Chuyển từ NFA sang DFA 84 Kiểm tra • Biến đổi những NFA sau thành DFA tương đương 85 86 Nội dung 1. Vai trò của bộ phân tích từ vựng 2. Lữu trữ tạm chương trình nguồn 3. Đặc tả Token 4. Nhận dạng Token 5. Sơ đồ dịch 6. Automat hữu hạn 7. Từ biểu thức chính quy đến NFA 8. Thiết kế bộ sinh bộ PTTV 7. Từ biểu thức chính quy đến NFA • Nhắc lại về BTCQ: – Mô tả chính xác các từ tố trong NNLT – Mỗi loại từ tố được mô tả bằng một BTCQ 87 a λ R|S RS R* L(a) = {a} – tập hợp gồm xâu “a” L(λ) = {λ} – tập hợp gồm xâu rỗng L(R|S) = L(R) L(S) – hợp của L(R) và L(S) L(RS) = {xy | x L(R), y L(S)} – nối 2 xâu bất kì của L(R) và L(S) L(R*) = L(λ|R|RR|RRR|RRRR ) – nối các xâu của L(R) lại với nhau 7. Từ biểu thức chính quy đến NFA 88 R+ R? [abcd] [a-z] [^abc] [^a-z] L(R+) = L(R*) \ {λ} – R* loại bỏ xâu rỗng L(R?) = L(R|λ) L([abcd]) = L(a|b|c|d) L([a-z]) = L(a|b|..|z) L([^abc]) = kí tự bất kì không thuộc L([abc]) L([^a-z]) = kí tự bất kì không thuộc L([a-z]) Một số quy ước với BTCQ 7. Từ biểu thức chính quy đến NFA • Ví dụ BTCQ: 89 Biểu thức chính quy (RE) Xâu thuộc ngôn ngữ a ab a | b (ab)* (a | ε) b (a+b.c)* “a” “ab” “a”, “b” “”, “ab”, “abab” “ab”, “b” Λ,a, bc,aa, abc, bca, bcbc,aaa , aabc, 7. Từ biểu thức chính quy đến NFA • Định nghĩa hình thức cho BTCQ: – Cho Σ là một bảng chữ cái, khi đó: 1. λ và a Є Σ tất cả đều là những BTCQ nguyên thủy. 2. Nếu r1 và r2 là những BTCQ thì r1+r2, r1.r2, r1* và (r1) cũng là BTCQ 3. Một chuỗi là một BTCQ nếu và chỉ nếu nó có thể được dẫn xuất từ các BTCQ nguyên thủy bằng một số lần hữu hạn áp dụng 2. 90 7. Từ biểu thức chính quy đến NFA • Định lý: – Cho r là một BTCQ, thì tồn tại một NFA chấp nhận L(r). • Bổ đề: – Với mọi NFA có nhiều hơn một trạng thái kết thúc thì luôn luôn có một NFA tương đương với chỉ một trạng thái kết thúc. 91 7. Từ biểu thức chính quy đến NFA • Thủ tục chuyển đổi từ RE sang NFA: – Input: Biểu thức chính quy r – Output: NFA M= (Q,Σ, δ , q0 ,F). 1. Xây dựng các NFA cho các BTCQ nguyên thủy 92 (a) NFA chấp nhận {λ} (b) NFA chấp nhận {a} 7. Từ biểu thức chính quy đến NFA • Thủ tục chuyển đổi từ RE sang NFA: 2. Xây dựng các NFA cho các BTCQ phức tạp: • NFA cho BTCQ r1+ r2 (r1|r2): Giả sử N(r1) và N(r2) là NFA cho biểu thức chính quy r1 và r2 93 hoặc 7. Từ biểu thức chính quy đến NFA • Xây dựng NFA cho các biểu thức phức tạp: – NFA cho BTCQ r1r2: – NFA cho BTCQ r*: 94 hoặc hoặc 7. Từ biểu thức chính quy đến NFA • Ví dụ: Tìm NFA chấp nhận L(r), trong đó: r = (a + bb)* (ba* + λ). 95 automat chấp nhận L((a + bb)* (ba* + λ). 7. Từ biểu thức chính quy đến NFA • Bài tập: – Xây dựng NFA cho các BTCQ sau: 96 97 Nội dung 1. Vai trò của bộ phân tích từ vựng 2. Lữu trữ tạm chương trình nguồn 3. Đặc tả Token 4. Nhận dạng Token 5. Sơ đồ dịch 6. Automat hữu hạn 7. Từ biểu thức chính quy đến NFA 8. Thiết kế bộ sinh bộ PTTV 8. Thiết kế bộ sinh bộ PTTV • Đặc điểm bộ PTTV: – Chương trình PTTV chuyển đổi mã nguồn thành một dãy các từ tố – RE có thể mô tả từ tố một cách chính xác – RE và thứ tự ưu tiên có thể chuyển thành bộ PTTV qua 2 bước: 1. Chuyển RE  NFA 2. Chuyển NFA  DFA (nếu có thể, tối ưu hóa DFA) – Kết quả: Bộ PTTV ngắn gọn và dễ bảo trì • Các chương trình sinh bộ PTTV đã có sẵn và miễn phí. Ví dụ như Lex. 98 8. Thiết kế bộ sinh bộ PTTV • Đặc tả chương trình PTTV: – Là đầu vào cho các chương trình sinh ra chương trình phân tích từ vựng • Danh sách REs theo thứ tự ưu tiên • Hành động gắn liền với mỗi RE khi chương trình PTTV nhận dạng được một từ tố bằng RE đó – Đầu ra của các chương trình này là một chương trình PTTV có thể • Đọc chương trình nguồn và tách nó ra thành các từ tố bằng cách nhận dạng REs • Thông báo lỗi nếu gặp phải kí tự không đúng theo REs 99 8. Thiết kế bộ sinh bộ PTTV • Đặc tả của LEX: Khai báo %% Quy tắc dịch %% Các thủ tục phụ 100 Bao gồm khai báo biến, hằng và các định nghĩa chính quy. Có dạng pi {action i }. pi là các biểu thức chính quy, action i là đoạn chương trình mô tả hành động của bộ phân tích từ vựng thực hiện khi pi tương ứng phù hợp với trị từ vựng. là sự cài đặt các hành động trong phần 2. 8. Thiết kế bộ sinh bộ PTTV • Ví dụ đặc tả chương trình Lex %% digits = 0|[1-9][0-9]* letter = [A-Za-z] identifier = {letter}({letter}|[0-9_])* whitespace = [\ \t\n\r]+ %% {whitespace} {/* discard */} {digits} { return new IntegerConstant(Integer.parseInt(yytext()); } “if” { return new IfToken(); } “while” { return new WhileToken(); } {identifier} { return new IdentifierToken(yytext()); } 101 Tổng kết Bài 3 • Các kiến thức cần nhớ: – Các khái niệm cơ bản: Token, trị từ vựng, – Đặc tả và nhận dạng Token – Các khái niệm BTCQ, Sơ đồ dịch và Automat – Kỹ thuật chuyển đổi trong Automat và BTCQ – Quy trình PTTV – Khái niệm bộ sinh bộ PTTV. • Về nhà đọc thêm: – Cách tối ưu hóa DFA (sách của Aho) – Sử dụng Lex trong Pascal hoặc Java – Cài đặt mã nguồn cho các sơ đồ dịch cơ bản bằng C 102 Bài học phần sau Bài 4: Phân tích cú pháp 103 Thảo luận 104