Principles
of compilers
25-04-12
©TS. Hà Chí Trung, Khoa CNTT - HVKTQS
1
GIẢ NG V I Ê N : T S . H À C H Í T R U N G
B Ộ M Ô N : K H M T
K H O A C N T T , H V K T Q S
Đ T : 0 1 6 8 . 5 5 8 . 2 1 . 0 2
E M A I L : H C T 2 0 0 9 @ Y A H O O . C O M

Giới thiệu chung
 Cơ sở môn Chương trình dịch:
 Lý thuyết automata và ngôn ngữ hình thức;
 Cấu trúc dữ liệu và giải thuật;
 Lập trình (C, C# )
 Tiêu chuẩn đánh giá sinh viên:
 Báo cáo đề tài;
 Chuyên cần, thường xuyên, thi hết môn;

25-04-12
©TS. Hà Chí Trung, Khoa CNTT - HVKTQS
2
Giới thiệu chung
3
 Tài liệu tham khảo:
1. Bài giảng của giảng viên;
2. A.V. Aho, M. Lam, R. Sethi, J.D.Ullman. Compilers: Principles,
Technique and Tools, 2
nd
Edition – Addison-Wesley, 2007.

1.3. Các giai đoạn làm việc của compiler
1.3.1. Phân tích từ vựng (lexical analysis)
1.3.2. Phân tích cú pháp (syntax analysis)
1.3.3. Phân tích ngữ nghĩa (semantic analysis)
1.3.4. Sinh mã trung gian (ICG)
1.3.5. Tối ưu mã (code optimition)
1.3.6. Sinh mã đích (code generation)
1.4. Vấn đề quản lý bảng ký tự
1.5. Xử lý lỗi biên dịch
25-04-12
5
©TS. Hà Chí Trung, Khoa CNTT - HVKTQS
1.1. Khái niệm về compiler
6
 Khái niệm: Chương trình dịch (compiler) là một chương
trình làm nhiệm vụ đọc một chương trình được viết bằng
một ngôn ngữ - ngôn ngữ nguồn (source language - SL) -
rồi dịch nó thành một chương trình tương đương ở một
ngôn ngữ khác - ngôn ngữ đích (target languague - TL).

 Chương trình dịch là một dạng của bộ xử lý ngôn ngữ
(languague proccessor)

25-04-12
©TS. Hà Chí Trung, Khoa CNTT - HVKTQS
Chương
trình nguồn

 Ứng dụng:
 Hiểu từng ngôn ngữ, điểm mạnh điểm yếu của nó;
 Lựa chọn ngôn ngữ và chương trình dịch thích hợp;
 Phân biệt được công việc do CTD thực hiện và do CT ứng dụng
thực hiện;
 Thực hiện các dự án xây dựng chương trình dịch;
 Trong giao tiếp người máy thông qua các câu lệnh
 Áp dụng trong NLP, dịch tự động, tóm tắt văn bản…

25-04-12
©TS. Hà Chí Trung, Khoa CNTT - HVKTQS
1.1. Khái niệm về compiler
 Phân loại Compilers: Có nhiều cách phân loại khác nhau,
tùy theo tiêu chí phân loại:
 Theo số lần duyệt: Duyệt đơn, duyệt nhiều lần.
 Theo mục đích: Tải và chạy, gỡ rối, tối ưu, chuyển đổi ngôn
ngữ, chuyển đôỉ định dạng…
 Theo độ phức tạp của chương trình nguồn và đích:
 Asembler (chương trình hợp dịch): Dịch từ ngôn ngữ asembly
ra ngôn ngữ máy;
 Preproccessor (tiền xử lý): Dịch từ ngôn ngữ cấp cao sang ngôn
ngữ cấp cao khác (thực chất là dịch một số cấu trúc mới sang
cấu trúc cũ);
 Compiler (biên dịch): dịch từ ngôn ngữ cấp cao sang ngôn ngữ
cấp thấp.
25-04-12
©TS. Hà Chí Trung, Khoa CNTT - HVKTQS
9
1.1. Khái niệm về compiler
 Phân loại Compilers: Có nhiều cách phân loại khác nhau,

Dữ liệu vào
(input)
Chương trình nguồn
(SP on the SL)
Trình biên dịch
(Compiler)
Chương trình đích
(TP on the TL)
Thông báo lỗi
(Error messages )
 Thông dịch:

 Biên dịch:
1.1. Khái niệm về compiler
12
 VD: Hệ thống dịch Java kết hợp cả thông dịch và biên
dịch. Mã nguồn Java được dịch ra dạng Bytecode. File
này được một trình thông dịch gọi là máy ảo Java thực
hiện.

25-04-12
©TS. Hà Chí Trung, Khoa CNTT - HVKTQS
Source
program
Compiler
Intermediate
program

1.2. Vị trí của compiler trong LPS
25-04-12
©TS. Hà Chí Trung, Khoa CNTT - HVKTQS
Skeletal source program
(Library
object
files)
Bộ tiền xử lí (Preprocessor)
Chương trình nguồn (Source program)
Ct hợp ngữ đích (Target assembly program)
Trình dịch hợp ngữ (Assembler)
Relocatable machine code
Trình tải/liên kết (Loader/link-
editor)
Absolute machine code
Trình biên dịch (Compiler)
Bài 1. Giới thiệu về chương trình dịch
1.1. Khái niệm về compiler
1.2. Vị trí của compiler trong LPS
1.3. Các giai đoạn làm việc của compiler
1.3.1. Phân tích từ vựng (lexical analysis)
1.3.2. Phân tích cú pháp (syntax analysis)
1.3.3. Phân tích ngữ nghĩa (semantic analysis)
1.3.4. Sinh mã trung gian (ICG)
1.3.5. Tối ưu mã (code optimition)
1.3.6. Sinh mã đích (code generation)
1.4. Vấn đề quản lý bảng ký tự
1.5. Xử lý lỗi biên dịch
25-04-12
15

Tối ưu mã
(Code optimizer)
Sinh mã
(Code generator)
Chương trình đích (Target program)
Phân tích ngữ nghĩa
(Semantic analyzer)
Quản lí bảng kí tự
(Symbol-table manager)
analysis
(front end)
synthesis
(back end)
1.3. Các giai đoạn làm việc của compiler
18
 Modern Compiler Implementation in C – A.W. Appel - Cambrige
University Press.
25-04-12
©TS. Hà Chí Trung, Khoa CNTT - HVKTQS
Bài 1. Giới thiệu về chương trình dịch
1.1. Khái niệm về compiler
1.2. Vị trí của compiler trong LPS
1.3. Các giai đoạn làm việc của compiler
1.3.1. Phân tích từ vựng (lexical analysis)
1.3.2. Phân tích cú pháp (syntax analysis)
1.3.3. Phân tích ngữ nghĩa (semantic analysis)
1.3.4. Sinh mã trung gian (ICG)
1.3.5. Tối ưu mã (code optimition)
1.3.6. Sinh mã đích (code generation)
1.4. Vấn đề quản lý bảng ký tự

©TS. Hà Chí Trung, Khoa CNTT - HVKTQS
1.3.1. Phân tích từ vựng (lexical analysis)
 VD: Câu lệnh trong chương trình nguồn viết bằng ngôn ngữ C:
a = b + c * 60; Chương trình phân tích từ vựng sẽ trả về:
1. a là tên (tên (định danh))
2. = là toán tử gán
3. b là tên (định danh)
4. + là toán tử cộng
5. c là định danh
6. * là toán tử nhân
7. 60 là một số;
 Kết quả phân tích từ vựng sẽ là: (tên, a), phép gán, (tên, b)
phép cộng (tên, c) phép nhân, (số, 60)
25-04-12
©TS. Hà Chí Trung, Khoa CNTT - HVKTQS
22
Bài 1. Giới thiệu về chương trình dịch
1.1. Khái niệm về compiler
1.2. Vị trí của compiler trong LPS
1.3. Các giai đoạn làm việc của compiler
1.3.1. Phân tích từ vựng (lexical analysis)
1.3.2. Phân tích cú pháp (syntax analysis)
1.3.3. Phân tích ngữ nghĩa (semantic analysis)
1.3.4. Sinh mã trung gian (ICG)
1.3.5. Tối ưu mã (code optimition)
1.3.6. Sinh mã đích (code generation)
1.4. Vấn đề quản lý bảng ký tự
1.5. Xử lý lỗi biên dịch
25-04-12
23

25