›
›

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

•Một số khái niệm

•Token: Một token là một tập hợp các xâu kí tự có một nghĩa xác định, ví dụ identifier token là tập hợp tất cả các identifier. Token chính là các kí hiệu kết thúc (terminal) trong định nghĩa văn phạm của một ngôn ngữ, ví dụ: Các từ khoá, định danh, toán tử, hằng, xâu kí tự, dấu ngoặc đơn, dấu phẩy, dấu chấm phẩy...

•Pattern: Pattern của một token là các qui tắc kết hợp các kí tự để tạo lên token đó

•Lexeme: Là một chuỗi  các kí tự thoả mãn pattern của một token


 

ppt 31 trang thamphan 27/12/2022 3120
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Xây dựng chương trình dịch - Chương 2: Phân tích từ vựng", để tải tài liệu gốc về máy hãy click vào nút Download ở trên.

File đính kèm:

  • pptbai_giang_xay_dung_chuong_trinh_dich_chuong_2_phan_tich_tu_v.ppt

Nội dung text: Bài giảng Xây dựng chương trình dịch - Chương 2: Phân tích từ vựng

  1. CHƯƠNG II Phân tích từ vựng Mục tiêu: Nắm được vai trò của giai đoạn phân tích từ vựng, sử dụng các khái niệm biểu thức chính qui (regular expression) và ô- tô- mát hứu hạn (finite automata) trong việc biểu diễn và nhận biết ngôn ngữ 1
  2. • Phân tích từ vựng giúp cho các giai đoạn biên dịch tiếp theo dễ dàng hơn, ví dụ: Giai đoạn phân tích cú pháp không phải quan tâm đến các khoảng trắng cũng như các lời chú trích vì nó đã được loại bỏ khi khi phân tích từ vựng • Giảm đáng kể thời gian đọc chương trình nguồn và nhóm thành các token nhờ một số chương trình xử lí chuyên dụng 3
  3. • Bảng sau đưa ra các ví dụ về token, pattern và lexeme Token Lexeme Thông tin mô tả của pattern const const const if if if relation , >=, =, hoặc >= hoặc = hoặc <> id pi, count, d2 một kí tự, tiếp theo là các kí tự hoặc chữ số num 3.1416, 0, 6.02E2 bất kì hằng số nào literal "computer" các kí tự nằm giữa " và " ngoại trừ " 5
  4. • Các phép toán trên ngôn ngữ: Giả sử L và M là hai ngôn ngữ khi đó Hợp (union)của L và M: LM={s|s L hoặc s M } Ghép (concatenation) của L và M: LM = { st | s L và t M } i Bao đóng Kleen (kleene closure) L: L* = i=0 L (Ghép của 0 hoặc nhiều L) + i Bao đóng dương (positive closure) của L: L = i=1 L (Ghép của 1 hoặc nhiều L) 7
  5. Biểu thức chính qui (regular expression) • Mỗi biểu thức chính qui (BTCQ) r dùng để đặc tả một ngôn ngữ L(r). Ví dụ: Trong pascal mọi identifier được đặc tả bởi biểu thức chính qui letter(letter|digit)* • Hai BTCQ r và s được gọi là tương đương (kí hiệu r=s) nếu chúng đặc tả chung một ngôn ngữ Ví dụ: (a|b)=(b|a) • Một BTCQ được xây dựng từ những BTCQ đơn giản bằng cách sử dụng các luật 9
  6. Ví dụ: Cho = { a, b}. 1. BTCQ a | b đặc tả {a, b} 2. BTCQ (a | b) (a | b) đặc tả {aa, ab, ba, bb}.Tập hợp này có thể được đặc tả bởi BTCQ tương đương sau: aa | ab | ba | bb 3. BTCQ a* đặc tả {, a, aa, aaa, } 4. BTCQ (a | b)* đặc tả {a, b, aa,bb, }. Tập hợp này có thể đặc tả bởi (a*b* )* 5. BTCQ a | a* b đặc tả {a, b, ab, aab, } 11
  7. Ví dụ: ĐNCQ của các định danh trong pascal là letter → A | B | | Z | a | b | | z digit → 0 | 1 | | 9 id → letter (letter | digit)* Ví dụ: ĐNCQ của các số không dấu trong pascal như 3254, 23.243E5,16.264E-3 là digit → 0 | 1 | | 9 digits → digit digit* optional_fraction → . digits | e optional_exponent → ( E ( + | - | e ) digits) | e num → digits optional_fraction optional_exponent 13
  8. Nhận dạng token • Làm thế nào để nhận dạng được token? Ta sẽ xét 1 ví dụ mang tính chất minh hoạ Ví dụ: Cho ngữ pháp (grammar) stmt → if expr then stmt | if expr then stmt else stmt |  expr → term relop term | term term → id | num 15
  9. • Mục đích của lexical analyzer tạo ra output là các cặp Regular Expression Token Attribute-value ws - - if if - then then - else else - id id pointer to table entry num num pointer to table entry relop NE > relop GT >= relop GE 17
  10. Ví dụ: Sơ đồ chuyển tiếp cho token các toán tử quan hệ relop start 3 return (relop, NE) other * 4 return (relop, LT) = 5 return (relop, EQ) > 6 = 7 return (relop, GE) other * 8 return (relop, GT) 19
  11. Ví dụ: Sơ đồ chuyển tiếp cho token các unsigned numbers trong pascal digit digit digit * start digit . digit E + or - digit other 12 13 14 15 16 17 18 19 E digit digit digit start digit . digit other * 20 21 22 23 24 digit start digit other * 25 26 27 21
  12. Công cụ phân tích từ vựng Lex • Một số công cụ có sẵn cho phép xây dựng một bộ phân tích từ vựng dựa trên các biểu thức chính qui • Một trong số những công cụ đó là Lex compiler (một công cụ có sẵn của Unix) • Sơ đồ sau chỉ rõ cách tạo một bộ phân tích từ vựng bằng cách sử dụng Lex 23
  13. Ô- tô- mát hữu hạn (finite automata) • Một bộ nhận dạng ngôn ngữ (recognizer for a language) là một chương trình nhận đầu vào là một xâu kí tự x, trả lời "Yes" nếu x thuộc ngôn ngữ và trả lời "No" nếu ngược lại • Ô- tô- mát hữu hạn là một sơ đồ chuyển tiếp được khái quát hoá, đóng vai trò là recognizer cho các biểu thức chính qui • Một Ô- tô- mát hữu hạn có thể là deterministic finite automata (DFA) hoặc nondeterministic finite automata (NFA) 25
  14. NFA • Một NFA là một mô hình toán học bao gồm: - Một tập hợp trạng thái S - Một trạng thái bắt đầu s0 S - Một tập hợp các trạng thái chấp nhận (hoặc trạng thái kết thúc) FS - Một tập hợp kí tự vào của bảng chữ cái  - Một hàm chuyển đổi trạng thái move: S x ({})→S (Một phép chuyển đổi (sk, ) → sj nghĩa là chuyển từ sk sang sj mặc dù không có kí tự nào được đọc vào) • NFA được biểu diễn trực tiếp bằng sơ đồ chuyển tiếp 27
  15. Ví dụ: NFA nhận biết biểu thức chính qui aa* | bb* a a 1 2  start 0 b  b 3 4 29
  16. Ví dụ: DFA nhận biết BTCQ (a|b)*abb a b a start 0 1 2 3 a b b a b 31