Bài giảng Chương trình dịch - Bài 5: Tự động sinh bộ PTTV - Trương Xuân Nam

CHƯƠNG TRÌNH DỊCH
 Bài 5: Tự động sinh bộ PTTV
Nội dung
1. Giải bài tập của các buổi trước
2. Giới thiệu về LEX
3. CsLex – phiên bản LEX cho C#
 TRƯƠNG XUÂN NAM 2
Phần 1
Giải bài tập của các buổi trước
 TRƯƠNG XUÂN NAM 3
Phần 2
Giới thiệu về LEX
 TRƯƠNG XUÂN NAM 4
Từ patterns đến scanner
 TRƯƠNG XUÂN NAM 5
Các bước để tạo một bộ PTTV
. Các bước để tạo một bộ PTTV:
 1. Định nghĩa từ loại ở dạng các RE
 2. Chuyển các RE thành một NFA duy nhất
 3. Chuyển NFA thành DFA
 4. Tối ưu hóa DFA
 5. Viết mã xử lý DFA
 6. Xử lý các tình huống nhập nhằng hoặc đặc biệt
. Tự viết bộ PTTV (ad-hoc analyser): tự làm tất cả 
 các bước trên
. Sử dụng LEX: làm bước 1 và bước 6, LEX làm các 
 bước còn lại
 TRƯƠNG XUÂN NAM 6
LEX: cách làm việc
 TRƯƠNG XUÂN NAM 7
LEX: đầu vào
 TRƯƠNG XUÂN NAM 8
Ví dụ về LEX
. Cho ngôn ngữ X có văn phạm như sau:
 stmt → if expr then stmt else stmt
 | if expr then stmt | ε
 expr → term relop term | term
 term → id | num
. Các từ loại:
 if → if
 then → then
 else → else
 relop → | > | >=
 id → letter (letter | digit)*
 num → digit+ (. digit+)? (E (+ | -)? digit+)?
 delim → blank | tab | newline
 ws → delim+
 TRƯƠNG XUÂN NAM 9
Ví dụ về LEX
%{
/* đoạn mã định nghĩa các hằng: LT, LE, EQ, NE, GT, GE, IF, THEN, 
ELSE, ID, NUMBER, RELOP */
#define LT 0
#define LE 1
}%
/* định nghĩa chính quy */
delim [\t\n]
ws {delim}+
letter [A - Za - z]
digit [0 - 9]
id {letter}({letter}| {digit})*
number {digit}+(\.{digit}+)?(E[+\-]?{digit}+)?
 TRƯƠNG XUÂN NAM 10
Ví dụ về LEX
%%
/* xử lý khi gặp các ký hiệu */
{ws} {/* Không có action, không có return */}
if {return(IF); }
then {return(THEN); }
else {return(ELSE); }
{id} {yylval = install_id( ); return(ID) }
{number} {yylval = install_num( ); return(NUMBER) }
"<" {yylval = LT; return(RELOP) }
"<=" {yylval = LE; return(RELOP) }
"=" {yylval = EQ; return(RELOP) }
"" {yylval = NE; return(RELOP) }
">" {yylval = GT; return(RELOP) }
">=" {yylval = GE; return(RELOP) }
 TRƯƠNG XUÂN NAM 11
Ví dụ về LEX
%%
/* các thủ tục bổ sung, viết bằng ngôn ngữ C */
/* Thủ tục phụ cài id vào trong bảng ký hiệu */
install_id ( ) {
}
/* Thủ tục phụ cài một số vào trong bảng ký hiệu */
install_num ( ) {
}
 TRƯƠNG XUÂN NAM 12
Phần 3
CsLex – phiên bản LEX cho 
C#
 TRƯƠNG XUÂN NAM 13
CsLex
. Cũng tương tự như Lex, nhưng sử dụng ngôn ngữ 
 C# để làm việc
. Phiên bản gần nhất có thể tìm thấy trên GitHub, yêu 
 cầu lớp về tìm hiểu để có thể làm bài thực hành
. Cấu trúc file input tương tự như Lex, nhưng có điều 
 chỉnh cho phù hợp với C#
 user code
 %%
 CsLex directives
 %%
 regular expression rules
 TRƯƠNG XUÂN NAM 14