Giáo trình Chương trình dịch (Phần 1)

Khoa công nghệ thông tin - Đại học Thái Nguyên
Bộ môn công nghệ phần mềm 
GIÁO TRÌNH MÔN CHƯƠNG TRÌNH DỊCH 
(Compiler Construction)
Thái nguyên, 2007 
LỜI NÓI ĐẦU
Môn học chương trình dịch là môn học của ngành khoa học máy tính. Trong 
suốt thập niên 50, trình biên dịch được xem là cực kỳ khó viết. Ngày nay, việc viết 
một chương trình dịch trở nên đơn giản hơn cùng với sự hỗ trợ của các công cụ 
khác. Cùng với sự phát triển của các chuyên ngành lý thuyết ngôn ngữ hình thức và 
automat, lý thuyết thiết kế một trình biên dịch ngày một hoàn thiện hơn. 
Có rất nhiều các trình biên dịch hiện đại, có hỗ trợ nhiều tính năng tiện ích 
khác nữa. Ví dụ: bộ visual Basic, bộ studio của Microsoft, bộ Jbuilder, netbean, 
Delphi  Tại sao ta không đứng trên vai những người khổng lồ đó mà lại đi nghiên 
cứu cách xây dựng một chương trình dịch nguyên thuỷ. Với vai trò là sinh viên 
công nghệ thông tin ta phải tìm hiểu nghiên cứu xem một chương trình dịch thực sự 
thực hiện như thế nào? 
Mục đích của môn học này là sinh viên sẽ học các thuật toán phân tích ngữ 
pháp và các kỹ thuật dịch, hiểu được các thuật toán xử lý ngữ nghĩa và tối ưu hóa 
quá trình dịch.
Yêu cầu người học nắm được các thuật toán trong kỹ thuật dịch.
Nội dung môn học : Môn học Chương trình dịch nghiên cứu 2 vấn đề:
- Lý thuyết thiết kế ngôn ngữ lập trình ( cách tạo ra một ngôn ngữ giúp người 
lập trình có thể đối thoại với máy và có thể tự động dịch được).
- Cách viết chương trình chuyển đổi từ ngôn ngữ lập trình này sang ngôn ngữ 
lập trình khác.
Học môn chương trình dịch giúp ta: 
- Nắm vững nguyên lý lập trình: Hiểu từng ngôn ngữ, điểm mạnh điểm yếu 
của nó => chọn ngôn ngữ thích hợp cho dự án của mình. Biết chọn chương trình 
dịch thích hợp (VD với pascal dưới Dos: chương trình dịch là turbo pascal. Đối với 
ngôn ngữ C: chọn turbo C hay bolean C? Bolean C tiện lợi, dễ dùng, turbo C sinh 
mã gọn, không phải lo vè vấn đề tương thích với hệ điều hành nhưng khoá dùng 
hơn). Phân biệt được công việc nào do chương trình dịch thực hiện và do chương 
trình ứng dụng thực hiện.
- Vận dụng: thực hiện các dự án xây dựng chương trình dịch. Áp dụng vào 
các ngành khác như xử lý ngôn ngữ tự nhiên 
Để viết được trình biên dịch ta cần có kiến thức về ngôn ngữ lập trình, cấu 
trúc máy tính, lý thuyết ngôn ngữ, cấu trúc dữ liệu, phân tích thiết kế giải thuật và 
công nghệ phần mềm.
Những kiến thức của môn học cũng có thể được sử dụng trong các lĩnh vực 
khác như xử lý ngôn ngữ tự nhiên.
Tài liệu tham khảo: 
1. Giáo trình sử dụng: Dick Grune, Ceriel Jacobs, Parsing Techniques: A 
Practical Guide, 1998
2. Một số tài nguyên trực tuyến có thể được tìm thấy bằng việc sử dụng máy 
tìm kiếm, chẳng hạn như  và 
3. Bài giảng Lý thuyết và Thực hành Chương Trình Dịch của Lê Anh Cường, 
khoa Công Nghệ, ĐHQG Hà nội, 2004.
4. Giáo trình lý thuyết, thực hành môn học Chương trình dịch của Phạm 
Hồng Nguyên, Khoa Công Nghệ, ĐHQG Hà nội, 1998.
5. Ngôn ngữ hình thức của Nguyễn Văn Ba, ĐHBK Hà nội, 1994
6. Thực hành kỹ thuật biên dịch của Nguyễn Văn Ba, ĐHBK Hà nội, 1993
7. Compiler: principles techniques and tools của A.V. Aho, Ravi Sethi, D. 
Ulman, 1986 
8. Bản dịch của tài liệu: Trình biên dịch: Nguyên lý, kỹ thuật và công cụ của 
Trần Đức Quang, 2000.
Chương 1: Tổng quan về ngôn ngữ lập trình và chương trình dịch
1. Ngôn ngữ lập trình và chương trình dịch.
Con người muốn máy tính thực hiện công việc thì con người phải viết yêu cầu 
đưa cho máy tính bằng ngôn ngữ máy hiểu được. Việc viết yêu cầu gọi là lập 
trình. Ngôn ngữ dùng để lập trình gọi là ngôn ngữ lập trình. Có nhiều ngôn 
ngữ lập trình khác nhau. Dựa trên cơ sở của tính không phụ thuộc vào máy 
tính ngày càng cao người ta phân cấp các ngôn ngữ lập trình như sau:
- Ngôn ngữ máy (machine languge)
- Hợp ngữ (acsembly langguge) 
- Ngôn ngữ cấp cao (high level langguage)
Ngôn ngữ máy chỉ gồm các số 0 và 1, khó hiểu đối với người sử dụng. Mà 
ngôn ngữ tự nhiên của con người lại dài dòng nhiều chi tiết mập mờ, không rõ ràng 
đối với máy. Để con người giao tiếp được với máy dễ dàng cần một ngôn ngữ trung 
gian gần với ngôn ngữ tự nhiên. Vì vậy ta cần có một chương trình để dịch các 
chương trình trên ngôn ngữ này sang mã máy để có thể chạy được. Những chương 
trình làm nhiệm vụ như vậy gọi là các chương trình dịch. Ngoài ra, một chương 
trình dịch còn chuyển một chương trình từ ngôn ngữ nay sang ngôn ngữ khác tương 
đương. Thông thường ngôn ngưc nguồn là ngôn ngữ bậc cao và ngôn ngữ đích là 
ngôn ngữ bậc thấp, ví dụ như ngôn ngữ Pascal hay ngôn ngữ C sang ngôn ngữ 
Acsembly.
* Định nghĩa chương trình dịch:
Chương trình dịch 
là một chương trình 
thực hiện việc chuyển 
đổi một chương trình 
hay đoạn chương trình 
từ ngôn ngữ này (gọi là 
ngôn ngữ nguồn) sang 
ngôn ngữ khác (gọi là 
ngôn ngữ đích) tương 
đương.
Để xây dựng được chương trình dịch cho một ngôn ngữ nào đó, ta cần biết về 
đặc tả của ngôn ngữ lập trình, cú pháp và ngữ nghĩa của ngôn ngữ lập trình đó 
Để đặc tả ngôn ngữ lập trình, ta cần định nghĩa:
- Tập các kí hiệu cần dùng trong các chương trình hợp lệ.
- Tập các chương trình hợp lệ.
chương trình 
nguồn (ngôn 
ngữ bậc cao)
chương trình 
dịch
chương trình 
đích (ngôn 
ngữ máy)
Lỗi
Hình 1.1: Sơ đồ một chương trình dịch
- Nghĩa của từng chương trình hợp lệ.
Việc định nghĩa tập các kí hiệu cần dùng của ngôn ngữ là dế dàng, ta chỉ cần 
liệt kê là đủ. Việc xác định các chương trình hợp lệ thì khó khăn hơn. Thông 
thường ta dùng các luật của văn phạm để đặc tả. Việc thứ 3, định nghĩa ý nghĩa của 
chương trình hợp lệ là khó khăn nhất. Có 3 phương pháp để xác định nghĩa của 
chương trình hợp lệ.
+ Phương pháp 1: định nghã bằng phép ánh xạ. ánh xạ mỗi chương trình vào 
một câu trong ngôn ngữ mà ta có thể hiểu được. 
+ Phương pháp 2: Xác định ý nghĩa của chương trình bằng một máy lý tưởng. 
Ý nghĩa của chương rình được đăc tả trong ngôn từ của máy lý tưởng. Máy lý 
tưởng là bộ thông dịch của ngôn ngữ.
+ Phương pháp 3: ý nghĩa cảu chương trình nguồn là sản phẩm xuất ra của 
trình biên dịch, khi nó dịch chương trình nguồn.
2. Phân loại chương trình dịch.
Có thể phân thành nhiều loại tuỳ theo các tiêu chí khác nhau.
- 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.
- Theo phương pháp dịch chạy: 
+ Thông dịch: (diễn giải - interpreter) chương trình thông dịch đọc chương 
trình nguồn theo từng lệnh và phân tích rồi thực hiện nó. (Ví dụ hệ điều hành thực 
hiện các câu lệnh DOS, hay hệ quản trị cơ sở dữ liệu Foxpro). Hoặc ngôn ngữ 
nguồn không được chuyển sang ngôn ngữ máy mà chuyển sang một ngôn ngữ 
trung gian. Một chương trình sẽ có nhiệm vụ đọc chương trình ở ngôn ngữ trung 
gian này và thực hiện từng câu lệnh. Ngôn ngữ trung gian được gọi là ngôn ngữ của 
một máy ảo, chương trình thông dịch thực hiện ngôn ngữ này gọi là máy ảo. 
Chương 
trình 
nguồn Compiler
CT ở NN 
trung gian Interpreter
Kết 
quảHình 1.2 Hệ thống thông dịch
Ví dụ hệ thông dịch Java. Mã nguồn Java được dịch ra dạng Bytecode. File 
đích này được một trình thông dịch gọi là máy ảo Java thực hiện. Chính vì vậy mà 
người ta nói Java có thể chạy trên mọi hệ điều hành có cài máy ảo Java.
+ Biên dịch: toàn bộ chương trình nguồn được trình biên dịch chuyển sang 
chương trình đích ở dạng mã máy. Chương trình đích này có thể chạy độc lập trên 
máy mà không cần hệ thống biên dịch nữa.
- Theo lớp văn phạm: LL (1) (LL – Left to right, leftmost) LR(1) (LR – letf to 
right, right most) 
1.3. Cấu trúc của chương trình dịch.
1.3.1. cấu trúc tĩnh (cấu trúc logic)
1) Phân tích từ vựng: đọc luồng kí tự tạo thành chương trình nguồn từ trái 
sang phải, tách ra thành các từ tố (token).
- Từ vựng: Cũng như ngôn ngữ tự nhiên, ngôn ngữ lập trình cũng được xây 
dựng dựa trên bộ từ vựng. Từ vựng trong ngôn ngữ lập trình thường được xây dựng 
dựa trên bộ chữ gồm có:
+ chữ cái: A .. Z, a . . z
+ chữ số: 0..9
+ các ký hiệu toán học: +, - , *, /, (, ), =, , !, %, /
+ các ký hiệu khác: [, ], . . . 
Các từ vựng được ngôn ngữ hiểu bao gồm các từ khóa, các tên hàm, tên hằng, tên 
biến, các phép toán, . . .
Các từ vựng có những qui định nhất định ví dụ: tên viết bởi chữ cái đầu tiên sau đó 
là không hoặc nhiều chữ cái hoặc chữ số, phép gán trong C là =, trong Pascal là 
:=,v. . . 
Để xây dựng một chương trình dịch, hệ thống phải tìm hiểu tập từ vựng của 
ngôn ngữ nguồn và phân tích để biết được từng loại từ vựng và các thuộc tính của 
nó, 
Ví dụ: 
Câu lệnh trong chương trình nguồn 
viết bằng ngôn ngữ pascal: 
“a := b + c * 60”
Chương trình phân tích từ vựng sẽ trả về:
 a là tên (tên (định danh ))
:= là toán tử gán
b là tên (định danh) 
+ là toán tử cộng
c là định danh 
* là toán tử nhân 
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) 
2). Phân tích cú pháp: Phân tích cấu 
trúc ngữ pháp của chương trình. Các từ tố 
được nhóm lại theo cấu trúc phân cấp.
- Cú pháp: Cú pháp là thành phần 
quan trọng nhất trong một ngôn ngữ. Như 
chúng ta đã biết trong ngôn ngữ hình thức 
thì ngôn ngữ là tập các câu thỏa mãn văn 
phạm của ngôn ngữ đó. Ví dụ như 
câu = chủ ngữ + vị ngữ
vị ngữ = động từ + bổ ngữ
v.v. . . 
Trong ngôn ngữ lập trình, cú pháp của nó 
được thể hiện bởi một bộ luật cú pháp. Bộ 
luật này dùng để mô tả cấu trúc của 
chương trình, các câu lệnh. Chúng ta quan 
tâm đến các cấu trúc này bao gồm:
1) các khai báo
2) biểu thức số học, biểu thức logic
3) các lệnh: lệnh gán, lệnh gọi hàm, 
lệnh vào ra, . . .
4) câu lệnh điều kiện if 
5) câu lệnh lặp: for, while
6) chương trình con (hàm và thủ tục)
Nhiệm vụ trước tiên là phải biết được bộ luật cú pháp của ngôn ngữ mà mình định 
xây dựng chương trình cho nó.
Với một chuỗi từ tố và tập luật cú pháp của ngôn ngữ, bộ phân tích cú pháp tự 
động đưa ra cây cú pháp cho chuỗi nhập. Khi cây cú pháp xây dựng xong thì quá 
trình phân tích cú pháp của chuỗi nhập kết thúc thành công. Ngược lại nếu bộ phân 
tích cú pháp áp dụng tất cả các luật hiện có nhưng không thể xây dựng được cây cú 
pháp của chuỗi nhập thì thông báo rằng chuỗi nhập không viết đúng cú pháp.
Chương trình phải phân tích chương trình nguồn thành các cấu trúc cú pháp 
của ngôn ngữ, từ đó để kiểm tra tính đúng đắn về mặt ngữ pháp của chương trình 
nguồn. 
3). Phân tích ngữ nghĩa: Phân tích các đặc tính khác của chương trình mà 
không phải đặc tính cú pháp. Kiểm tra chương trình nguồn để tìm lỗi cú pháp và sự 
hợp kiểu.
Dựa trên cây cú pháp bộ phân tích ngữ nghĩa xử lý từng phép toán. Mỗi phép 
toán nó kiểm tra các toán hạng và loại dữ liệu của chúng có phù hợp với phép toán 
không.
 VD: tên (biến) được khai báo kiểu real, 60 là số kiểu interge vì vậy trình biên 
dịch đổi thành số thực 60.0.
- Ngữ nghĩa: của một ngôn ngữ lập trình liên quan đến:
+ Kiểu, phạm vi của hằng và biến
+ Phân biệt và sử dụng đúng tên hằng, tên biến, tên hàm
Chương trình dịch phải kiểm tra được tính đúng đắn trong sử dụng các đại lượng 
này. Ví dụ kiểm tra không cho gán giá trị cho hằng, kiểm tra tính đúng đắn trong 
gán kiểu, kiểm tra phạm vi, kiểm tra sử dụng tên như tên không được khai báo 
trùng, dùng cho gọi hàm phải là tên có thuộc tính hàm, . . . 
4) Sinh mã trung gian: Sinh chương trình rong ngôn ngữ trung gian nhằm: dễ 
sinh và tối ưu mã hơn dễ chuyển đổi về mã máy hơn.
sau giai đoạn phân tích thì mã trung gian sinh ra như sau:
temp1 := 60
temp2 := id3 * temp1
temp3 := id2 + temp 2
id1 := temp3 (1.2)
(trong đó id1 là position; id2 là initial và id3 là rate)
5). Tối ưu mã: Sửa đổi chương trình trong ngôn ngữ trung gian hằm cải tién 
chương trình đích về hiệu năng.
Ví dụ như với mã trung gian ở (1.2), chúng ta có thể làm tốt hơn đoạn mã để 
tạo ra được các mã máy chạy nhanh hơn như sau:
temp1 := id3 * 60
id1 := id2 + temp1 (1.3)
6). Sinh mã: tạo ra chương trình đích từ chương trình trong ngôn ngữ trung 
gian đẫ tối ưu.
Thông thường là sinh ra mã máy hay mã hợp ngữ. Vấn đề quyết định là việc 
gán các biến cho các thanh ghi. 
Chẳng hạn sử dụng các thanh ghi R1 và R2, các chỉ thị lệnh MOVF, MULF, 
ADDF, chúng ta sinh mã cho (1.3) như sau:
MOVF id3, R2
MULF #60, R2
MOVF id2, R1
ADDF R2, R1
MOVF R1, id1 (1.4)
Ngoài ra, chương trình dịch còn phải thực hiện nhiệm vụ:
* Quản lý bảng ký hiệu: Để ghi lại các kí hiệu, tên  đã sử dụng trong 
chương trình nguồn cùng các thuộc tính kèm theo như kiểu, phạm vi, giá trị ... để 
dùng cho các bước cần đến.
Tõ tè(token) + Thuéc tÝnh (kiÓu, ®Þa chØ lu tr÷) = B¶ng ký 
hiÖu (Symbol table). 
Trong quá trình phân tích từ vựng, các tên sẽ được lưu vào bảng ký hiệu, sau 
đó từ giai đoạn phân tích ngữ nghĩa các thông tin khác như thuộc tính về tên (tên 
hằng, tên biến, tên hàm) sẽ được bổ sung trong các giai đoạn sau.
- Giai đoạn phân tích từ vựng: lưu trữ trị từ vựng vào bảng kí hiệu nếu nó 
chưa có.
- Giai đoạn còn lại: lưu trữ thuộc tính của từ vựng hoặc truy xuất các thông 
tin thuộc tính cho từng giai đoạn.
Bảng kí hiệu được tổ chức như cấu trúc dữ liệu với mỗi phần tử là một mẩu 
tin dùng để lưu trữ trị từ vựng và các thuộc tính của nó.
- Trị từ vựng: tên từ tố.
- Các thuộc tính: kiểu, tầm hoạt động, số đối số, kiểu của đối số ...
VÝ dô: var position, initial, rate : real th× thuéc tÝnh kiÓu 
real cha thÓ x¸c ®Þnh. C¸c giai ®o¹n sau ®ã nh ph©n tÝch 
ng÷ nghÜa vµ sinh m· trung gian míi ®a thªm c¸c th«ng tin 
nµy vµo vµ sö dông chóng. Nãi chung giai ®o¹n sinh m· sÏ sö 
dông b¶ng ký hiÖu ®Ó gi÷ c¸c th«ng tin chi tiÕt vÒ danh 
biÓu.
* Xử lý lỗi: Khi phát hiện ra lỗi trong quá trình dịch thì nó ghi lại vị trí gặp 
lỗi, loại lỗi, những lỗi khác có liên quan đến lỗi này để thông báo cho người lập 
trình. 
Mçi giai ®o¹n cã thÓ cã nhiÒu lçi, tïy thuéc vµo tr×nh biªn 
dÞch mµ cã thÓ lµ:
- Dõng vµ th«ng b¸o lçi khi gÆp lçi dÇu tiªn (Pascal).
- Ghi nhËn lçi vµ tiÕp tôc qu¸ tr×nh dÞch (C).
+ Giai ®o¹n ph©n tÝch tõ vùng: cã lçi khi c¸c ký tù kh«ng thÓ 
ghÐp thµnh mét token (vÝ dô: 15a, a@b,...)
+ Giai ®o¹n ph©n tÝch có ph¸p: Cã lçi khi c¸c token kh«ng 
thÓ kÕt hîp víi nhau theo cÊu tróc ng«n ng÷ (vÝ dô: if stmt then 
expr).
+ Giai ®o¹n ph©n tÝch ng÷ nghÜa b¸o lçi khi c¸c to¸n h¹ng cã 
kiÓu kh«ng ®óng yªu cÇu cña phÐp to¸n.
* Giai đoạn phân tích có đầu vào là ngôn ngữ nguồn, đầu ra là ngôn ngữ trung 
gian gọi là kỳ trước (fron end). Giai đoạn tổng hợp có đầu vào là ngôn ngữ trung 
gian và đầu ra là ngô ngữ đích gọi là kỳ sau (back end). 
Đối với các ngôn ngữ nguồn, ta chỉ cần quan tâm đến việc sinh ra mã trung 
gian mà không cần biết mã máy đích của nó. Điều này làm cho công việc đơn giản, 
không phụ thuộc vào máy đích. Còn giai đoạn sau trở nên đơn giản hơn vì ngôn 
ngữ trung gian thường thì g ...  chưa kết thúc A, nếu goto (Ii,A) = Ij thì goto [i, A] = j
4. Tất cả các ô không xác định được bởi 2 và 3 đều là “error”
5. Trạng thái khởi đầu của bộ phân tích cú pháp được xây dựng từ tập các mục 
chứa S’→ • S
Ví dụ Ta xây dựng bảng phân tích cú pháp SLR cho văn phạm tăng cường G' trong ví dụ 
trên.
E' → E E → E + T | T T → T * F | F F → (E) | id
(0) E'→ E
(1) E → E + T
(2) E → T
(3) T → T * F
(4) T → F
(5) F → (E)
(6) F → id
1. C = { I0, I1, ... I11 }
2. FOLLOW(E) = {+, ), $}
 FOLLOW(T) = {*, +, ), $} 
 FOLLOW(F) = {*, +, ), $}
 Dựa vào họ tập hợp mục C đã được xây dựng trong ví dụ 4.22, ta thấy:
 Trước tiên xét tập mục I0 : Mục F → • (E) cho ra action[0, (] = "shift 4", và mục F → • 
id cho action[0, id] = "shift 5". Các mục khác trong I0 không sinh được hành động nào.
Bây giờ xét I1 : Mục E'→ E • cho action[1, $] = "accept", mục E → E • + T cho 
action[1, +] = "shift 6".
 Kế đến xét I2: E → T • 
 T → T • * F
Vì FOLLOW(E) = {+, ), $}, mục đầu tiên làm cho action[2, $] = action[2,+] = "reduce 
(E → T)". Mục thứ hai làm cho action[2,*] = "shift 7".
 Tiếp tục theo cách này, ta thu được bảng phân tích cú pháp SLR:
 trạng 
thái
Action goto
a + * ( ) $ E T F
0 s5 S4 1 2 3
1 s6 acc
2 r2 s7 r2 r2
3 r4 r4 r4 r4
4 s5 S4 8 2 3
5 r6 r6 r6 r6
6 s5 S4 9 3
7 s5 S4 10
8 s6 s11
9 r1 s7 r1 r1
10 r3 r3 r3 r3
11 r5 r5 r5 r5
Bảng phân tích xác định bởi giải thuật 4.7 gọi là bảng SLR(1) của văn phạm G, bộ 
phân tích LR sử dụng bảng SLR(1) gọi là bộ phân tích SLR(1) và văn phạm có một bảng 
SLR(1) gọi là văn phạm SLR(1).
 Mọi văn phạm SLR(1) đều không mơ hồ, Tuy nhiên 
có những văn phạm không mơ hồ nhưng không phải là 
SLR(1).
 Ví dụ: Xét văn phạm G với tập luật sinh như sau:
 S → L = R S → R L → * R 
L → id R → L
 Ðây là một văn phạm không mơ hồ nhưng không 
phải là văn phạm SLR(1).
 Họ tập hợp các mục C bao gồm:
I
0
 : S' → • S
S → • L = R
S → • R
L → • * R
L → • id
 R → • L
I
1
 : S' → S •
I
2 
: S → L • = R
 R → L • 
 I
3
 : S → R •
 I
4
 : L → * • R
 R → • L
 L → • * R
 L → • id
 I
5
 : L id •
 I
6
 : S → L = • R
 R → • L
 L → • * R
 L → • id
I
7
 : L → * R•
I
8
 : R → L•
I
9
 : S → L = R•
 Khi xây dựng bảng phân tích SLR cho văn phạm, khi xét tập mục I2 ta thấy mục 
đầu tiên trong tập này làm cho action[2, =] = "shift 6". Bởi vì = ∈ FOLLOW(R), 
nên mục thứ hai sẽ đặt action[2, =] = "reduce (R → L)" ⇒ Có sự đụng độ tại 
action[2, =]. Vậy văn phạm trên không là văn phạm SLR(1).
2.3.4.4. Xây dựng bảng phân tích LR chuẩn.
* Mục LR(1) của văn phạm G là một cặp dạng [A → α• β , a], trong đó A → 
α β là luật sinh, a là một ký hiệu kết thúc hoặc $. 
* Thuật toán xây dựng họ tập hợp mục LR(1)
  Giải thuật: Xây dựng họ tập hợp các mục LR(1)
 Input : Văn phạm tăng cường G’
Output: Họ tập hợp các mục LR(1).
 Phương pháp: Các thủ tục closure, goto và thủ tục chính Items như sau:
 Function Closure (I);
begin
Repeat
For Mỗi mục [A → α • Bβ ,a] trong I, mỗi luật sinh B → γ trong G' và mỗi 
ký hiệu kết thúc b ∈ FIRST (β a) sao cho [B → • γ , b] ∉ I do
Thêm [ B → • γ , b] vào I;
Until Không còn mục nào có thể thêm cho I được nữa;
return I;
end;
Function goto (I, X);
begin
Gọi J là tập hợp các mục [A → α X•β , a] sao cho [A → α• Xβ , a]∈ I;
return Closure(J);
end;
 Procedure Items (G');
begin
C := Closure ({[S' → •S, $]})
Repeat
For Mỗi tập các mục I trong C và mỗi ký hiệu văn phạm X
sao cho goto(I, X) ≠ ∅ và goto(I, X) ∉ C do
Thêm goto(I, X) vào C;
Until Không còn tập các mục nào có thể thêm cho C;
 end;
Ví dụ: Xây dựng bảng LR chính tắc cho văn phạm gia tố G' có các luật sinh sau :
 S' S
 (1) S L = R3
 (2) S R
 (3) L * R
 (4) L id
 (5) R L
 Trong đó: tập ký hiệu chưa kết thúc ={S, L, R} và tập ký hiệu kết thúc {=, *, id, $}
 I0 : S' → • S, $
Closure (S' •S, $) S → • L = R, $
 S → • R, $
 L → • * R, = | $
 L → • id, = | $
 R → • L, $
Goto (I0,S) I1 : S' → S •, $
Goto (I0, L) I2 : S → L • = R, $
 R → L •, $
Goto (I 0,R) I3: S → R •, $
Goto (I0,*) I4: L → * • R, = | $
 R • L, = | $ 
 L → • * R, = | $
 R → • id, = | $
Goto (I0,id) I5 : L → id •, = | $
Goto (I2,=) I6 : S → L = • R, $
 R → • L, $
 L → • * R, $
 L → • id, $
Goto (I4,R) I7 : L → * R•, = | $
Goto (I4, L) I8 : R→ L•, = | $
Goto (I6,R) I9 : S → L = R•, $
Goto (I6,L) I10 :R → L•, $
Goto (I6,*) I11 :L → * • R, $
 R → • L, $ 
 L → • * R, $
 R → • id, $
Goto (I6, id) I12 :L → id •, $
Goto (I11,R) I13 :R → * R•, $
Goto (I11,L) ≡ I10
Goto (I11,*) ≡ I11
Goto (I11,id) ≡ I12
* Thuật toán xây dựng bảng phân tích cú pháp LR chính tắc 
 Giải thuật: Xây dựng bảng phân tích LR chính tắc
 Input: Văn phạm tăng cường G'
Output: Bảng LR với các hàm action và goto
Phương pháp:
1. Xây dựng C = { I0, I1, .... In } là họ tập hợp mục LR(1)
2. Trạng thái thứ i được xây dựng từ Ii. Các action tương ứng trạng thái i 
được xác định như sau:
2.1. Nếu [A → α • aβ ,b] ∈ Ii và goto(Ii,a) = Ij thì action[i, a]= "shift 
j". Ở đây a phải là ký hiệu kết thúc. 
2.2. Nếu [A → α •, a] ∈ Ii , A ≠ S' thì action[i, a] = "reduce (A → α)
2.3. Nếu [S' → S•,$] ∈ Ii thì action[i, $] = "accept".
Nếu có một sự đụng độ giữa các luật nói trên thì ta nói văn phạm không 
phải là LR(1) và giải thuật sẽ thất bại.
 3. Nếu goto(Ii, A) = Ij thì goto[i,A] = j
4. Tất cả các ô không xác định được bởi 2 và 3 đều là "error"
5. Trạng thái khởi đầu của bộ phân tích cú pháp được xây dựng từ tập các 
mục chứa [S' → •S,$]
 Bảng phân tích xác định bởi giải thuật 4.9 gọi là bảng phân tích LR(1) chính tắc của văn 
phạm G, bộ phân tích LR sử dụng bảng LR(1) gọi là bộ phân tích LR(1) chính tắc và văn phạm 
có một bảng LR(1) không có các action đa trị thì được gọi là văn phạm LR(1).
 Ví dụ : Xây dựng bảng phân tích LR chính tắc cho văn phạm ở ví dụ trên
Trạng 
thái
Action Goto
= * id $ S L R
0 s4 s5 1 2 3
1 acc 
2 s6 r5 
3 r2 
4 s4 s5 8 7
5 r4 
6 s11 s12 10 9
7 r3 
8 r5 
9 r1 
10 r5 
11 s11 s12 10 13
12 r4 
13 r3 
Hình 4.14 - Bảng phân tích cú pháp LR chính tắc
Mỗi văn phạm SLR(1) là một văn phạm LR(1), nhưng với một văn phạm SLR(1), bộ 
phân tích cú pháp LR chính tắc có thể có nhiều trạng thái hơn so với bộ phân tích cú 
pháp SLR cho văn phạm đó. 
2.3.4.5. Xây dựng bảng phân tích LALR.
Phần này giới thiệu phương pháp cuối cùng để xây dựng bộ phân tích cú pháp LR - kỹ 
thuật LALR (Lookahead-LR), phương pháp này thường được sử dụng trong thực tế bởi vì những 
bảng LALR thu được nói chung là nhỏ hơn nhiều so với các bảng LR chính tắc và phần lớn các 
kết cấu cú pháp của ngôn ngữ lập trình đều có thể được diễn tả thuận lợi bằng văn phạm LALR.
a. Hạt nhân (core) của một tập hợp mục LR(1)
1. Một tập hợp mục LR(1) có dạng {[A → α• β , a]}, trong đó A → α β là một 
luật sinh và a là ký hiệu kết thúc có hạt nhân (core) là tập hợp {A → α •β }.
2. Trong họ tập hợp các mục LR(1) C = {I0, I1, ..., In} có thể có các tập hợp các 
mục có chung một hạt nhân.
Ví dụ : Trong ví dụ 4.25, ta thấy trong họ tập hợp mục có một số các mục có chung hạt 
nhân là : 
I4 và I11
I5 và I12
I7 và I13
I8 và I10
b. Thuật toán xây dựng bảng phân tích cú pháp LALR
 Giải thuậ: Xây dựng bảng phân tích LALR
 Input: Văn phạm tăng cường G'
Output: Bảng phân tích LALR
Phương pháp:
1. Xây dựng họ tập hợp các mục LR(1) C = {I0, I1, ..., In } 
2. Với mỗi hạt nhân tồn tại trong tập các mục LR(1) tìm trên tất cả các tập hợp 
có cùng hạt nhân này và thay thế các tập hợp này bởi hợp của chúng.
3. Ðặt C' = {I0, I1, ..., Im } là kết quả thu được từ C bằng cách hợp các tập 
hợp có cùng hạt nhân. Action tương ứng với trạng thái i được xây dựng từ Ji 
theo cách thức như giải thuật 4.9.
Nếu có một sự đụng độ giữa các action thì giải thuật xem như thất bại và ta 
nói văn phạm không phải là văn phạm LALR(1).
4. Bảng goto được xây dựng như sau
Giả sử J = I1 ∪ I2 ∪ ... ∪ Ik . Vì I1, I2, ... Ik có chung một hạt nhân nên goto 
(I1,X), goto (I2,X), ..., goto (Ik,X) cũng có chung hạt nhân. Ðặt K bằng hợp tất 
cả các tập hợp có chung hạt nhân với goto (I1,X) ( goto(J, X) = K.
Ví dụ : Với ví dụ trên, ta có họ tập hợp mục C' như sau
 C' = {I0, I1, I2, I3, I411, I512, I6, I713, I810, I9 }
 I0 : S' → • S, $
closure (S' •S, $) : S → • L = R, $
 S → • R, $
 L → • * R, =
 L → • id, =
 R → • L, $
I1 = Goto (I0,S) : S' → S •, $ 
I2 = Goto (I0, L) : S → L • = R, 
$ 
 R → L •, $
I3 = Goto (I 0,R) : S → R • 
I411 = Goto (I0,*), Goto (I6,*) : 
 L → * • R, = | $ 
 R → • L, = | $ 
 L → • * R, = | $ 
 R → • id, = | $
I512 = Goto (I0,id), Goto (I6,id) : 
 L → id •, = | $ 
I6 = Goto(I2,=) :
 S → L = • R,$ 
 R → • L, $
 L → • * R, $
 L → • id, $
I713 = Goto(I411, R) : 
 L → * R•, = | $ 
I810 = Goto(I411, L), Goto(I6, L): 
 R → L•, = | $ 
I9 = Goto(I6, R) : 
 S → L = R•, $ 
 Ta có thể xây dựng bảng phân tích cú pháp LALR cho văn phạm như sau :
State
Action Goto
= * id $ S L R
0 s411 s512 1 2 3
1 acc 
2 s6 
3 r2 
411 810 713
512 r4 r4 
6 s411 s512 810 9
713 r3 r3 
810 r5 r5 
9 r1 
Hình - Bảng phân tích cú pháp LALR
 Bảng phân tích được tạo ra bởi giải thuật 4.10 gọi là bảng phân tích LALR cho văn phạm G. 
Nếu trong bảng không có các action đụng độ thì văn phạm đã cho gọi là văn phạm LALR(1). Họ 
tập hợp mục C' được gọi là họ tập hợp mục LALR(1).
2.4. Bắt lỗi.
* Giai đoạn phân tích cú pháp phát hiện và khắc phục được khá nhiều 
lỗi. Ví dụ lỗi do các từ tố từ bộ phân tích từ vựng không theo thứ tự của luật 
văn phạm của ngôn ngữ.
* Bộ bắt lỗi trong phần phân tích cú pháp có mục đích:
+ Phát hiện, chỉ ra vị trí và mô tả chính xác rõ rang các lỗi.
+ Phục hồi quá trìh phân tích sau khi gặp lỗi đủ nhanh để có thể phát 
hiện ra các lỗi tiếp theo.
+ Không làm giảm đáng kể thời gian xử lý các chương trình viết đúng.
* Các chiến lược phục hồi lỗi.
- Có nhiều chiến lược mà bộ phân tích có thể dùng để phục hồi quá 
trình phân tích sau khi gặp một lỗi cú pháp. Không có chiến lược nào tổng 
quát và hoàn hảo, có một số phương pháp dùng rộng rãi.
+ Phục hồi kiểu trừng phạt: Phương pháp đơn giản nhất và được áp 
dụng trong đa số các bộ phân tích. Mỗi khi phát hiện lỗi bộ phân tích sẽ bỏ 
qua một hoặc một số kí hiệu vào mà không kiểm tra cho đến khi nó gặp một kí 
hiệu trong tập từ tố đồng bộ. Các từ tố đồng bộ thường được xác định trước 
( VD: end, ; )
Người thiết kế chương trình dịch phải tự chọn các từ tố đồng bộ. 
Ưu điểm: Đơn giản, không sợ bj vòng lặp vô hạn, hiệu quả khi gặp câu 
lệnh có nhiều lỗi.
+ Khôi phục cụm từ: Mỗi khi phát hienj lỗi, bộ phân tích cố gắng phân 
tích phần còn lại của câu lệnh. Nó có thể thay thế phần đầu của phần còn lại 
xâu này bằng một xâu nào đó cho phép bộ phân tích làm việc tiếp. Những việc 
này do người thiết kế chương trình dịch nghĩ ra.
+ Sản xuất lỗi: Người thiết kế phải có hiểu biết về các lỗi hường gặp và 
gia cố văn phạm của ngôn ngữ này tại các luật sinh ra cấu trúc lỗi. Dùng văn 
phạm này để khôi phục bộ phân tích. Nếu bọ phân tích dùng một luật lỗi có 
thể chỉ ra các cấu trúc lỗi phát hiện ở đầu vào.
Ngoài ra ngừơi ta có cách bắt lỗi cụ thể hơn trong từng phương pháp phân 
tích khác nhau.
2.4.1. Khôi phục lỗi trong phân tích tất định LL.
* Một lỗi được phát hiện trong phân tích LL khi:
- Ký hiệu kết thúc nằm trên đỉnh ngăn xếp không đối sánh được với ký hiệu 
đầu vào hiện tại.
- Mục M(A,a) trong bảng phân tích là lỗi (rỗng).
* Khắc phục lỗi theo kiểu trừng phạt là bỏ qua các ký hiệu trên xâu vào cho 
đến khi xuất hiện một ký hiệu thuộc tập ký hiệu đã xác định trước gọi là tập ký hiệu 
đồng bộ. Xét một số cách chọn tập đồng bộ như sau:
a) Đưa tất cả các ký hiệu trong Follow(A) vào tập đồng bộ hoá của ký 
hiệu không kết thúc A. Nếu gặp lỗi, bỏ qua các từ tố của xâu vào cho đến khi gặp 
một phần tử của Follow(A) thì lấy A ra khỏi ngăn xếp và tiếp tục quá trình phân tích.
b) Đưa tất cả các ký hiệu trong First(A) vào tập đồng bộ hoá của ký hiệu 
không kết thúc A. Nếu gặp lỗi, bỏ qua các từ tố của xâu vào cho đến khi gặp một 
phần tử thuộc First(A) thì quá trình phân tích được tiếp tục.
Ví dụ: với ví dụ trên, ta thử phân tích xâu vào có lỗi là “)id*+id” với tập đồng bộ 
hoá của các ký hiệu không kết thúc được xây dựng từ tập First và tập Follow của 
ký hiệu đó.
Ngăn xếp Xâu vào Hành động
$E )id*+id$ M(E,)) = lỗi, bỏ qua ‘)’ để găp id ∈ First(E)
$E id*+id$ E->TE’
$E’T id*+id$ T->FT’
$E’T’F id*+id$ F->id
$E’T’id id*+id$ rút gọn id
$E’T’ *+id$ T’->*FT’
$E’T’F* *+id$ rút gọn *
$E’T’F +id$ M(F,+) = lỗi, bỏ qua. Tại đây xảy ra hai trường hợp(ta 
chọn a): a).bỏ qua + vì id ∈ First(F) 
 b).bỏ qua F vì + ∈ Follow(F)
$E’T’F id$ F->id
$E’T’id id$ rút gọn id
$E’T’ $ T’->ε
$E’ $ E’->ε
$ $
2.4.2. Khôi phục lỗi trong phân tích LR.
Một bộ phân tích LR sẽ phát hiện ra lỗi khi nó gặp một mục báo lỗi trong 
bảng action (chú ý sẽ không bao giờ bộ phân tích gặp thông báo lỗi trong bảng 
goto). Chúng ta có thể thực hiện chiến lược khắc phục lỗi cố gắng cô lập đoạn câu 
chứa lỗi cú pháp: quét dọc xuống ngăn xếp cho đến khi tìm được một trạng thái s 
có một hành động goto trên một ký hiệu không kết thúc A ngay sau nó. Sau đó bỏ 
đi không hoặc nhiều ký hiệu đầu vào cho đến khi gặp một ký hiệu kết thúc a thuộc 
Follow(A), lúc này bộ phân tích sẽ đưa trạng thái goto(s,A) vào ngăn xếp và tiếp 
tục quá trình phân tích.
Phương pháp phân tích bảng CYK (Cocke – Younger – Kasami)
- Giải thuật làm việc với tất cả các VP PNC. Thời gian phân tích là: n3 (n là 
độ dài xâu vào cần phân tích), nếu văn phạm không nhập nhằng thì thờI gian phân 
tích là: n2.
- Điều kiện của thuật toán là văn phạm PNC ở dạng chuẩn chômsky (CNF) 
và không có ε sản xuất (sản xuất A → ε ) và các kí hiệu vô ích.
Giải thuật CYK:
- Tạo một hình tam giác (mỗi chiều có độ dài là n , n là độ dài của xâu). 
Thực hiện giải thuật:
Begin
1) For i:=1 to n do
∆ ij = { A | A → a là một sản xuất và a là kí hiệu thứ i trong w};
2) For j:=2 to n do
For i:=1 to (n – j +1) do
Begin
∆ ij = ∅;
For k:=1 to (j -1) do
∆ ij = ∆ ij ∪ { A | A → BC là một sản xuất; B ∈ ∆ ik C∈ ∆ i+k, j -k 
};
end;
end;
Ví dụ: Xét văn phạm chuẩn chômsky 
S → AB|BC; A → BA|a; B → CC|b; C → AB|a;
 (1) (2) (3) (4) (5) (6) (7) (8) 
Xâu vào w= baaba;
 i 
j
b a a b a
B A,C A,C B A,C
S,A B S,C S,A
∅ B B
∅ S,A,C
S,A,C
b a a b a
B A,C A,C B A,C
S,A B S,C S,A
∅ B B
∅ S,A,C
S,A,C
- Quá trình tính ∆ ij . VD: tính ∆ 24 , Tính:
 ∆ 21 = {A,C}, ∆ 33 = {B}, ∆ 21∆ 33 = {AB,CB} Do (1), (7) nên đưa S,C vào 
∆ 24.
∆ 22 = {B}, ∆ 42 = {S,A}, ∆ 22∆ 42 = {BS,BA} Do (3) nên đưa A vào ∆ 24.
∆ 23 = {B}, ∆ 51 = {A,C}, ∆ 23∆ 51 = {BA,BC} (2),(3) nên đưa S,C vào ∆ 
24.
Kết quả: ∆ 24 = {S,A,C}.
- Nếu S ở ô cuối cùng thì ta kết luận: Xâu vào phân tích thành công và có 
thể dựng được cây phân tích cho nó. Số lượng cây phân tích = số lượng S có 
trong ô này.
b a a b a
B A,C A,C B A,C
S,A B S,C S,A
∅ B B
∅ S,A,C
S,A,C
A B
S
BB A C C
b a
C
A B a
a b
Bài tập
Luyện tập: 
cho văn phạm 
E -> T + E | T
T -> a
Hãy xây dựng bảng SLR(1) cho văn phạm trên
Thực hành: Thử nghiệm trên văn phạm biểu thức nêu trên
1) xây dựng tập LR(0) tự động
2) xây dựng bảng phân tích SLR(1) tự động
3) phân tích xâu vào