Kết nối các kỹ thuật
Trong các phần trên, chúng ta đã trình bày một số kỹ thuật phiên dịch trực tiếp cú pháp để xây dựng kỳ đầu của trình biên dịch. Phần này sẽ thực hiện việc kết nối chúng lại bằng cách giới thiệu một chương trình C có chức năng dịch trung tố - ...
Trong các phần trên, chúng ta đã trình bày một số kỹ thuật phiên dịch trực tiếp cú pháp để xây dựng kỳ đầu của trình biên dịch. Phần này sẽ thực hiện việc kết nối chúng lại bằng cách giới thiệu một chương trình C có chức năng dịch trung tố - hậu tố cho một ngôn ngữ gồm dãy các biểu thức kết thúc bằng các dấu chấm phẩy. Các biểu thức gồm có các số, danh biểu, các toán tử +, -, *, /, div và mod. Output cho chương trình là dạng biểu diễn hậu tố cho mỗi biểu thức.
Mô tả chương trình dịch
Chương trình dịch được thiết kế bằng cách dùng lược đồ dịch trực tiếp cú pháp có dạng như sau :
start → list eof
list → expr ; list
| ε
expr → expr + term { print (‘+ ’) }
| expr - term { print (‘- ’) }
| term
term → term * factor { print (‘* ’) }
| term / factor { print (‘/ ’) }
| term div factor { print (‘DIV’) }
| term mod factor { print (‘MOD’) }
| factor
factor → ( expr )
| id { print (id.lexeme) }
| num { print (num.value) }
Trong đó, token id biểu diễn một dãy không rỗng gồm các chữ cái và ký số bắt đầu bằng một chữ cái, num là dãy ký số, eof là ký tự cuối tập tin (end - of - file). Các token được phân cách bởi một dãy ký tự blank, tab và newline - gọi chung là các khoảng trắng (white space). Thuộc tính lexeme của token id là chuỗi ký tự tạo ra token dó, thuộc tính value của token num chứa số nguyên được biểu diễn bởi num.
Ðoạn mã cho chương trình dịch bao gồm 7 thủ tục, mỗi thủ tục được lưu trong một tập tin riêng. Ðiểm bắt đầu thực thi chương trình nằm trong thủ tục chính main.c gồm có một lời gọi đến init( ) để khởi gán, theo sau là một lời gọi đến parse( ) để dịch. Các thủ tục còn lại được mô tả tổng quan như hình sau:
Trước khi trình bày đoạn mã lệnh cho chương trình dịch, chúng ta mô tả sơ lược từng thủ tục và cách xây dựng chúng.
Thủ tục phân tích từ vựng lexer.c
Bộ phân tích từ vựng là một thủ tục có tên lexan( ) được gọi từ bộ phân tích cú pháp khi cần tìm các token. Thủ tục này đọc từng ký tự trong dòng nhập, trả về token vừa xác định được cho bộ phân tích cú pháp. Giá trị của các thuộc tính đi kèm với token được gán cho biến toàn cục tokenval. Bộ phân tích cú pháp có thể nhận được các token sau : + - * / DIV MOD ( ) ID NUM DONE
| Trị từ vựng | Token | Giá trị thuộc tính |
| Khoảng trắng | ||
| Chuỗi các chữ số | NUM | Giá trị số |
| Div | DIV | |
| Mod | MOD | |
| Chuỗi mở đầu là chữ cái, theo sau là chữ cái hoặc chữ số | ID | Chỉ số trong symtable |
| Ký tự cuối tập tin - eof | DONE | |
| Các ký tự khác | Ký tự tương ứng | NONE |
Trong đó ID biểu diễn cho một danh biểu, NUM biểu diễn cho mộ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
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 đó.
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.
/ **** global.h***************************************** /
# include <stdio.h> /* tải các thủ tục xuất nhập */
# include <ctype.h> /* 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 = = ‘ ’) ; /* xóa các khoảng trắng */
else if (t = = ‘ ’)
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 */
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;
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"
emit (t, tval) /* tạo ra kết quả */
int t, tval;
{
switch ( t ) {
case ' + ' : case ' - ' : case ' * ' : case ' / ' :
printf (" %c ", t); break;
case DIV :
printf (" DIV ", t); break;
case MOD :
printf (" MOD ", t); break;
case NUM :
printf (" %d ", tval ); break;
case ID :
printf (" %s ", symtable [tval]. lexptr); break;
default :
printf (" token %d , tokenval %d ", 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 */
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 , lineno, m)
exit ( 1 ) /* kết thúc không thàình công * /
}
/ **** main.c ***************************************** /
# include "global.h"
main ( )
{
init ( );
parse ( );
exit (0); /* kết thúc thành công * /
}
