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

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:4

Thêm vào BST

Báo xấu

16
lượt xem 1
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài viết Giải pháp kiểm tra tính đúng của văn phạm phi ngữ cảnh 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.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Giải pháp kiểm tra tính đúng của văn phạm phi ngữ cảnh

90 Nguyễn Thị Minh Hỷ, Trần Hồ Thủy Tiên 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ỷ, Trần Hồ Thủy Tiên Trường Đại học Bách khoa, Đại học Đà Nẵng Minhy81199@yahoo.com; 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 Abstract - Languages can be represented in many different ways, nhau, tuy nhiên đối với các ngôn ngữ có cầu trúc thì cần phải có but structured languages usually use correct grammar for một văn phạm đúng để biểu diễn. Một văn phạm phi ngữ cảnh đúng representation. Only an exact context - free grammar can generate mới có thể sản sinh được ngôn ngữ. Bài báo giới thiệu một phương a language. This paper introduces a method to check the accuracy pháp nhằm kiểm tra tính đúng của văn phạm phi ngữ cảnh bằng of context-free grammar; particularly, checking the accuracy of 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 components forming this grammar step by step. The proposed nên văn phạm này. Phương pháp đề xuất bao gồm các công việc method consists of some major tasks such as checking the 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 structure of terminals as well as non-terminals, verifying the use of 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 these symbols to create the productions and checking up whether 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 a production has met the conditions for constructing a language. được ngôn ngữ hay không? Giải pháp đề xuất có thể ứng dụng để The proposed method can be applied to check a context-free kiểm tra một văn phạm phi ngữ cảnh trước khi hoạt động để sản grammar before it produces a language for the purpose of sinh ra ngôn ngữ, phục vụ cho việc giảng dạy. teaching. Từ khóa - văn phạm phi ngữ cảnh; vế trái; vế phải; sản xuất; ký Key words - context - free grammar; the left side; the right side; hiệu chưa kết thúc; ký hiệu kết thúc. production; non-terminal; terminal. 1. Đặt vấn đề - Không ký hiệu kết thúc hoặc chưa kết thúc chưa Ngày nay, nhu cầu sử dụng công nghệ thông tin ngày được sử dụng trong sản xuất. càng nhiều, ở mọi lúc, mọi nơi, trên mọi lĩnh vực nên vấn - Không có sản xuất vế phải bằng vế trái. đề tạo ra các loại ngôn ngữ lập trình mới là rất cần thiết. - Không có ký hiệu vô sinh: 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 Ký hiệu A được gọi là ký hiệu vô sinh khi * trình, câu lệnh, từ (hay còn gọi là xâu) được tạo ra theo một A≠+ qui tắc nhất định, qui tắc đó chính là văn phạm. Hay nói - Không có ký hiệu không đạt đến được. cách khác, văn phạm là cơ chế để sản sinh ra ngôn ngữ. Ký hiệu A được gọi là ký hiệu không đạt đến được Chương trình trước khi được thực thi thì phải thông qua khi S ≠+ A 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, 3. Giải pháp thực hiện đòi hỏi việc xây dựng văn phạm để tạo ra ngôn ngữ lập Giải pháp đề ra là xây dựng một lớp đối tượng để mô tả trình cũng phải chính xác. các thành phần của một văn phạm cũng như các hoạt động Do đó việc đưa ra giải pháp để kiểm tra tính đúng của kiểm tra từng thành phần của nó. văn phạm phi ngữ cảnh là rất cần thiết. Đầu vào: Văn phạm phi ngữ cảnh G(, , S, p). 2. Tính đúng của văn phạm phi ngữ cảnh Đầu ra: Văn phạm G đúng hay không đúng. Văn phạm phi ngữ cảnh G [1], [3], [4] được xác định Thiết kế cấu trúc dữ liệu: thông qua 4 thành phần: , , S, P. - Cấu trúc lưu trữ sản xuất : tập ký hiệu kết thúc public struct clsanxuat{ : tập ký hiệu chưa kết thúc //vế trái của sản xuất S: ký hiệu bắt đầu, S public string vetrai; P: tập các sản xuất có dạng A với A;  //vế phải của sản xuất ()*; A là vế trái;  là vế phải public string[] vephai; Ví dụ: S0S | 1S | 0 | 1 //vế phải của sản xuất Văn phạm phi ngữ cảnh trên sản sinh ra ngôn ngữ là public string[] vephai; một số nhị phân. //số ký hiệu ở vế phải Một văn phạm phi ngữ cảnh đúng thì mới sản sinh ra public int sokhvephai; được ngôn ngữ. Văn phạm đó phải thỏa mãn những điều } kiện sau: - Lớp văn phạm clvanpham - Không sử dụng dấu cách trong ký hiệu.
ISSN 1859-1531 - TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ ĐẠI HỌC ĐÀ NẴNG, SỐ 7(104).2016 91 public class clvanpham{ return t; //tập ký hiệu kết thúc } public static IList khkt; //Hàm kiểm tra văn phạm có sản xuất mà vế trái bằng //tập ký hiệu chưa kết thúc vế phải hay không? public static IList khckt; private bool kosxvetraibangvephai(){ //ký hiệu bắt đầu foreach(clsanxuat obj in clvanpham.sanxuat) public static IList khckt ; if((obj.vetrai.trim()==obj.vephai[0].trim()) //tập ký hiệu chưa kết thúc &&(obj.vephai.count==1)) return false; public static string khbd; //số các sản xuất return true; } public static int sosx; //tập các sản xuất //Hàm kiểm tra ký hiệu chưa kết thúc A có phải là ký public static clsanxuat[] sanxuat; hiệu không vô sinh không? // Hàm kiểm tra tất cả các ký hiệu của văn phạm có sử private static bool kovosinh(string A){ dụng dấu cách không? bool ok = false; if((A=="epsilon")|| private bool kokyhieusudungdaucach(){ (clvanpham.khkt.Contains(A))) foreach(string obj in clvanpham.khkt) return true; f(obj.indexof(“ ”)!=-1) return false; for (int i = 0; i < clvanpham.sosx; i++) foreach(string obj in clvanpham.khckt) if (clvanpham.sanxuat[i].vetrai == A){ if(obj.indexof(“ ”)!=-1) return false; ok = true; break; } return true; if (!ok) return false; } for (int i = 0; i < clvanpham.sosx; i++) //Hàm kiểm tra ký hiệu kết thúc a đã có? if((clvanpham.sanxuat[i].vetrai==A)&& private static bool dasudungkhkt(string a) { (!clvanpham.sanxuat[i].vephai.Contains(A))){ foreach (clsanxuat obj in clvanpham.sanxuat) ok = true; if (obj.vephai.Contains(a)) return true; for(int j=0; return false; j
92 Nguyễn Thị Minh Hỷ, Trần Hồ Thủy Tiên for(int i = 0; i < clvanpham.sosx; i++) Văn phạm G không đúng if(tddduoc[k]==clvanpham.sanxuat[i].vetrai) 4. Phát triển ứng dụng foreach(string objvp in Chương trình ứng dụng được xây dựng bằng phần mềm clvanpham.sanxuat[i].vephai) Microsoft Visual C Sharp 2010 [2]. Chúng ta có thể áp if(!tddduoc.Contains(objvp)&& dụng chương trình ứng dụng này để kiểm tra các văn phạm (clvanpham.khckt.Contains(objvp))) phi ngữ cảnh. tddduoc.Add(objvp); Nhập các thành phần của văn phạm phi ngữ cảnh G1 có return tddduoc; A là ký hiệu không đạt đến được sau: } S0S | 1S | 0 | 1 //Hàm xác định tập ký hiệu không đạt đến được A 0 | 1 private static IList tapkodatdenduoc(){ Bằng form sau: 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; Hình 1. Form nhập văn phạm G1 if (clvanpham.khckt.Count == 0) return false; Sau khi chọn chức năng biên dịch ta được cửa sổ thông if (clvanpham.khbd == null) return false; báo kết quả như sau: 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 Hình 2. Cửa sổ thông báo kết quả của G1 sử dụng? Nhập các thành phần của văn phạm phi ngữ cảnh G2 có t = tapkhcktchuasudung(); A là ký hiệu vô sinh sau: if (t.Count != 0) return false; SA //kiểm tra vế trái = vế phải sản xuất? S0S | 1S | 0 | 1 if(!kosxvetraibangvephai()) return false; A0A //kiểm tra ký hiệu vô sinh? Bằng form sau: 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 Hình 3. Form nhập văn phạm G2 - Nếu (G. kiemtratinhdung()==true) thì văn phạm G đúng Sau khi chọn chức năng biên dịch ta được cửa sổ thông - Ngược lại báo kết quả như sau:
ISSN 1859-1531 - TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ ĐẠI HỌC ĐÀ NẴNG, SỐ 7(104).2016 93 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 Hình 6. Cửa sổ thông báo kết quả của G3 G3 sau: S0S | 1S | 0 | 1 5. Kết luận Bằng form sau: 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 [1] J. Hopscoft, R. Motwani, J. D. Ullman, Introduction to Automata Theory, Languages and Computation, Addsion–Wesley, 2001. [2] Allen Jones, Microsoft Visual C Sharp, Microsoft Press Deutschland, 2010 [3] Alfred V.Aho, Ravi Sethi, Jeffrey D.Ullman, Compiler Principles Techniques and Tools, Bell Telephone Laboratories Incorporated, Hình 5. Form nhập văn phạm phi ngữ cảnh G3 1986 Sau khi chọn chức năng biên dịch ta được cửa sổ thông [4] Nguyễn Thanh Bình, Giáo trình Ngôn ngữ hình thức, NXB. 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)