intTypePromotion=1

Bài giảng Chương trình dịch: Bài giảng 2 - Nguyễn Phương Thái

Chia sẻ: Năm Tháng Tĩnh Lặng | Ngày: | Loại File: PPT | Số trang:51

0
50
lượt xem
6
download

Bài giảng Chương trình dịch: Bài giảng 2 - Nguyễn Phương Thái

Mô tả tài liệu
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng 2 cung cấp các nội dung liên quan đến phân tích từ vựng như: Phân tích từ vựng: từ tố, từ vị, mẫu; giới thiệu về REs, FA (DFA, NFA); nâng cao: REs đến NFA; NFA đến DFA; DFA đến minimal-state DFA;...và một số bài tập. Mời các bạn cùng tham khảo.

Chủ đề:
Lưu

Nội dung Text: Bài giảng Chương trình dịch: Bài giảng 2 - Nguyễn Phương Thái

  1. Nguyễn Phương Thái Bộ môn Khoa học Máy tính http://www.coltech.vnu.vn/~thainp/
  2. 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  15/11/15 Nguyễn Phương Thái ­ Coltech ­ Compiler 2009 2
  3. Vai trò của hệ phân tích từ vựng (scanner) (từ tố) (cây cú pháp) (mã nguồn) (lỗi từ vựng) Từ tố trong ngôn ngữ lập trình cũng giống như từ trong  ngôn ngữ tự nhiên Hệ phân tích từ vựng hoạt động như một thủ tục được  gọi bởi hệ phân tích cú pháp khi nó cần một từ tố mới  trong dòng vào 15/11/15 Nguyễn Phương Thái ­ Coltech ­ Compiler 2009 3
  4. Từ tố (token) Từ tố trong VC được phân loại như sau:  các định danh (vd sum, i, j)  các từ khóa (vd int, if hay while)  các toán tử (vd “+” hay “∗”, “
  5. Từ vị (lexeme) Từ vị của một từ tố: chuỗi ký tự tạo thành từ tố Ví dụ: 15/11/15 Nguyễn Phương Thái ­ Coltech ­ Compiler 2009 5
  6. Mẫu (từ tố)  Mẫu: luật mô tả tập các từ vị mà có thể biểu diễn một từ tố cụ thể  Mẫu khớp với mỗi xâu ký tự trong tập đó Loại từ tố Mẫu Từ vị INTLITERAL a string of decimal digits 127, 0 FLOATLITERAL fill a verbal spec here for C! 127.1, .1, 1.1e2 ID a string of letters, digits and sum, line num underscores beginning with a letter or underscore + the character ‘+’ + while the letters ‘w’, ‘h’, ‘i’, ’l’, ’e’ while  Biểu diễn hình thức cho từ tố là cần thiết ⇒ REs, NFA, DFA 15/11/15 Nguyễn Phương Thái ­ Coltech ­ Compiler 2009 6
  7. Các biểu thức chính qui (REs) cho số nguyên và số thực trong C 15/11/15 Nguyễn Phương Thái ­ Coltech ­ Compiler 2009 7
  8. Các máy hữu hạn trạng thái (FSMs) cho số nguyên và số thực 15/11/15 Nguyễn Phương Thái ­ Coltech ­ Compiler 2009 8
  9. 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  15/11/15 Nguyễn Phương Thái ­ Coltech ­ Compiler 2009 9
  10. REs, DFA và 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) 15/11/15 Nguyễn Phương Thái ­ Coltech ­ Compiler 2009 10
  11. Ứ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.) http://www.robotwisdom.com/net/regexres.html 15/11/15 Nguyễn Phương Thái ­ Coltech ­ Compiler 2009 11
  12. Ứ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 15/11/15 Nguyễn Phương Thái ­ Coltech ­ Compiler 2009 12
  13. 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 {ε} 15/11/15 Nguyễn Phương Thái ­ Coltech ­ Compiler 2009 13
  14. 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 15/11/15 Nguyễn Phương Thái ­ Coltech ­ Compiler 2009 14
  15. Các thuật ngữ về xâu ký tự (Figure 3.7 of Text) Thuật ngữ Định nghĩa Prefix of s (tiền tố của s) a string obtained by removing 0 or more trailing symbols of s Suffix of s (hậu tố của s) a string obtained by removing 0 or more leading symbols of s Substring of s (xâu con của s) a string obtained by deleting a prefix and a suffix from s proper prefix Any nonempty string x that is,  suffix, substring of s (tiền tố, hậu tố, xâu  respectively, con phù hợp (?) của s)  a prefix, suffix or substring of s such that s ≠ x 15/11/15 Nguyễn Phương Thái ­ Coltech ­ Compiler 2009 15
  16. 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 15/11/15 Nguyễn Phương Thái ­ Coltech ­ Compiler 2009 16
  17. Các phép toán trên ngôn ngữ (Figure 3.8 of Text) 15/11/15 Nguyễn Phương Thái ­ Coltech ­ Compiler 2009 17
  18. Ví dụ về các phép toán trên ngôn ngữ 15/11/15 Nguyễn Phương Thái ­ Coltech ­ Compiler 2009 18
  19. Ví dụ về các phép toán trên ngôn ngữ 15/11/15 Nguyễn Phương Thái ­ Coltech ­ Compiler 2009 19
  20. 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 15/11/15 Nguyễn Phương Thái ­ Coltech ­ Compiler 2009 20
ADSENSE
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

 

Đồng bộ tài khoản
2=>2