BỘ GIÁO DỤC – ĐÀO TẠO
ĐẠI HỌC ĐÀ NẴNG

BÁO CÁO TIỂU LUẬN MÔN LÝ THUYẾT TÍNH TOÁN
Đề tài: Văn phạm phi ngữ cảnh tương ứng với một
máy nhận PDA và sự phân tích cú pháp
Giáo viên hướng dẫn : PGS.TS Phan Huy Khánh
Nhóm học viên thực hiện : Nguyễn Tiến Mẫu
Nguyễn Văn Phong
Nguyễn Thị Vũ Thảo
Lớp : Khoa học máy tính
Khóa : Tháng 8/2009
Đà Nẵng, tháng 5/2010
Trang 1
Phần 1. LÝ THUYẾT
PUSHDOWN AUTOMATA
1. Văn phạm phi ngữ cảnh tương ứng với máy nhận PDA
Phần này sẽ hữu ích để ghi nhớ rằng máy PDA đẩy xuống đã được cấu trúc
trong phần trước để giả lập các dẫn xuất bên trái nhất trong một văn phạm phi ngữ
cảnh được thừa nhận. Nếu tại một điểm nào đó trong một dẫn xuất chuỗi hiện tại
là xα. x là một chuỗi chứa kí tự kết thúc, khi đó tại một điểm nào đó trong dãy mô
phỏng, chuỗi vào đọc tới x và ngăn xếp chứa chuỗi α. Ngăn xếp alphabet của PDA
là ΣUV. Sự di chuyển được định nghĩa để những biến được lấy ra từ ngăn xếp và
được thay thế bởi những biến ở phía bên phải nó, và những kí tự kết thúc trên ngăn
xếp được dùng để so sánh với những kí tự vào. Trong cấu trúc này những trạng
thái hầu hết là ngẫu nhiên; sau khi kí tự đầu tiên di chuyển, máy PDA dừng lại tại
một trạng thái cho đến khi nó sẵn sàng để nhận.
Bây giờ hãy xem xét vấn đề ngược lại, cấu trúc một văn phạm phi ngữ cảnh, cái
sinh ra ngôn ngữ được chấp nhận bởi một máy nhận PDA. Những đối số được
phức tạp hóa một cách vừa phải, nhưng nó sẽ được đơn giản hóa đến mức độ mà
chúng ta có thể thừa nhận rằng máy PDA chấp nhận ngôn ngữ bởi một stack rỗng.

δ
1
) chấp nhận ngôn ngữ
L bởi ngăn xếp rống. Nói cách khác, cho bất kì một chuỗi x, x

L nếu và chỉ nếu
(q1, x, Z1)

*M1 (q,
Λ
,
Λ
) cho một vài trạng thái q

Q1.
Chứng minh ngắn gọn:
Tại thời điểm máy PDA M chấp nhận một chuỗi thì ngăn xếp của nó có thể
không rỗng. Chúng ta muốn xây dựng M1

để khi 2 máy M1

và M xử lí trên cùng
một chuỗi kí tự vào thì ngăn xếp của M1 sẽ chính xác bị rỗng khi máy M chuyển
sang một trạng thái chấp nhận. Nếu chúng ta tạo ra máy M1 một cách đơn giản là
một bản sao của máy M nhưng với khả năng tự làm rỗng ngăn xếp mà không cần
đọc một kí tự vào nào. Khi máy M chuyển sang một trạng thái nhận thì chúng ta sẽ
có phần chúng ta muốn: bất kì khi nào máy M chuyển sang một trạng thái nhận, thì
câu vào cũng được M1

chấp nhận bởi ngăn xếp rỗng. Lí do mà điều này không

0
, bỏ qua những trạng thái đầy đủ của PDA.
Mỗi khi PDA di chuyển là đọc a ( a là A hoặc một phần tử của Σ) và thay thế A
trên ngăn xếp bởi B
1
, B
2
,…B
m
, có kết quả sau.
A
→
a B
1
B
2
…B
m
Cách tiếp cận này phác thảo cho chúng ta sự tương quan ở trên giữa những nội
dung của ngăn xếp hiện tại và chuỗi các biến còn lại trong chuỗi kí tự hiện tại đang
được thành lập. tuy nhiên, nó sẽ cho phép grammar tạo ra tất cả các chuỗi kí tự
được thừa nhận bởi PDA. Nguyên nhân mà nó khá đơn giản là bằng cách bỏ qua
những trạng thái của PDA mà chúng ta có thể để cho những chuỗi kí tự khác được
nhận được. Chúng ta xem xét ví dụ 7.1 Có một PDA thừa nhận ngôn ngữ {xcxr

x

{a,b}*}. Sự thừa nhận bởi trạng thái cuối cùng, đúng ra là là bởi ngăn xếp rỗng
nhưng chúng ta có thể sữa chữa điều này và cũng có thể loại trừ trạng thái q
2

)}
δ
(q
1
, c, A) = {(q
1
, A)}
δ
(q
1
, a, A) = {(q
1
,
Λ
)}
δ
(q
1
,
Λ
, Z
0
) = {(q
1
,
Λ
)}
Sử dụng qui luật mà chúng ta giả định trên, chúng ta thu được những bước
chuyển tương ứng
Z

⇒
aca
Tương ứng với chuỗi các dịch chuyển sau
(q
0,
aca, Z
0
)

(q
0
, ca, AZ
0
)

(q1, a, AZ
0
)

(q1,
Λ
, Z0)

(q1,
Λ
,
Λ
)
Nếu chúng ta chạy PDA và thay chuỗi vào là aa, thì di sự chuyển đầu tiên là
(q

là các biến, chúng ta thử sử dụng những đối tượng của dạng sau:
[p,A,q]
trong đó, q và p là các trạng thái. Cho biến [p,A,q] được thay thế bởi a (
Λ
hoặc
là một kí tự cuối), nó phải là trường hợp mà tại đó PDA đi chuyển đọc a, lấy A ra
từ ngăn xếp và làm cho máy chuyển từ trạng thái p sang trạng thái q. Tổng quát
hơn, dẫn xuất này bao gồm biến [p,A,q] dùng làm đại diện cho bất kì sự di chuyển
nào làm cho PDA chuyển từ trạng thái p sang trạng thái q, và có tác dụng cuối
cùng là việc gỡ bỏ A từ stack.
Nếu biến [p,A,q] xuất hiện trong chuỗi kí tự hiện tại của một dẫn xuất, thì mục
tiêu của chúng ta là thay thế nó bởi
Λ
hoặc một kí tự kết thúc. Điều này có thể xảy
ra nếu có một sự di chuyển làm cho PDA chuyển từ trạng thái p sang trạng thái q
và lấy A ra khỏi stack. Tuy nhiên, giả sử một cách khác rằng có một sự dịch
chuyển từ p sang trạng thái p1 nào đó, nó đọc a và thay thế A trên stack bởi B1,
B2,… Bm. Cách này thích hợp để đưa a vào chuỗi hiện tại của chúng ta tại điểm
này, bởi vì chúng ta muốn chuỗi khởi tạo của các kí tự kết thúc tương ứng với kí tự
đọc vào sau này. Nhưng cho tới giờ thì mục tiêu ban đầu của chúng ta đang bị thay
Trang 4
đổi vì tất cả các kí tự mới được đưa vào stack. Cách trực tiếp nhất để loại bỏ những
kí tự mới B1, B2,… Bm là: bắt đầu từ trạng thái p1 và thực hiện một chuỗi các dịch
chuyển-kết thúc tại trạng thái p2 nào đó, hay nói khác kết quả là B1 sẽ được gỡ bỏ
từ ngăn xếp. Sau đó thực hiện một vài sự dịch chuyển nữa và gỡ bỏ B2 trong quá
trình dịch chuyển từ p2 sang trạng thái P3 nào đó,…Tóm lại, để dịch chuyển từ
Pm-1 sang Pm nào đó thì gỡ bỏ Bm-1, và cuối cùng dịch chuyển từ P
m
đến q và gỡ
bỏ B

3
]…[ p
m
,B
m
,q]
cho tất cả các trạng thái có thể trong chuỗi trạng thái p2, p3, pm. Một vài chuỗi
như vậy sẽ bị tắc ngẽn, có nghĩa là sẽ không có chuỗi dịch chuyển nào theo sau
chuỗi trạng thái này và không có được kết quả tối ưu trên. Nhưng sẽ không có tổn
hại nào từ những kết quả này, bởi vì với bất kì sự dẫn xuất nào trong số những
chuỗi tắc ngẽn đó xuất hiện, sẽ có ít nhất một biến không thể bị loại trừ từ chuỗi kí
tự và vì vậy sự dẫn xuất sẽ không đưa ra một chuỗi kí tự của những kí tự kết thúc.
Nếu chúng ta biểu thị S làm kí tự đầu tiên của grammar, và kết quả mà chũng ta
cần có dạng sau
S
→
[q
0
, Z
0
, q]
Trong đó q0 là trạng thái ban đầu. Khi chúng ta thừa nhận các chuỗi bằng stack
rỗng thì trạng thái cuối cùng là không liên quan, vì vậy chúng ta phải kể đến một
kết quả của loại này cho mỗi trạng thái q có thể.
Bây giờ thì chúng ta đã có bằng chứng rằng CFG mà chúng ta mô tả tạo ra ngôn
ngữ được thừa nhận bởi M.
Định lí 7.4
Cho M=(Q, Σ, Γ, q
0
, Z

∈
Q, a
∈
Σ
∪
{Λ} và A
∈
Γ, nếu
δ
(q, a, A) chứa (q
1
,
Λ
), thì [q,
A, q
1
]
→
a nằm trong P.
3. Với mỗi q, q
1
∈
Q, a
∈
Σ
∪
{Λ, A
∈
Γ và m>=1, nếu
δ

,B
1
,q
2
][ q
2
,B
2
,q
3
]…[ q
m
, B
m
,, q
m+1
]
nằm trong P
YÙ tưởng chính của sự chứng minh này là mô tả những chuỗi các kí tự kết thúc
có thể được dẫn xuất từ một biến [q, A, q’]; cụ thể, để thấy rằng với mỗi q, q’
∈
Q,
A
∈
Γ và x
∈
Σ
*
, thì
(1) [q, A, q’]

Q thì (1) đưa đến là [q
0
, Z
0
, q]
⇒
*
G
x; vì vậy x
∈
L(G) bởi vì chúng ta
có thể bắt đầu một dẫn xuất với một luật sinh của loại 1. Mặc khác, nếu x
∈
L(G)
thì bước đầu tiên trong bất kì một dẫn xuất nào của x phải là S
⇒
[q
0
, Z
0
, q] cho mỗi
q
∈
Q, có nghĩa là [q
0
, Z
0
, q]
⇒
*

⇒
1
G
x. Chỉ có thể suy
diễn rằng một bước dẫn xuất này là thuộc loại 2, và điều này chỉ xảy ra nếu x là
Λ
hoặc là một phần tử của Σ và
δ
(q, x, A) chứa (q’,
Λ
). Trong trường hợp này thì (q,
x, A

(q’,
Λ
,
Λ
) là hiển nhiên đúng.
Bước tiếp theo là với k>=1 và khi (q, A,q’)
⇒
n
G
x với n<=k thì (q, x, A

*
(q’,
Λ
,
Λ
). Bây giờ, giả sử rằng, (q, A, q’)

Với m ≥1, a
∈
Σ
∪
{
Λ
}, một vài chuỗi B
1,
B
2
B
m
∈
Γ, và một vài chuỗi q
1,
q
2
q
m
∈
Q để cho
δ
(q, a, A) chứa (q
1,
B
1.
B
m
). Phần còn lại của sự dẫn xuất sẽ làm
cho mỗi biến trong [q

m-1 thì
(q
i
, x
i
, B
i
)

*
(q
i+1
,
Λ
,
Λ
)
và
(q
m
, x
m
, B
m
)

*
(q’,
Λ
,

B
m
)
sau đó M có thể đi đến một chuỗi của bước
(q
2
, x
2
…x
m
, B
2
B
m
)
Trang 6
sau đó đến (q
3
, x
3
…x
m
, B
3
B
m
) và cuối cùng là đến bước (q’,
Λ
,
Λ

n
(q’,
Λ
,
Λ
), thì [q, A, q’]
⇒
*
x. Tiếp theo ta giả sử rằng
(q, x, A)

k +1
(q’,
Λ
,
Λ
), và điều chúng ta muốn là chứng tỏ rằng [q, A, q’]
⇒
*
x.
Chúng ta đã biết rằng với mỗi a
∈
Σ
∪
{
Λ
} và y
∈Σ
*
, x=ay và bước di chuyển đầu

≤
i
≤
m thì đây là một điểm trung gian mà tại đó stack phải
chứa chính xác chuỗi B
i
, B
i+1
B
m
. Với mỗi i như vậy, đưa q
i
vào làm trạng thái của
M trong lần đầu tiên ngăn xếp chứa B
i
B
m
và x
i
là phần kí tự đọc vào nó được dùng
để di chuyển từ q
i
đến q
i+1
(hoặc nếu i=m, thì trong sự di chuyển từ q
m
đến cấu hình
(q’,
Λ
,


*
(q’,
Λ
,
Λ
)
trong đó, mỗi chuỗi di chuyển được đưa ra bao gồm tối đa k bước. Vì vậy, bằng
cách đưa ra giả thuyết
(q
i
, B
i
, q’)

*
G
x
i
mỗi i với 1
≤
i
≤
m-1 và
(q
m
, B
m
, q’)


∈
{a,b}
*
} mà chúng ta đã dùng để
đưa vào việc xây dựng định lí 7.4. Trong thảo luận đó chúng ta đã chấp nhận PDA
với bảng các chuyển tiếp của nó được cho dưới đây. (nó đã được sửa đổi một phần
trong ví dụ 7.1, cả 2 cách sử dụng các kí tự in hoa cho các kí tự của stack và việc
thừa nhận bởi stack rỗng).
Move State Input Stack symbol Move(s)
Trang 7
number
1 q
0
a Z
0
(q
0
,
AZ
0
)
2 q
0
b Z
0
(q
0
,
BZ
0

8 q
0
c A (q
1
, A)
9 q
0
c B (q
1
, B)
10 q
1
a A
(q
1
, Λ)
11 q
1
b B
(q
1
, Λ)
12 q
1
Λ
Z
0
(q
1
, Λ)

, B, p][p, Z
0
, q]
(3) [q
0
, A, q] → a[q
0
, A, p][p, A, q]
(4) [q
0
, A, q] → b[q
0
, B, p][p, A, q]
(5) [q
0
, B, q] → a[q
0
, A, p][p, B, q]
(6) [q
0
, B, q] → b[q
0
, B, p][p, B, q]
(7) [q
0
, Z
0
, q] → c[q
1
, Z

Xem xét chuỗi bacab. PDA chấp nhận nó bởi chuỗi các dịch chuyển sau:
(q
0
,bacab, Z
0
)  (q
0
, acab, BZ
0
)
 (q
0
, cab, ABZ
0
)
 (q
1
, ab, ABZ
0
)
 (q
1
, b, BZ
0
)
Trang 8
 (q
1
,
Λ

, q
1
]
⇒
ba[q
0
, A, q
1
][q
1
, B, q
1
][q
1
, Z
0
, q
1
]
⇒
bac[q
1
, A, q
1
][q
1
, B, q
1
][q
1

, Z
0
, q
0
].
Tuy nhiên, nhớ rằng [q
0
, Z
0
, q] biểu diễn cho chuỗi di chuyển từ trạng thái q
0
sang
trạng thái q và gỡ bỏ Z
0
ra khỏi stack. Bởi vì PDA kết thúc ở trạng thái q
1
, vậy rõ
ràng là q nên là q
1
. Tương tự như vậy, thì bước thứ 2 sẽ là:
[q
0
, Z
0
, q
1
]
⇒
b[q
0

*
x
( kiểm tra x được sinh ra từ văn phạm G, hoặc xác định không được sinh
ra) điều này rất hữu ích. Phân tích cú pháp trong ngôn ngữ lập trình, là ví dụ rất
cần thiết để phân loại lớp cú pháp; phân tích một biểu thức đại số cơ bản cho phép
để đánh giá biểu thức đó. Vấn đề là tìm kiếm một thuật toán hiệu quả để phân tích
cú pháp là vấn đề lớn trong nghiên cứu khoa học, và có rất nhiều kỹ thuật thiết kế
phụ thuộc vào thuộc tính của văn phạm.
Trong phần này chúng ta trở lại hai cách cơ bản đã được trình bày trong
phần 7.4 thu được từ một PDA chấp nhận ngôn ngữ L(G). Trong cả hai trường
hợp PDA không chỉ chấp nhận câu trong L(G) mà còn nêu lên nguồn gốc của quá
trình tạo ra câu x (trong trường hợp này nó bắt nguồn từ bên cực trái, trường hợp
khác bên cực phải). Mặc dù câu trả lời của một PDA là đúng hoặc sai, nó đủ để
làm tăng lên tính nổi bật của cái máy có đầu đọc di chuyển. Vì vậy đó là lý do mà
các chuỗi được chấp nhận và được hiển thị. Tuy nhiên cấu trúc câu cũng không thể
nói là nó sinh ra từ phân tích thuật toán. Bởi vì cả hai PDA vốn đã không đơn định.
Trong mỗi trường hợp, xác định trạng thái kế tiếp đúng đắn, nó sẽ được xác
nhận cuối cùng bởi PDA.
Phương pháp tiếp cận thu được ở thuật toán phân tích câu sẽ xem xét dự
đoán tất cả các trường hợp có thể để cấu tạo nên PDA, để xem một trong số đó dẫn
đến sự chấp nhận. Ví dụ 7.47 giải thuật quay lui với văn phạm đơn giản CFG. Tuy
nhiên có thể thực hiện với hai kiểu PDA không đơn định và không đơn định trực
tiếp: hơn là tạo ra một lựa chọn tuỳ ý và cố gắng xác nhận điều đó là đúng , và cố
gắng sử dụng tất cả thông tin để có sự lựa chọn chính xác. Trong phần còn lại của
phần này, chúng ta tập trung trên hai lớp văn phạm cơ bản, cho băng vào là ký tự
và ký tự trên đỉnh ngăn xếp phần còn lại là PDA cung cấp đủ các thông tin mỗi
bước chuyển kế tiếp. Hơn nữa các văn phạm tổng quát cách tiếp cận ít nhất phải
cung cấp một điểm bắt đầu cho việc phân tích câu hiệu quả.
2.1 Phân tích cú pháp từ trên xuống:
Chúng ta xem xét ngôn ngữ các câu là dấu ngoặc đơn, để thuận lợi chúng ta

cho
trường hợp khi T trên đỉnh ngăn xếp và ký tự vào kế tiếp là [. Mặc dù trong trường
hợp này T được thay thế trên đỉnh ngăn xếp bởi xâu dài hơn [T]T, Trạng thái
chuyển từ q
]
chỉ lấy ra ký tự [ từ ngăn xếp và chuyển về trạng thái q
1
. Sự lựa chọn
này hy vọng sẽ hiệu quả hơn, thay thế hai bước chuyển thành một và q
1
ở PDA và
thay thế T trên đỉnh ngăn xếp bởi T]T.
Trong bảng dịch chuyển trạng thái của PDA không đơn định ban đầu ở biểu
diễn ở hình 7.8. và 7.9 miêu tả PDA đơn định kết hợp với nhìn vào đầu.
Tuần tự của bước chuyển mà PDA chấp nhận chuỗi []$, tương ứng với bước
chuyển cực trái của chuỗi này, được biểu diễn bên dưới.
( q
0
, []$, Z
0
)
├ ( q
1
, []$, SZ
0
) S
├ ( q
1
, []$, T$Z
0

, S$)
3 q
1
A T (q
1
, [T]T),(q
1
,A)
4 q
1
[ [ (q
1
, A)
5 q
1
] ] (q
1
, A)
6 q
1
$ $ (q
1
, A)
7 A Z
0
(q
2
, Z
0
)

1
] T (q
]
, A)
6 q
1
A ] (q
1
, A)
7 q
1
$ T (q
$
, A)
8 q
1
A $ (q
1
, A)
9 q
1
[ [ (q
1
, A)
10 q
1
] ] (q
1
, A)
11 q

) =>[]$
├ ( q
1
,A, Z
0
)
├ ( q
2
,A, Z
0
)
Chúng ta có lẽ đã thấy các trạng thái di chuyển 9, 10, và 11 của PDA đơn
định, và nó còn giữ lại các máy không đơn định, sẽ chưa bao giờ thực sự được sử
dụng. Các ví dụ mang tính tổng quát về chuyển trạng thái vẫn rất cần thiết. Mặc dù
không chứng minh được rằng PDA chấp nhận ngôn ngữ, có thể tìm trạng thái di
chuyển cho băng vào các xâu dài hơn.
Trong phần phân tích từ trên xuống của PDA từ văn phạm phi ngữ cảnh như
đã định nghĩa ở phần 7.4, nhìn vào giá trị băng vào kế tiếp không đủ để xác định
bước chuyển kế tiếp. Tuy nhiên, đôi khi thay đổi cấu trúc văn phạm đủ để thiết lập
thuộc tính này, như là hai ví dụ kế tiếp sau đây.
Rõ ràng khác vớ ngôn ngữ CFG ở ví dụ 7.8 ở đây ta có luật sinh :
S → T $
T→ T [T] | A
Phân tích PDA trên xuống các luật sinh văn phạm này cũng giống như ví dụ
7.8, ngoại trừ câu được thay thế bởi T trên đỉnh stack ở trạng thái di chuyển đầu ở
Trang 12
dòng 3. chúng ta thấy vấn đề ở đây là thay thế các chuỗi [][][]$, mà bắt đầu từ bên
cực trái.
S => T$ => T[T]$ => T[T][T]$ => T[T][T][T]$ => => [][][]$
Tuần tự các bước chuyển của câu vào trước khi bắt đầu:

là T, nhưng tuần tự chuyển bắt đầu của bốn điểm là khác nhau. Từ đó tất các băng
vào còn lại rất giống nhau ở tất cả các cấu hình, nhìn vào phía trên của ký tự vào kế
tiếp, thậm chí trên phía trước, sẽ không có sự trợ giúp nào; không có sự lựa chọn
cơ bản nào cho bước chuyển kế tiếp của băng vào.
Một vấn đề xuất hiện ở đây là, bởi vì luật sinh T → T[T], luật sinh này xuất
hiện đệ quy trái. Bởi vì phía bên phải bắt đầu bằng T, PDA phải chứa một số bước
chuyển nhất định trước khi nó làm bất cứ gì khác, và nhìn vào băng vào và nó có
quyết định như thế nào. Trong trường hợp này chúng ta có thể loại trừ đệ quy trái
bằng cách thay đổi ngữ pháp, giả sử ta có T- luật sinh tổng quát cho một văn phạm:
T → T α | β
ở đây chuỗi β không được bắt đầu bằng T, cho phép tất cả các chuỗi βα
n
, cho n ≥
0, nếu ở đây ta có hai luật sinh được thay như sau:
T → β U
U → αU | A
ngôn ngữ không bị thay đổi và vấn đề đệ quy trái đã được loại bỏ, Ví dụ với, α =
[T] và β = A, chúng ta thay thế
T → T [T] | A
bởi T → U
U → [T] U | A
và kết quả cho phép văn phạm xây dựng nhiều PDA đơn định như ví dụ 7.8
Cho văn phạm phi ngữ cảnh có các luật sinh như sau:
S → T $
T → [T] | [] T | [T] T | []
Trang 13
Điều này thu được không rõ ràng từ một ví dụ 7.8 bởi loại bỏ một luật sinh T
→ [T] | A; Ngôn ngữ không thay đổi chỉ có điều nó không còn chứa chuỗi $.
Mặc dù ở đây không có đệ quy trái trong CFG, chúng ta có thể nói rằng
ngay sau khi biết ký tự tiếp theo đưa vào sẽ không có lựa chọn cho PDA không

,[U]W)
4 q
[
A [ (q
1
,A)
5 q
1
] U (q
[
,]W)
6 q
]
A ] (q
1
,A)
7 q
1
[ W (q
[
,[U)
8 q
1
[ W (q
]
,A)
9 q
1
$ W (q
$

CFG gọi là một văn phạm LL(1), điều đó có nghĩa là phân tích các luật sinh từ trên
xuông của PDA không đơn định từ văn phạm có thể chuyển sang phân tích từ trên
xuống của PDA đơn định bằng cách nhìn băng vào của ký tự kế tiếp. Một văn
Trang 14
phạm LL(k) nếu nó nhìn vào phía trước k ký tự ở băng vào thì luôn luôn có đủ các
lựa chọn cho bước chuyển kế tiếp của PDA.
Như vậy một văn phạm cho phép xây dựng phân tích câu đơn định từ trên
xuống, và ở đây hệ thống các phương pháp cho đơn định dù CFG là LL(k) và xây
dựng từ bên ngoài (xem chỉ dẫn).
Cho một văn phạm phi ngữ cảnh LL(1), một PDA đơn định một cách hình
thức miêu tả các bước chấp nhân câu bằng cách nhìn vào ký tự vào kế tiếp. Phương
pháp đệ quy lùi cũng là một cách khác. Tên tham chiếu đến tập hợp các thủ tục đệ
quy tương ứng với các biến trong văn phạm.
Phân tích đệ quy lùi cho văn phạm LL(1) trong ví dụ 7.10:
Cho văn phạm phi ngữ cảnh có luật sinh như sau:
S → [ US
U → ] W | [U] W
W → [ U | A
Chúng ta có một phiên bản C++ dùng phân tích đệ quy lùi. Thuật ngữ đoán
nhận câu chính xác hơn phân tích, mặt dù nó không khó thêm vào các câu lệnh cho
một chương trình, điều đó cho phép xây dựng lại nguồn gốc nhận biết xâu.
Chương trình bao gồm các hàm s, u và w tương ứng với ba biến. Gọi tương
ứng ba hàm tương ứng thay thế các biến trong suốt quá trình xử lý. hoặc thay thế
các biến trên ngăn xếp trong quá trình thực hiện PDA. Ở đây có một biến cục bộ
curr_ch giá trị của nó được tạo trước khi ba hàm trên được gọi. Nếu ký tự hiện tại
là trong số hàm chờ đợi., Thì nó phù hợp thì các hàm vào được gọi và đọc và nhảy
đến ký tự kế tiếp, ngoài ra nếu hàm quản lý lỗi được gọi và nó hiển thị ký tự nào đã
vào; trong trường hợp này chương trình được ngắt và hiển thị thông báo lỗi.
Chú ý chương trình đúng phụ thuộc trên văn phạm LL(1), cho đến khi mỗi
hàm có thể lựa chọn hành động đúng trên cơ sở ký tự vào hiện tại.

{
if (curr_ch=='[') {match ('['); u();}
}
void get_ch()
{
if (cin >>curr_ch) cout<<curr_ch;
if (cin.eof() && curr_ch !='$')
{ cout << "Kết thúc"; error("[ or ]");}
}
void match(char this_ch)
{ if (curr_ch==this_ch) get_ch(); else error(this_ch);}
void error( char* some_chars)
{ cout <<"\n Lỗi:"<<some_chars<<"\n";
exit(0);
}
void error( char a_char)
{
cout <<"\n Lỗi:"<<a_char<<"\n";
exit(0);
}
Chương trình không được đầy đủ nó chỉ quan tâm vài chi tiết cụ thể. Trong
trường hợp một chuỗi không thuộc ngôn ngữ, nó đọc và chỉ hiển thị ký tự không
hợp lệ đầu tiên, đó là điểm được DPDA khai thác, ngoài ra nó không đọc được $;
Trang 16
nếu chuỗi ký tự vào là [] $ . Ví dụ, chương trình chỉ đơn thuần hiển thị các ký tự []
$] trong ngôn ngữ. Cuối cùng các thông báo lỗi có thể là vấn đề nhỏ, Có hai lỗi
trong ví dụ này là tìm ra trong hàm s, sau khi được trả về khi gọi hàm u. Luật sinh
là S → [U S; hàm mà ta mong đợi thấy ký tự $ ở điểm này, mặc dù ký tự không
khác với $ sẽ đưa ra thông báo lỗi. Ký tự [ sẽ hợp lệ ở đây và sẽ có kết quả là trình
tự các hàm gọi khác nhau. Sao cho chương trình sẽ không phải thực hiện điều này

A S
1
(q, S)
Dịch chuyển để biến đổi S
1
+ T theo S
1
Q A T (q
1,1
, A)
q
1,1
A + (q
1,2
, A)
q
1,2
A S
1
(q, S
1
)
Dịch chuyển để biến đổi T theo S
1
Q A T (q, S
1
)
Dịch chuyển để biến đổi T * a theo T
Q A a (q
3,1

các câu.
Trở lại với câu hỏi thứ nhất, cho trên đỉnh ngăn xếp là T, và cho các khả
năng của ký tự vào. Nêu nó là +, chúng ta có chuỗi S
1
+ T, đảo ngược thứ tự trên
đỉnh ngăn xếp, và trạng thái chuyển đúng của điểm này là biến đổi T hoặc S
1
+ T
( phụ thuộc vào bên dưới của ngăn xếp) thành T. Nếu ký tự kế tiếp là * thì sẽ thay
thế T * a thành a, cho đến khi T đã hoàn thành. Cuối cùng, nếu nó là $ chúng sẽ
thay thế T hoặc S
1
+ T thành T cho phép biến đổi S
1
$. Trong bất kỳ trường hợp
chúng có thể quyết định các ký tự cơ bản của băng vào kế tiếp. Điều này đúng cho
ví dụ này điều đó có sự kết hợp chắc chắn các ký tự trên đỉnh ngăn xếp và ký tự
vào thì sự biến đổi luôn luôn phù hợp, một sự thay đổi đúng cho tất cả sự kết hợp
khác. Các bộ cặp đôi được thay đổi phù hợp là một ví dụ của quan hệ thứ tự. (nó là
quan hệ từ Γ đến ∑ ở phần 1.4). Một số loại văn phạm ưu tiên, quan hệ ưu tiên có
thể được sử dụng
Một PDA đơn định hoạt động như phân văn phạm như bảng 7.12. Khác với
PDA không đơn định, chúng ta thực hiện một vài quan sát. Bộ ký tự trong ngăn
xếp có thể được chia làm 3 nhóm: (1) ký tự yêu cầu trên ngăn xếp không quan tâm
đến ký tự vào kế tiếp là gì (chúng như Z
0
, S
1
, + và *); (2) yêu cầu biến đổi hoặc đi
đến chấp nhận (a, $, và S); và (3) T chỉ có lựa chọn đúng chỉ khi có thể tham khảo

A S
1
(q, S)
Dịch chuyển biến đổi a hoặc T * a theo T
5 q A a (q
a,1
,A)
6 q
a,1
A * (q
a,2
,A)
7 q
a,2
A T (q, T)
8 q
a,1
A X (q, TX)
X là bất kỳ trong ngăn xếp khác *
Dịch chuyển biến đổi S
1
+ T hoặc T và chuyển sang ký băng vào
9 q σ T (q
T,σ
, A)
10 q
T,σ
A + (q
T,σ
, A)

0
)
├(q
T,+
, a*a$,Z
0
)
├(q , a*a$, +S
1
Z
0
)
├(q, *a$, a+S
1
Z
0
)
├(q
a,1
, *a$, +S
1
Z
0
)
├(q, *a$, T+S
1
Z
0
)
├(q, a$, *T+S

├(q , A ,$S
1
Z
0
)
├(q
$
, A ,S
1
Z
0
)
Trang 19
├(q , A ,SZ
0
)
├(q
1
, A ,Z
0
)
chấp nhận.
Trang 20
Phần 2. BÀI TẬP
Đề số 12: Cho
},,{ cba=Σ
và một số nguyên n.
Hãy viết một chương trình trong một ngôn ngữ tùy chọn để liệt kê:
- Dãy n câu đầu tiên trên bảng chữ
Σ

If s
vt
là ký tự a thì gán lại bằng ký tự b
Ngược lại thì gán s
vt
là ký tự c
Gán s
i
bằng ký tự a với i= (vt+1, n)
}
Ngược lại S=

1

+n
aaa
2. Sinh dãy n câu đầu tiên:
S
1
=”a”;
For i=2 to n
S
i
= chuỗi kế tiếp của S
i-1

3. Dãy n cặp câu có độ dài tùy ý:
Q={}; // Dùng để lưu trữ các chuỗi ký tự theo yêu cầu
I=0;
While (i<n)

using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Text;
using System.Windows.Forms;
using System.Collections;
namespace WindowsApplication1
Trang 23
{
public partial class frmBT : Form
{
static char[] ch ={ 'a', 'b', 'c' };
public frmBT()
{
InitializeComponent();
}
private void Form1_Load(object sender, EventArgs e)
{
//StringS(4);
}
//them
/* static void Main(string[] args)
{
//DoubleString(20);
//System.Console.WriteLine(radomString(2) + "&&" + radomString(2));
StringS(20);
//NSentenceStart(100);
System.Console.ReadLine();
}*/

for (int i = 0; i < st.Length; i++) kq = kq+'a';
kq=kq+'a';
}
return kq;
}
// sinh mot chuoi ky tu theo do dai n
String radomString(int n)
{
String kq = "";
for (int i = 0; i < n; i++)
kq = kq + ch[myRandom(3+i)%3];
return kq;
}
// day n cap cau co do dai tuy y tren bang chu cai
void DoubleString(int n)
{
bool[] check=new bool[2*n];
String st1, st2;
int i;
for(i=0;i<2*n;i++)check[i]=false;
check[0] = true;
i = 0;
while (i < n)
{
// lay mot do dai tuy y
int len = myRandom(2 * n);
while (check[len]) len = myRandom(2 * n);
check[len] = true;
// sinh mot cap chuoi co do dai tuy y
st1 = radomString(len);