Giải pháp kiểm tra tính đÚng của văn phạm phi ngữ CẢNH



tải về 48.29 Kb.
Chuyển đổi dữ liệu21.12.2018
Kích48.29 Kb.

TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ, ĐẠI HỌC ĐÀ NẴNG - SỐ …………..

GIẢI PHÁP KIỂM TRA TÍNH ĐÚNG CỦA VĂN PHẠM PHI NGỮ CẢNH

a method to check thE accuracy of CONTEXT-FREE GRAMMAR



Nguyễn Thị Minh Hỷ1, Trần Hồ Thủy Tiên2

1Trường Đại Học Bách Khoa, Đại Học Đà Nẵng; Minhy81199@yahoo.com

2Trường Đại Học Bách Khoa, Đại học Đà Nẵng; thttien@dut.udn.vn

Tóm tắt - Ngôn ngữ có thể được biểu diễn bởi nhiều cách khác nhau, tuy nhiên đối với các ngôn ngữ có cầu trúc thì cần phải có một văn phạm đúng để biểu diễn. Một văn phạm phi ngữ cảnh đúng thì mới có thể sản sinh được ngôn ngữ. Bài báo này giới thiệu một phương pháp nhằm kiểm tra tính đúng của văn phạm phi ngữ cảnh bằng cách từng bước kiểm tra tính chính xác của các thành phần tạo nên văn phạm này. Phương pháp đề xuất bao gồm các công việc chính sau: kiểm tra cấu tạo của các ký hiệu kết thúc và ký hiệu chưa kết thúc, kiểm tra việc sử dụng các ký hiệu này để tạo ra các sản xuất, kiểm tra các sản xuất có vi phạm các điều kiện để tạo ra được ngôn ngữ hay không?. Giải pháp đề xuất có thể ứng dụng để kiểm tra một văn phạm phi ngữ cảnh trước khi hoạt động để sản sinh ra ngôn ngữ, phục vụ cho việc giảng dạy.

Từ khóa - văn phạm phi ngữ cảnh; vế trái; vế phải; sản xuất; ký hiệu chưa kết thúc; ký hiệu kết thúc

Abstract - Languages can be represented in many different ways, but structured languages usually use correct grammar for representation. Only an exact context - free grammar can generate a language. This paper introduces a method to check the accuracy of context-free grammar; particularly, checking the accuracy of components forming this grammar step by step. The proposed method consists of some major tasks such as checking the structure of terminals as well as non-terminals, verifying the use of these symbols to create the productions and checking up whether a production has met the conditions for constructing a language. The proposed method can be applied to check a context-free grammar before it produces a language for the purpose of teaching.

Key words - context - free grammar; the left side; the right side; production; non-terminal; terminal



1.Đặt vấn đề


Ngày nay, nhu cầu sử dụng công nghệ thông tin ngày càng nhiều, ở mọi lúc, mọi nơi, trên mọi lĩnh vực nên vấn đề tạo ra các loại ngôn ngữ lập trình mới là rất cần thiết.

Một chương trình là một dãy các câu lệnh, một câu lệnh là một dãy các từ, một từ được tạo ra từ các ký tự. Chương trình, câu lệnh, từ (hay còn gọi là xâu) được tạo ra theo một qui tắc nhất định, qui tắc đó chính là văn phạm. Hay nói cách khác văn phạm là cơ chế để sản sinh ra ngôn ngữ.

Chương trình trước khi được thực thi thì phải thông qua giai đoạn biên dịch để kiểm tra xem nó có bị các lỗi từ vựng hay lỗi cú pháp không. Để việc kiểm tra được chính xác thì đòi hỏi việc xây dựng văn phạm để tạo ra ngôn ngữ lập trình cũng phải chính xác.

Do đó việc đưa ra giải pháp để kiểm tra tính đúng của văn phạm phi ngữ cảnh là rất cần thiết.


2.Tính đúng của văn phạm phi ngữ cảnh


Văn phạm phi ngữ cảnh G [1][3][4] được xác định thông qua 4 thành phần: , , S, P

: tập ký hiệu kết thúc

: tập ký hiệu chưa kết thúc

S: ký hiệu bắt đầu, S



P: tập các sản xuất có dạng A với A;  ()*; A là vế trái;  là vế phải

Ví dụ: S0S | 1S | 0 | 1

Văn phạm phi ngữ cảnh trên sản sinh ra ngôn ngữ là một số nhị phân.

Một văn phạm phi ngữ cảnh đúng thì mới sản sinh ra được ngôn ngữ. văn phạm đó phải thỏa mãn những điều kiện sau:



  • Không sử dụng dấu cách trong ký hiệu.

  • Không ký hiệu kết thúc hoặc chưa kết thúc chưa được sử dụng trong sản xuất.

  • Không có sản xuất vế phải bằng vế trái.

  • Không có ký hiệu vô sinh:

Ký hiệu AÎD được gọi là ký hiệu vô sinh khi A≠+aS*

  • Không có ký hiệu không đạt đến được.

Ký hiệu AÎD được gọi là ký hiệu không đạt đến được khi S ≠+ aA

3.Giải pháp thực hiện


Giải pháp đề ra là xây dựng một lớp đối tượng để mô tả các thành phần của một văn phạm cũng như các hoạt động kiểm tra từng thành phần của nó.

Đầu vào: Văn phạm phi ngữ cảnh G(, , S, p).

Đầu ra: Văn phạm G đúng hay không đúng.

Thiết kế cấu trúc dữ liệu:

- Cấu trúc lưu trữ sản xuất

public struct clsanxuat{

//vế trái của sản xuất

public string vetrai;

//vế phải của sản xuất

public string[] vephai;

//vế phải của sản xuất

public string[] vephai;

//số ký hiệu ở vế phải

public int sokhvephai;

}

- Lớp văn phạm clvanpham



public class clvanpham{

//tập ký hiệu kết thúc

public static IList khkt;

//tập ký hiệu chưa kết thúc

public static IList khckt;

//ký hiệu bắt đầu

public static IList khckt ;

//tập ký hiệu chưa kết thúc

public static string khbd;

//số các sản xuất

public static int sosx;

//tập các sản xuất

public static clsanxuat[] sanxuat;

// Hàm kiểm tra tất cả các ký hiệu của văn phạm có sử dụng dấu cách không?

private bool kokyhieusudungdaucach(){

foreach(string obj in clvanpham.khkt)

f(obj.indexof(“ ”)!=-1) return false;

foreach(string obj in clvanpham.khckt)

if(obj.indexof(“ ”)!=-1) return false;

return true;

}

//Hàm kiểm tra ký hiệu kết thúc a đã có?

private static bool dasudungkhkt(string a) {

foreach (clsanxuat obj in clvanpham.sanxuat)

if (obj.vephai.Contains(a)) return true;

return false;

}

//Hàm xác định tập ký hiệu kết thúc chưa sử dụng



private static IList tapkhktchuasudung(){

IList t = new List();

foreach (string obj in clvanpham.khkt)

if (!dasudungkhkt(obj)) t.Add(obj);

return t;

}

//Hàm kiểm tra ký hiệu chưa kết thúc A đã được sử dụng chưa?



private static bool dasudungkhckt(string A){

foreach (clsanxuat obj in clvanpham.sanxuat)

if (obj.vetrai == A) return true;

if (dasudungkhkt(A)) return true;

return false;

}

//Hàm xác định tập ký hiệu chưa kết thúc chưa sử dụng



private static IList tapkhcktchuasudung() {

IList t = new List();

foreach (string obj in clvanpham.khckt)

if (!dasudungkhckt(obj)) t.Add(obj);

return t;

}

//Hàm kiểm tra văn phạm có sản xuất mà vế trái bằng vế phải hay không?



private bool kosxvetraibangvephai(){

foreach(clsanxuat obj in clvanpham.sanxuat)

if((obj.vetrai.trim()==obj.vephai[0].trim())

&&(obj.vephai.count==1)) return false;

return true;

}

//Hàm kiểm tra ký hiệu chưa kết thúc A có phải là ký hiệu không vô sinh không?

private static bool kovosinh(string A){

bool ok = false;

if((A=="epsilon")||

(clvanpham.khkt.Contains(A)))

return true;

for (int i = 0; i < clvanpham.sosx; i++)

if (clvanpham.sanxuat[i].vetrai == A){

ok = true; break;

}

if (!ok) return false;



for (int i = 0; i < clvanpham.sosx; i++)

if((clvanpham.sanxuat[i].vetrai==A)&&

(!clvanpham.sanxuat[i].vephai.Contains(A))){

ok = true;

for(int j=0;

j

j++)

ok=ok&&


kovosinh(

clvanpham.sanxuat[i].vephai[j]);

if (ok) return true;

}

return false;



}

//Hàm xác định tập ký hiệu vô sinh

private static IList tapkhvosinh(){

IList t = new List();

foreach (string obj in clvanpham.khckt)

if(!clvanpham.kovosinh(obj)) t.Add(obj);

return t;

}

//Hàm xác định tập ký hiệu đạt đến được



private static IList tapdatdenduoc(){

IList tddduoc = new List();

tddduoc.Add(clvanpham.khbd);

for(int k = 0; k < tddduoc.Count; k++)

for(int i = 0; i < clvanpham.sosx; i++)

if(tddduoc[k]==clvanpham.sanxuat[i].vetrai)

foreach(string objvp in

clvanpham.sanxuat[i].vephai)

if(!tddduoc.Contains(objvp)&& (clvanpham.khckt.Contains(objvp)))

tddduoc.Add(objvp);

return tddduoc;

}

//Hàm xác định tập ký hiệu không đạt đến được



private static IList tapkodatdenduoc(){

IList t = new List();

IList t1 = new List();

t1 = tapdatdenduoc();

foreach (string obj in clvanpham.khckt)

if (!t1.Contains(obj)) t.Add(obj);

return t;

}

//Hàm kiểm tra tính đúng của văn phạm phi ngữ cảnh



public static bool kiemtratinhdung(){

if (clvanpham.khkt.Count == 0) return false;

if (clvanpham.khckt.Count == 0) return false;

if (clvanpham.khbd == null) return false;

if (clvanpham.sosx == 0) return false;

if(!kokyhieusudungdaucach()) return false;

//kiểm tra tất cả các ký hiệu kết thúc đã được sử dụng?

IList t = new List();

t = tapkhktchuasudung();

if (t.Count != 0) return false;

//kiểm tra tất cả các ký hiệu chưa kết thúc đã được sử dụng?

t = tapkhcktchuasudung();

if (t.Count != 0) return false;

//kiểm tra vế trái = vế phải sản xuất?

if(!kosxvetraibangvephai()) return false;

//kiểm tra ký hiệu vô sinh?

t = clvanpham.tapkhvosinh();

if (t.Count != 0) return false;

//kiểm tra ký hiệu không đạt đến được?

t = clvanpham.tapkodatdenduoc();

if (t.Count != 0) return false;

return true;

}

}

Thuật toán:



  • Nhập văn phạm phi ngữ cảnh G

  • Nếu (G. kiemtratinhdung()==true) thì

văn phạm G đúng

  • Ngược lại

Văn phạm G không đúng

4.Phát triển ứng dụng


Chương trình ứng dụng được xây dựng bằng phần mềm Microsoft Visual C Sharp 2010 [2]. Chúng ta có thể áp dụng chương trình ứng dụng này để kiểm tra các văn phạm phi ngữ cảnh.

Nhập các thành phần của văn phạm phi ngữ cảnh G1 có A là ký hiệu không đạt đến được sau:

S0S | 1S | 0 | 1

A 0 | 1

Bằng form sau:





Hình 1: Form nhập văn phạm G1

Sau khi chọn chức năng biên dịch ta được cửa sổ thông báo kết quả như sau:





Hình 2: Cửa sổ thông báo kết quả của G1

Nhập các thành phần của văn phạm phi ngữ cảnh G2 có A là ký hiệu vô sinh sau:

SA


S0S | 1S | 0 | 1

A0A


Bằng form sau:



Hình 3: Form nhập văn phạm G2

Sau khi chọn chức năng biên dịch ta được cửa sổ thông báo kết quả như sau:





Hình 4: Cửa sổ thông báo kết quả của G2

Nhập các thành phần của văn phạm phi ngữ cảnh đúng G3 sau:

S0S | 1S | 0 | 1

Bằng form sau:



Hình 5: Form nhập văn phạm phi ngữ cảnh G3

Sau khi chọn chức năng biên dịch ta được cửa sổ thông báo kết quả như sau:





Hình 6: Cửa sổ thông báo kết quả của G3

5.Kết luận


Bài báo đã trình bày một giải pháp mới để kiểm tra tính đúng của văn phạm phi ngữ cảnh thông qua việc kiểm tra các thành phần tạo nên nó và đã xây dựng thành công chương trình ứng dụng có thể được sử dụng trong giảng dạy và nghiên cứu khoa học. Làm tiền đề cho việc ứng dụng văn phạm phi ngữ cảnh để tạo ra các ngôn ngữ lập trình.

Tài liệu tham khảo

5.1.1.a.1.1.1.1.1.J. Hopscoft, R. Motwani, J. D. Ullman, Introduction to Automata Theory, Languages and Computation, Addsion–Wesley, 2001.

5.1.1.a.1.1.1.1.2.Allen Jones, Microsoft Visual C Sharp, Microsoft Press Deutschland, 2010

5.1.1.a.1.1.1.1.3.Alfred V.Aho, Ravi Sethi, Jeffrey D.Ullman, Compiler Principles Techniques and Tools, Bell Telephone Laboratories Incorporated, 1986

5.1.1.a.1.1.1.1.4.Nguyễn Thanh Bình, Giáo trình Ngôn ngữ hình thức, nhà xuất bản Thông tin và Truyền thông, 2012


(BBT nhận bài: 29/06/2016, phản biện xong: 05/07/2016)

Thông tin về tác giả

Hinh tác giả 1

Nguyễn Thị Minh Hỷ

- Năm Tốt nghiêp Thạc sỹ: 2003 ngành Công nghệ thông tin

- Cơ quan: Trường Đại học Bách Khoa, Đại học Đà Nẵng, Việt nam

- Lĩnh vực nghiên cứu: Công nghệ thông tin;

- Điện thoại: 0989600305 – 0913760710

- Email: Minhy81199@yahoo.com



Hinh tác giả2

Trần Hồ Thủy Tiên

- Năm Tốt nghiêp Thạc sỹ: 2004 ngành Công nghệ thông tin

- Cơ quan: Trường Đại học Bách Khoa - Đại học Đà Nẵng, Việt nam

- Lĩnh vực nghiên cứu:Công nghệ thông tin;

- Điện thoại: 0983461008

- Email: thttien@dut.udn.vn







Поделитесь с Вашими друзьями:


Cơ sở dữ liệu được bảo vệ bởi bản quyền ©tieuluan.info 2019
được sử dụng cho việc quản lý

    Quê hương