TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI
VIỆN ĐÀO TẠO SAU ĐẠI HỌC
=====o0o=====

BÀI TẬP LỚN
MÔN: NGUYÊN LÝ NGÔN NGỮ LẬP TRÌNH

Giáo viên giảng dạy: TS. Nguyễn Hữu Đức

Đề tài: Tìm hiểu bộ công cụ Flex, Bison, ứng dụng trong phân tích từ
Vựng và phân tích cú pháp của một ngôn ngữ nào đó

NHÓM: 10
Lớp: CH2012B

Sinh viên thực hiện:
Nguyễn Thành Đô
Nguyễn Xuân Trường
Trần Văn Trung
Nguyễn Thị Thùy Dương

Hà Nội, tháng 12/2012


I.

GIỚI THIỆU
Ta sẽ phải tốn rất nhiều thời gian để tìm hiểu và xây dựng một trình trình biên dịch hoàn chỉnh một cách

thủ công. Trên thực tế, đã có rất nhiều công cụ có khả năng phát sinh ra bộ phân tích từ vựng và bộ phân tích cú
pháp. Một trong những bộ cổ điển nhất là lex và yacc – được phát minh tại Bell Lab trong thập niên 1970.

Mô

Mô tả
Các hằng số với các kiểu dữ liệu (số nguyên, số thực,

CONSTANT

…)

một

1.
tả
số

Chuỗi hằng (ví dụ “hello world”)

STRING_VALUE

Các danh biểu trong chương trình, bao gồm tên biến,

IDENTIFIER

tên hàm (bắt đầu là chữ cái, theo sau là chữ hoặc số)

IF

Lệnh if

ELSE


Hình 1 .Giao thức liên hệ của bộ phân tích từ vựng.


Qua đó, trình phân tích từ vựng sẽ nhận những định nghĩa về token từ trình phân
tích cú pháp và sẽ trả về token phù hợp.
Chính sự giao tiếp đơn giản này đã khiến cho bộ phân tích từ vựng tỏ ra khá độc
lập so với các phần còn lại của trình biên dịch. Theo giao thức đã trình bày ở Hình , trình
phân tích từ vựng chỉ liên hệ trực tiếp với trình phân tích cú pháp trong vai trò như một
thủ tục. Do đó, một sự thay đổi dù lớn hay nhỏ ở trình phân tích từ vựng cũng không gây
ảnh hưởng đến hoạt động chung của trình biên dịch.
Tuy nhiên, có một số trường hợp mà trình phân tích từ vựng, trình phân tích cú
pháp và bảng danh biểu cần có sự liên hệ mật thiết với nhau để xử lý.
Ví dụ 2: Khai báo kiễu dữ liệu do người dùng tự định nghĩa
typedef int Dummy;
Hoặc
struct Dummy
{
int first, second;
};
Từ cấu trúc khai báo trở đi, Dummy khi được sử dụng sẽ không được hiểu là một danh
biểu nữa mà phải là một từ dành riêng, một kiểu dữ liệu do người dùng định nghĩa. Vì vậy,
bộ phân tích từ vựng sẽ trả về một token đặc biệt khác để bộ phân tích cú pháp có thể
nhận dạng Dummy như một kiểu dữ liệu.
Một công việc nữa của bộ phân tích từ vựng là xác định loại hằng số và chuyển
sang dạng lưu trữ thích hợp (từ dạng dữ liệu nhập là chuỗi).
Ví dụ 3: Với các biễu diễn:
0b1010

: biểu diễn nhị phân của số 10

cách xây dựng cây phân tích cú pháp bắt đầu từ nút gốc.
• Phân tích cú pháp từ dưới lên (Bottom-Up Parsing): bộ phân
tích cú pháp sẽ bắt đầu từ chuỗi token và cố gắng tìm kiếm
luật sinh thích hợp để có thể dẫn về ký tự bắt đầu của văn
phạm.

ngôn ngữ nguồn
token
Trình phân tích từ vựng

cây phân tích cú pháp
Trình phân tích cú pháp

biểu diễn trung gian
Phần còn lại của chuyến trước

yêu cầu token

Bảng danh biểu

Hình 2. Vị trí của trình phân tích cú pháp trong chuyến trước của trình biên dịch
IV.

Bộ công cụ Flex và Bison


1. Bộ phát sinh trình phân tích từ vựng FLEX
a.

Cấu trúc.



File mô tả nguồn
lex.l

FLEX Compiler

lex.yy.c

C Compiler

lex.out

lex.out

chuỗi token

Chương trình nguồn

lex.yy.c

Hình 1. Quá trình phân tích từ vựng

Sau khi được phát sinh từ tập biểu thức chính quy, bộ phân tích từ vựng sẽ được định nghĩa như một
hàm trả ra token tiếp theo (TOKEN yylex();). Khi yylex() được gọi, nó sẽ phân tích chương trình nguồn
thành từng đơn vị từ vựng và tìm biểu thức chính quy phù hợp với những đơn vị từ vựng đó. Khi có sự đối sánh
xuất hiện, yylex() sẽ thực hiện phần mã C tương ứng với biểu thức chính quy được chọn.

c. Một số hàm hỗ trợ.
int main() :

thúc bằng ký tự “ nhưng chưa xét tới trường hợp chuỗi có thể chứa ký tự “ ở giữa như
“string with a \” in it”. Rõ ràng đây là chuỗi hợp lệ và ta nhận dạng ký tự ” ở giữa
bằng ký tự \. Do đó, khi yytext[yyleng – 2] == ‘\\’, tức là ký tự trước ký tự nháy kép
là ký tự \ thì ta không dừng lại mà tiếp tục xét chuỗi nhập cho đến khi gặp ký báo hiệu kết
thúc chuỗi thực sự (yymore())
ECHO
Xuất lexeme hiện tại ra màn hình console (stdout).

2.

Bộ phát sinh trình phân tích cú pháp BISON
a. Cấu trúc.

Tương tự như FLEX, Bison nhận input là một file bao gồm các đặc
tả của một ngôn ngữ. Từ đó, Bison biên dịch ra bộ phân tích cú pháp
bằng mã C để chạy cùng với chương trình. Cấu trúc của file đặc tả
ngôn ngữ cũng gồm 3 phần :


- Phần khai báo:
a. Khai báo C thông thường (biến, prototype hàm, cấu trúc, đĩnh

nghĩa...), được giới hạn trong %{ và %} như FLEX.
b. Khai báo kiểu dữ liệu của các thuộc tính tổng hợp.
c. Khai báo các token và các thuộc tính kết hợp với token (nếu
có).
d. Khai báo các thuộc tính kết hợp với các ký hiệu không kết thúc.
Ví dụ 1: Văn phạm thuộc tính của một số ký hiệu không kết thúc trong file input
của Bison.
%union {

Hành vi ngữ nghĩa của Bison là một chuỗi các lệnh mã C với:

•

$$ Giá trị thuộc tính kết hợp với ký hiệu chưa kết thúc bên vế trái

của luật sinh.
• $n Giá trị thuộc tính kết hợp với ký hiệu văn phạm thứ n (ký hiệu kết
thúc hoặc chưa kết thúc) của vế phải.
-

Các hàm hỗ trợ.

Ngôn ngữ chủ yếu để mô tả các luật hình thành nên parser là
CFG (văn phạm phi ngữ cảnh). Và dạng tiêu chuẩn để mô tả một CFG
mà BISON áp dụng là BNF (Backus-Naur Form) [5]– từng được dùng để
miêu tả ngôn ngữ Algol 60.
Ví dụ 3: Mô tả dạng BNF cho ngôn ngữ xây dựng biểu thức đơn giản
<s> ::= <e>
<e> ::= <e> ‘+’<t>
|
<t>
<t> ::= <t> ‘*’ <f>
|
<f>
<f> ::= ‘(‘ <e> ‘)’
|
NUM
Mỗi dòng là một luật sinh chỉ ra cách hình thành nên một
nhánh của cây phân tích cú pháp. Bison đã đơn giản hóa BNF để

Quy trình vận hành.
Bison nhận tập tin mô tả ngữ pháp (luật sinh, luật ngữ nghĩa) để
qua đó phát sinh ra bộ phân tích cú pháp (viết bằng ngôn ngữ C). Bộ
phân tích cú pháp này cũng sẽ được biên dịch chung với chương trình

--defines

và được sử dụng như một thủ tục (yyparse()).

Mô tả tập luật sinh, luật ngữ nghĩa (*.y)

--verbose Bản mô tả các trạng thái (y.out)

Bison

Bản định nghĩa các token
Bộ phân
(yyout.h)
tích cú pháp bằng mã C (yyout.c)

Hình 2. Quá trình phân tích cú pháp của BISON

Khi yyparse() được gọi, nó sẽ dựa vào trạng thái hiện tại và
bảng ACTION-GOTO để chọn ra hành vi thích hợp, đồng thời, thực hiện
luật ngữ nghĩa ứng với văn phạm sau khi rút gọn. Ngoài ra, BISON
cũng có thể tạo ra file định nghĩa các token (đã khai báo) được sử
dụng chung trong trình phân tích từ vựng cũng như trình phân tích cú
pháp.
Phương pháp phân tích dưới lên sử dụng một Stack để lưu trữ thông tin về cây con
đã được phân tích. Chúng ta có thể mở rộng Stack này để lưu trữ giá trị thuộc tính tổng