Một chương trình dịch biểu thức đơn giản
Sử dụng các kỹ thuật nêu trên, chúng ta xây dựng một bộ dịch trực tiếp cú pháp mà nó dịch một biểu thức số học đơn giản từ trung tố sang hậu tố. Ta bắt đầu với các biểu thức là các chữ số viết cách nhau bởi + hoặc -. Xét lược đồ dịch ...
Sử dụng các kỹ thuật nêu trên, chúng ta xây dựng một bộ dịch trực tiếp cú pháp mà nó dịch một biểu thức số học đơn giản từ trung tố sang hậu tố. Ta bắt đầu với các biểu thức là các chữ số viết cách nhau bởi + hoặc -.
Xét lược đồ dịch cho dạng biểu thức này :
Văn phạm nền tảng cho lược đồ dịch trên có chứa luật sinh đệ qui trái, bộ phân tích cú pháp dự đoán không xử lý được văn phạm dạng này, cho nên ta cần loại bỏ đệ quy trái bằng cách đưa vào một ký hiệu chưa kết thúc mới rest để được văn phạm thích hợp như sau:
expr → term rest
rest → + term { print(‘+’) } rest | - term {print(‘-’) rest | ε
term → 0 { print(‘0’) }
term → 1 { print(‘1’) }
...
term → 9 { print(‘9’) }
Hình sau đây mô tả quá trình dịch biểu thức 9 - 5 + 2 dựa vào lược đồ dịch trên:
Bây giờ ta cài đặt chương trình dịch bằng C theo đặc tả như trên. Phần chính của chương trình này là các đoạn mã C cho các hàm expr, term và rest.
// Hàm expr( ) tương ứng với ký hiệu chưa kết thúc expr
expr( )
{
term( ) ; rest( );
}
// Hàm expr( ) tương ứng với ký hiệu chưa kết thúc expr
rest( )
{
if (lookahead = = ‘+’ ) {
match(‘+’) ; term( ) ; putchar (‘+ ‘) ; rest( );
}
else if (lookahead = = ‘-’) {
match(‘-’) ; term( ) ; putchar (‘-’) ; rest( );
}
else ;
}
// Hàm expr( ) tương ứng với ký hiệu chưa kết thúc expr
term( )
{
if (isdigit (lookahead) {
putchar (lookahead); match (lookahead);
}
else error( );
}
Tối ưu hóa chương trình dịch
Một số lời gọi đệ quy có thể được thay thế bằng các vòng lặp để làm cho chương trình thực hiện nhanh hơn. Ðoạn mã cho rest có thể được viết lại như sau :
rest( )
{
L : if (lookahead = = ‘+’ ) {
match(‘+’) ; term( ) ; putchar (‘+ ‘) ; goto L;
}
else if (lookahead = = ‘-’) {
match(‘-’) ; term( ) ; putchar (‘-’) ; goto L;
}
else ;
}
Nhờ sự thay thế này, hai hàm rest và expr có thể được tích hợp lại thành một.
Mặt khác, trong C, một câu lệnh stmt có thể được thực hiện lặp đi lặp lại bằng cách viết : while (1) stmt với 1 là điều kiện hằng đúng. Chúng ta cũng có thể thóat khỏi vòng lặp dễ dàng bằng lệnh break.
Đoạn chương trình có thể được viết lại như sau :
expr ( )
{
term ( )
while (1)
if (lookahead = = ‘+’ ) {
match(‘+’) ; term( ) ; putchar (‘+ ‘) ;
}
else if (lookahead = = ‘-’) {
match(‘-’) ; term( ) ; putchar (‘-’) ;
}
else break;
}
Chương trình C dịch biểu thức trung tố sang hậu tố
Chương trình nguồn C hoàn chỉnh cho chương trình dịch có mã như sau :
# include< ctype.h> /* nạp tập tin chứa isdigit vào*/
int lookahead;
main ( )
{
lookahead = getchar( );
expr( ) ; putchar(‘ ‘); /* thêm vào ký tự xuống hàng */
}
expr( )
{
term( );
while(1)
if (lookahead = = ‘+’)
{ match(‘+’); term( ); putchar(‘+ ‘); }
else if (lookahead = = ‘-’ )
{ match(‘-’); term( ); putchar(‘-’); }
else break;
}
term( )
{
if (isdigit(lookahead))
{ putchar(lookahead); match(lookahead); }
else error( );
}
match ( int t)
{
if (lookahead = = t)
lookahead = getchar();
else error( );
}
error( )
{
printf (“syntax error ”); /* in ra thông báo lỗi */
exit(1); /* rồi kết thúc */
}
