Bộ phân tích từ vựng và ôtômat hữu hạn môn Chương trình dịch | Trường Đại học Bách Khoa Hà Nội

Định danh Dấu phép gán := lOMoAR cPSD| 59421307 Ôtômat hữu hạn
• Ôtômat hữu hạn (máy hữu hạn trạng thái là mô hình ược
ứng dụng trong nhiều lĩnh vực như kỹ thuật, mạng, xử lý ngôn ngữ
• Nguyên tắc làm việc: Thay ổi trạng thái căn cứ vào trạng
thái hiện hành và tín hiệu iều khiển
• Trong kỹ thuật, ôtômat hữu hạn ược dùng ể iều khiển
máy bán hàng tự ộng, thang máy, biểu diễn mạch, mô tả
giao thức truyền thông…
• Trong compiler, ôtômat hữu hạn là mô hình cho bộ phân tích từ vựng
• Bộ sinh phân tích từ vựng là một phần của bộ sinh
compiler. Đầu vào là các biểu thức chính quy mô tả các
luật từ vựng. Đầu râ là chương trình phân tích từ vựng.
Quá trình biến ổi từ biểu thức chính quy sang code òi lOMoAR cPSD| 59421307
hỏi qua nhiều bước trung gian. Tại mỗi bước trung gian,
mô hình ôtômat hữu hạn ược dung ể biến ổi lOMoAR cPSD| 59421307 ược kiểm
ặt ra là mọi người chỉ lOMoAR cPSD| 59421307
ược mở khi có người ưng ở vùng sau vì sẽ lOMoAR cPSD| 59421307
Sơ ồ trạng thái của ôtômat hữu hạn
• Đồ thị ịnh hướng với các ỉnh là các trạng thái, các
cung có nhãn là các ký hiệu vào
• Trạng thái ầu có mũi tên với nhãn “ ầu”
• Các trạng thái kết thúc ược ký hiệu bằng vòng tròn kép.
• Ôtômat hữu hạn ơn ịnh (ÔHĐ): Với mọi ký hiệu a Σ
tồn tại nhiều nhất một cung nhãn a xuất phát từ b mỗi trạng thái. a,c,d b,c,d Start C O a 9 lOMoAR cPSD| 59421307
Nhận biết các từ tố của KPL
• Ngôn ngữ chứa các từ tố là ngôn ngữ chính quy. Nó
có thể ược oán nhận bởi một ôtômat hữu hạn
• Mô hình ôtômat hữu hạn có nhiều loại: ơn ịnh,
không ơn ịnh, có dịch chuyển …
• Mô hình ôtômat hữu hạn ể code bộ phân tích từ
vựng là ôtômat hữu hạn ơn ịnh (ÔHĐ) 10 lOMoAR cPSD| 59421307
Định nghĩa hình thức của ôtômat hữu hạn ơn ịnh
• Xuất phát từ 1 trạng thái có tối a 1 cung ứng với mỗi ký hiệu ược xét.
• Khi phải xét hoạt ộng của một ôtômat hữu hạn trên
máy tính, cần phải mô tả nó ở dạng máy ọc ược.
Mô tả hình thức chính là dạng ó.
• Ôtômat hữu hạn ơn ịnh (ÔHĐ) là bộ 5
M = (Q, , , qo, F ),trong ó :
: Bảng chữ hữu hạn - bảng chữ của xâu vào
Q : Tập hữu hạn trạng thái qo Q : Trạng thái ầu
F Q : Tập trạng thái kết thúc : hàm
Q Q gọi là hàm chuyển trạng thái lOMoAR cPSD| 59421307 Hàm chuyển lOMoAR cPSD| 59421307 lOMoAR cPSD| 59421307 lOMoAR cPSD| 59421307 ịnh 15 lOMoAR cPSD| 59421307
Phân loại các ký tự của CT nguồn typedef enum {
CHAR_SPACE, // Khoảng trống CHAR_LETTER, // Chữ cái CHAR_DIGIT, // Chữ số CHAR_PLUS, // ‘+’ CHAR_MINUS, // ‘-’ CHAR_TIMES, // ‘*’ CHAR_SLASH, // ‘/’ CHAR_LT, // ‘<‘ CHAR_GT, // ‘<‘ CHAR_EXCLAIMATION, // ‘!’ CHAR_EQ, // ‘=‘ CHAR_COMMA, // ‘,’ CHAR_PERIOD, // ‘.’ CHAR_COLON, // ‘:’ CHAR_SEMICOLON, // ‘;’
CHAR_SINGLEQUOTE, // ‘\’’ CHAR_LPAR, // ‘(‘ CHAR_RPAR, // ‘)’
CHAR_UNKNOWN // Ký tự không ược phép có mặt trong chương trình } CharCode;
CharCode charCodes[256] ={……} lOMoAR cPSD| 59421307 16 lOMoAR cPSD| 59421307 lOMoAR cPSD| 59421307 Phạm vi sử dụng