tailieunhanh - ctd_chuong_2_phan_tich_tu_vung_5655

CHƯƠNG II. Phân tích từ vựngMục tiêu: Nắm được vai trò của giai đoạn từ vựng, sử dụng các khái niệm biểu qui (regular expression) và ô- tô- hạn (finite automata) trong việc biểu nhận biết ngôn ngữ. 1 Vai trò của phân tích từ vựng.• Đây là giai đoạn đầu tiên của quá trình biên dịch.• Nhiệm vụ chính: Đọc từng kí tự vào (input. characters) từ chương trình nguồn và nhóm lại. thành các token phục vụ cho giai đoạn phân tích cú. pháp sau đó Source Lexical Token. Parser. program analyzer. Get next token. Symbol. table. 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 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. 4 • Bảng sau đưa ra các ví dụ về token, pattern và. lexeme Token Lexeme Thông tin mô tả của patternconst const if , =, =, 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ữ , 0, bất kì hằng số "computer" các kí tự nằm giữa " và " ngoại trừ " 5 Đặc tả Token.• Xâu kí tự (string): Là một chuỗi các kí tự từ một. bảng chữ cái. Kí hiệu xâu rỗng là.• Một số khái niệm liên quan đến xâu kí tự: Tiền tố. (prefix), hậu tố (suffix), xâu con (substring), tiền. tố thực sự (proper prefix).• Ngôn ngữ (language): Là tập hợp các xâu kí tự. được xây dựng từ một bảng chữ cái. 6• 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}. Bao đóng Kleen (kleene closure) L: L* = i=0 Li (Ghép của 0 hoặc nhiều L). Bao đóng dương (positive closure) của L: L+ = i=1 Li. (Ghép của 1 hoặc nhiều L). 7Ví dụ: L = {A, B, ., Z, a, b, ., z } và. D = { 0, 1, , ., 9 }. 1. L D là tập hợp các chữ cái và chữ số. 2. LD là tập hợp các xâu bao gồm một chữ cái và một. chữ số. 3. L4 là tập hợp tất cả các xâu 4 chữ cái. 4. L * là tâp hợp tất cả các xâu của các chữ cái bao. gồm cả chuỗi rỗng. 5. L(L D)* là tập hợp tất cả các xâu mở đầu bằng. một chữ cái theo sau là chữ cái hay chữ số. 6. D+ là tập hợp tất cả các xâu gồm một hoặc nhiều. chữ số 8 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ú

• Lịch sử - Văn hoá