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

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.
Nội dung trích xuất từ tài liệu:
Giải pháp kiểm tra tính đúng của văn phạm phi ngữ cảnh90 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.vnTó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 formộ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 generatemớ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 accuracyphá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 ofcá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 proposednê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 thechí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 ofchư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 whethersả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-freekiể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 ofsinh 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ệnhlà 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ựnghay 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 ...