Trình biên dịch - Chương 2: Một trình biên dịch đơn giản

ột số và DONE là 
ký tự cuối tập tin eof. Các khoảng trắng đã được loại bỏ. Bảng sau trình bày các token 
và giá trị thuộc tính được sinh ra bởi bộ phân tích từ vựng cho mỗi token trong chương 
trình nguồn. 
Thủ tục phân tích cú pháp parser.c 
 Bộ phân tích cú pháp được xây dựng theo phương pháp phân tích đệ quy xuống. 
Trước tiên, ta loại bỏ đệ quy trái ra khỏi lược đồ dịch bằng cách thêm vào 2 biến mới 
R1 cho expr và R2 cho factor, thu được lược đồ dịch mới như sau: 
 start → list eof 
 38
 list → expr ; list 
| ε 
 expr → term R1 
 R1 → + term { print (‘ + ’) } R1 
 | - term { print (‘ - ’) } R1 
 | ε 
 term → factor R2 
 R2 → * factor { print (‘ * ’) } R2 
 | / factor { print (‘ / ’) } R2 
 | DIV factor { print (‘DIV’) } R2 
 | MOD factor { print (‘MOD’) }R2 
 | ε 
 factor → ( expr ) 
 | id { print (id.lexeme) } 
 | num { print (num.value) } 
Sau đó, chúng ta xây dựng các hàm cho các ký hiệu chưa kết thúc expr, term và 
factor. Hàm parse( ) cài đặt ký hiệu bắt đầu start của văn phạm, nó gọi lexan mỗi khi 
cần một token mới. Bộ phân tích cú pháp ở giai đoạn này sử dụng hàm emit để sinh ra 
kết quả và hàm error để ghi nhận một lỗi cú pháp. 
Thủ tục kết xuất emitter.c 
 Thủ tục này chỉ có một hàm emit (t, tval) sinh ra kết quả cho token t với giá trị 
thuộc tính tval. 
Thủ tục quản lý bảng ký hiệu symbol.c và khởi tạo init.c 
 Thủ tục symbol.c cài đặt cấu trúc dữ liệu cho bảng danh biểu. Các ô trong mảng 
symtable là các cặp gồm một con trỏ chỉ đến mảng lexemes và một số nguyên biểu thị 
cho token được lưu tại vị trí đó. 
Thủ tục init.c được dùng để khởi gán các từ khóa vào bảng danh biểu. Biểu diễn 
trị từ vựng và token cho tất cả các từ khóa được lưu trong mảng keywords cùng kiểu 
với mảng symtable. Hàm init( ) duyệt lần lượt qua mảng keyword, sử dụng hàm insert 
để đặt các từ khóa vào bảng danh biểu. 
Thủ tục lỗi error.c 
 Thủ tục này quản lý các ghi nhận lỗi và hết sức cần thiết. Khi gặp một lỗi cú pháp, 
trình biên dịch in ra một thông báo cho biết rằng một lỗi đã xảy ra trên dòng nhập hiện 
hành và dừng lại. Một kỹ thuật khắc phục lỗi tốt hơn có thể sẽ nhảy qua dấu chấm 
phẩy kế tiếp và tiếp tục phân tích câu lệnh sau đó. 
2. Cài đặt chương trình nguồn 
Chương trình nguồn C cài đặt chương trình dịch trên. 
 39
/ **** global.h ***************************************** / 
# include /* tải các thủ tục xuất nhập */ 
# include /* tải các thủ tục kiểm tra ký tự */ 
# define BSIZE 128 /* buffer size kích thước vùng đệm */ 
# define NONE - 1 
# define EOS ' \ 0 ' 
# define NUM 256 
# define DIV 257 
# define MOD 258 
# define ID 259 
# define DONE 260 
int tokenval; /* giá trị cuả thuôcü tính token */ 
int lineno; 
struct entry { /* khuôn dạng cho ô trong bảng ký hiệu*/ 
 char * lexptr; 
 int token; 
} 
struct entry symtable[ ] /* bảng ký hiệu*/ 
/ **** lexer.c ***************************************** / 
# include "global.h" 
char lexbuf [BSIZE] 
int lineno = 1; 
int tokenval = NONE; 
int lexan ( ) /* bộ phân tích từ vựng */ 
{ 
 int t; 
 while(1) { 
 t = getchar ( ); 
 if ( t = = ‘ ‘ || t = = ‘ \t’) ; /* xóa các khoảng trắng */ 
 else if (t = = ‘ \n ’) 
lineno = lineno + 1; 
 else if ( isdigit (t) ) { /* t là một ký số */ 
 ungetc (t, stdin); 
scanf (" %d", & tokenval); 
 return NUM; 
 } 
else if ( isalpha (t) ) { /* t là một chữ cái */ 
 40
int p, b = 0; 
 while ( isalnum (t) ) { /* t thuộc loại chữ - số */ 
 lexbuf[b] = t; 
 t = getchar ( ); 
 b = b + 1; 
 if (b > = BSIZE) 
 error("compiler error"); 
 } 
 lexbuf[b] = EOS; 
 if (t ! = EOF) 
 ungetc (t, stdin); 
 p = lookup (lexbuf); 
 if (p = = 0) 
 p = insert (lexbuf, ID) 
 tokenval = p; 
 return symtable[p].token; 
 } 
 else if (t = = EOF) { 
return DONE; 
 else { 
 tokenval = NONE; 
return t; 
 } 
 } 
 } 
/ **** parser.c ***************************************** / 
# include "global.h" 
int lookahead; 
parse ( ) /* phân tích cú pháp và dịch danh sách biểu thức */ 
{ 
lookahead = lexan ( ); 
while (lookahead ! = DONE) { 
expr( ) ; match (‘ ; ’); 
 } 
} 
expr ( ) 
{ 
 int t; 
term ( ); 
 while(1) 
 switch (lookahead) { 
 case ' + ' : case ' - ' : 
 t = lookahead; 
 41
 match (lookahead); term ( ); emit (t, NONE); 
 continue; 
 default : 
 return; 
 } 
} 
term ( ) 
{ 
 int t; 
factor ( ); 
 while(1) 
 switch (lookahead) { 
 case ' * ' : case ' / ' : case ' DIV ' : case 'MOD ' : 
 t = lookahead; 
 match (lookahead); factor ( ); emit (t, NONE); 
 continue; 
 default : 
 return; 
 } 
} 
factor ( ) 
{ 
 switch (lookahead) { 
 case ' ( ' : 
 match (' ( '); expr ( ); match (' ) '); break; 
 case NUM : 
 emit (NUM, tokenval) ; match (' NUM '); break; 
 case ID : 
 emit (ID, tokenval) ; match (' ID '); break; 
 default : 
 error ( "syntax error"); 
 } 
} 
match ( t ) 
 int t; 
{ 
 if (lookahead = = t) 
lookahead = lexan( ); 
 else error ("syntax error"); 
} 
/ **** emitter.c ***************************************** / 
# include "global.h" 
 42
emit (t, tval) /* tạo ra kết quả */ 
 int t, tval; 
{ 
switch ( t ) { 
 case ' + ' : case ' - ' : case ' * ' : case ' / ' : 
 printf (" %c \n", t); break; 
 case DIV : 
 printf (" DIV \n", t); break; 
 case MOD : 
 printf (" MOD \n", t); break; 
 case NUM : 
 printf (" %d \n", tval ); break; 
 case ID : 
 printf (" %s \n", symtable [tval]. lexptr); break; 
 default : 
 printf (" token %d , tokenval %d \n ", t, tval ); 
 } 
} 
/ **** symbol.c ***************************************** / 
# include "global.h" 
# define STRMAX 999 /* kích thước mảng lexemes */ 
# define SYMMAX 100 /* kích thước mảng symtable */ 
char lexemes [STRMAX]; 
int lastchar = -1 /* vị trí được dùng cuối cùng trong lexemes */ 
struct entry symtable [SYMMAX]; 
int lastentry = 0 /* vị trí được dùng cuối cùng trong symtable */ 
int lookup (s) /* trả về vị trí của ô cho s */ 
 char s [ ]; 
{ 
 int p; 
 for (p = lastentry; p > 0; p = p - 1) 
 if (strcmp (symtable[p].lexptr, s ) = = 0) 
 return p; 
 return 0; 
} 
int insert (s, tok) /* trả về vị trí của ô cho s */ 
 char s [ ]; 
 int tok; 
{ 
 int len; 
 len = strlen (s) /* strlen tính chiều dài của s */ 
 43
 if ( lastentry + 1 > = SYMMAX) 
 error ("symbol table full"); 
 if ( lastchar + len + 1 > = SYMMAX) 
 error ("lexemes array full"); 
 lastentry = lastentry + 1; 
 symable [lastentry].token = tok; 
 symable [lastentry].lexptr = &lexemes [lastchar + 1]; 
 lastchar = lastchar + len + 1; 
 strcpy (symable [lastentry].lexptr, s); 
 return lastentry; 
} 
/ **** init.c ***************************************** / 
# include "global.h" 
struct entry keyword [ ] = { 
 "div", DIV 
 "mod", MOD 
 0, 0 
} 
init ( ) /* đưa các từ khóa vào symtable */ 
{ 
 struct entry * p ; 
for (p = keywords; p → token; p ++ ) 
 if (strcmp (symtable[p].lexptr, s ) = = 0) 
 insert (p → lexptr, p → token) ; 
} 
/ **** error.c ***************************************** / 
# include "global.h" 
eeror (m) /* sinh ra tất cả các thông báo lỗi * / 
 char * m; 
{ 
 fprintf (stderr, " line % d : % s \n, lineno, m) 
 exit ( 1 ) /* kết thúc không thàình công * / 
} 
/ **** main.c ***************************************** / 
# include "global.h" 
main ( ) 
{ 
 44
 init ( ); 
 parse ( ); 
 exit (0); /* kết thúc thàình công * / 
} 
/ ****************************************************************** / 
 45
BÀI TẬP CHƯƠNG II 
2.1. Cho văn phạm phi ngữ cảnh sau: 
 S → S S + | S S * | a 
 a) Viết các luật sinh dẫn ra câu nhập: a a + a * 
 b) Xây dựng một cây phân tích cú pháp cho câu nhập trên? 
 c) Văn phạm này sinh ra ngôn ngữ gì? Giải thích câu trả lời. 
2.2. Ngôn ngữ gì sinh ra từ các văn phạm sau? Văn phạm nào là văn phạm mơ hồ? 
a) S → 0 S 1 | 0 1 
 b) S → + S S | - S S | a 
c) S → S ( S ) S | ∈ 
d) S → a S b S | b S a S | ∈ 
e) S → a | S + S | S S | S * | ( S ) 
2.3. Xây dựng văn phạm phi ngữ cảnh đơn nghĩa cho các ngôn ngữ sau đây: 
a) Các biểu thức số học dưới dạng hậu tố. 
b) Danh sách danh biểu có tính kết hợp trái được phân cách bởi dấu phẩy. 
c) Danh sách danh biểu có tính kết hợp phải được phân cách bởi dấu phẩy. 
d) Các biểu thức số học của số nguyên và danh biểu với 4 phép toán hai ngôi : 
+. -, *, /. 
2.4. Viết chỉ thị máy ảo kiểu Stack cho quá trình dịch các biểu thức sau sang dạng 
hậu tố: 
a) t : = (a mod b) * 1998 - (2000 * c +100 ) div 4 +1999 
b) t : = a1 mod c2 + ( b3 -156 * d4 ) div 7 / 3 
c) y := x + 100 z 3 t 
2.5. Xây dựng lược đồ dịch trực tiếp cú pháp để dịch một biểu thức số học từ dạng 
trung tố sang dạng hậu tố ( cho các phép toán 2 ngôi ). 
a) Xây dựng chương trình đổi mã hậu tố sang mã máy ảo kiểu Stack . 
b) Viết chương trình thực thi mã máy ảo . 
 46
2.6. Yêu cầu như bài 5 cho biểu thức số học ở dạng hậu tố sang dạng trung tố. 
2.7. Xây dựng một lược đồ dịch trực tiếp cú pháp để xác định rằng các dấu ngoặc 
trong một chuỗi nhập là cân bằng. 
2.8. Xây dựng lược đồ dịch trực tiếp cú pháp để dịch phát biểu FOR của ngôn ngữ C 
có dạng như sau: FOR ( exp1; exp2; exp3 ) Stmt sang dạng mà máy ảo kiểu Stack. 
Viết chương trình thực thi mã máy ảo kiểu Stack . 
2.9. Xét đoạn văn phạm sau đây cho các câu lệnh if-then và if-then-else: 
 Stmt → if expr then stmt 
 | if expr then stmt else stmt 
 | other 
 a) Chứng tỏ văn phạm này là văn phạm mơ hồ. 
 b) Xây dựng một văn phạm không mơ hồ tương đương với quy tắc: mỗi else 
chưa được kết hợp sẽ được kết hợp với then chưa kết hợp gần nhất trước đó. 
 c) Xây dựng một lược đồ dịch trực tiếp cú pháp để dịch các câu lệnh điều kiện 
thành mã máy ảo kiểu Stack. 
2.10. Xây dựng lược đồ dịch trực tiếp cú pháp để dịch các phát biểu của ngôn ngữ 
PASCAL có dạng như sau sang dạng mà máy ảo kiểu Stack. Viết chương trình thực 
thi mã máy ảo kiểu Stack: 
a) REPEAT Stmt UNTIL expr 
 b) IF expr THEN Stmt ELSE Stmt 
 c) WHILE expr DO Stmt 
 d) FOR i := expr1 downto expr2 DO Stmt 
 47