Bài giảng Trình biên dịch - Chương 4: Phân tích cú pháp

CHƯƠNG 4 
PHÂN TÍCH CÚ PHÁP
4.1. Vai trò của bộ phân tích cú pháp
- Phương pháp tổng quát: Cocke-Younger-Kasami và Earley.
- Phân tích từ trên xuống.
- Phân tích từ dưới lên.
4.2. Xây dựng văn phạm cho ngôn ngữ lập trình
Loại bỏ sự không tường minh
stmt → if exp then stmt 
if exp then stmt else stmt
| other
Thí dụ: phát biểu: if E1 then if E2 then S1 else S2 là phát biểu
không tường minh
- Loại bỏ sự không tường minh.
Quy ứơc hoặc sửa văn phạm. 
stmt → matched-stmt 
lunmatched-stmt
matched-stmt→ if exp then matched-stmt else matched-stmt1 
| other
unmatched-stmt → if exp then stmt
| if exp then matched-stmt else unmatched-stmt
Loại bỏ đệ quay trái
Văn phạm gọi là đệ quy trái nếu tồn tại dẫn xuất.
A ⇒ Aα, với α ⊂ ( Vt ∪ Vn)
Đệ quy trái là bao gồm đệ quy trái đơn giản (trực tiếp) và đệ quy trái
tổng quát.
Để loại bỏ đệ quy đơn giản, ta sẽ thay thếõ tập luật sinh:
A → Aα1⏐Aα2⏐  ⏐Aαm⏐β1⏐β2⏐..⏐βn
bằng cặp luật sinh
A→ β1A’⏐β2A’⏐⏐βnA.’
A’→α1A’⏐α2A’⏐ ..⏐αmA’⏐∈
Thí dụ 4.1. Loại bỏ đệ quy trái cho văn phạm:
E → E + T ⏐ T 
T → T * F ⏐ F 
F → (E) ⏐ id
Giải thuật 4.1. Loại bỏ đệ qy trái
Nhập: Văn phạm G không có vòng lặp hội luật sinh rỗng.
Xuất : Văn phạm tương đương G’ không có đệ quy trái.
Phương pháp: Áp dụng giải thuật ở mô phỏng 4.1 cho G. G’ không
còn đệ quy trái nhưng có thể có luật sinh rỗng.
Sắp xếp caucus ký hiệu không kết thúc theo một thứ tự nào đó: A1, 
A2, . An .
Mô phỏng 4.1. Giải thuật loại bỏ đệ quy trái từ văn phạm
for i := 1 to n do
for j := 1 to i - 1 do begin
- Thay các luật sinh có dạng Ai → Aj γ bằng các luật sinh
Ai→ δ1γ⏐δ2γ⏐..⏐δkγ
- Với Aj luật sinh có dạng Ai → δ1⏐δ2⏐ .⏐δk
- Loại tất cả cả các luật sinh có đệ quy trái trực tiếp trong các
Ai luật sinh
end;
Thí dụ: Chúng ta có áp dụng giải thuật 4.1 vào văn phạm sau để loại
bỏ đệ quy trái.
S→ Aa⏐ b A → Ac⏐ Sd ⏐∈
Thừa số trái: Thí dụ ta có hai luật sinh:
stmt → if exp then stmt else stmt
⏐if exp then stmt 
Cả hai luật sinh đều có if dẫn đầu nên ta sẽ không biết chọn luật sinh
nào để triển khai. Vì thế để làm chậm lại quyết định lựa chọn chúng
ta sẽ tạo ra thừa số trái.
Giải thuật 4.2. Tạo văn phạm có thừa số trái
Nhập: cho văn phạm G.
Xuất: văn phạm G’ có thừa số trái tương đương. 
Phương pháp: Tìm chuỗi dẫn đầu chung của các vế phải luật sinh, thí
dụ: A → αβ1⏐αβ2⏐..⏐αβn⏐γ . γ là chuỗi không bắt đầu bởi α. Ta 
thay các luật trên bằng các luật A→αA’ A’→ β1⏐β2⏐⏐βn
Thí du: ï Ta áp dụng giải thuật trên cho văn phạm phát biểu if, nước
văn phạm tương đương
S → i E t SS’⏐a S’→ e S⏐∈ E → b 
4.3. Phân tích cú pháp từ trên xuống
Phân tích cú pháp đệ quy đi xuống.
Phân tích cú pháp đoán nhận trứơc.
1. Phân tích cú pháp đệ quy đi xuống
Thí dụ: Cho văn phạm G : S→ cAd A → ab ⏐ a 
S S 
c cA d A d
a
b)
a b
a)
Hình 4.4. Các bước phân tích cú pháp từ trên xuống
2. Phân tích cú pháp đoán nhận trước
- Hãy loại bỏ đệ quy trái cho văn phạm mà chúng ta thiết kế.
- Hãy tạo văn phạm có thừa số trái nếu cần thiết.
Sơ đồ dịch cho bộ phân tích đoán nhận trước
Sơ đồ này có đặc điểm như sau:
- Mỗi ký hiệu không kết thúc có một sơ đồ.
- Tên các cạnh là token và các ký hiệu không kết thúc.
Sự truyền trên token sẽ được thực hiện nếu ký hiệu nhập trùng với
token đó. Nếu có sự truyền trên ký hiệu không kết thúc A thì ta thực
hiện một lệnh gọi thủ tục A.
Để xây dựng sơ đồ chúng ta sẽ tiến hành các bước sau đây:
1. Tạo trạng thái bắt đầu và kết thúc.
2. Với mỗi luật sinh có dạng A Ỉ X1X2Xn , ta xây dựng đường đi từ
trạng thái bắt đầu đến trạng thái kết thúc sao cho các cạnh có tên X1, 
X2, X3Xn.
Cơ chế hoạt động của bộ phân tích đoán nhận trước
Thí dụ 4.3. Chúng ta hãy tạo sơ đồ dịch cho văn phạm
G: E Ỉ TE’
E’Ỉ + TE’ |∈
T Ỉ FT’
T’Ỉ ∗ FT’ |∈
F’Ỉ (E) | id
T E’ + T E’
E:
T:
F T’
T’: F’ T’
∈
∗
2
9
1
3
Hình 4.5. Sơ đồ dịch của các ký hiệu không kết thúc của G
E’: ∈
4 5 630 1
7
10 11 12
8
( )∈
F: id
1
714 15 16
)( E
Hình 4.6. Sơ đồ dịch của các ký hiệu không kết thúc của G, đã được
thu giảm
Giải thuật:
procedure E;
procedure T;
procedure F;
begin nextchar (c);
if c = ‘(‘ then begin
match (‘(‘); E;
match (‘)‘); end
else if c = id then match (id)
else error;
E: F:
id
6 170 14 15 163
+
T: 7 10
∗
13
T ∈ ∈F
end; {F}
begin
F;
while c = ‘*‘ do F;
end; {T}
begin
T;
while c = ‘+‘ do T;
end; {E}
3. Phân tích cú pháp đoán nhận trước không đệ quy
Cấu tạo của bộ phân tích cú pháp
Stack a1a2  an $ bộ đệm nhập
X Chương trình điều khiển
Y
Z
$
Bảng phân tích M
Xuất
Hình 4.7. Mô hình cấu tạo của bộ phân tích đoán nhận trước
không đệ quy.
Hoạt động của bộ phân tích
Ở trạng thái bắt đầu, stack chỉ chứa các ký hiệu mục tiêu của văn
phạm nằm trên $, trên đỉnh stack. Bảng phân tích M là ma trận. Hai
ký hiệu X và a sẽ xác định hành vi của bộ phân tích. Bộ phân tích có
ba hành vi như sau:
1. Nếu X = a = $.
2. Nếu X = a ≠ $.
3. Nếu X là ký hiệu không kết thúc.
Giải thuật 4.2. Phân tích cú pháp đoán nhận trước không đệ quy.
Nhập: chuỗi nhập w và bảng phân tích M cho văn phạm G.
Xuất: nếu w thuộc L (G), sẽ tạo ra dẫn xuất trái của w, ngược lại sẽ
báo lỗi.
Phương pháp: lúc đầu cấu hình của bộ phân tích là ($S, w$) với S là
ký hiệu mục tiêu của G. Đặt ip (là con trỏ hoặc còn gọi là đầu đọc
của bộ phân tích) vào ký hiệu nhập đầu tiên của w$.
Mô phỏng 4.2. Chương trình phân tích cú pháp đoán nhận trước
repeat
X trên stack và ký hiệu a đang được đầu đọc ip đọc;
if X là ký hiệu kết thúc hoặc $ then
if X = a then begin
- đẩy X ra khỏi stack;
- dịch đầu đọc đến ký hiệu nhập kế tiếp; end
else error ()
else ifM [X, a] = X Ỉ X1X2Xk then begin
- đẩy X ra khỏi stack;
- đẩy XkXk-1 X1 lên stack (X1 trên đỉnh stack);
- xuất luật sinh X Ỉ X1X2  Xk ; end
else error ()
until X = $
Thí dụ 4.4. Giả sử chúng ta có văn phạm G.
E Ỉ E + T | T
T Ỉ T ∗ F | F
F Ỉ (E) | id
Chúng ta sẽ thực hiện loại bỏ đệ quy trái, nhận được G’:
E Ỉ TE’
E’Ỉ + TE’ |∈
T Ỉ FT’
T Ỉ ∗ FT’ |∈
F Ỉ (E) | id
Bây giờ chúng ta sẽ phân tích cú pháp cho câu nhập w = id + id * id 
bằng bảng phân tích M cho trước, ở Bảng 4.1.
Bảng 4.1. Bảng phân tích M cho văn phạm G
Ký hiệu nhậpKý hiệu không
kết thúc id + * ( ) $
E E Ỉ TE’ E Ỉ TE’
E’ E Ỉ
+TE’
E’Ỉ ∈ E’Ỉ ∈
T T Ỉ FT’ T Ỉ FT’
T’ T’Ỉ ∈ T Ỉ* FT’ T’Ỉ ∈ T’Ỉ ∈
F F Ỉ id F Ỉ (E)
Quá trình phân tích cú pháp câu nhập w = id + id ∗ id sẽ được trình 
bày ở bảng 4.2.
Bảng 4.2. Các bước phân tích cú pháp câu id + id ∗ id
Stack Chuỗi nhập Xuất Stack Chuỗi nhập Xuất
$E id + id ∗ id $ $E’T’F id ∗ id $ T Ỉ FT’
$E’T id + id ∗ id $ E Ỉ TE’ $E’T’id id ∗ id $ F Ỉ id
$E’T’F id + id ∗ id $ T Ỉ FT’ $E’T’ ∗ id $
$E’T’id id + id ∗ id $ F Ỉ id $E’T’F∗ ∗ id $ T’Ỉ ∗FT’
$E’T’ + id ∗ id $ $E’T’F id $
$E’ + id ∗ id $ T’Ỉ ∈ $E’T’id id $ F Ỉ id
$E’T+ + id ∗ id $ E’Ỉ +TE’ $E’T’ $
$E’T id ∗ id $ $E’ $ T’Ỉ ∈
$ $ E’Ỉ ∈
Xây dựng bảng phân tích M
a. first và follow
first(α) là tập c ký hiệu kết thúc a, dẫn đầu các chuỗi được dẫn xuất
từ α, α ⇒ aγ. Nếu α ⇒ ∈ thì ∈ thuộc first(α). 
follow(A) là tập các ký hiệu kết thúc a, xuất hiện ngay bên phải A 
trong dạng câu. Như vậy tồn tại dẫn xuất S ⇒ αAaβ. Nếu giữa A và a 
tồn tại chuỗi ký hiệu, thì nó sẽ dẫn xuất ra chuỗi rỗng. Nếu A ở tận
cùng bên phải của dạng câu thì $ thuộc follow(A). 
- Các quy tắc tính first(X) với X là ký hiệu văn phạm.
- Các quy tắc tính follow(A) cho tất cả các ký hiệu không kết thúc
A.
Thí dụ 4.5. Cho văn phạm G.
E Ỉ TE’
E’Ỉ + TE’⏐∈
T Ỉ FT’
T’Ỉ ∗ FT’⏐∈
F’Ỉ (E)⏐id
Toàn bộ các hàm first và follow của các ký hiệu văn phạm của G :
first(E) = first(T) = first(F) = {(, id}
first(E’) = {+, ∈} ; first(T’) = {*, ∈}
follow(E) = follow(E’) = {$, )}
follow(T) = follow(T’) = {+, $, )}
follow(F) = {*, +, $, )}
b. Xây dựng bảng phân tích M
Giải thuật 4.3. Xây dựng bảng phân tích M.
Nhập: văn phạm G.
Xuất: bảng phân tích M.
Phương pháp:
1. Với mỗi luật sinh A Ỉ α hãy thực thi bước 2 và 3.
2. Với mỗi ký hiệu kết thúc a thuộc first(α), thêm A Ỉ α vào M[A, a].
3. Nếu ký hiệu ∈ thuộc first(α), thêm A Ỉ α vào M[A, b] sao cho b 
thuộc follow(A). Nếu $ thuộc follow(A) thì thêm A Ỉ α vào M [A, $].
4. Những phần tử của bảng M trống, hãy đánh dấu lỗi.
Văn phạm LL (1)
Thí dụ 4.7. Cho văn phạm G.
S Ỉ iEtSS’⏐a ; S’Ỉ eS⏐∈ ; E Ỉ b
Bảng 4.3. Bảng phân tích M cho thí dụ 4.7.
Ký hiệu nhậpCác
ký hiệu
không
KT
a b e i t $
S S Ỉ a S Ỉ iEtSS’
S’ S’Ỉ ∈
S’Ỉ eS
S’Ỉ ∈
E E Ỉ b
- Văn phạm không có phần tử nào của bảng phân tích M có nhiều hơn
một trị thì được gọi là văn phạm LL (1).
- Văn phạm LL (1) có các tính chất sau.
Khắc phục lỗi trong phân tích cú pháp đoán nhận trước
Lỗi xuất hiện trong các trường hợp sau: Một là ký hiệu kết thúc trên
stack không trùng với ký hiệu nhập đang được đọc. Hai là A là ký
hiệu không kết thúc trên đỉnh stack, a trên chuỗi nhập, được đọc, mà
M [A, a] là trống.
Một số heuristics được áp dụng cho việc khắc phục lỗi.
Thí dụ 4.8. Cho văn phạm
E Ỉ TE’ ; E’Ỉ + TE’⏐∈ ; T Ỉ FT’ ; T’Ỉ * FT’⏐∈; F Ỉ (E)⏐id
first(E) = first(T) = first(F) = {(, id)}
first(E’) = {+, }∈; first (T’) = {*, }∈
follow(E) = follow(E’) = {$, )}
follow(T) = follow(T’) = {+, $, )}
follow(F) = {*, +, $, )}
Bảng 4.4. Phân tích M có ký hiệu khắc phục lỗi.
Ký hiệu nhậpKý hiệu
không
KT id + * ( ) $
E E Ỉ TE’ E Ỉ TE’ synch synch
E’ E’Ỉ +TE’ E’Ỉ ∈ E’Ỉ ∈
T T Ỉ FT’ synch T Ỉ FT’ synch synch
T’ T’Ỉ ∈ T’Ỉ * FT’ T’Ỉ ∈ T’Ỉ ∈
F F Ỉ id synch synch F Ỉ (E) synch synch
4.4. Phân tích cú pháp từ dưới lên
Phân tích cú pháp từ dưới lên được hiểu là phân tích đẩy và thu giảm
(Shift-Reduce parsing) là phương pháp phân tích LR.
Thí dụ 4.9. Cho văn phạm G.
S Ỉ aABe ; A Ỉ Abc⏐b ; BỈ d
Phân tích câu w = abbcde.
Tóm tắt các bước thu giảm như sau:
Quá trình thu giảm nếu theo chiều ngược lại thì đó chính là quá trình
dẫn xuất phải. Quá trình này đã sinh cây cú pháp của câu phân tích từ
dưới lên. 
Hình 4.8. Cây cú pháp được xây dựng từ dưới lên của câu w = abbcde.
Handle 
Tìm kiếm handle
Bắt đầu từ chuỗi cần phân tích w, ta đặt w = γn . γn là dạng câu được
dẫn xuất ở lần thứ n. 
S = γ0⇒ γ1⇒ γ2⇒ ⇒ γn-1⇒ γn = w
Xây dựng dẫn xuất phải ngược từ w = γn . Ta tìm βn trong γn sao choβn là vế phải luật sinh AnỈ βn . Thay βn trong γn bằng An , ta nhận
được dạng câu thứ (n – 1) là γn – 1. 
Quá trình thu giảm cứ tiếp tục như vậy cho đến khi đạt được γo chỉ còn
là một ký hiệu không kết thúc và là ký hiệu mục tiêu.
1. Phân tích cú pháp thứ tự yếu
Văn phạm có tính chất: không có luật sinh nào có vế phải là chuỗi
rỗng (A Ỉ ∈) hoặc ở vế phải không có hai ký hiệu không kết thúc
đứng kề nhau gọi là văn phạm thứ tự yếu.
n
rm rmrm
2 r -1
rmrm
1
Bộ phân tích cú pháp thứ tự yếu
1. Cấu tạo
$ X1 X2  Xn-1 Xn Y1 Y2  Yn-1 Yn $
Chương trình
phân tích
Bảng phân
tích S-R
Hình 4.9. Mô hình bộ phân tích cú pháp thứ tự yếu
Xuất
2. Hoạt động
Thí dụ 4.10. Cho văn phạm của phát biểu gán
 Ỉ id = 
 Ỉ + | 
 Ỉ * ⏐ 
 Ỉ id ⏐ ()
Ký hiệu là ký hiệu mục tiêu. 
Bảng 4.6. Bảng phân tích S-R cho văn phạm ở thí dụ 4.10.
id ∗ + ( ) = $
 R*
 S S R
 S R R R
 R R R R
id R R R S R
* S S
+ S S
( S S
) R R R R
= S S
$ S
Giải thuật 4.4. Phân tích cú pháp thứ tự yếu
Mô phỏng 4.3. Giải thuật của chương trình phân tích thứ tự yếu
- Lúc đầu stack trạng thái chỉ có ký hiệu $. Stack nhập chứa
chuỗi nhập, được kết thúc bởi dấu $ ; c:=false ;
repeat
if Ký hiệu mục tiêu ở trên đỉnh và ký hiệu $ ở đáy stack trạng thái, 
đồng thời stack nhập chỉ chứa $ then 
c:=true /∗phân tích thành công, cây cú pháp xây dựng xong∗/
else begin
- X ở trên đỉnh stack trạng thái, Y ở trên đỉnh stack nhập. 
- Giả sử T là trị của phần tử S-R [X, Y];
if T là rỗng then error ()
else if T = R then 
if trên đỉnh stack có chứa vế phải của luật sinh nào đó
then begin
- Gọi A Ỉ X1 X2  Xn là luật sinh nào có vế phải dài
nhất so trùng với chuỗi trên stack trạng thái: (a) Giải tỏa X1 X2  Xn
ra khỏi stack; (b) Thay A lên stack. (c) Tạo nút mới A trên cây cú
pháp, có các con là X1 X2  Xn
end
else error ()
else begin 
(a) Giải tỏa Y ra khỏi stack nhập; (b) Đẩy Y lên đỉnh
stack trạng thái; (c) Tao nút mới tên Y trên cây cú pháp;
end;
end;
until c;
3. Xây dựng bảng phân tích S-R
Định nghĩa các quan hệ :
- Chúng ta nói X <• Y nếu và chỉ nếu tồn tại một luật sinh mà vế
phải có dạng  XA với A là ký hiệu không kết thúc và sinh ra một
chuỗi bắt đầu bằng Y (A ⇒ Y).
- X •> Y nếu và chỉ nếu tồn tại một luật sinh mà vế phải có dạng
AB. A sinh ra một chuỗi ký hiệu được kết thúc bằng X (A ⇒ X). B 
sinh ra một chuỗi được bắt đầu bằng Y (B ⇒ Y), hoặc B = Y.
Ở đây có hai trường hợp xảy ra trong quá trình tìm các mối quan hệ
cho cặp (X, Y):
•
Trường hợp 1: Y là ký hiệu kết thúc
Trường hợp 2: Y là ký hiệu không kết thúc.
a. Tồn tại $ ≤• A với A là ký hiệu mục tiêu của văn phạm cho trước.
b. Nếu vế phải luật sinh có X nằm kề ngay Y về phía trái (XY)
thì X ≤• Y
c. Nếu X ≤• Y mà tồn tại một luật sinh Y Ỉ Z1  Zn thì X ≤• • Z1
d. Tồn tại A •> $ với A là ký hiệu mục tiêu
e. Nếu X ≤• •Y và tồn tại một luật sinh X Ỉ Z1  Zn thì Zn • > Y
g. Nếu X •> Y và tồn tại một luật sinh Y Ỉ Z1  Zn thì X • > Z1
4. Văn phạm thứ tự yếu
Một văn phạm được gọi là thứ tự yếu nếu thỏa các điều kiện sau:
1. Không có hai luật sinh có cùng một vế phải.
2. Không có phần tử S-R [X, Y] nào của bảng S-R vừa có trị S 
vừa có trị R.
3. Nếu tồn tại luật sinh AỈX1 X2  Xn và luật sinh BỈXiXi+1 Xn
thì không tồn tại quan hệ Xi – 1 ≤• • B.
2. Bộ phân tích cú pháp LR
- Các tính chất của phương pháp phân tích LR
- Giải thuật phân tích cú pháp LR
1. Bộ phân tích cú pháp có cấu tạo như sau:
a1 a2  ai an $
Sm
Xm
Sm –1 
Xm – 1 
$ action goto bảng phân tích
Chương trình
điều khiển
bộ đệm nhập
Stack
xuất
Hình 4.11. Mô hình bộ phân tích cú pháp LR
2. Hoạt động
Stack được dùng để chứa chuỗi ký hiệu có dạng s0 X1 s1 X2  Xm sm. 
Cặp (sm, ai ) sẽ xác định một trị được lưu chứa trong bảng phân tích. 
Bảng phân tích gồm hai phần biểu thị bởi hàm action và goto. Cấu
hình (configuration) của bộ phân tích LR: 
s0 X1 s1  Xi si  Xm sm, ai ai+1  an $). Cấu hình này cho chúng ta dạng 
câu X1 X2  Xm ai ai+1  an. 
Giải thuật 4.5. Phân tích cú pháp LR
Nhập: chuỗi nhập w, bảng phân tích action goto của văn phạm G.
Xuất: nếu w thuộc L (G), nó tạo ra sự phân tích từ dưới lên. Ngược lại, 
bộ phân tích sẽ báo lỗi.
Phương pháp:
- Thời điểm ban đầu stack có trạng thái s0.
- Chuỗi w$ nằm trên bộ đệm nhập.
- Bộ phân tích đặt đầu đọc (con trỏ ip) vào ký hiệu nhập đầu tiên của 
w.
c:=false; /*c là biến luận lý, báo cho biết quá trình phân tích kết 
thúc*/
repeat
- Đặt s là trạng thái trên đỉnh stack a là ký hiệu nhập được ip 
chỉ đến 
if action [s, a] = shift(s’) then begin
(a)đẩy a lên stack (b)sau đó đẩy s’ lên đỉnh stack 
(c)chuyển ip sang ký hiệu nhập kế tiếp; end
else if action [s, a] = reduce(A Ỉ β) then
begin
(a)đẩy (2*⏐β⏐) ký hiệu ra khỏi stack, s’ là trạng thái
trên đỉnh stack
(b)Tìm j = goto [s’, A]; (c)đẩy A và sau đó là j lên đỉnh
stack; (d)xuất luật A Ỉ β
end
else if action [s, a] = accept then c := true
else error ();
until c;
Thí dụ 4.12. Cho văn phạm G
(1) E Ỉ E + T (2) E Ỉ T (3) T Ỉ T * F
(4) T Ỉ F (5) F Ỉ (E) (6) F Ỉ id
Bảng 4.8. Bảng phân tích cho văn phạm G ở thí dụ 4.12.
action goto
id + * ( ) $ 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 s11
9 r1 s7 r1 r1
10 r3 r3 r3 r3
11 r5 r5 r5 r5
Trạng thái
Thí dụ: Phân tích câu w = id ∗ id + id
Văn phạm LR
Xây dựng bảng phân tích SLR
Định nghĩa thực thể LR (0)
Thí dụ: G có luật sinh A Ỉ XYZ, sẽ cho bốn thực thể:
AỈ•XYZ; AỈX•YZ; AỈXY•Z; AỈXYZ•
Nếu A Ỉ ∈ sẽ cho ta thực thể A Ỉ • •
Ý tưởng cơ bản của giải thuật xây dựng bảng phân tích SLR là từ văn
phạm, chúng ta đi tìm DFA, nhận dạng chuỗi dẫn đầu bên trái của
dạng câu (viable prefixe). 
Định nghĩa văn phạm gia tố: nếu G là văn phạm, thì G’ là văn phạm
gia tố, là G có S’ là ký hiệu mục tiêu và có thêm luật sinh
S’Ỉ S.
Phép bao đóng – Closure.
Giải thuật tính closure.
Mô phỏng 4.4. Giải thuật tính hàm closure
function closure (| : item) : item;
begin J := |;
repeat
for với mỗi thực thể A Ỉ α.Bβ trong J và với mỗi
luật sinh
B Ỉ γ trong G sao cho
thực thể B Ỉ • γ chưa có trong J do 
thêm B Ỉ • γ vào J;
until không thể thêm thực thể mới vào J;
closure := J;
end;
Giải thuật tính goto: hàm goto (I, X) với I là tập các thực thể, X là ký
hiệu văn phạm. Goto (I, X) là closure của tập các thực thể có dạng A 
Ỉ αX.β sao cho thực thể A Ỉ α.Xβ ở trong I.
Mô phỏng 4.5. Giải thuật tính tập tuyển các tập thực thể
procedure items (G’);
begin
C := {closure ({S’Ỉ • S}}}
repeat
for với mỗi tập thực thể I trong C và với mỗi ký
hiệu văn phạm X sao cho phép goto (I, X) không rỗng và không có
trong C do
thêm goto (I, X) vào C;
until không thể thêm tập thực thể mới vào C;
end;
Thí dụ 4.13. Cho văn phạm gia tố G’
E’Ỉ E ; E Ỉ E + T ; E Ỉ T
T Ỉ T* F ; T Ỉ F ; F Ỉ (E) ; F Ỉ id
Hãy tìm tập C và sơ đồ DFA. 
Xây dựng bảng phân tích SLR
Giải thuật 4.6. Xây dựng bảng phân tích
Nhập: văn phạm gia tố G’
Xuất: bảng phân tích SLR với hàm action và goto cho văn phạm G’
Phương pháp:
1. Xây dựng C = {Io, I1,  In}.
2. i là trạng thái đại diện cho tập thực thể Ii.
a. Nếu A Ỉ α•aβ là thực thể ở trong Ii và goto (Ii, a) = Ij thì phần tử
action [i, a] = shift(j), với a phải là ký hiệu kết thúc.
b. Nếu A Ỉ α• ở trong Ii thì action [i, a] = reduce(A Ỉα) với a là
tất cả các ký hiệu nằm trong follow (A). A không phải là S’ (ký hiệu
mục tiêu mới).
c. Nếu S’Ỉ S• ở trong Ii thì action [i, $] = accept.
3. Cho tất cả các ký hiệu không kết thúc A. Nếu goto [Ii, A]=Ij thì
hàm goto [i, A]=j.
4. Tất cả các phần tử của bảng phân tích không được xác định bằng
quy tắc 2 và 3, chúng ta coi là lỗi.
5. Trạng thái bắt đầu của bộ phân tích là tập thực thể có chứa thực thể
S’Ỉ•S.
Thí dụ 4.14. Xây dựng bảng phân tích SLR cho văn phạm G ở thí dụ
4.13.
Thí dụ 4.15. Cho văn phạm G.
(1) S Ỉ L = R
(2) S Ỉ R
(3) L Ỉ * R
(4) L Ỉ id
(5) R Ỉ L
Ta nhận thấy đụng độ khi action [2, =] = s6 đồng thời action [2, =] = r5
và action [2, $] = r5. Do đó tại phần tử action [2, =] có hai trị s6 và r5. 
Như vậy G không phải là văn phạm SLR.
Xây dựng bảng phân tích Canonical LR
Dạng tổng quát của thực thể là [A Ỉ α.β, a] với A Ỉ αβ là luật sinh
và a là ký hiệu kết thúc hoặc dấu $. Thực thể có dạng như thế được
gọi là thực thể LR (1). Nếu β = ∈ thì thực thể sẽ có dạng [A Ỉ α• , a]. 
Lúc này chúng ta thực hiện thu giảm bằng luật sinh A Ỉ α chỉ với
điều kiện ký hiệu nhập kế tiếp là a.
Chúng ta nói thực thể LR (1) [A Ỉ α.β, a] là hợp lệ với chuỗi ký hiệu
dẫn đầu dạng câu γ nếu tồn tại dẫn xuất phải:
S ⇒ δAw ⇒ δαβw với
rm rm
1. γ = δα và
2. hoặc a là ký hiệu dẫn đầu của w, hoặc w = ∈ thì a là $.
Thí dụ 4.16. Cho văn phạm G
S Ỉ BB
B Ỉ aB | b
Tính tập tuyển các thực thể LR (1)
Phép tính closure
Giải thuật 4.7. Xây dựng các tập thực thể LR (1).
Mô phỏng 4.7. Giải thuật tính các tập thực thể LR (1) cho văn phạm
gia tố G’
function closure (I: items): items;
begin
repeat
for với mỗi thực thể [A Ỉ α • Bβ, a] trong , với mỗi
luật sinh B Ỉ η trong G’ và với mỗi ký hiệu kết
thúc b thuộc first sao cho thực thể [B Ỉ • η, b] 
không có trong | do
thêm thực thể [B Ỉ η, b] vào |
until không thể thêm thực thể mới vào |;
closure := |;
end;
function goto (| :items; X: symbol): items;
begin
j là tập các thực thể có dạng [A Ỉ αX• β, a] sao cho
thực thể [A Ỉ α• Xβ, a] ở trong | ; goto := closure (J); 
end;
procedure items (G’);
begin
d := {closure ({S’Ỉ• S, $}}};
repeat
for với mỗi tập thực thể | ở trong C và với mỗi ký
hiệu văn phạm X sao cho goto (|, X) không rỗng và
chưa có trong C do thêm goto (|, X) vào C;
until không thể thêm tập thực thể mới vào C;
end;
Thí dụ 4.17. Xây dựng các tập thực thể LR (1) cho văn phạm gia tố
G’: S’Ỉ .S ; S Ỉ CC ; C Ỉ cC|d
Giải thuật 4.8. Xây dựng bảng phân tích Canonical LR.
Nhập: văn phạm gia tố G’
Xuất: bảng phân tích Canonical LR với hai hàm action và goto cho G’
Phương pháp:
1. Xây dựng C = {Io, I1, , In}.
2. Trạng thái i đại diện cho Ii.
a. Nếu thực thể [A Ỉ α.aβ, b] ở trong Ii và goto (Ii , a) = Ij thì
phần tử action [i, a] = shift(j), a phải là ký hiệu kết thúc.
b. Nếu [A Ỉ α• , a] ở trong Ii, A ≠ S’ thì action[i, a]=reduce(AỈα)
c. Nếu [S’Ỉ S• , $] ở trong Ii thì action [i, $] = accept. 
3. Nếu goto (Ii , A) = Ij thì phần tử goto [i, A] = j.
4. Tất cả các phần tử không áp dụng được quy tắc 2 và 3 thì là lỗi.
5. Trạng thái bắt đầu của bộ phân tích cú pháp là tập thực thể co
chứa thực thể [S’Ỉ •S , $].
Bảng phân tích Canonical LR cho văn phạm ở thí dụ 4.17. được xây
dựng dựa vào giải thuật 4.7.
Bảng 4.10. Bảng phân tích Canonical LR
action goto
c d $ S C
0
1
2
3
4
5
6
7
8
9
s3
s6
s3
r3
s6
r2
s4
s7
s4
r3
s7
r2
acc
r1
r3
r2
1 2
5
8
9
Trạng thái
Bộ sinh phân tích cú pháp
Bộ sinh phân tích cú pháp Yacc
Trình biên dịch
Yacc
Trình biên dịch C a.out
a.out dẫn xuất
Tập tin đặc tả
Yacc translate.y
y.tab.c
y.tab.c
chuỗi token
Hình 4.14. Tạo bộ phân tích cú pháp bằng Yacc.
Thí dụ 4.23. Chúng ta sẽ tạo tập tin đặc tả văn phạm cho Yacc của
văn phạm G.
E Ỉ E + T | T
T Ỉ T * F | F
F Ỉ (E) | digit
Mô phỏng 4.10. Tập tin đặc tả văn phạm cho Yacc ở thí dụ 4.23.
% { # include 
% }
% token DIGIT
% %
line : exp ′\n′{printf (″% d\n″, $1) ;}
;
exp : exp ′+′ term {$$ = $1 + $3;}
: term
;
term : term ′*′ factor {$$ = $1 + $3;}
: factor
; 
factor : ′(′exp′)′ {$$ = $2;}
: DIGIT
;
%%
yylex ( ) {
int c ;
c = getchar ( ) ;
if (isdigit (c)) { yylval = c - ′0′ ;
return DIGIT;
}
return c;
}
Phần đặc tả
Phần các luật biên dịch:
 Ỉ | | 
Luật biên dịch trong Yacc:
 : {hành vi ngữ nghĩa 1}
: {hành vi ngữ nghĩa 2}
: {hành vi ngữ nghĩa n}
Phần các chương trình con C phụ trợ