MỤC LỤC
MỤC LỤC......................................................................................................................1
MỞ ĐẦU........................................................................................................................2
CHƯƠNG I: PHÂN TÍCH CÚ PHÁP LR.....................................................................3
1. Thuật toán phân tích cú pháp LR...........................................................................3
2. Xây dựng bảng phân tích SLR...............................................................................5
2.1. Mục..................................................................................................................5
2.2. Văn phạm mở rộng..........................................................................................6
2.3. Hàm closure.....................................................................................................6
2.4. Hàm goto.........................................................................................................8
2.5. Xây dựng tập mục...........................................................................................9
2.6. Hàm FIRST(α)................................................................................................9
2.7.Hàm FOLLOW(A).........................................................................................11
2.8. Bảng phân tích SLR......................................................................................12
CHƯƠNG II: THỰC HÀNH.......................................................................................13
1. Xây dựng bảng phân tích SLR cho văn phạm G..................................................13
1.1.Xây dựng tập mục:.........................................................................................13
1.2.Hàm FOLLOW..............................................................................................15
1.3.Xây dựng bảng phân tích SLR.......................................................................15
2.Áp dụng phân tích cú pháp của câu.......................................................................15
TÀI LIỆU THAM KHẢO............................................................................................16

1


MỞ ĐẦU
Phân tích cú pháp là một nội dung quan trọng của chương trình dịch, nó thực hiện
hai nhiệm vụ chính là: Kiểm tra tính đúng đắn về cú pháp của chương trình nguồn,
đồng thời xác định chức năng của các thành phần trong chương trình nguồn.
Trong phạm vi bài tập, em đã tiến hành nghiên cứu dạng phân tích cú pháp từ dưới
lên LR, đồng thời nghiên cứu phương pháp xây dựng bảng phân tích cú pháp SLR.

Bài tập được trình bày thành hai phần:
- Chương I: Trình bày các kiến thức cơ bản về bộ phân tích cú pháp LR và
phương pháp xây dựng bảng phân tích SLR
- Chương II: Áp dụng xây dựng bảng phân tích cho văn phạm cụ thể, ứng dụng
phân tích cú pháp cho một chuỗi nhập vào.
Do các hiểu biết về chương trình dịch còn hạn chế nên trong bài tập không tránh
khỏi các thiếu sót, em kính mong thầy giáo – TS Hà Chí Trung giúp đỡ, tạo điều kiện
để em hoàn thiện bài tập của mình.
Hà Nội, ngày 05 tháng 01 năm 2015
Học viên

2


CHƯƠNG I: PHÂN TÍCH CÚ PHÁP LR
1. Thuật toán phân tích cú pháp LR
Kỹ thuật phân tích cú pháp LR(k) là một kỹ thuật phân tích cú pháp từ dưới lên
khá hiệu quả, có thể sử dụng để phân tích một lớp rộng các văn phạm phi ngữ cảnh.
Trong đó:
- L (left - to - right): Duyệt chuỗi nhập từ trái sang phải.
- R (rightmost derivation): Xây dựng chuỗi dẫn xuất phải nhất đảo ngược.
- k : Số lượng ký hiệu nhập được xét tại mỗi thời điểm dùng để đưa ra quyết định
phân tích. Khi không đề cập đến k, chúng ta hiểu ngầm là k = 1.
Các ưu điểm của bộ phân tích cú pháp LR là:
- Bộ phân tích cú pháp LR có thể được xây dựng để nhận biết hầu như tất cả
các ngôn ngữ lập trình được tạo ra bởi văn phạm phi ngữ cảnh.
- Phương pháp phân tích cú pháp LR là phương pháp tổng quát của phương
pháp chuyên thu gọn không quay lui. Nó có thể được cài đặt có hiệu quả như các
phương pháp chuyên thu gọn khác.
- Lớp văn phạm có thể dùng phương pháp LR là một lớp rộng lớn hơn lớp văn

phạm có thể sử dụng phương pháp dự đoán.
- Bộ phân tích cú pháp LR cũng có thể xác định lỗi cú pháp nhanh ngay trong
khi duyệt dòng nhập từ trái sang phải.
Tuy nhiên, phương pháp này cũng có nhược điểm chủ yếu là cần phải thực
hiện quá nhiều công việc để xây dựng được bộ phân tích cú pháp LR theo kiểu thủ
công cho một văn phạm ngôn ngữ lập trình điển hình.
Mô hình bộ phân tích cú pháp LR được mô tả như sau:

3


Trong đó:
-

Stack lưu một chuỗi s0X1s1X2s2 ... Xmsm trong đó sm nằm trên đỉnh Stack. Xi là
một ký hiệu văn phạm, si là một trạng thái tóm tắt thông tin chứa trong Stack
bên dưới nó.
- Bảng phân tích bao gồm 2 phần: hàm action và hàm goto.
o action[sm, ai] có thể có một trong 4 giá trị :
1. shift s: đẩy s, trong đó s là một trạng thái.
2. reduce A→ β: thu gọn bằng luật sinh A→ β.
3. accept: Chấp nhận
4. error: Báo lỗi
o goto lấy 2 tham số là một trạng thái và một ký hiệu văn phạm, nó sinh ra
một trạng thái.
Giải thuật phân tích cú pháp LR được trình bày như sau:
Input: Một chuỗi nhập w, một bảng phân tích LR với hàm action và goto cho văn
phạm G.
Output: Nếu w ∈ L(G), đưa ra một sự phân tích dưới lên cho w. Ngược lại, thông
báo lỗi.

Phương pháp:
1. Khởi tạo s0 là trạng thái khởi tạo nằm trong Stack và w$ nằm trong bộ đệm
nhập.
2. Ðặt ip vào ký hiệu đầu tiên của w$;
3. Repeat forever begin
Gọi s là trạng thái trên đỉnh Stack và a là ký hiệu được trỏ bởi ip;
If action[s, a] = Shift s' then begin
Ðẩy a và sau đó là s' vào Stack;
Chuyển ip tới ký hiệu kế tiếp;
end
4


else if action[s, a] = Reduce (A → β) then begin
Lấy 2 * | β| ký hiệu ra khỏi Stack;
Gọi s' là trạng thái trên đỉnh Stack;
Ðẩy A, sau đó đẩy goto[s', A] vào Stack;
Xuất ra luật sinh A → β;
end
else if action[s, a] = accept then
return
else error ( )
end

2. Xây dựng bảng phân tích SLR
Vấn đề ở đây là làm sao để xây dựng được bảng phân tích LR. Có ba phương
pháp xây dựng như sau:
- Xây dựng bảng phân tích cú pháp SLR (Simple LR)
- Xây dựng bảng phân tích cú pháp LR chính tắc (Canonical LR)
- Xây dựng bảng phân tích cú pháp LALR( Lookahead-LR)

Trong đó phương pháp xây dựng bảng phân tích cú pháp SLR là phương pháp
"yếu" nhất nếu tính theo số lượng văn phạm có thể xây dựng thành công bằng phương
pháp này, nhưng đây lại là phương pháp dễ cài đặt nhất. Ta gọi bảng phân tích cú
pháp tạo ra bởi phương pháp này là bảng SLR và bộ phân tích cú pháp tương ứng là
bộ phân tích cú pháp SLR, với văn phạm tương đương là văn phạm SLR.
Trước hết, ta nghiên cứu một số vấn đề sau:
2.1. Mục
Một mục LR(0) (LR(0) item – và gọi tắt là mục) của một văn phạm G là một
sản xuất của G có một dấu chấm nằm ở đâu đó bên vế phải. Do vậy sản xuất AXYZ
sẽ có 4 mục như sau:
AXY•Z

A •XYZ

AX•YZ
AXYZ•
Sản xuất Aε chỉ có một mục là A •. Một mục có thể được biểu diễn bằng
một cặp số nguyên, số đầu tiên là số thứ tự của sản xuất, số thứ hai là vị trí của dấu
chấm.
5


Về trực quan, một mục cho biết một sản xuất trong quá trình phân tích có thể
suy dẫn như thế nào. Ví dụ, mục đầu tiên ở trên nói rằng, ta hi vọng thấy một xâu con
tiếp theo trên đầu vào một xâu suy dẫn từ XYZ. Mục thứ hai chỉ rằng ta đã thấy trên
đầu vào một suy dẫn từ X và ta hi vọng thấy một xâu tiếp theo có thể suy dẫn từ YZ.
Tư tưởng chủ đạo của phương pháp SLR là ta sẽ xây dựng từ văn phạm đã cho
một ô tô mát hữu hạn đơn định DFA dùng để nhận dạng các tiền tố có thể có. Ta
nhóm các mục với nhau thành các tập và các tập này được lấy làm các trạng thái của
bộ phân tích SLR.

Một tập các tập mục LR (0) được gọi là tập LR (0) chuẩn, là cơ sở cho việc xây
dựng các bộ phân tích SLR. Để xây dựng tập LR (0) chuẩn cho một văn phạm ta định
nghĩa văn phạm mở rộng và hai hàm: closure (bao đóng) và goto (nhảy tới).
2.2. Văn phạm mở rộng
Nếu G là một văn phạm với ký hiệu bắt đầu là E thì G’ là văn phạm mở rộng
của G bằng cách thêm vào G một ký hiệu bắt đầu E’ và thêm vào đó một sản xuất
E’E. Lý do của việc sửa đổi này là nhằm chỉ cho bộ phân tích biết khi nào nên dừng
phân tích và thông báo chấp nhận xâu vào. Do đó, việc chấp nhận sẽ xảy ra khi và chỉ
khi bộ phân tích thu gọn bằng sản xuất E’ E.
2.3. Hàm closure
Nếu I là tập các mục của một văn phạm G thì bao đống closure(I) là tập các
mục được xây dựng từ I bằng hai luật:
1. Khởi đầu, mọi mục trong I đều được thêm vào closure(I).
2. Nếu A  α•Bβ có trong closure(I) và B  γ là một sản xuất thì thêm mục
B •γ vào I nếu nó chưa sẵn sàng trong đó. Áp dụng luật này cho đến khi không
thêm được một mục nào nữa vào closure(I).
Trực quan, A  α•Bβ trong closure(I) chỉ ra rằng, tại một điểm nào đó trong
quá trình phân tích, có thể thấy tiếp một xâu con suy dẫn từ Bβ ở đầu vào. Nếu B  γ
6


là một sản xuất, ta cũng mong muốn thấy một xâu con suy dẫn từ γ tại điểm này. Vì
những lý do đó ta thêm B  •γ vào closure(I).
Ví dụ: Xem xét văn phạm mở rộng của các biểu thức như sau:
E’  E
EE+T|T
TT*F|F
F  (E) | a
Nếu I là tập mục chỉ có đúng một mục {[E’  •E]} thì closure(I) bao gồm các mục:
E’  •E


E  •E + T

F  •(E)

F  •a

E  •T

T  •T * F

T  •F

Ở đây E’  •E được đặt vào closure(I) theo luật 1. Khi có một E đi ngay sau một
chấm thì bằng luật 2 ta thêm các sản xuất E với các chấm nằm ở đầu trái, tức là
E•E+T và E •T. Bây giờ lại có một T đi ngay sau một chấm và ta lại thêm
T•T*F và T•F. Tiếp theo, tương tự với F ta thêm được F•(E) và F•a. Và
bây giờ không còn thêm được một mục nào nữa vào closure(I) qua luật 2.
Hàm closure có thể được tính như dưới đây. Một cách thuận tiện thực hiện hàm
này là dùng một mảng boolean added, được đánh chỉ số theo các ký hiệu không kết
thúc của G, ví dụ như added[B] được đặt là true nếu và khi ta thêm các mục B  •γ
đối với mỗi sản xuất B  γ.
function closure(I);
begin
J:=I;
repeat
for với mỗi mục A  α•Bβ trong J và với mỗi sản xuất B  γ
của G mà B  •γ không trong J do thêm B  •γ vào J.
until không còn mục nào được thêm vào J;
Trả lại J;

7


end;
Chú ý khi một sản xuất được thêm vào bao đóng của I với dấu chấm ở đầu bên
trái, thì tất cả các sản xuất B sẽ được thêm tương tự vào bao đóng này. Thật ra, trong
một số hoàn cảnh thực tế không cần thiết liệt kê các mục B  •γ thêm vào I bằng
hàm closure. Ta có thể chia tất cả các tập mục mà ta quan tâm thành hai lớp mục:
1. Mục nhân: bao gồm mục khởi đầu E’  •E và tất cả các mục mà các chấm
không ở đầu bên trái.
2. Mục không phải nhân: các mục có chấm nằm ở đầu bên trái.
Ta thấy rằng, mỗi tập mục được hình thành bằng cách lấy bao đóng của một tập
mục nhân, dĩ nhiên các mục được thêm vào bao đóng không còn là mục nhân nữa. Do
đó có thể biểu diễn các tập mục ta thật sự quan tâm với lưu trữ ít nhất bằng cách loại
bỏ tất cả các mục không phải nhân đi và nếu cần có thể được sinh lại bằng hàm tính
bao đóng.
2.4. Hàm goto
Hàm thứ hai là goto(I,X) với I là một tập các mục và X là một ký hiệu văn phạm
goto(I,X) được xác định là bao đóng closure của tập tất cả các mục [A  αX•β] mà
[A  α•Xβ] là thuộc I. Ta có thể thấy, nếu I là tập các mục hợp lệ đối với một tiền tố
có thể có γ nào đó, thì goto(I,X) là tập các mục hợp lệ với tiền tố có thể có γX.
Ví dụ :
Nếu I là tập hai mục {[E’  E•], [E  E•+T]} thì goto(I, +) bao gồm:
E  E + •T

F  •(E)

T  •T * F

F  •a


T  •F
Ta tính goto(I, +) bằng cách kiểm tra I cho các mục với dấu + ở ngay bên phải
dấu chấm. E’  E• không phải là mục như vậy, nhưng E  E + •T thì đúng. Ta
8


chuyển dấu chấm qua bên kia dấu + để nhận được {E  E + •T} và sau đó tính
closure cho tập này.
function goto(I,X);
begin
Đặt J là tập mục [A→αX•β, a] mà [A→αX•β, a] trong I
Trả lại closure(J);
end;

2.5. Xây dựng tập mục
Thuật toán dưới đây dùng để xây dựng C là tập một tập chuẩn LR (0) cho một
văn phạm mở rộng G’:
procedure items(G’);
begin
C:= { closure({[E’ • E]})};
repeat
for với mỗi tập mục I của C và mỗi ký hiệu văn phạm X mà goto(I,X)
không rỗng và không thuộc C do
Thêm goto(I,X) vào C;
until không thêm được tập mục nào nữa vào C;
end;
2.6. Hàm FIRST(α )
Ðịnh nghĩa : FIRST(α) là tập hợp các ký hiệu kết thúc mà nó bắt đầu một
chuỗi dẫn xuất từ α. Với α là một chuỗi các ký hiệu văn phạm, Nếu α ⇒* ε thì ε ∈

FIRST(α).
Cách tính: Để tính FIRST(α) trước hết ta tính FIRST(X) như sau: Thực hiện
các quy luật sau cho đến khi không còn có ký hiệu kết thúc nào hoặc ε có thể thêm
vào tập FIRST(X) :
1. Nếu X là kí hiệu kết thúc thì FIRST(X) là {X}
2. Nếu X → ε là một luật sinh thì thêm ε vào FIRST(X).

9


3. Nếu X → Y1Y2Y3 ...Yk là một luật sinh thì thêm tất cả các ký hiệu kết thúc
khác ε của FIRST(Y1) vào FIRST(X). Nếu ε ∈ FIRST(Y1) thì tiếp tục thêm vào
FIRST(X) tất cả các ký hiệu kết thúc khác ε của FIRST(Y 2). Nếu ε ∈ FIRST(Y1) ∩
FIRST(Y2) thì thêm tất cả các ký hiệu kết thúc khác ε ∈ FIRST(Y3) ... Cuối cùng
thêm ε vào FIRST(X) nếu ε ∈
Bây giờ ta có thể tính được FIRST(α) cho mọi xâu α có dạng X1 X2 …Xn như
sau: Thêm vào FIRST(X1 X2 …Xn) tất cả các ký hiệu không phải ε của FIRST(X1). Ta
cũng thêm tất cả các ký hiệu không phải ε của FIRST(X 2) nếu ε thuộc FIRST(X1), các
ký hiệu không phải ε của FIRST(X 3) nếu ε thuộc FIRST(X2) … Cuối cùng thêm ε vào
FIRST(X1 X2 …Xn) nếu với mọi i mà FIRST(Xi) có chứa ε hoặc nếu n = 0.
Ví dụ: Với văn phạm sau:
E → T E'
E' → + T E' | ε
T → F T'
T'→ * F T' | ε
F → (E) | id
Theo định nghĩa tập FIRST, ta có :
Vì F ⇒ (E) | id ⇒ FIRST(F) = { (, id }
Từ T → F T' và ε ∉ FIRST(F) ⇒ FIRST(T) = FIRST(F)
Từ E → T E' và ε ∉ FIRST(T) ⇒ FIRST(E) = FIRST(T)

Vì

E' → ε ⇒ ε ∈ FIRST(E')

Mặt khác do E' → + TE' mà FIRST(+) = {+} ⇒ FIRST(E') = {+, ε }
Tương tự FIRST(T') = {*, ε }
Vậy ta có :
FIRST(E) = FIRST(T) = FIRST(F) = { (, id }
FIRST(E') = {+, ε }
10


FIRST(T') = {*, ε }
2.7.

Hàm FOLLOW(A)
Định nghĩa: FOLLOW(A) là tập hợp các ký hiệu kết thúc a mà nó xuất hiện

ngay sau A (bên phía phải của A) trong một dạng câu nào đó. Tức là tập hợp các ký
hiệu kết thúc a, sao cho tồn tại một dẫn xuất dạng S ⇒* αAaβ. Chú ý rằng nếu A là ký
hiệu phải nhất trong một dạng câu nào đó thì $ ∈ FOLLOW(A) ($ là ký hiệu kết thúc
chuỗi nhập ). Với A là ký hiệu chưa kết thúc.
Cách tính: Áp dụng các quy tắc sau cho đến khi không thể thêm gì vào mọi tập
FOLLOW được nữa.
1. Ðặt $ vào follow(S), trong đó S là ký hiệu bắt đầu của văn phạm và $ là ký
hiệu kết thúc chuỗi nhập.
2. Nếu có một luật sinh A→ αBβ thì thêm mọi phần tử khác ε của FIRST(β)và
trong FOLLOW(B).
3. Nếu có luật sinh A→ αB hoặc A→ αBβ mà ε ∈ FIRST(β) thì thêm tất cả các
phần tử trong FOLLOW(A) vào FOLLOW(B).

Ví dụ: Với văn phạm trong ví dụ trên:
- Áp dụng luật 2 cho luật sinh F→ (E) ⇒ ) ∈ FOLLOW(E) ⇒ FOLLOW(E)={$,)
- Áp dụng luật 3 cho E → TE' ⇒ ), $ ∈ FOLLOW(E') ⇒ FOLLOW(E') ={$, ) }
- Áp dụng luật 2 cho E → TE' ⇒ + ∈ FOLLOW(T). Áp dụng luật 3 cho
E'→+TE', E' → ε
⇒ FOLLOW(E') ⊂ FOLLOW(T) ⇒ FOLLOW(T) = { +, ), $ }.
- Áp dụng luật 3 cho T→ FT' thì FOLLOW(T') = FOLLOW(T) ={+, ), $ }
- Áp dụng luật 2 cho T→ FT' ⇒ * ∈ FOLLOW(F)
- Áp dụng luật 3 cho T' → * F T' , T'→ ε
⇒ FOLLOW(T') ⊂ FOLLOW(F) ⇒ FOLLOW(F) = {*, +, ), $ }.
* Vậy ta có:
o FOLLOW(E) = FOLLOW(E') = { $, ) }
o FOLLOW(T) = FOLLOW(T') = { +, ), $ }
o FOLLOW(F) = {*,+, ), $ }
11


2.8. Bảng phân tích SLR
Bây giờ ta sẽ xem cách xây dựng các hàm action và goto của phân tích SLR từ
DFA dùng để nhận dạng các tiền tố có thể có. Thuật toán này không phải luôn đưa ra
được các bảng action cho mọi văn phạm, nhưng nó thành công đối với nhiều ngôn
ngữ lập trình.
Cho một văn phạm G, ta mở rộng nó thành G’ và từ G’ ta xây dựng C là tập
chuẩn của các tập mục cho G’. Ta xây dựng hàm phân tích action và hàm nhảy goto
từ C bằng thuật toán dưới đây. Nó đòi hỏi ta tính FOLLOW(A) cho mọi ký hiệu
không kết thúc của văn phạm.
Thuật toán : Xây dựng một bảng phân tích SLR

1.
2.


3.
4.
5.

Input: một văn phạm mở rộng G’.
Output: Bảng phân tích SLR có các hàm action và goto cho G’.
Phương pháp:
Xây dựng C = {I0, I1,…, In} là tập các tập mục LR(0) cho G’.
Trạng thái i được xây dựng từ I i. Các hoạt động phân tích cho trạng thái i được
xác định như sau:
a. Nếu [A→α•aβ] thuộc Ii và goto(Ii, a) = Ij thì đặt action[i, a] thành “gạt j”.
Ở đây a phải là một ký hiệu kết thúc.
b. Nếu [A→α•] thuộc Ii thì đặt action[i, a] là “thu gọn A→αn” cho mọi a
thuộc FOLLOW(A); ở đây A phải khác E’.
c. Nếu [E’ →E•] thuộc Ii thì đặt action [i, $] là “chấp nhận”.
Nếu có bất kỳ đụng độ nào được sinh ra bằng các luật trên thì ta nói văn
phạm đã cho không phải là SLR(1). Thuật toán thông báo không sinh được
bộ phân tích trong trường hợp này.
Các bước chuyển goto cho trạng thái i được xây dựng cho mọi ký hiệu không
kết thúc A bằng luật: nếu goto(Ii, A) = Ij thì action[i, A] = j.
Mọi vị trí không được xác định bằng luật 2 và 3 sẽ được đặt là “lỗi”.
Trạng thái khởi đầu của bộ phân tích được xây dựng từ tập mục có chứa
[E’→•E].

Bảng phân tích ở trên được gọi là bảng SLR(1) cho văn phạm G’ và gọi tắt là SLR.

12



CHƯƠNG II: THỰC HÀNH
1. Xây dựng bảng phân tích SLR cho văn phạm G
Văn phạm G =<{not, true, false, or, and, (, )}, {bexpr , bterm, bfactor}, bterm, P>.
P là tập các luật sinh như sau:
bexpr→bexpr or bterm | bterm
bterm→bterm and bfactor | bterm
bfactor→not bfactor | (bexpr) | true | false
Để rút gọn các ký hiệu, thuận lợi cho phân tích và xây dựng bảng, ta ký hiệu lại
văn phạm như sau:
STT Ký hiệu trước
1
2
3
4
5

Not
True
false
Or
And

Ký hiệu thay
thế
a
b
c
+
*


STT Ký hiệu trước
6
7
8
9
10

(
)
Bexpr
Bterm
Bfactor

Ký hiệu thay
thế
(
)
E
T
F

Vậy, văn phạm G có thể phát biểu lại thành:
G =<{a, b, c, +, *, (, )}, {E , T, F}, T, P>. P là tập các luật sinh như sau:
E→E + T | T
T→T * F | T
F→a F | (E) | b | c
1.1. Xây dựng tập mục:
Ta có văn phạm tăng cường G’ như sau:
E’→E
E→E + T | T

T→T * F | T
F→a F | (E) | b | c
13


I0
E’→•E
E→•E + T
E→•T
T→•T*F
T→•T
F→•aF
F→•(E)
F→•b
F→•c
I1 = goto(I0, E)
E’→E•
E→E•+ T
I9 = goto(I3, F)
F→aF•

I10 = goto(I4, E)
F→(E•)
E→E•+ T

I2 = goto(I0, T)
E→T•
T→T•* F
T→T∙
I3 = goto(I0, a)

F→a•F
F→•aF
F→•(E)
F→•b
F→•c

I4 = goto(I0, ( )
F→(•E)
E→•E + T
E→•T
T→•T*F
T→•T
I5 = goto(I0, b)
F→b•
I6 = goto(I0, c)
F→c•

I11 = goto(I7, T)
E→E+T•
T→T•* F
T→T∙

I12 = goto(I8, F)
T→T* F•

I13= goto(I10, ))
F→(E ) •

14


I7= goto(I1, +)
E→E+•T
T→•T*F
T→•T
I8 = goto(I2, *)
T→T*•F
F→•aF
F→•(E)
F→•b
F→•c


1.2. Hàm FOLLOW
Ta tính được hàm FOLLOW cho các ký hiệu chưa kết thúc như sau:
FOLLOW(E) = {+, ), $}
FOLLOW(T) = FOLLOW(F) = {+, *, ), $}
1.3. Xây dựng bảng phân tích SLR
Dựa vào tập mục và hàm FOLLOW đã xây dựng ở trên, ta xây dựng được bảng
phân tích cú pháp SLR như sau
Trạng
thái
0
1
2
3
4
5
6
7
8

9
10
11
12
13

a
s3

b
s5

c
s7

ACTION
+
*
s7
r2

s3
s3

s5
s5
s5
s5

s8


s6
s6

)

$

r2

acc
r2

s4
s4
r6
r7

s3
s3

(
s4

r6
r7

11
r6
r7


s6
s6
r4

s8
r3
r5

12
r4
s13
r1
r3
r5

r4
r1
r3
r5

Ý nghĩa:
si : chuyển trạng thái i
ri : thu gọn bởi luật sinh i
acc: accept (chấp nhận)
error : khoảng trống
2. Áp dụng phân tích cú pháp của câu
Câu: not false or (true or false) được chuyển thành : ac+(b+c)
15


2

10
3

r6
r7

s4
s4
r4
s7
r1
r3
r5

E
1

GOTO
T
F
2
3

3
13


Stack

(1)
(2)
(3)
(4)
(5)
(6)
(7)
(8)
(9)
(10)
(11)
(12)
(13)
(14)
(15)
(16)
(17)
(18)
(19)
(20)
(21)
(22)

Input
Action
ac+(b+c)$
c+(b+c)$
+(b+c)$
+(b+c)$
+(b+c)$

+(b+c)$
+(b+c)$
(b+c)$
b+c)$
+c)$
+c)$
+c)$
+c)$
c)$
)$
)$
)$
)$
$
$
$
$ Acc

0
0a4
0a4c7
0 a 4 F 10
0F3
0T2
0E1
0E1+8
0E1+8(5
0E1+8(5b6
0E1+8(5F3
0E1+8(5T2

0 E 1 + 8 ( 5 E 11
0 E 1 + 8 ( 5 E 11 + 8
0 E 1 + 8 ( 5 E 11 + 8 c 7
0 E 1 + 8 ( 5 E 11 + 8 F 3
0 E 1 + 8 ( 5 E 11 + 8 T 12
0 E 1 + 8 ( 5 E 11
0 E 1 + 8 ( 5 E 11 ) 14
0E1+8F3
0 E 1 + 8 T 12
0E1

TÀI LIỆU THAM KHẢO
[1] Phạm Hồng Nguyên, “Nhập môn Chương trình dịch”.
[2] Phạm Hồng Nguyên, “Giáo trình thực hành Chương trình dịch”.
[3] Aho, Sethi, Ullman, “Compilers – Principles, Techniques and Tools”.
[4] Bài giảng môn học Lý thuyết chương trình dịch – TS Hà Chí Trung – HV KTQS

16