1
Nghiên cứu tổng quan về chương trình dịch Trần Thị Hoa

Trường Đại học Khoa học Tự nhiên
Khoa Toán – Cơ – Tin học
Luận văn ThS. ngành: Đảm bảo toán học cho máy tính và hệ thống tính toán
Mã số: 60 46 35
Người hướng dẫn: TS. Nguyễn Thị Minh Huyền
Năm bảo vệ: 2012 Abstract. Chương 1: Giới thiệu về chương trình dịch. Chương 2: Phân tích từ vựng,
cú pháp và ngữ nghĩa (ngôn ngữ và văn phạm hình thức; phân tích từ vựng; phân
tích cú pháp; phân tích ngữ nghĩa). Chương 3: Các công cụ hỗ trợ xây dựng chương
trình dịch (bộ sinh trình phân tích từ vựng FLEX, bộ sinh trình phân tích cú pháp
BISON). Chương 4: Xây dựng chương trình dịch cho ngôn ngữ Minipas.

Keywords. Ngôn ngữ lập trình; Ngôn ngữ máy tính; Chương trình dịch; Toán tin;
Hệ thống tính toán

Content

MỞ ĐẦU
Từ ngàn xưa con người muốn giao tiếp với nhau phải dùng ngôn ngữ, vậy người giao
tiếp với máy tính tất nhiên cũng phải thông qua ngôn ngữ. Con người muốn máy tính thực
hiện công việc, thì phải viết các yêu cầu đưa cho máy bằng ngôn ngữ máy có thể hiểu được.
Việc viết các yêu cầu gọi là lập trình. Ngôn ngữ dùng để lập trình được gọi là ngôn ngữ lập

+ Chương III: Các công cụ hỗ trợ xây dựng chương trình dịch.
+Chương IV: Xây dựng chương trình dịch cho ngôn ngữ Minipas.Trong quá trình
nghiên cứu tác giả khó tránh khỏi những sai sót, rất mong nhận được nhiều ý kiến đóng góp
từ các thầy giáo, cô giáo và các bạn đọc để luận văn được hoàn thiện hơn.

Chƣơng 1 - GIỚI THIỆU VỀ CHƢƠNG TRÌNH DỊCH
Chương này trình bày kiến thức tổng quan về chương trình dịch, được trích từ tài liệu
tham khảo [2, 4, 5].
1.1. Chương trình dịch
Chương trình dịch, còn gọi là phần mềm biên dịch, là một chương trình máy tính làm
công việc dịch một chuỗi các câu lệnh được viết bằng một ngôn ngữ lập trình (ngôn ngữ
nguồn hay mã nguồn), thành một chương trình tương đương nhưng ở dưới dạng một ngôn
ngữ mới (gọi là ngôn ngữ đích hay mã đích) và thường là ngôn ngữ ở cấp thấp hơn, như ngôn
ngữ máy.
1.2. Các bước thiết kế chương trình dịch
Chương trình nguồn trong ngôn ngữ lập trình chính là chuỗi các ký tự. Chương trình
dịch có nhiệm vụ chuyển chuỗi ký tự này sang chuỗi ký tự khác. Quá trình này bao gồm các
quá trình nhỏ hơn và được đặt tên như sau:
1.2.1. Phân tích từ vựng
Là công việc đọc chương trình nguồn từ trái sang phải (hay được gọi là quá trình quét
nguyên liệu) để tách ra thành các thẻ từ (token). Nói cách khác, quá trình phân tích từ vựng là
quá trình dịch mà đầu nhập của nó là chuỗi các ký tự, tượng trưng cho chương trình nguồn,
đầu ra là các token. Dạng đầu ra này lại là đầu nhập của quá trình phân tích cú pháp về sau.
1.2.2. Tổ chức bảng ký hiệu
Bảng ký hiệu là một cấu trúc dữ liệu mà mỗi phần tử là một mẫu tin dùng để lưu trữ
một token được bộ phân tích từ vựng nhận biết và các thông tin của token đó, bao gồm các

3
trường lưu giữ ký hiệu và các thuộc tính của nó. Cấu trúc này cho phép chúng ta tìm ra nhanh
chóng mẫu tin của mỗi token và cũng có thể lưu trữ và truy xuất token một cách nhanh

và phân tích ngữ nghĩa. Trước khi đi vào tìm hiểu ba bước trên là nhắc lại kiến thức về ngôn
ngữ và văn phạm được tham khảo từ [1].
2.1. Ngôn ngữ và văn phạm hình thức
2.1.1. Bảng chữ cái
Là một tập hữu hạn các ký hiệu, tập này thường được ký hiệu bằng

.
2.1.2. Chuỗi (từ)

4
Cho

là bảng chữ cái, một chuỗi (hay một từ)
w
trên

là một dãy hữu hạn các ký
hiệu thuộc

được xếp liền kề nhau. Độ dài chuỗi
w
là số các ký hiệu hợp thành
w
và được
ký hiệu là
w
. Chuỗi rỗng ký hiệu là

, là chuỗi có độ dài bằng không.
Tập tất cả các chuỗi trên

*

.
2.1.4. Văn phạm hình thức
Định nghĩa văn phạm: Một văn phạm
),,,( SPNG 
là một bộ bốn, trong đó:
•
N
: là tập hữu hạn các ký hiệu chưa kết thúc hay các biến,
•

: là tập hữu hạn các ký hiệu kết thúc,
•
P
: là tập luật sinh của văn phạm,
•
NS 
: là ký hiệu bắt đầu của văn phạm.
Ngôn ngữ sinh bởi văn phạm: Với văn phạm
G
có ký hiệu bắt đầu
S
. Ta dùng
quan hệ


để định nghĩa
)(GL
là ngôn ngữ được sinh ra bởi

tích cú pháp.
2.1.5.1. Văn phạm chính quy
Một văn phạm
),,,( SPNG 
được gọi là tuyến tính phải nếu tất cả các luật sinh có
dạng:
xBX 
hoặc
xX 
, trong đó:
NBX ,
và
*
x
.
Một văn phạm
),,,( SPNG 
được gọi là tuyến tính trái nếu tất cả các luật sinh có
dạng:
BxX 
hoặc
xX 
, trong đó:
NBX ,
và
*
x
.
Một văn phạm được gọi là văn phạm chính quy nếu nó là văn phạm hoặc tuyến tính
trái hoặc tuyến tính phải.

 Chiến lược phân tích cú pháp từ dưới lên (bottom – up).
2.3.1.1. Chiến lƣợc phân tích từ trên xuống
Cho một văn phạm phi ngữ cảnh
),,,( SPNG 
và một câu cần phân tích
w
. Ta
xuất phát từ điểm khởi đầu, nghĩa là từ
S
, áp dụng các suy dẫn trái, tiến từ trái qua phải thử
tạo ra câu đưa vào phân tích
w
.
Một trong số các thuật toán sử dụng chiến lược phân tích từ trên xuống là thuật toán
phân tích cú pháp Earley
1
.
2.3.1.1.1. Giới thiệu thuật toán Earley
Earley là một thuật toán thuộc loại phân tích cú pháp từ trên xuống và xây dựng các
dẫn xuất trái nhất của chuỗi ký tự nhập. Khi sử dụng thuật toán Earley chúng ta không phải
đưa văn phạm về một dạng chuẩn nào cả.
2.3.1.1.2. Thuật toán phân tích cú pháp Earley
Input: Văn phạm phi ngữ cảnh
),,,( SPNG 
, chuỗi
n
aaaw
21

thuộc

được nữa.

1
http://en.wikipedia.org/wiki/Earley_parser

6
(2) Nếu
 
0,

B
thuộc
0
I
(chú ý:

có thể là

) thì đưa vào trong tập
0
I
mục
 
0,

 BA
cho tất cả các mục có dạng
 
0,


I
sau khi đã có các tập
110
, ,,
j
III

(4) Bước quét (Scan): Với mỗi mục trong
1j
I
có dạng
 
iaB ,


(với
j
aa 
) thì
cho mục
 
iaB ,


vào trong
j
I
. Thực hiện bước (5) và (6) cho đến khi không
còn mục mới được thêm vào.
(5) Bước hoàn thành (Complete): Nếu


là một mục trong
j
I
, tìm trong
P
tất cả
các luật sinh có dạng

B
thì ta thêm mục
 
jB ,


vào
j
I
.
 Kết thúc thuật toán khi
nj 
.
2.3.1.1.3. Độ phức tạp thời gian theo chiều dài chuỗi nhập
Thuật toán có độ phức tạp là 0(
3
n
).
2.3.1.2. Chiến lƣợc phân tích dƣới lên
Quá trình ngược lại với phân tích từ trên xuống, xuất phát từ chính câu cần phân tích
w

(có hình một
tam giác), mỗi phần tử
ij

với
ni 1
và
11  inj
có các giá trị là một tập
con của
N
.
 Một kí hiệu không kết thúc A thuộc
ij

nếu và chỉ nếu
11
*



jiii
aaaA
.
 Chuỗi nhập
w
thuộc ngôn ngữ
)(GL
nếu
n

(4) FOR
1:i
TO
1 jn
DO
BEGIN
(5)
ij

=


(6) FOR
1:k
TO
1j
DO
(7)
ij

:=
ij



{
BCAA |
là một luật sinh,
B


văn phạm và các hành vi ngữ nghĩa nằm trong cặp dấu { } được chèn vào bên phải của luật
sinh.

8
Chƣơng 3 - CÁC CÔNG CỤ HỖ TRỢ XÂY DỰNG CHƢƠNG TRÌNH DỊCH

3.1. Giới thiệu
Trên thực tế, đã có rất nhiều công cụ có khả năng 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.
 Yacc [6] (Yet Another Compiler Compiler) – công trình của Stephen
C. Johnson được ra đời sớm hơn, có nhiệm vụ sinh ra trình phân tích cú pháp.
 Trong khi đó Mike Lesk và Eric Schmidt đã thiết kế và phát triển Lex
[6]– bộ sinh trình phân tích từ vựng – để hỗ trợ yacc trong việc xác định các token từ chuỗi
nhập.
Flex
4
và Bison
5
chính là phiên bản cải tiến của lex và yacc, có khả năng phân tích trên
bộ văn phạm rộng hơn, quản lý bộ nhớ tốt hơn và được sử dụng trên nhiều nền tảng.

3.2. Bộ sinh trình phân tích từ vựng Flex
3.2.1. Cấu trúc
Flex nhận đầu vào là một tệp bao gồm các đặc tả của các token. Cấu trúc của một
chương trình được viết bằng ngôn ngữ Flex gồm ba phần:
Phần khai báo
%%
Phần quy tắc dịch
%%

minh họa trong hình 3.2 trên. Trước tiên, cần chuẩn bị một tập tin, chẳng hạn là translate.y,
chứa một đặc tả Bison của chương trình dịch. Lệnh bison translate.y sẽ biến đổi tập tin
translate.y thành một chương trình C có tên là y.tab.C. Bằng cách dịch y.tab.C cùng với thư
viện ly nhờ lệnh cc y.tab.C - ly chúng ta thu được một chương trình đối tượng a.out thực
hiện quá trình dịch được đặc tả bởi chương trình Bison ban đầu. Nếu cần thêm các thủ tục
khác, chúng có thể được biên dịch hoặc được tải vào y.tab.C giống như mọi chương trình C
khác.

Chƣơng 4 - XÂY DỰNG CHƢƠNG TRÌNH DỊCH CHO NGÔN NGỮ MINIPAS
Trong chương này, luận văn sẽ định nghĩa một ngôn ngữ tựa Pascal có tên gọi là
Minipas và sau đó sử dụng các công cụ đã được giới thiệu trong chương ba để xây dựng bộ
phân tích từ vựng và bộ phân tích cú pháp cho ngôn ngữ Minipas.
4.1. Yêu cầu
Minipas được xây dựng dựa trên ngôn ngữ Pascal. Mặc dù còn đơn giản hơn Pascal
rất nhiều nhưng Minipas đáp ứng được các yêu cầu sau:
- Đơn giản, gọn nhẹ, dễ học.
- Đủ dùng để diễn tả một số thuật toán đơn giản cho người mới làm quen với ngôn
ngữ lập trình.
4.2. Ngôn ngữ Minipas
4.2.1. Giới thiệu sơ lƣợc
Ngôn ngữ xây dựng được đặt tên là Minipas có một số đặc điểm:
- Có năm kiểu dữ liệu đơn giản: nguyên (integer), thực (double), logic (bool), kí tự
(char), chuỗi ký tự (string). Hỗ trợ các phép toán số học - logic cơ bản trên ba kiểu đầu tiên.
Kiểu char chỉ hỗ trợ phép gán và so sánh.
- Có kiểu cấu trúc là kiểu mảng một chiều với chỉ số nguyên, kiểu phần tử là kiểu đơn
giản.
- Có ba cấu trúc điều khiển: tuần tự, rẽ nhánh (if… then… else) và vòng lặp
(for…to…do, while do).

10

Var
CONST
Const
READ
Read
WRITE
Write
WRITELINE
Writeline
IF
If
THEN
Then
ELSE
Else
FOR
For
TO
To
DO
Do
ENDFOR
Endfor
WHILE
while
ENDWHILE
Endwhile
NUMBER_VAL
{DIGIT}
NUMBERD_VAL

"/*"
whitespace
[ \t\n]+
Bảng 4.1. Biểu thức chính quy đặc tả token
4.3.2. Xây dựng trình phân tích cú pháp cho Minipas
Văn phạm phi ngữ cảnh sinh ngôn ngữ Minipas:
// Luật sinh sinh chƣơng trình
program

var declarations
constant
const_declarations
func_decls
BEGIN
commands
END ‘.’
// Các luật sinh khai báo identifier
var



| LET
declarations



| declarations declaration
declaration

INTEGER id_seq_int IDENTIFIER ‘;’



| id_seq_str IDENTIFIER‘,’
// Các luật sinh khai báo hằng
constant



| CONST
const_declarations



| const_declarations const_declaration
const_declaration

INTEGER IDENTIFIER ASSGNOP NUMBER_VAL‘;’
| CHAR IDENTIFIER ASSGNOP CHR_VAL ‘;’

12
| DOUBLE IDENTIFIER ASSGNOP NUMBERD_VAL ‘;’
| STRING IDENTIFIER ASSGNOP STR_VAL ‘;’
| BOOLEAN IDENTIFIER ASSGNOP NUMBERB_VAL‘;’
// Các luật sinh khai báo hàm
func_decls



| func_decl
func_decl



| func_declarations func_declaration
func_declaration

INTEGER fun_id_seq_int IDENTIFIER ‘;’
| CHAR fun_id_seq_chr IDENTIFIER ‘;’
| DOUBLE fun_id_seq_dou IDENTIFIER ‘;’
| STRING fun_id_seq_str IDENTIFIER ‘;’
| BOOLEAN fun_id_seq_bol IDENTIFIER ‘;’
| ARRAY_I IDENTIFIER '[' NUMBER_VAL ']' ‘;’
| ARRAY_D IDENTIFIER '[' NUMBER_VAL ']' ‘;’
| ARRAY_C IDENTIFIER '[' NUMBER_VAL ']' ‘;’
| ARRAY_B IDENTIFIER '[' NUMBER_VAL ']' ‘;’
fun_id_seq_int



| fun_id_seq_int IDENTIFIER ‘,’
fun_id_seq_chr



| fun_id_seq_chr IDENTIFIER ‘,’
fun_id_seq_dou



| fun_id_seq_dou IDENTIFIER ‘,’
fun_id_seq_str



| read_exp ‘,’ IDENTIFIER
read_array_exp


| read_array_exp ‘,’ IDENTIFIER
else_exp


| ELSE commands
// Luật sinh biểu thức
exp

NUMBER_VAL | NUMBERD_VAL | STR_VAL | CHR_VAL
| NUMBERB_VAL | IDENTIFIER | IDENTIFIER '(' values ')'
| exp '<' exp | exp '=' exp
| exp '!''=' exp | exp '>''=' exp
| exp '<''=' exp | exp '>' exp
| exp '+' exp | exp '-' exp
| exp '*' exp | exp '/' exp
| exp '&' exp | exp '|' exp
| exp '%' exp | '!' exp
| arr_exp | '(' exp ')'
arr_exp

IDENTIFIER '[' index ']'
values



toán cho kiểu kí tự và mảng kí tự. Hỗ trợ tham biến cho chương trình con. Cho phép sử dụng
mảng nhiều chiều và kiểu dữ liệu tự định nghĩa.
Tìm hiểu tiếp về các giai đoạn sau của quá trình thiết kế chương trình dịch như tối ưu
mã.

References
[1] Nguyễn Văn Ba (2002), Ngôn ngữ hình thức, Nhà xuất bản Khoa học và kỹ thuật.
[2] Trần Đức Quang (biên dịch, 2000), Trình biên dịch – Nguyên lý, kỹ thuật và công cụ -
Tập 1, Nhà xuất bản Thống kê.
[3] Thái Thuần Thạch (2000), Xây dựng bộ công cụ thực hiện một số thuật toán trong lý
thuyết ngôn ngữ hình thức và automat, Luận văn tốt nghiệp, Đại học Bách khoa Đà
Nẵng.
[4] Phan Thị Tươi (2009), Giáo trình Trình biên dịch, Nhà xuất bản Đại học Quốc Gia
thành phố Hồ Chí Minh.
[5] Alfred V. Aho, Ravi Sethi, Jeffrey D. Ullman (2002), Compilers: Principles,
Techniques and Tools, Addison – Wesley Publishing Company.
[6] John R.Levine, Tony Mason & Doug Brown (1992), Lex and Yacc, O’Reilly &
Associates, Inc.