TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN
KHOA CÔNG NGHỆ THÔNG TIN
BỘ MÔN KHOA HỌC MÁY TÍNH
NGUYỄN VIỆT CƢỜNG – NGUYỄN THÀNH TRUNG KHẢO SÁT VÀ XÂY DỰNG THỬ NGHIỆM
CHUYẾN TRƯỚC CỦA TRÌNH BIÊN DỊCH
DÀNH CHO NGÔN NGỮ ANSI C GIẢN LƯỢC
CHUYẾN TRƯỚC CỦA TRÌNH BIÊN DỊCH
DÀNH CHO NGÔN NGỮ ANSI C GIẢN LƯỢC
KHÓA LUẬN TỐT NGHIỆP CỬ NHÂN CNTT

GIÁO VIÊN HƢỚNG DẪN
TS. NGUYỄN THANH PHƢƠNG KHÓA 2006 – 2010 i
NHẬN XÉT CỦA GIÁO VIÊN HƢỚNG DẪN
………………………………………………………………………………
………………………………………………………………………………

NHẬN XÉT CỦA GIÁO VIÊN PHẢN BIỆN
………………………………………………………………………………
………………………………………………………………………………
………………………………………………………………………………
………………………………………………………………………………
………………………………………………………………………………
………………………………………………………………………………
………………………………………………………………………………
………………………………………………………………………………
………………………………………………………………………………
………………………………………………………………………………
………………………………………………………………………………
………………………………………………………………………………
………………………………………………………………………………
………………………………………………………………………………
………………………………………………………………………………
………………………………………………………………………………
………………………………………………………………………………
………………………………………………………………………………
………………………………………………………………………………
………………………………………………………………………………
………………………………………………………………………………
………………………………………………………………………………
Khóa luận đáp ứng yêu cầu của Khóa luận cử nhân CNTT.
TpHCM, ngày … tháng …… năm ……
Giáo viên phản biện


Nguyễn Việt Cường – Nguyễn Thành Trung

iv

KHOA CÔNG NGHỆ THÔNG TIN
BỘ MÔN: KHOA HỌC MÁY TÍNH
ĐỀ CƢƠNG CHI TIẾT
Tên đề tài: Khảo sát và xây dựng thử nghiệm chuyến trước của trình biên dịch dành
cho ngôn ngữ ANSI C giản lược.
Giáo viên hƣớng dẫn: TS. Nguyễn Thanh Phƣơng
Thời gian thực hiện: Từ ngày 01/09/2009 đến ngày 10/07/2010
Sinh viên thực hiện:
1. Nguyễn Việt Cường - 0612051
2. Nguyễn Thành Trung - 0612468
Loại đề tài: Tìm hiểu công nghệ và xây dựng ứng dụng.
Nội Dung Đề Tài:
Nội dung:
– Tìm hiểu kỹ thuật xây dựng trình biên dịch.
– Khảo sát các công cụ hỗ trợ phát sinh một phần trình biên dịch.
– Vận dụng vào việc xây dựng chuyến trước cho ngôn ngữ ANSI C giản lược.
– Giải quyết các bài toán nảy sinh trong thực tế, vốn không xuất hiện trong lý
thuyết nền tảng.
Yêu cầu:
– Nắm vững và vận dụng có sáng tạo các kiến thức tiếp thu được từ lý thuyết
cũng như thực tế.
– Xây dựng thành công chuyến trước của trình biên dịch (có thể vận hành).
Kết quả:
1

MỤC LỤC
MỤC LỤC 1
DANH MỤC CÁC HÌNH VẼ 3
DANH MỤC CÁC BẢNG 5
CHƢƠNG 1: TỔNG QUAN 6
1.1. GIỚI THIỆU VỀ TRÌNH BIÊN DỊCH 6
1.1.1. Trình biên dịch là gì? 6
1.1.2. Phân loại trình biên dịch 6
1.1.3. Quá trình biên dịch 7
1.1.4. Quá trình phân tích 8
1.1.5. Quá trình tổng hợp 9
1.1.6. Các pha trong quá trình biên dịch 9
1.1.7. Các module phụ của trình biên dịch 11
1.2. CÁC GIỚI HẠN CỦA LUẬN VĂN 13
1.2.1. Các giới hạn chung 13
1.2.2. Ngôn ngữ ANSI C giản lược 13
1.3. NỘI DUNG LUẬN VĂN 17
CHƢƠNG 2: GIỚI THIỆU VỀ CHUYẾN TRƢỚC 18
2.1. VAI TRÒ, CHỨC NĂNG CỦA CHUYẾN TRƯỚC. 18
2.2. BẢNG DANH BIỂU. 18
2.2.1. Bảng danh biểu là gì? Vai trò và chức năng? 18
2.2.2. Tầng dữ liệu 20
2.2.3. Tổ chức lưu trữ dạng bảng băm 21

4.4.1. Biểu thức 59
4.4.2. Mảng và con trỏ 67
4.4.3. Dịch biểu thức logic - luồng điều khiển. 73
4.4.4. Khai báo 96
CHƢƠNG 5: TỔNG KẾT 115
5.1. KẾT QUẢ 115
5.2. HẠN CHẾ 115
5.3. HƯỚNG PHÁT TRIỂN 115
PHỤ LỤC 117
PHỤ LỤC 1: Bảng xác định độ ưu tiên của các toán tử. 117
PHỤ LỤC 2: Dịch chương trình mẫu. 118
THAM KHẢO 133

3 DANH MỤC CÁC HÌNH VẼ
Hình 1.1. Trình biên dịch 6
Hình 1.2. Quá trình biên dịch 8
Hình 1.3. Các pha biên dịch mã nguồn 10
Hình 1.4. Quá trình dịch mã cho chip 11
Hình 1.5. Cấu trúc chương trình 13
Hình 2.1. Sự phân chia tầng trong cài đặt bảng danh biểu 19
Hình 2.2. Cấu trúc lưu trữ (dạng đơn giản) cho danh biểu 20
Hình 2.3. Bảng băm với kích thước khóa 256 21
Hình 2.4. Bảng danh biểu với liên kết chỉ định phạm vi 23
Hình 2.5 .Giao thức liên hệ của bộ phân tích từ vựng. 25
Hình 2.6. 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
27
Hình 2.7. Cấu trúc của một bộ phân tích cú pháp LR 31

Hình 4.24. Cây phân tích cú pháp của một chương trình đơn giản 97
Hình 4.25. Sự tương quan giửa khai báo và external_definition 98
Hình 4.26. Sự lan truyền thuộc tính “int” và “x” 101
Hình 4.27. Sơ đồ tổ chức lưu trữ khai báo int x; 102
Hình 4.28. Cây phân tích cú pháp và lan truyền thuộc tính cho ví dụ ví dụ 4.20: . 105
Hình 4.29. Sơ đồ tổ chức lưu trữ hàm inc trong Ví dụ 4.20: 106
Hình 4.30. Cây phân tích cú pháp và quá trình lan truyền thuộc tính cho khai báo
struct 109
Hình 4.31. Sơ đồ tổ chức lưu trữ cho kiểu dữ liệu struct 110
Hình 4.32. Cây phân tích cú pháp cho khai báo con trỏ 111
Hình 4.33 Sơ đồ lưu trữ cho khai báo int *x; 112
Hình 4.34. Cây phân tích cú pháp cho khai báo typedef 113
Hình 4.36. Tổ chức lưu trữ typedef 114
5

DANH MỤC CÁC BẢNG
Bảng 1.1. Các kiểu dữ liệu 14
Bảng 1.2. Các toán tử 2 ngôi 15
Bảng 2.1. Mô tả một số token của ngôn ngữ C 24
Bảng 2.2. Mô tả từng bước hoạt động của phương pháp phân tích cú pháp dưới lên
29
Bảng 2.3. Bảng phân tích cú pháp của văn phạm dành cho biểu thức đơn giản 33
Bảng 2.4. Các bước thực hiện của bộ phân tích cú pháp LR với câu nhập 2 * 3 34
Bảng 4.1. Cách hình thành một toán hạng từ danh biểu hoặc một constant 59
Bảng 4.2. Luật sinh và luật ngữ nghĩa trường hợp tính toán biểu thức 64
Bảng 4.3. Luật sinh và luật ngữ nghĩa trường hợp mảng, con trỏ 71
Bảng 4.4. Mô tả các hành vi ngữ nghĩa và phát sinh mã ba địa chỉ của lệnh if 84

1.1.2. Phân loại trình biên dịch
Theo số bước biên dịch, ta chia làm hai loại chính: một bước và nhiều
bước.
1.1.2.1. Trình biên dịch một bước
Việc biên dịch mã nguồn viết bằng ngôn ngữ cấp cao sang ngôn ngữ
máy (hay mã máy) gọi là trình biên dịch 1 bước. Các trình biên dịch trước
đây cho Pascal hay Borland C là trình biên dịch một bước.
Trình biên dịch
Chương trình nguồn
(mã nguồn)

Chương trình đích
(mã nguồn)

Báo lỗi

Hình 1.1. Trình biên dịch
Chương 1 – Tổng quan
7

1.1.2.2. Trình biên dịch nhiều bước.
Các trình biên dịch cần nhiều hơn một bước để hoàn tất gọi là trình
biên dịch nhiều bước.
Các kiểu trình biên dịch nhiều bước bao gồm:
 Trình biên dịch nguồn sang nguồn: dịch từ một ngôn ngữ cấp cao
này sang một ngôn ngữ cấp cao khác. Chẳng hạn biên dịch một
chương trình viết bằng ngôn ngữ C++ sang một chương trình viết
bằng ngôn ngữ C.
 Trình biên dịch phân đoạn: biên dịch sang một loại mã thực thi gần
với máy, thông thường là mã hợp ngữ. Ví dụ biên dịch một chương

Phân tích
Chương trình nguồn
(mã nguồn)

Chương trình đích
(mã nguồn)

Tổng hợp
Biểu diễn trung gian

Một tập hợp các thông tin
mà trình biên dịch thu thập
được từ chương trình nguồn
Trình biên dịch
Hình 1.2. Quá trình biên dịch
Chương 1 – Tổng quan
9

 Phát sinh mã trung gian. Tạo ra mã trung gian – một dạng biểu
diễn của chương trình nguồn. Mã trung gian thường độc lập với
các đặc trưng kỹ thuật của máy đích.
1.1.5. Quá trình tổng hợp
Là quá trình xây dựng nên chương trình đích từ các thông tin trong biểu
biểu diễn trung gian đã thu thập được.
Quá trình tổng hợp thực hiện các bước sau để phát sinh mã đích:
 Tối ưu mã trung gian. Tối ưu mã trung gian để tạo ra dạng biểu
diễn tốt hơn. Giúp mã đích khi được phát sinh có thể thực thi nhanh
hơn hoặc tiết kiệm không gian hay năng lượng.
 Phát sinh mã đích. Tạo ra mã đích từ biễu diễn trung gian đã tối ưu.
 Tối ưu mã đích. Thực hiện tối ưu để tạo ra một tập mã đích có thể

Chương trình
(mã nguồn)
Phân tích cú pháp
Token
Phân tích ngữ nghĩa
Cây phân tích cú pháp
Cây phân tích cú pháp

Bộ phát sinh mã trung
gian
Bộ tối ưu mã trung gian
Mã trung gian
Bộ phát sinh mã đích
Mã trung gian đã tối ưu
Mã đích đã tối ưu
Bộ tối ưu mã đích
Mã đích
Chương 1 – Tổng quan
11

trình biên dịch ngôn ngữ mới để dịch mã cho cùng một loại phần cứng chỉ là
việc xây dựng lại chuyến trước cho phù hợp với ngôn ngữ mới.
Quản lý bảng danh biểu và quản lý lỗi là hai pha luôn được thực hiện
xuyên suốt trong quá trình biên dịch.
 Bảng danh biểu. Những thông tin về một danh biểu (tên, kiểu, phạm
vi,…) sẽ được trình biên dịch thu thập và lưu trữ vào bảng danh biểu.
Chuyến sau sẽ sử dụng những dữ liệu này để phát sinh mã.
 Kiểm và thông báo lỗi. Mỗi bước xử lý trong sơ đồ trên đều có thể
xuất hiện lỗi về khai báo, cú pháp, ngữ nghĩa, Trình biên dịch cần
kiểm tra được các lỗi và thông báo lỗi cho người sử dụng.

o Macro chèn tập tin.
Ví dụ: #include <global.h>
o Built-in macro: là các macro được xây dựng sẵn để hỗ trợ lập
trình.
Ví dụ như macro khai báo chèn một đoạn lệnh hợp ngữ:
__asm
__endasm;
1.1.7.2. Bộ dịch mã hợp ngữ - Assembler
Đa số trình biên dịch chỉ dịch ra mã hợp ngữ, do phụ thuộc vào đặc
tính của thiết bị phần cứng nên mã hợp ngữ chưa thể thực thi được, ví dụ như
mã hợp ngữ cần thực thi trên một loại vi xử lý PIC[6] có bộ nhớ RAM, ROM
ở mức hạn chế. Lúc đó ta cần chuyển đổi từ mã hợp ngữ sang mã thực thi
(opcode) cụ thể để phù hợp với vi xử lý PIC thì mới có thể thực thi được.
1.1.7.3. Trình liên kết/Tải – Linker/Loader
Do cấu trúc chương trình đôi khi có sử dụng đến các hàm thư viện đã
được biên dịch sẵn (nhằm tránh biên dịch nhiều lần), đồng thời không gian bộ
nhớ dùng để thực thi lệnh trên chip (thường gọi là ROM) có tính chất đặc thù
riêng, nên ta cần một chương trình được gọi là linker để thực hiện liên kết các
đoạn mã lại với nhau thành 1 khối thống nhất trước khi nạp xuống bộ nhớ
ROM.
Chương 1 – Tổng quan
13

1.2. CÁC GIỚI HẠN CỦA LUẬN VĂN
1.2.1. Các giới hạn chung
Nhằm mục đích tìm hiểu và học hỏi, việc xây dựng trình biên dịch trong
khuôn khổ luận văn này sẽ bao gồm các giới hạn sau:
 Xây dựng cho ngôn ngữ ANSI C giản lược.
 Chỉ thực hiện xây dựng chuyến trước. Mã phát sinh được tính đến
thời điểm hiện tại là mã trung gian.

}
void func3()
{
Statments }
LEVEL1
LEVEL2
LEVEL3
Hình 1.5. Cấu trúc chương trình
Chương 1 – Tổng quan
14

o Thập phân: -3, 10,…
o Thập lục phân (hexadecimal): 0x30, …
o Nhị phân: 0b00011101
 Ký tự hằng: „A‟, „b‟…
 Chuỗi hằng: “ABCD”
1.2.2.3. Biến và các kiểu biến

Tên kiểu
Kích thƣớc
Giá trị tối thiểu
Giá trị tối đa
unsigned char
1 byte
0
255
char

 Hỗ trợ các thao tác số học trên con trõ.
 Kích thước con trỏ: 2 bytes.
 Không hỗ trợ con trỏ hàm.
Chương 1 – Tổng quan
15

1.2.2.5. Mảng
 Hỗ trợ mảng 1 chiều, mảng nhiều chiều.
 Hỗ trợ truy xuất mảng thông qua con trỏ.
1.2.2.6. Cấu trúc
 Hỗ trợ khai báo cấu trúc
 Cấu trúc lồng cấu trúc.
1.2.2.7. Toán tử
 Toán tử 1 ngôi: !, ~, ++,
 Toán tử 2 ngôi:
Toán tử
Ý nghĩa
+
Cộng
-
Trừ
<<
Dịch trái
>>
Dịch phải
*
Nhân
/
Chia
%

statement1;
statement2;
statement3;
…
statementn;
}
 Biểu thức:
o Số học.
o Luận lý
o Quan hệ
 Các lệnh điều khiển:
o Goto
o If
o Switch
o While
o For
o Do
o Continue
o Break
o Return
Chương 1 – Tổng quan
17

1.3. NỘI DUNG LUẬN VĂN
Việc xây dựng thành công một trình biên dịch hoàn chỉnh là rất phức tạp, tốn
nhiều thời gian và cần nhiều kiến thức. Do đó, trong khuôn khổ của luận văn này, ta
chỉ tập trung vào các phần chính yếu sau:
– Tìm hiểu kỹ thuật xây dựng trình biên dịch.
– Khảo sát các công cụ hỗ trợ phát sinh một phần trình biên dịch.
– Vận dụng vào việc xây dựng một trình biên dịch cho ngôn ngữ ANSI C

 Phát sinh mã trung gian.
 Quản lý bảng danh biểu, quản lý lỗi.
2.2. BẢNG DANH BIỂU.
2.2.1. Bảng danh biểu là gì? Vai trò và chức năng?
Như đã biết, một chương trình cơ bản sẽ gồm 3 phần chính: khai báo
(declaration), biểu thức (expression) và lệnh (statement). Bảng
danh biểu (symbol table) được dùng để lưu giữ thông tin về các khai báo trong
chương trình. Ví dụ như biến, chương trình con, struct, typedef,
v.v…Mỗi khai báo như thế được gọi là một danh biểu. Trong đa số các trường
hợp, thông tin sẽ được tích lũy ở giai đoạn phân tích và được sử dụng bởi giai
đoạn tổng hợp để sinh mã đích.
Ví dụ 2.1: Với khai báo biến toàn cục
int x;