Sửa lỗi tự động trong ngôn ngữ lập trình. Bài toán SK (SK-Problem)

ó). Khi đó nó 
sẽ chuyển điều khiển sang phần E cùng với thông tin về trạng thái hiện tại q và ký hiệu trên 
đỉnh bĕng đẩy xuống Z.
2. Phần E sẽ đọc quét trên các ký hiệu nhập cho đến khi tìm được ký hiệu s khung đầu tiên 
thuộc tập khung trên phần xâu nhập đã được xử lý. Các ký hiệu khung sẽ xác định các điểm cần 
phải chỉnh sửa trên xâu nhập. Các tính chất này sẽ được nói rõ trong phần sau.
3. Phần E sẽ cung cấp mộ xâu u cho bĕng nhập và chuyển điều khiển vào đó.
Bước 3 sẽ được lặp lại cho đến khi M’ được sẵn sàng chấp nhận s. 
Các ký hiệu tạo nên tập khung K được lựa chọn sao cho các lỗi trong xâu nhập không rơi 
vào chúng. Theo nghĩa đó thì các lỗi chỉ rơi vào xâu ký hiệu nằm giữa hai ký hiệu khung trên 
xâu nhập nên ta có thể tạo một cơ chế tự động chỉnh sửa các lỗi này mà vẫn bảo đảm tính đúng 
đắn về mặt cú pháp cho xâu nhập.
Các ký hiệu khung tựa như các ký hiệu then chốt của ngôn ngữ và đã được sử dụng trong 
việc thiết kế của nhiều trình biên dịch trong việc phát hiện lỗi. 
Ý tưởng của phương pháp khắc phục lỗi do Chytil-Demner đề xuất được hiện thực dựa trên 
giả định là tập khung của ngôn ngữ đã được xác định.
3. Các định nghĩa hình thức và đặc trưng cơ bản của tập khung
Trong mục này chúng tôi sẽ đưa ra các định nghĩa hình thức và đặc trưng cơ bản liên quan 
đến khái niệm tập khung, đồng thời cũng cho rằng các độc giả đã nắm vững các khái niệm và ký 
hiệu trong lý thuyết ngôn ngữ hình thức và lý thuyết phân tích cú pháp được áp dụng trong việc 
thiết kế các trình biên dịch.
Định nghĩa 1: Với ngôn ngữ L tùy ý. Pref(L) ký hiệu tập tất cả các tiền tố của các xâu thuộc L.
Định nghĩa 2: Với ôtômát đẩy xuống M bất kỳ, L(M) ký hiệu ngôn ngữ được nhận dạng bởi 
ôtômát M. Không làm mất tính tổng quát ta có thể giả định mỗi từ thuộc ngôn ngữ L(M) đều 
được giới hạn bởi các ký hiệu mút trái và mút phải ├, ┤. 
Định nghĩa 3: Cho L là ngôn ngữ trên bảng chữ cái X, và cho x, y∈ X*, c∈ X, ta nói rằng 
xâu xc xác định lỗi đầu tiên trong xâu xcy nếu x∈ Pref(L) còn xc∈ Pref(L). Xâu được sửa lỗi 
của xâu xcy là xâu bất kỳ xy’∈ L.
41
Sữa lỗi . . .
Định nghĩa 4: Cho L là ngôn ngữ trên bảng chữ Σ, K là tập con của ∈ sao cho {├, ┤} ⊂ K. 
K cũng ký hiệu cho đồng cấu Σ*A K* bằng cách bỏ đi tất cả các ký hiệu không thuộc K trong 
một xâu bất kỳ thuộc Σ*.
Định nghĩa 5: (Tập khung) Cho L là ngôn ngữ trên bảng chữ Σ, K là tập con của Σ sao cho 
{├, ┤} ⊂ K. Ta gọi K là tập khung của ngôn ngữ L, nếu với mọi a,b ∈ K; u,v ∈ (Σ - K)* ; x,y ∈Σ* và mọi z ∈Σ* sao cho K(z) = K(x) thoả mãn điều kiện:
xauby ∈ L & zavb∈ Pref(L) ⇒ xavby∈ L.
Định nghĩa 6: Cho w∈Σ* và K là tập khung của ngôn ngữ L, khi đó ta gọi xâu K(w) là 
khung của w. Ta nói rằng, xâu w là thiết lập tốt nếu như K(w) ∈ K(L). 
Chú ý:
1. Từ định nghĩa 5 ta thấy rằng, nếu K là tập khung và a,b là hai ký hiệu khung thì ta có 
thể thay xâu u bằng xâu v bất kỳ thoả điều kiện của định nghĩa. Từ đây sẽ suy ra được ý tưởng 
chính của phương pháp sửa lỗi Chytil-Demner. Nghĩa là nếu lỗi nằm giữa hai ký hiệu khung 
thì ta có thể thay xâu lỗi không chứa ký hiệu khung bằng một xâu khác để nhận được một xâu 
đúng của ngôn ngữ đã cho.
2. Trong [5] đã chỉ ra rằng tập khung nhỏ nhất của ngôn ngữ lập trình Pascal là tập {begin, 
case, end, repeat, until, if, else , ;}. 
3. Từ định nghĩa 5 về tập khung dễ dàng nhận thấy rằng, đối với mỗi ngôn ngữ L bất kỳ trên 
bảng chữ cái S luôn tồn tại hai tập khung tầm thường là K = {├, ┤} và K = S. Chúng ta chỉ quan 
tâm đến các tập khung không tầm thường.
Định nghĩa 7: Cho L là ngôn ngữ trên bảng chữ cái Σ. K là tập con của Σ sao cho {├, ┤} ⊂ K ⊂Σ. Khi đó bài toán xác định, liệu K có phải là tập khung của ngôn ngữ L hay không, gọi 
là bài toán SK.
Trong [3] và [4] đã chỉ ra một đặc trưng của tập khung được xác định bởi định lý sau:
Định lý : (Điều kiện Chytil – Demner [3], [4] )
Cho K là tập con của S sao cho {├, ┤} ⊂ K, khi đó hai điều kiện sau là tương đương:
1. K là tập khung của ngôn ngữ L.
2. Cho a,b ∈ K; y,y’∈S* và x,z ∈S* sao cho K(x) = K(z). Nếu như xauby ∈ L và zavby’∈ 
L với u, v nào đó ∈ (S - K)* , khi đó ta có:
{u ∈ (S - K)* ; xauby ∈ L} = {v ∈ (S - K)* ; zavby’ ∈ L} 
Đặc trưng trên chỉ ra rằng, tập K là tập khung khi và chỉ khi các ngôn ngữ có thể có nằm 
giữa hai ký hiệu khung kề nhau của cùng một khung được xác định một cách đơn trị. Điều này 
hoàn toàn phù hợp đối với các ngôn ngữ lập trình. Ta cũng sẽ sử dụng ký hiệu K để biểu diễn 
đồng cấu X* A K* bằng cách loại bỏ các ký hiệu không phải khung trong các xâu từ X*.
Các đặc trưng của tập khung dựa trên tập hậu tố của ngôn ngữ phi ngữ cảnh
Trong mục này chúng tôi sẽ chỉ ra một số đặc trưng khác với nhưng tương đương với điều 
kiện do Chytil, Demner đã đề xuất ở trên. Các đặc trưng này sẽ tạo thuận lợi cho việc khảo sát 
các tính chất của tập khung cũng như giải quyết bài toán SK. Đặc trưng khung do chúng tôi 
đưa ra chỉ ra rằng với hai xâu bất kỳ có khung như nhau thì các ngôn ngữ hậu tố của chúng là 
như nhau
42
Taïp chí Kinh teá - Kyõ thuaät
Định nghĩa 8: Cho L là ngôn ngữ phi ngữ cảnh trên bảng chữ cái Σ. Xâu y ∈Σ* gọi là 
tập hậu tố ứng với tiền tố x ∈ Pref(L) trong ngôn ngữ L nếu xy ∈ L. Ta ký hiệu:
 Sufx(L) = {y ∈S* ; xy ∈ L}
Là tập tất cả các hậu tố ứng với xâu x trong L.
Định lý 1: Cho L là ngôn ngữ phi ngữ cảnh trên bảng chữ cái S và K là tập khung của 
ngôn ngữ L. Với mọi a ∈ K, x,z ∈S* sao cho K(x) = K(z) và xa, za Î Pref(L), khi đó ta có đẳng 
thức sau:
 Sufxa(L) = Sufza(L) (1)
Chứng minh:
Giả sử y Î Sufxa(L), với các xâu bất kỳ x,z ÎS* thoả mãn điều kiện định lý khi đó ta có thể 
viết các xâu xa và za trong dạng:
xa = a0 u1 a1  un an và za = a0 v1 a1  vn an
với aiÎ K, ui, viÎ (S - K)* 1 ≤ i ≤ n và an = a.
Do xay Î L và từ định nghĩa 4 dễ dàng suy ra za = a0 v1 a1  vn any Î L. Do đó :
 y Î Sufza(L)
Bao hàm thức ngược lại được chứng minh tương tự.
Đinh nghĩa 9: Cho L là ngôn ngữ phi ngữ cảnh trên bảng chữ cái S và K là tập con bất 
kỳ của S. Nếu với mọi a Î K, x,z ÎS* sao cho K(x) = K(z) và xa,za Î Pref(L) thoả mãn đẳng 
thức (1) , khi đó ta nói rằng ngôn ngữ L có tính chất K-hậu tố.
Định lý 2: Tính chất K-hậu tố là điều kiện cần và đủ của tập khung.
Chứng minh:
1. Điều kiện cần suy từ định lý 1.
2. Điều kiện đủ: Giả sử ngôn ngữ L có tính chất K-hậu tố. Khi đó với mọi xâu xaub, zavb 
Î Pref(L) với a,b Î K; u, v Î (S - K)* và x,z ÎS* sao cho K(x) = K(z) ta có:
K(xaub) = K(x)ab = K(z)ab = K(zavb) (2)
Từ tính chất K-hậu tố của ngôn ngữ L và từ biểu thức (2) ta có các đẳng thức sau:
 Sufxa(L) = Sufza(L)
 Sufxaub(L) = Sufzavb(L)
Nếu như xauby Î L vớii y ÎS* nào đó, khi đó từ đẳng thức sau cùng suy ra zavbyÎL nên 
ta có vby Î Sufza(L). Từ đó suy ra xavby Î L theo đẳng thức đầu.
Như vậy, tính khung của tập K trong ngôn ngữ L đã được chứng minh.
Định nghĩa 10: Cho a = xb là dạng câu trái trong vĕn phạm phi ngữ cảnh 
 G = (N, å ,P,S)
Sao cho xÎå* và b hoặc bắt đầu bằng một ký hiệu không kết thúc hoặc là xâu rỗng. Ta sẽ 
gọi x là phần đã sẵn sàng và b là phần chưa sẵn sàng trong xâu a.
Định nghĩa 11: Cho G = (N,å, P, S) là vĕn phạm phi ngữ cảnh. Ta ký hiệu 
 L(a) = {xÎΣ* ; aÞ* x}
với mọi aÎ (NÈå)*. Ta nói rằng hai xâu a,bÎ (NÈå)* là tương đương nếu như L(a) = L(b).
Định nghĩa 12: Vĕn phạm phi ngữ cảnh G = (N,å, P, S) trong dạng chuẩn Greibach gọi là vĕn 
phạm đơn trị mạnh nếu như với hai dạng câu trái bất kỳ xa và xb với xÎå* , a,bÎ N* thì a =b.
43
Sữa lỗi . . .
Định lý 3: Cho G = (N,å , P, S) là vĕn phạm đơn trị mạnh trong dạng chuẩn Greibach. Tập con 
K của å là tập khung của ngôn ngữ L(G), khi và chỉ khi với hai dạng câu trái bất kỳ xaa và zab với 
aÎK, x,z Îå* sao cho K(x) = K(z) và a, bÎ N* thì các phần chưa sẵn sàng a và b là tương đương.
Chứng minh: Điều kiện G trong GNF bảo đảm là trên mỗi bước của dẫn xuất trái sẽ sinh 
ra đúng một ký hiệu kết thúc còn phần chưa sẵn sàng của một dạng câu trái bất kỳ chỉ toàn các 
ký hiệu không kết thúc. Điều kiện “ G là vĕn phạm đơn trị mạnh” bảo đảm là với xâu bất kỳ 
w Î Pref(L(G)) sẽ tồn tại trong G duy nhất một dẫn xuất S Þ* wb. Ngoài ra ta có
 Sufw(L(G)) = L(b)
Từ định lý 2 và giả thiết tập K là tập khung ta có
 Sufxa(L(G)) = Sufza(L(G))
Nhưng ta cũng có các đẳng thức sau
 Sufxa(L(G)) = L(a)
 Sufza(L(G)) = L(b)
Từ đây suy ra L(a) = L(b), điều này nghĩa là a và b là tương đương trong G.
Ngược lại, nếu a tương đương với b khi đó suy ra
 L(a) = L(b) và
 L(a) = Sufxa(L(G)) , L(b) = Sufza(L(G))
Từ đây suy ra Sufxa(L) = Sufza(L). Điều này có nghĩa là ngôn ngữ L(G) có tính chất K-hậu 
tố, nên K là tập khung của ngôn ngữ L(G).
Định lý 2 chỉ ra rằng tập hậu tố của các từ của ngôn ngữ L chỉ phụ thuộc vào khung của các 
tiền tố của các từ đó. Đặc trưng của tập khung được chỉ ra trong định lý 2 là rất tiện lợi cho việc 
khảo sát các tập khung của ngôn ngữ được cho nhờ tính chất của các từ của ngôn ngữ.
Định nghĩa 13: Cho xa Î Pref(L) với aÎK, xÎå*, ta ký hiệu
Pref[K(x)a](L) = {za Î Pref(L); K(z) = K(x)}
Ta có hệ quả trực tiếp sau:
Hệ quả 4: Cho K là tập khung của ngôn ngữ L và xaÎ Pref(L) với aÎK, xÎå* khi đó ta có:
 Sufxa(L) = Sufza(L)
 với mọi zaÎ Pref[K(x)a](L).
Chứng minh: Hiển nhiên.
TÀI LIỆU THAM KHẢO
1. Freeman D. N. Error Correction in CORC, The Cornell Computing Language, Proc. AFIPS Fall 
Joint Computer Conference, 26, 15-34.
2. Morgan H.L. Spelling Correction in System Programs, Comm. ACM, 13:2, 56-58.
3. Chytil M.P., Demner J., Calmly on Panic mode. Preprint , November 1986.
4. Chytil M.P., Demner J., Panic mode without Panic. Automata, Languages and Programming. 14th 
International Colloquium. Karsruhe, Federal Republic of Germany, July 1987. Procceding.
5. Chytil M.P., Demner J., Platek M. , Effectivní metoda zotavení ze syntaktickych chyb. SOFSEM ’86. 
Sborník referatu.
6. Nguyen Xuan Dung. O rozhodnosti skeletalních mnozin. Kandidatská Disertacní Práce. MFF UK 
Praha 1988.
7. Nguyen Xuan Dung. On Decidability of Skeletal Sets. Technique Report of Prague University, No 
49, May 1989.