Giáo trình Nguyên lý ngôn ngữ lập trình - Chương 2: Một trình biên dịch đơn giản

CHƯƠNG II 
MỘT TRÌNH BIÊN DỊCH ÐƠN GIẢN 
Nội dung chính: 
Chương này giới thiệu một trình biên dịch cho các biểu thức số học đơn giản (trình 
biên dịch đơn giản) gồm hai kỳ: Kỳ đầu (Front end) và kỳ sau (Back end). Nội dung 
chính của chương tập trung vào kỳ đầu gồm các giai đoạn: Phân tích từ vựng, phân 
tích cú pháp và sinh mã trung gian với mục đích chuyển một biểu thức số học đơn giản 
từ dạng trung tố sang hậu tố. Kỳ sau chuyển đổi biểu thức ở dạng hậu tố sang mã máy 
ảo kiểu stack, sau đó sẽ thực thi đoạn mã đó trên máy ảo kiểu stack để cho ra kết quả 
tính toán cuối cùng. 
Mục tiêu cần đạt: 
Sau khi học xong chương này, sinh viên phải nắm được: 
• Các thành phần cấu tạo nên trình biên dịch đơn giản. 
• Hoạt động và cách cài đặt các giai đoạn của kỳ trước của một trình biên dịch 
đơn giản. 
• Cách sử dụng máy trừu tượng kiểu stack để chuyển đổi các biểu thức hậu tố 
sang mã máy ảo và cách thực thi các đoạn mã ảo này để có được kết quả cuối 
cùng. 
Kiến thức cơ bản 
Để tiếp nhận các nội dung được trình bày trong chương 2, sinh viên phải: 
• Biết một ngôn ngữ lập trình nào đó: C, Pascal, v.v để hiểu cách cài đặt trình 
biên dịch. 
• Có kiến thức về cấu trúc dữ liệu để hiểu cách tổ chức dữ liệu khi thực hiện cài 
đặt. 
Tài liệu tham khảo: 
[1] Trình Biên Dịch - Phan Thị Tươi (Trường Ðại học kỹ thuật Tp.HCM) - NXB 
Giáo dục, 1998. 
[2] Compilers : Principles, Technique and Tools - Alfred V.Aho, Jeffrey 
D.Ullman - Addison - Wesley Publishing Company, 1986. 
I. ÐỊNH NGHĨA CÚ PHÁP 
1. Văn phạm phi ngữ cảnh 
 Ðể xác định cú pháp của một ngôn ngữ, người ta dùng văn phạm phi ngữ cảnh CFG 
(Context Free Grammar) hay còn gọi là văn phạm BNF (Backers Naur Form) 
 Văn phạm phi ngữ cảnh bao gồm bốn thành phần: 
1. Một tập hợp các token - các ký hiệu kết thúc (terminal symbols). 
 Ví dụ: Các từ khóa, các chuỗi, dấu ngoặc đơn, ... 
 11
2. Một tập hợp các ký hiệu chưa kết thúc (nonterminal symbols), còn gọi là các 
biến (variables). 
 Ví dụ: Câu lệnh, biểu thức, ... 
3. Một tập hợp các luật sinh (productions) trong đó mỗi luật sinh bao gồm một 
ký hiệu chưa kết thúc - gọi là vế trái, một mũi tên và một chuỗi các token 
và / hoặc các ký hiệu chưa kết thúc gọi là vế phải. 
4. Một trong các ký hiệu chưa kết thúc được dùng làm ký hiệu bắt đầu của văn 
phạm. 
 Chúng ta qui ước: 
- Mô tả văn phạm bằng cách liệt kê các luật sinh. 
- Luật sinh chứa ký hiệu bắt đầu sẽ được liệt kê đầu tiên. 
- Nếu có nhiều luật sinh có cùng vế trái thì nhóm lại thành một luật sinh duy 
nhất, trong đó các vế phải cách nhau bởi ký hiệu “|”đọc là “hoặc”. 
Ví dụ 2.1: Xem biểu thức là một danh sách của các số phân biệt nhau bởi dấu + và dấu 
-. Ta có, văn phạm với các luật sinh sau sẽ xác định cú pháp của biểu thức. 
 list → list + digit 
 list → list - digit ⇔ list → list + digit | list - digit | digit 
 list → digit digit → 0 | 1 | 2 ...| 9 
 digit → 0 | 1 | 2 | ...| 9 
 Như vậy văn phạm phi ngữ cảnh ở đây là: 
 - Tập hợp các ký hiệu kết thúc: 0, 1, 2, ..., 9, +, - 
 - Tập hợp các ký hiệu chưa kết thúc: list, digit. 
 - Các luật sinh đã nêu trên. 
 - Ký hiệu chưa kết thúc bắt đầu: list. 
Ví dụ 2.2: 
 Từ ví dụ 2.1 ta thấy: 9 - 5 + 2 là một list vì: 
 9 là một list vì nó là một digit. 
 9 - 5 là một list vì 9 là một list và 5 là một digit. 
 9 - 5 + 2 là một list vì 9 - 5 là một list và 2 là một digit. 
Ví dụ 2.3: 
 Một list là một chuỗi các lệnh, phân cách bởi dấu ; của khối begin - end trong 
Pascal. Một danh sách rỗng các lệnh có thể có giữa begin và end. 
 Chúng ta xây dựng văn phạm bởi các luật sinh sau: 
 block → begin opt_stmts end 
 opt_stmts → stmt_list | ε 
 stmt_list → stmt_list ; stmt | stmt 
 12
 Trong đó opt_stmts (optional statements) là một danh sách các lệnh hoặc không có 
lệnh nào (ε). 
 Luật sinh cho stmt_list giống như luật sinh cho list trong ví dụ 2.1, bằng cách thay 
thế +, - bởi ; và stmt thay cho digit. 
2. Cây phân tích cú pháp (Parse Tree) 
 Cây phân tích cú pháp minh họa ký hiệu ban đầu của một văn phạm dẫn đến một 
chuỗi trong ngôn ngữ. 
 Nếu ký hiệu chưa kết thúc A có luật sinh A → XYZ thì cây phân tích cú pháp có 
thể có một nút trong có nhãn A và có 3 nút con có nhãn tương ứng từ trái qua phải là 
X, Y, Z. A 
Z Y X 
 Một cách hình thức, cho một văn phạm phi ngữ cảnh thì cây phân tích cú pháp là 
một cây có các tính chất sau đây: 
1. Nút gốc có nhãn là ký hiệu bắt đầu. 
2. Mỗi một lá có nhãn là một ký hiệu kết thúc hoặc một ε. 
3. Mỗi nút trong có nhãn là một ký hiệu chưa kết thúc. 
4. Nếu A là một ký hiệu chưa kết thúc được dùng làm nhãn cho một nút trong 
nào đó và X1 ... Xn là nhãn của các con của nó theo thứ tự từ trái sang phải thì 
A → X1X2 ... Xn là một luật sinh. Ở đây X1, ..., Xn có thể là ký hiệu kết thúc 
hoặc chưa kết thúc. Ðặc biệt, nếu A → ε thì nút có nhãn A có thể có một con 
có nhãn ε. 
3. Sự mơ hồ của văn phạm 
 Một văn phạm có thể sinh ra nhiều hơn một cây phân tích cú pháp cho cùng một 
chuỗi nhập thì gọi là văn phạm mơ hồ. 
 Ví du 2.4: Giả sử chúng ta không phân biệt một list với một digit, xem chúng đều 
là một string ta có văn phạm: 
 string → string + string | string - string | 0 | 1 | ... | 9. 
 Với văn phạm này thì chuỗi biểu thức 9 - 5 + 2 có đến hai cây phân tích cú 
pháp như sau : 
Hình 2.1 - Minh họa văn phạm mơ hồ 
string 
string 
string string 
string 
string 
string string +
+ string string 
-
- 2
2
9
9 5 5
 13
Tương tự với cách đặt dấu ngoặc vào biểu thức như sau : 
 (9 - 5) + 2 9 - ( 5 + 2) 
Bởi vì một chuỗi với nhiều cây phân tích cú pháp thường sẽ có nhiều nghĩa, do 
đó khi biên dịch các chương trình ứng dụng, chúng ta cần thiết kế các văn phạm không 
có sự mơ hồ hoặc cần bổ sung thêm các qui tắc cần thiết để giải quyết sự mơ hồ cho 
văn phạm. 
4. Sự kết hợp của các toán tử 
 Thông thường, theo quy ước ta có biểu thức 9 + 5 + 2 tương đương (9 + 5) + 2 và 9 
- 5 - 2 tương đương với (9 - 5) - 2. Khi một toán hạng như 5 có hai toán tử ở trái và 
phải thì nó phải chọn một trong hai để xử lý trước. Nếu toán tử bên trái được thực hiện 
trước ta gọi là kết hợp trái. Ngược lại là kết hợp phải. 
 Thường thì bốn phép toán số học: +, -, *, / có tính kết hợp trái. Các phép toán như 
số mũ, phép gán bằng (=) có tính kết hợp phải. 
 Ví dụ 2.5: Trong ngôn ngữ C, biểu thức a = b = c tương đương a = ( b = c) vì 
chuỗi a = b = c với toán tử kết hợp phải được sinh ra bởi văn phạm: 
 right → letter = right | letter 
 letter → a | b | ... | z 
 Ta có cây phân tích cú pháp có dạng như sau (chú ý hướng của cây nghiêng về bên 
phải trong khi cây cho các phép toán có kết hợp trái thường nghiêng về trái) 
right 
right =
=
letter 
letter letter a 
c b 
Hình 2.2 - Minh họa cây phân tích cú pháp cho toán tử kết hợp phải 
5. Thứ tự ưu tiên của các toán tử 
 Xét biểu thức 9 + 5 * 2. Có 2 cách để diễn giải biểu thức này, đó là 9 + (5 * 2) 
hoặc ( 9 + 5) * 2. Tính kết hợp của phép + và * không giải quyết được sự mơ hồ này, 
vì vậy cần phải quy định một thứ tự ưu tiên giữa các loại toán tử khác nhau. 
Thông thường trong toán học, các toán tử * và / có độ ưu tiên cao hơn + và -. 
Cú pháp cho biểu thức : 
Văn phạm cho các biểu thức số học có thể xây dựng từ bảng kết hợp và ưu tiên của 
các toán tử. Chúng ta có thể bắt đầu với bốn phép tính số học theo thứ bậc sau : 
 Kết hợp trái +, - Thứ tự ưu tiên 
 Kết hợp trái *, / từ thấp đến cao 
 14
 Chúng ta tạo hai ký hiệu chưa kết thúc expr và term cho hai mức ưu tiên và một ký 
hiệu chưa kết thúc factor làm đơn vị phát sinh cơ sở của biểu thức. Ta có đơn vị cơ bản 
trong biểu thức là số hoặc biểu thức trong dấu ngoặc. 
 factor → digit | (expr) 
 Phép nhân và chia có thứ tự ưu tiên cao hơn đồng thời chúng kết hợp trái nên luật 
sinh cho term tương tự như cho list : 
 term → term * factor | term / factor | factor 
 Tương tự, ta có luật sinh cho expr : 
 expr → expr + term | expr - term | term 
 Vậy, cuối cùng ta thu được văn phạm cho biểu thức như sau : 
 expr → expr + term | expr - term | term 
 term → term * factor | term / factor | factor 
 factor → digit | (expr) 
 Như vậy: Văn phạm này xem biểu thức như là một danh sách các term được phân 
cách nhau bởi dấu + hoặc -. Term là một list các factor phân cách nhau bởi * hoặc /. 
Chú ý rằng bất kỳ một biểu thức nào trong ngoặc đều là factor, vì thế với các dấu 
ngoặc chúng ta có thể xây dựng các biểu thức lồng sâu nhiều cấp tuỳ ý. 
Cú pháp các câu lệnh: 
 Từ khóa (keyword) cho phép chúng ta nhận ra câu lệnh trong hầu hết các ngôn 
ngữ. Ví dụ trong Pascal, hầu hết các lệnh đều bắt đầu bởi một từ khóa ngoại trừ lệnh 
gán. Một số lệnh Pascal được định nghĩa bởi văn phạm (mơ hồ) sau, trong đó id chỉ 
một danh biểu (tên biến). 
 stmt → id := expr 
 | if expr then stmt 
 | if expr then stmt else stmt 
 | while expr do stmt 
 | begin opt_stmts end 
 Ký hiệu chưa kết thúc opt_stmts sinh ra một danh sách có thể rỗng các lệnh, 
phân cách nhau bởi dấu chấm phẩy (;) 
II. DỊCH TRỰC TIẾP CÚ PHÁP (Syntax - Directed Translation) 
 Ðể dịch một kết cấu ngôn ngữ lập trình, trong quá trình dịch, bộ biên dịch cần lưu 
lại nhiều đại lượng khác cho việc sinh mã ngoài mã lệnh cần tạo ra cho kết cấu. Chẳng 
hạn nó cần biết kiểu (type) của kết cấu, địa chỉ của lệnh đầu tiên trong mã đích, số lệnh 
phát sinh,v.v Vì vậy ta nói một cách ảo về thuộc tính (attribute) đi kèm theo kết cấu. 
Một thuộc tính có thể biểu diễn cho một đại lượng bất kỳ như một kiểu, một chuỗi, 
một địa chỉ vùng nhớ, v.v 
 Chúng ta sử dụng định nghĩa trực tiếp cú pháp (syntax - directed definition) 
nhằm đặc tả việc phiên dịch các kết cấu ngôn ngữ lập trình theo các thuộc tính đi kèm 
 15
với thành phần cú pháp của nó. Chúng ta cũng sẽ sử dụng một thuật ngữ có tính thủ 
tục hơn là lược đồ dịch (translation scheme) để đặc tả quá trình dịch. Trong chương 
này, ta sử dụng lược đồ dịch để dịch một biểu thức trung tố thành dạng hậu tố. 
1. Ký pháp hậu tố (Postfix Notation) 
 Ký pháp hậu tố của biểu thức E có thể được định nghĩa quy nạp như sau: 
 1. Nếu E là một biến hay hằng thì ký pháp hậu tố của E chính là E. 
 2. Nếu E là một biểu thức có dạng E1 op E2 trong đó op là một toán tử hai ngôi 
thì ký pháp hậu tố của E là E1’ E2’ op. Trong đó E1’, E2’ tương ứng là ký pháp hậu tố 
của E1, E2. 
 3. Nếu E là một biểu thức dạng (E1) thì ký pháp hậu tố của E là ký pháp hậu tố 
của E1. 
 Trong dạng ký pháp hậu tố, dấu ngoặc là không cần thiết vì vị trí và số lượng các 
đối số chỉ cho phép xác định một sự giải mã duy nhất cho một biểu thức hậu tố. 
 Ví dụ 2.6: Dạng hậu tố của biểu thức (9 - 5) + 2 là 9 5 - 2 + 
 Dạng hậu tố của biểu thức 9 - (5 + 2) là 9 5 2 + - 
2. Ðịnh nghĩa trực tiếp cú pháp (Syntax - Directed Definition) 
 Ðịnh nghĩa trực tiếp cú pháp sử dụng văn phạm phi ngữ cảnh để đặc tả cấu trúc cú 
pháp của dòng input nhập. Nó liên kết mỗi ký hiệu văn phạm với một tập các thuộc 
tính và mỗi luật sinh kết hợp với một tập các quy tắc ngữ nghĩa (semantic rule) để tính 
giá trị của thuộc tính đi kèm với những ký hiệu có trong luật sinh văn phạm. Văn phạm 
và tập các quy tắc ngữ nghĩa tạo nên định nghĩa trực tiếp cú pháp. 
 Phiên dịch (translation) là một ánh xạ giữa input - output (input - output mapping). 
Output cho mỗi input x được xác định theo cách sau. Trước hết xây dựng cây phân 
tích cú pháp cho x. Giả sử nút n trong cây phân tích cú pháp có nhãn là ký hiệu văn 
phạm X. Ta viết X.a để chỉ giá trị của thuộc tính a của X tại nút đó. Giá trị của X.a tại 
n được tính bằng cách sử dụng quy tắc ngữ nghĩa cho thuộc tính a kết hợp với luật 
sinh cho X tại nút n. Cây phân tích cú pháp có thể hiện rõ giá trị của thuộc tính tại mỗi 
nút gọi là cây phân tích cú pháp chú thích (annotated parse tree). 
3. Thuộc tính tổng hợp (Synthesized Attributes) 
 Một thuộc tính được gọi là tổng hợp nếu giá trị của nó tại một nút trên cây cú pháp 
được xác định từ các giá trị của các thuộc tính tại các nút con của nút đó. 
 Ví dụ 2.7: Ðịnh nghĩa trực tiếp cú pháp cho việc dịch các biểu thức các số cách 
nhau bởi dấu + hoặc - thành ký pháp hậu tố như sau: 
Luật sinh Quy tắc ngữ nghĩa 
 E → E1 + T E.t := E1.t || T.t || ‘+’ 
 E → E1 - T E.t := E1.t || T.t || ‘-’ 
 E → T E.t := T.t 
 T → 0 T.t := ‘0’ 
 ... ... 
 16
 T → 9 T.t := ‘9’ 
Hình 2.3 - Ví dụ về định nghĩa trực tiếp cú pháp 
 Chẳng hạn, một quy tắc ngữ nghĩa E.t := E1.t || T.t || ‘+’ kết hợp với luật sinh xác 
định giá trị của thuộc tính E.t bằng cách ghép các ký pháp hậu tố của E1.t và T.t và 
dấu ‘+’. Dấu || có nghĩa như sự ghép các chuỗi. 
Ta có cây phân tích cú pháp chú thích cho biểu thức 9 - 5 + 2 như sau : 
E.t = 9 5 - 2 + 
E.t = 9 5 - T.t = 2 
T.t = 5 E.t = 9 
T.t = 9 
2 + 5 -9 
Hình 2.4 - Minh họa cây phân tích cú pháp chú thích 
 Giá trị của thuộc tính t tại mỗi nút được tính bằng cách dùng quy tắc ngữ nghĩa kết 
hợp với luật sinh tại nút đó. Giá trị thuộc tính tại nút gốc là ký pháp hậu tố của chuỗi 
được sinh ra bởi cây phân tích cú pháp. 
4. Duyệt theo chiều sâu (Depth - First Traversal) 
 Quá trình dịch được cài đặt bằng cách đánh giá các luật ngữ nghĩa cho các thuộc 
tính trong cây phân tích cú pháp theo một thứ tự xác định trước. Ta dùng phép duyệt 
cây theo chiều sâu để đánh giá quy tắc ngữ nghĩa. Bắt đầu từ nút gốc, thăm lần lượt 
(đệ qui) các con của mỗi nút theo thứ tự từ trái sang phải. 
Procedure visit (n : node); 
 begin 
 for với mỗi nút con m của n, từ trái sang phải do 
 visit (m); 
 Ðánh giá quy tắc ngữ nghĩa tại nút n; 
 end 
5. Lược đồ dịch (Translation Scheme) 
 Một lược đồ dịch là một văn phạm phi ngữ cảnh, trong đó các đoạn chương trình 
gọi là hành vi ngữ nghĩa (semantic actions) được gán vào vế phải của luật sinh. Lược 
đồ dịch cũng như định nghĩa trực tiếp cú pháp nhưng thứ tự đánh giá các quy tắc ngữ 
nghĩa được trình bày một cách rõ ràng. Vị trí mà tại đó một hành vi được thực hiện 
được trình bày trong cặp dấu ngoặc nhọn { } và viết vào vế phải luật sinh. 
 Ví dụ 2.8: rest → + term {print (‘+’)} rest1. 
 17
Hình 2.5 - Một nút lá được xây dựng cho hành vi ngữ nghĩa 
rest 
term+ rest1{print(‘+’) } 
 Lược đồ dịch tạo ra một output cho mỗi câu nhập x sinh ra từ văn phạm đã cho 
bằng cách thực hiện các hành vi theo thứ tự mà chúng xuất hiện trong quá trình duyệt 
theo chiều sâu cây phân tích cú pháp của x. Chẳng hạn, xét cây phân tích cú pháp với 
một nút có nhãn rest biểu diễn luật sinh nói trên. Hành vi ngữ nghĩa { print(‘+’) } được 
thực hiện sau khi cây con term được duyệt nhưng trước khi cây con rest1 được thăm. 
6. Phát sinh bản dịch (Emitting a Translation) 
 Trong chương này, hành vi ngữ nghĩa trong lược đồ dịch sẽ ghi kết quả của quá 
trình phiên dịch vào một tập tin, mỗi lần một chuỗi hoặc một ký tự. Chẳng hạn, khi 
dịch 9 - 5 + 2 thành 9 5 - 2 + bằng cách ghi mỗi ký tự trong 9 - 5 + 2 đúng một lần mà 
không phải ghi lại quá trình dịch của các biểu thức con. Khi tạo ra output dần dần theo 
cách này, thứ tự in ra các ký tự sẽ rất quan trọng. 
 Chú ý rằng các định nghĩa trực tiếp cú pháp đều có đặc điểm sau: chuỗi biểu diễn 
cho bản dịch của ký hiệu chưa kết thúc ở vế trái của mỗi luật sinh là sự ghép nối của 
các bản dịch ở vế phải theo đúng thứ tự của chúng trong luật sinh và có thể thêm một 
số chuỗi khác xen vào giữa. Một định ngh ... đi bằng các câu lệnh nhảy có điều kiện hoặc không điều kiện. Có 
một số các tùy chọn dùng để mô tả các đích nhảy : 
 1. Toán hạng làm chỉ thị cho biết vị trí đích. 
 2. Toán hạng làm chỉ thị mô tả khoảng cách tương đối cần nhảy theo chiều tới 
hoặc lui. 
 3. Ðích nhảy đến được mô tả bằng các ký hiệu tượng trưng gọi là các nhãn. 
Một số chỉ thị điều khiển trình tự cho máy là : 
lable l : Gán đích của các lệnh nhảy đến là l, không có tác dụng khác. 
goto l : Chỉ thị tiếp theo được lấy từ câu lệnh có lable l . 
gofalse l : Lấy giá trị trên đỉnh Stack ra, nếu giá trị là 0 thì nhảy đến l, 
ngược lại, thực hiện lệnh kế tiếp. 
gotrue l : Lấy giá trị trên đỉnh Stack ra, nếu giá trị khác 0 thì nhảy đến l, 
ngược lại, thực hiện lệnh kế tiếp. 
halt : Ngưng thực hiện chương trình. 
6. Dịch các câu lệnh 
Sơ đồ phác thảo đoạn mã máy ảo cho một số lệnh cấu trúc được chỉ ra trong hình 
sau: 
 IF expr THEN stmt WHILE expr DO stmt 
Code for expr 
Gofalse out 
Code for stmt 1 
Lable out 
Label test 
Code for expr 
Gofalse out 
Code for stmt 1 
Goto test 
Lable out 
 Hình 2.16 - Sơ đồ đoạn mã cho một số lệnh cấu trúc 
Xét sơ đồ đoạn mã cho câu lệnh If . Giả sử rằng newlable là một thủ tục trả về một 
 35
nhãn mới cho mỗi lần gọi. Trong hành vi ngữ nghĩa sau đây, nhãn được trả về bởi một 
lời gọi đến newlabel được ghi lại bằng cách dùng một biến cục bộ out : 
stmt → if expr then stmt1 { out := newlable; 
 stmt.t := expr.t || 
‘ gofalse ’ out || 
stmt1.t || 
‘ lable ’ out } 
 Thay vì in ra các câu lệnh, ta có thể sử dụng thủ tục emit để che dấu các chi tiết in. 
Chẳng hạn như emit phải xem xét xem mỗi chỉ thị máy ảo có cần nằm trên một hàng 
riêng biệt hay không. Sử dụng thủ tục emit, ta có thể viết lại như sau : 
stmt → if 
 expr { out := newlable; emit (‘ gofalse ’, out); } 
 then 
 stmt1 { emit (‘ lable ’, out); } 
Khi một hành vi ngữ nghĩa xuất hiện bên trong một luật sinh, ta xét các phần tử ở 
vế phải của luật sinh theo thứ tự từ trái sang phải. Ðoạn mã (ngôn ngữ giả) cho phép 
dịch phép gán và câu lệnh điều kiện If tương ứng như sau : 
 procedure stmt; 
 var test, out: integer; /* dùng cho các nhãn */ 
 begin 
 if lookahead = id then 
 begin 
 emit (‘lvalue’, tokenval); match (id); match (‘:=‘); expr; 
 end 
 else if lookahead = ‘if’ then 
 begin 
 match (‘if’); expr; out := newlable; 
 emit (‘gofalse’, out); match(‘then’); stmt; 
 emit (‘lable’, out); 
 end 
/* đoạn mã cho các lệnh còn lại */ 
 else error; 
 end; 
 36
VIII. KẾT NỐI CÁC KỸ THUẬT 
Trong các phần trên, chúng ta đã trình bày một số kỹ thuật phiên dịch trực tiếp cú 
pháp để xây dựng kỳ đầu của trình biên dịch. Phần này sẽ thực hiện việc kết nối chúng 
lại bằng cách giới thiệu một chương trình C có chức năng dịch trung tố - hậu tố cho 
một ngôn ngữ gồm dãy các biểu thức kết thúc bằng các dấu chấm phẩy. Các biểu thức 
gồm có các số, danh biểu, các toán tử +, -, *, /, div và mod. Output cho chương trình là 
dạng biểu diễn hậu tố cho mỗi biểu thức. 
1. Mô tả chương trình dịch 
 Chương trình dịch được thiết kế bằng cách dùng lược đồ dịch trực tiếp cú pháp có 
dạng như sau : 
 start → list eof 
 list → expr ; list 
 | ε 
 expr → expr + term { print (‘+ ’) } 
 | expr - term { print (‘- ’) } 
 | term 
 term → term * factor { print (‘* ’) } 
 | term / factor { print (‘/ ’) } 
 | term div factor { print (‘DIV’) } 
 | term mod factor { print (‘MOD’) } 
 | factor 
 factor → ( expr ) 
 | id { print (id.lexeme) } 
 | num { print (num.value) } 
Trong đó, token id biểu diễn một dãy không rỗng gồm các chữ cái và ký số bắt 
đầu bằng một chữ cái, num là dãy ký số, eof là ký tự cuối tập tin (end - of - file). Các 
token được phân cách bởi một dãy ký tự blank, tab và newline - gọi chung là các 
khoảng trắng (white space). Thuộc tính lexeme của token id là chuỗi ký tự tạo ra token 
dó, thuộc tính value của token num chứa số nguyên được biểu diễn bởi num. 
Ðoạn mã cho chương trình dịch bao gồm 7 thủ tục, mỗi thủ tục được lưu trong một 
tập tin riêng. Ðiểm bắt đầu thực thi chương trình nằm trong thủ tục chính main.c gồm 
có một lời gọi đến init( ) để khởi gán, theo sau là một lời gọi đến parse( ) để dịch. Các 
thủ tục còn lại được mô tả tổng quan như hình sau: 
 37
Hình 2.17 - Sơ đồ các thủ tục cho chương trình dịch biểu thừc 
Biểu thức trung tố 
Biểu thức hậu tố 
lexer.c 
init.c 
error.c parser.c symbol.c 
emitter.c 
 Trước khi trình bày đoạn mã lệnh cho chương trình dịch, chúng ta mô tả sơ lược 
từng thủ tục và cách xây dựng chúng. 
Thủ tục phân tích từ vựng lexer.c 
 Bộ phân tích từ vựng là một thủ tục có tên lexan( ) được gọi từ bộ phân tích cú 
pháp khi cần tìm các token. Thủ tục này đọc từng ký tự trong dòng nhập, trả về token 
vừa xác định được cho bộ phân tích cú pháp. Giá trị của các thuộc tính đi kèm với 
token được gán cho biến toàn cục tokenval. Bộ phân tích cú pháp có thể nhận được các 
token sau : + - * / DIV MOD ( ) ID NUM DONE 
Trị từ vựng Token Giá trị thuộc tính 
Khoảng trắng 
Chuỗi các chữ số NUM Giá trị số 
Div DIV 
Mod MOD 
Chuỗi mở đầu là chữ cái, theo 
sau là chữ cái hoặc chữ số 
ID Chỉ số trong symtable 
Ký tự cuối tập tin - eof DONE 
Các ký tự khác Ký tự tương ứng NONE 
 Trong đó ID biểu diễn cho một danh biểu, NUM biểu diễn cho một số và DONE là 
ký tự cuối tập tin eof. Các khoảng trắng đã được loại bỏ. Bảng sau trình bày các token 
và giá trị thuộc tính được sinh ra bởi bộ phân tích từ vựng cho mỗi token trong chương 
trình nguồn. 
Thủ tục phân tích cú pháp parser.c 
 Bộ phân tích cú pháp được xây dựng theo phương pháp phân tích đệ quy xuống. 
Trước tiên, ta loại bỏ đệ quy trái ra khỏi lược đồ dịch bằng cách thêm vào 2 biến mới 
R1 cho expr và R2 cho factor, thu được lược đồ dịch mới như sau: 
 start → list eof 
 38
 list → expr ; list 
| ε 
 expr → term R1 
 R1 → + term { print (‘ + ’) } R1 
 | - term { print (‘ - ’) } R1 
 | ε 
 term → factor R2 
 R2 → * factor { print (‘ * ’) } R2 
 | / factor { print (‘ / ’) } R2 
 | DIV factor { print (‘DIV’) } R2 
 | MOD factor { print (‘MOD’) }R2 
 | ε 
 factor → ( expr ) 
 | id { print (id.lexeme) } 
 | num { print (num.value) } 
Sau đó, chúng ta xây dựng các hàm cho các ký hiệu chưa kết thúc expr, term và 
factor. Hàm parse( ) cài đặt ký hiệu bắt đầu start của văn phạm, nó gọi lexan mỗi khi 
cần một token mới. Bộ phân tích cú pháp ở giai đoạn này sử dụng hàm emit để sinh ra 
kết quả và hàm error để ghi nhận một lỗi cú pháp. 
Thủ tục kết xuất emitter.c 
 Thủ tục này chỉ có một hàm emit (t, tval) sinh ra kết quả cho token t với giá trị 
thuộc tính tval. 
Thủ tục quản lý bảng ký hiệu symbol.c và khởi tạo init.c 
 Thủ tục symbol.c cài đặt cấu trúc dữ liệu cho bảng danh biểu. Các ô trong mảng 
symtable là các cặp gồm một con trỏ chỉ đến mảng lexemes và một số nguyên biểu thị 
cho token được lưu tại vị trí đó. 
Thủ tục init.c được dùng để khởi gán các từ khóa vào bảng danh biểu. Biểu diễn 
trị từ vựng và token cho tất cả các từ khóa được lưu trong mảng keywords cùng kiểu 
với mảng symtable. Hàm init( ) duyệt lần lượt qua mảng keyword, sử dụng hàm insert 
để đặt các từ khóa vào bảng danh biểu. 
Thủ tục lỗi error.c 
 Thủ tục này quản lý các ghi nhận lỗi và hết sức cần thiết. Khi gặp một lỗi cú pháp, 
trình biên dịch in ra một thông báo cho biết rằng một lỗi đã xảy ra trên dòng nhập hiện 
hành và dừng lại. Một kỹ thuật khắc phục lỗi tốt hơn có thể sẽ nhảy qua dấu chấm 
phẩy kế tiếp và tiếp tục phân tích câu lệnh sau đó. 
2. Cài đặt chương trình nguồn 
Chương trình nguồn C cài đặt chương trình dịch trên. 
 39
/ **** global.h ***************************************** / 
# include /* tải các thủ tục xuất nhập */ 
# include /* tải các thủ tục kiểm tra ký tự */ 
# define BSIZE 128 /* buffer size kích thước vùng đệm */ 
# define NONE - 1 
# define EOS ' \ 0 ' 
# define NUM 256 
# define DIV 257 
# define MOD 258 
# define ID 259 
# define DONE 260 
int tokenval; /* giá trị cuả thuôcü tính token */ 
int lineno; 
struct entry { /* khuôn dạng cho ô trong bảng ký hiệu*/ 
 char * lexptr; 
 int token; 
} 
struct entry symtable[ ] /* bảng ký hiệu*/ 
/ **** lexer.c ***************************************** / 
# include "global.h" 
char lexbuf [BSIZE] 
int lineno = 1; 
int tokenval = NONE; 
int lexan ( ) /* bộ phân tích từ vựng */ 
{ 
 int t; 
 while(1) { 
 t = getchar ( ); 
 if ( t = = ‘ ‘ || t = = ‘ \t’) ; /* xóa các khoảng trắng */ 
 else if (t = = ‘ \n ’) 
lineno = lineno + 1; 
 else if ( isdigit (t) ) { /* t là một ký số */ 
 ungetc (t, stdin); 
scanf (" %d", & tokenval); 
 return NUM; 
 } 
else if ( isalpha (t) ) { /* t là một chữ cái */ 
 40
int p, b = 0; 
 while ( isalnum (t) ) { /* t thuộc loại chữ - số */ 
 lexbuf[b] = t; 
 t = getchar ( ); 
 b = b + 1; 
 if (b > = BSIZE) 
 error("compiler error"); 
 } 
 lexbuf[b] = EOS; 
 if (t ! = EOF) 
 ungetc (t, stdin); 
 p = lookup (lexbuf); 
 if (p = = 0) 
 p = insert (lexbuf, ID) 
 tokenval = p; 
 return symtable[p].token; 
 } 
 else if (t = = EOF) { 
return DONE; 
 else { 
 tokenval = NONE; 
return t; 
 } 
 } 
 } 
/ **** parser.c ***************************************** / 
# include "global.h" 
int lookahead; 
parse ( ) /* phân tích cú pháp và dịch danh sách biểu thức */ 
{ 
lookahead = lexan ( ); 
while (lookahead ! = DONE) { 
expr( ) ; match (‘ ; ’); 
 } 
} 
expr ( ) 
{ 
 int t; 
term ( ); 
 while(1) 
 switch (lookahead) { 
 case ' + ' : case ' - ' : 
 t = lookahead; 
 41
 match (lookahead); term ( ); emit (t, NONE); 
 continue; 
 default : 
 return; 
 } 
} 
term ( ) 
{ 
 int t; 
factor ( ); 
 while(1) 
 switch (lookahead) { 
 case ' * ' : case ' / ' : case ' DIV ' : case 'MOD ' : 
 t = lookahead; 
 match (lookahead); factor ( ); emit (t, NONE); 
 continue; 
 default : 
 return; 
 } 
} 
factor ( ) 
{ 
 switch (lookahead) { 
 case ' ( ' : 
 match (' ( '); expr ( ); match (' ) '); break; 
 case NUM : 
 emit (NUM, tokenval) ; match (' NUM '); break; 
 case ID : 
 emit (ID, tokenval) ; match (' ID '); break; 
 default : 
 error ( "syntax error"); 
 } 
} 
match ( t ) 
 int t; 
{ 
 if (lookahead = = t) 
lookahead = lexan( ); 
 else error ("syntax error"); 
} 
/ **** emitter.c ***************************************** / 
# include "global.h" 
 42
emit (t, tval) /* tạo ra kết quả */ 
 int t, tval; 
{ 
switch ( t ) { 
 case ' + ' : case ' - ' : case ' * ' : case ' / ' : 
 printf (" %c \n", t); break; 
 case DIV : 
 printf (" DIV \n", t); break; 
 case MOD : 
 printf (" MOD \n", t); break; 
 case NUM : 
 printf (" %d \n", tval ); break; 
 case ID : 
 printf (" %s \n", symtable [tval]. lexptr); break; 
 default : 
 printf (" token %d , tokenval %d \n ", t, tval ); 
 } 
} 
/ **** symbol.c ***************************************** / 
# include "global.h" 
# define STRMAX 999 /* kích thước mảng lexemes */ 
# define SYMMAX 100 /* kích thước mảng symtable */ 
char lexemes [STRMAX]; 
int lastchar = -1 /* vị trí được dùng cuối cùng trong lexemes */ 
struct entry symtable [SYMMAX]; 
int lastentry = 0 /* vị trí được dùng cuối cùng trong symtable */ 
int lookup (s) /* trả về vị trí của ô cho s */ 
 char s [ ]; 
{ 
 int p; 
 for (p = lastentry; p > 0; p = p - 1) 
 if (strcmp (symtable[p].lexptr, s ) = = 0) 
 return p; 
 return 0; 
} 
int insert (s, tok) /* trả về vị trí của ô cho s */ 
 char s [ ]; 
 int tok; 
{ 
 int len; 
 len = strlen (s) /* strlen tính chiều dài của s */ 
 43
 if ( lastentry + 1 > = SYMMAX) 
 error ("symbol table full"); 
 if ( lastchar + len + 1 > = SYMMAX) 
 error ("lexemes array full"); 
 lastentry = lastentry + 1; 
 symable [lastentry].token = tok; 
 symable [lastentry].lexptr = &lexemes [lastchar + 1]; 
 lastchar = lastchar + len + 1; 
 strcpy (symable [lastentry].lexptr, s); 
 return lastentry; 
} 
/ **** init.c ***************************************** / 
# include "global.h" 
struct entry keyword [ ] = { 
 "div", DIV 
 "mod", MOD 
 0, 0 
} 
init ( ) /* đưa các từ khóa vào symtable */ 
{ 
 struct entry * p ; 
for (p = keywords; p → token; p ++ ) 
 if (strcmp (symtable[p].lexptr, s ) = = 0) 
 insert (p → lexptr, p → token) ; 
} 
/ **** error.c ***************************************** / 
# include "global.h" 
eeror (m) /* sinh ra tất cả các thông báo lỗi * / 
 char * m; 
{ 
 fprintf (stderr, " line % d : % s \n, lineno, m) 
 exit ( 1 ) /* kết thúc không thàình công * / 
} 
/ **** main.c ***************************************** / 
# include "global.h" 
main ( ) 
{ 
 44
 init ( ); 
 parse ( ); 
 exit (0); /* kết thúc thàình công * / 
} 
/ ****************************************************************** / 
 45
BÀI TẬP CHƯƠNG II 
2.1. Cho văn phạm phi ngữ cảnh sau: 
 S → S S + | S S * | a 
 a) Viết các luật sinh dẫn ra câu nhập: a a + a * 
 b) Xây dựng một cây phân tích cú pháp cho câu nhập trên? 
 c) Văn phạm này sinh ra ngôn ngữ gì? Giải thích câu trả lời. 
2.2. Ngôn ngữ gì sinh ra từ các văn phạm sau? Văn phạm nào là văn phạm mơ hồ? 
a) S → 0 S 1 | 0 1 
 b) S → + S S | - S S | a 
c) S → S ( S ) S | ∈ 
d) S → a S b S | b S a S | ∈ 
e) S → a | S + S | S S | S * | ( S ) 
2.3. Xây dựng văn phạm phi ngữ cảnh đơn nghĩa cho các ngôn ngữ sau đây: 
a) Các biểu thức số học dưới dạng hậu tố. 
b) Danh sách danh biểu có tính kết hợp trái được phân cách bởi dấu phẩy. 
c) Danh sách danh biểu có tính kết hợp phải được phân cách bởi dấu phẩy. 
d) Các biểu thức số học của số nguyên và danh biểu với 4 phép toán hai ngôi : 
+. -, *, /. 
2.4. Viết chỉ thị máy ảo kiểu Stack cho quá trình dịch các biểu thức sau sang dạng 
hậu tố: 
a) t : = (a mod b) * 1998 - (2000 * c +100 ) div 4 +1999 
b) t : = a1 mod c2 + ( b3 -156 * d4 ) div 7 / 3 
c) y := x + 100 z 3 t 
2.5. Xây dựng lược đồ dịch trực tiếp cú pháp để dịch một biểu thức số học từ dạng 
trung tố sang dạng hậu tố ( cho các phép toán 2 ngôi ). 
a) Xây dựng chương trình đổi mã hậu tố sang mã máy ảo kiểu Stack . 
b) Viết chương trình thực thi mã máy ảo . 
 46
2.6. Yêu cầu như bài 5 cho biểu thức số học ở dạng hậu tố sang dạng trung tố. 
2.7. Xây dựng một lược đồ dịch trực tiếp cú pháp để xác định rằng các dấu ngoặc 
trong một chuỗi nhập là cân bằng. 
2.8. Xây dựng lược đồ dịch trực tiếp cú pháp để dịch phát biểu FOR của ngôn ngữ C 
có dạng như sau: FOR ( exp1; exp2; exp3 ) Stmt sang dạng mà máy ảo kiểu Stack. 
Viết chương trình thực thi mã máy ảo kiểu Stack . 
2.9. Xét đoạn văn phạm sau đây cho các câu lệnh if-then và if-then-else: 
 Stmt → if expr then stmt 
 | if expr then stmt else stmt 
 | other 
 a) Chứng tỏ văn phạm này là văn phạm mơ hồ. 
 b) Xây dựng một văn phạm không mơ hồ tương đương với quy tắc: mỗi else 
chưa được kết hợp sẽ được kết hợp với then chưa kết hợp gần nhất trước đó. 
 c) Xây dựng một lược đồ dịch trực tiếp cú pháp để dịch các câu lệnh điều kiện 
thành mã máy ảo kiểu Stack. 
2.10. Xây dựng lược đồ dịch trực tiếp cú pháp để dịch các phát biểu của ngôn ngữ 
PASCAL có dạng như sau sang dạng mà máy ảo kiểu Stack. Viết chương trình thực 
thi mã máy ảo kiểu Stack: 
a) REPEAT Stmt UNTIL expr 
 b) IF expr THEN Stmt ELSE Stmt 
 c) WHILE expr DO Stmt 
 d) FOR i := expr1 downto expr2 DO Stmt 
 47