Trình biên dịch - Chương 3: Phân tích từ vựng

iệu 
num num giá trị số 
< relop LT (Less Than) 
<= relop LE (Less Or Equal) 
= relop EQ (Equal) 
 relop NE (Not Equal) 
> relop GT (Greater Than) 
>= relop GE (Greater Or Equal) 
Hình 3.6 - Mẫu biểu thức chính quy cho một số token 
1. Sơ đồ dịch 
 Ðể dễ dàng nhận dạng token, chúng ta xây dựng cho mỗi token một sơ đồ dịch 
(translation diagram). Sơ đồ dịch bao gồm các trạng thái (state) ký hiệu bởi vòng tròn 
và các cạnh mũi tên nối các trạng thái. 
Nói chung thường có nhiều sơ đồ dịch, mỗi sơ đồ đặc tả một nhóm token. Nếu xảy 
ra thất bại khi chúng ta đang đi theo một sơ đồ dịch thì chúng ta dịch lui con trỏ tới về 
nơi nó đã ở trong trạng thái khởi đầu của sơ đồ này rồi kích họat sơ đồ dịch tiếp theo. 
Do con trỏ đầu trị từ vựng và con trỏ tới cùng chỉ đến một vị trí trong trạng thái khởi 
đầu của sơ đồ, con trỏ tới sẽ được dịch lui lại để chỉ đến vị trí được con trỏ đầu trị từ 
vựng chỉ tới. Nếu xảy ra thất bại trong tất cả mọi sơ đồ dịch thì xem như một lỗi từ 
vựng đã được phát hiện và chúng ta sẽ khởi động một thủ tục khắc phục lỗi. 
Phần dưới đây trình bày một số sơ đồ dịch nhận dạng các token trong văn phạm ví 
dụ trên. 
Sơ đồ dịch nhận dạng cho token relop: 
0 1 2
3
4
5
6 7
8
< start =
return( relop, LE ) 
>
return( relop, NE ) 
return( relop, LT ) 
other
*
= 
return( relop, EQ )> 
=
other
return( relop, GE ) 
return( relop, GT ) 
*
Hình 3.7 - Sơ đồ dịch cho các toán tử quan hệ 
Chúng ta dùng ký hiệu * để chỉ ra những trạng thái mà chúng ta đã đọc quá một ký 
tự, cần phải quay lui con trỏ lại. 
Sơ đồ dịch nhận dạng token id: 
 57
 9 
start 
10 11
otherletter *
letter or digit 
return( gettoken(), install_id() ) 
Hình 3.8 - Sơ đồ dịch cho các danh biểu và từ khóa 
Một kỹ thuật đơn giản để tách từ khóa ra khỏi các danh biểu là khởi tạo bảng ký 
hiệu lưu trữ thông tin về danh biểu một cách thích hợp. Ðối với các token cần nhận 
dạng trong văn phạm này, chúng ta cần nhập các chuỗi if, then và else vào bảng ký 
hiệu trước khi đọc các ký hiệu trong bộ đệm nguyên liệu. Ðồng thời ghi chú trong 
bảng ký hiệu để trả về token đó khi một trong các chuỗi này được nhận ra. Sử dụng 
các hàm gettoken( ) và install_id( ) tương ứng để nhận token và các thuộc tính trả về. 
Sơ đồ dịch nhận dạng token num: 
Một số vấn đề sẽ nảy sinh khi chúng ta xây dựng bộ nhận dạng cho các số không 
dấu. Trị từ vựng cho một token num phải là trị từ vựng dài nhất có thể được. Do đó, 
việc thử nhận dạng số trên các sơ đồ dịch phải theo thứ tự từ sơ đồ nhận dạng số dài 
nhất. 
+ or -
17
digit 
18 
digit 
other 
1912 
start digit 
13 
digit
14
digit
15
digit
E
16
E digit
*•
20
start digit
21
digit
22
 digit
23
digit
24 
other * •
25
digit
26
digit
27
other *start 
Hình 3.9 - Sơ đồ dịch cho các số không dấu trong Pascal 
Có nhiều cách để tránh các đối sánh dư thừa trong các sơ đồ dịch trên. Một cách là 
viết lại các sơ đồ dịch bằng cách tổ hợp chúng thành một - một công việc nói chung là 
không đơn giản lắm. Một cách khác là thay đổi cách đáp ứng với thất bại trong qua 
trình duyệt qua một sơ đồ. Phương pháp được sử dụng ở đây là cho phép ta vượt qua 
nhiều trạng thái kiểm nhận và quay trở lại trạng thái kiểm nhận cuối cùng đã đi qua khi 
thất bại xảy ra. 
Sơ đồ dịch nhận dạng khoảng trắng ws (white space): 
Việc xử lý các khoảng trắng ws không hoàn toàn giống như các mẫu nói trên bởi 
vì không có gì để trả về cho bộ phân tích cú pháp khi tìm thấy các khoảng trắng trong 
 58
chuỗi nhập. Và do đó, thao tác đơn giản cho việc dò tìm trên sơ đồ dịch khi phát hiện 
khoảng trắng là trở lại trạng thái bắt đầu của sơ đồ dịch đầu tiên để tìm một mẫu khác. 
28
delim
29
delim
30
other *start 
Hình 3.10 - Sơ đồ dịch cho các khoảng trắng 
2. Cài đặt một sơ đồ dịch 
 Dãy các sơ đồ dịch có thể được chuyển thành một chương trình để tìm kiếm token 
được đặc tả bằng các sơ đồ. Mỗi trạng thái tương ứng với một đoạn mã chương trình. 
Nếu có các cạnh đi ra từ trạng thái thì đọc một ký tự và tùy thuộc vào ký tự đó mà đi 
đến trạng thái khác. Ta dùng hàm nextchar( ) đọc một ký tự từ trong bộ đệm input và 
con trỏ p2 di chuyển sang phải một ký tự. Nếu không có một cạnh đi ra từ trạng thái 
hiện hành phù hợp với ký tự vừa đọc thì con trỏ p2 phải quay lại vị trí của p1 để 
chuyển sang sơ đồ dịch kế tiếp. Hàm fail( ) sẽ làm nhiệm vụ này. Nếu không có sơ đồ 
nào khác để thử, fail( ) sẽ gọi một thủ tục khắc phục lỗi. 
Ðể trả về các token, chúng ta dùng một biến tòan cục lexical_value. Nó được gán 
cho các con trỏ được các hàm install_id( ) và install_num( ) trả về, tương ứng khi tìm 
ra một danh biểu hoặc một số. Lớp token được trả về bởi thủ tục chính của bộ phân 
tích từ vựng có tên là nexttoken( ). 
int state = 0, start = 0; 
int lexical_value; /* để “trả về” thành phần thứ hai của token */ 
int fail ( ) 
{ 
 forward = token_beginning; 
 switch (start) { 
 case 0 : start = 9; break; 
 case 9 : start = 12; break; 
 case 12 : start = 20; break; 
 case 20 : start = 25; break; 
 case 25 : recover ( ); break; 
 default : / * lỗi trình biên dịch */ 
 } 
return start; 
} 
 token nexttoken ( ) 
 59
 { while (1) { 
 switch (state) { 
 case 0 : c = nextchar ( ) ; / * c là ký hiệu đọc trước */ 
 if ( c = = blank || c = = tab || c = = newline ) { 
 state = 0; 
 lexeme_beginning ++ ; / * dịch con trỏ đến đầu trị từ vựng */ 
 } 
 else if (c = = ‘ < ’) state = 1; 
 else if (c = = ‘ = ’) state = 5; 
 else if (c = = ‘ > ’) state = 6; 
 else state = fail ( ) ; break ; 
. . . / * các trường hợp 1- 8 ở đây */ 
[ case 9 : c = nextchar ( ) ; 
 if (isletter (c)) state=10; 
 else state = fail ( ) ; break ; 
 case 10 : c = nextchar ( ) ; 
 if (isletter (c)) state=10; 
 else if (isdigit(c)) state = 10 ; 
 else state = 11 ; break ; 
 case 11 : retract (1) ; install_id ( ) ; 
 return (gettoken ( )); 
. . . / * các trường hợp 12 - 24 ở đây */ 
 case 25 : c = nextchar ( ) ; 
 if (isdigit (c)) state=26; 
 else state = fail ( ) ; break ; 
 case 26 : c = nextchar ( ) ; 
 if (isdigit (c)) state=26; 
 else state = 27 ; break ; 
 case 27 : retract (1) ; install_num ( ) ; 
 return (NUM); 
 60
 } 
 } 
} 
V. NGÔN NGỮ ÐẶC TẢ CHO BỘ PHÂN TÍCH TỪ VỰNG 
1. Bộ sinh bộ phân tích từ vựng 
 Có nhiều công cụ để xây dựng bộ phân tích từ vựng dựa vào các biểu thức chính 
quy. Lex là một công cụ được sử dụng rộng rãi để tạo bộ phân tích từ vựng. 
 Trước hết đặc tả cho một bộ phân tích từ vựng được chuẩn bị bằng cách tạo ra một 
chương trình lex.l trong ngôn ngữ lex. Trình biên dịch Lex sẽ dịch lex.l thành một 
chương trình C là lex.yy.c. Chương trình này bao gồm các đặc tả về sơ đồ dịch được 
xây dựng từ các biểu thức chính quy của lex.l, kết hợp với các thủ tục chuẩn nhận dạng 
trị từ vựng. Các hành vi kết hợp với biểu thức chính quy trong lex.l là các đoạn 
chương trình C được chuyển sang lex.yy.c. Cuối cùng trình biên dịch C sẽ dịch 
lex.yy.c thành chương trình đối tượng a.out, đó là bộ phân tích từ vựng có thể chuyển 
dòng nhập thành chuỗi các token. 
Lex Compiler Chương trình nguồn 
của lex: lex.l 
Lex.yy.c 
C Compiler 
a.out 
Lex.yy.c 
Chuỗi nhập 
a.out 
Chuỗi các 
token
Hình 3.11 - Tạo ra bộ phân tích từ vựng bằng Lex 
Chú ý: Những điều ta nói trên là nói về lex trong UNIX. Ngày nay có nhiều 
version của lex như Lex cho Pascal hoặc Javalex. 
2. Ðặc tả lex 
 Một chương trình lex bao gồm 3 thành phần: 
Khai báo 
%% 
Quy tắc dịch 
%% 
Các thủ tục phụ 
Phần khai báo bao gồm khai báo biến, hằng và các định nghĩa chính quy. 
Phần quy tắc dịch cho các lệnh có dạng: 
p1 {action 1 } 
 61
p2 {action 2 } 
 . . . 
pn {action n } 
Trong đó pi là các biểu thức chính quy, action i là đoạn chương trình mô tả hành 
động của bộ phân tích từ vựng thực hiện khi pi tương ứng phù hợp với trị từ vựng. 
Trong lex các đoạn chương trình này được viết bằng C nhưng nói chung có thể viết 
bằng bất cứ ngôn ngữ nào. 
Các thủ tục phụ là sự cài đặt các hành động trong phần 2. 
Ví dụ 3.8: Sau đây trình bày một chương trình Lex nhận dạng các token của văn 
phạm đã nêu ở phần trước và trả về token được tìm thấy. 
%{ 
/* định nghĩa các hằng 
LT, LE, EQ, NE, GT, GE, IF, THEN, ELSE, ID, NUMBER, RELOP */ 
}% 
/* đị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}+)? 
%% 
{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) } 
%% 
 62
 install_id ( ) { 
 /* Thủ tục phụ cài id vào trong bảng ký hiệu */ 
 } 
 install_num ( ) { 
 /* Thủ tục phụ cài một số vào trong bảng ký hiệu */ 
 } 
 63
BÀI TẬP CHƯƠNG III 
3.1. Xác định bộ chữ cái của các ngôn ngữ sau: 
a) Pascal 
b) C 
c) LISP 
3.2. Hãy xác định các trị từ vựng có thể hình thành các token trong các đoạn chương 
trình sau: 
a) PASCAL 
 function max (i, j :integer) : integer; 
 { Trả về số nguyên lớn hơn trong 2 số i và j } 
 begin 
 i > j then max : = i 
 else max : = j; 
 end; 
b) C 
 int max (i, j) int i, j; /* Trả về số nguyên lớn hơn trong 2 số i và j */ 
 { return i > j ? i : j 
 } 
c) FORTRAN 77 
 FUNCTION MAX (i, j) 
 C Trả về số nguyên lớn hơn trong 2 số i và j 
 IF ( I .GT. J) THEN 
 MAX = I 
 ELSE 
 MAX = J 
 END IF 
 RETURN 
 64
3.3. Viết một chương trình Lex sao chép một tập tin, thay các chuỗi khoảng trắng 
thành một khoảng trắng duy nhất. 
3.4. Viết một đặc tả Lex cho các token của ngôn ngữ Pascal và dùng trình biên dịch 
Lex để xây dựng một bộ phân tích từ vựng cho Pascal. 
 65