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

Thêm vào BST

Báo xấu

95
lượt xem 9
download

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ủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

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

Nguyễn Phương Thái Bộ môn Khoa học Máy tính http://www.coltech.vnu.vn/~thainp/
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
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
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 “∗”, “
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
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
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
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
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
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 ⇒minimalstate 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
Ứ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
Ứ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
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
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
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
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
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
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
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
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