Tài liệu Nghiên cứu ngôn ngữ hình thức, văn phạm phi ngữ cảnh và automata đẩy xuống

Mô tả:

LỜI CẢM ƠN Trước hết, em xin chân thành cảm ơn các thầy cô giáo trong khoa Công nghệ thông tin Trường ĐH Kỹ thuật – Hậu cần CAND đã trang bị những kiến thức cơ bản, cần thiết và quý báu để em thực hiện chuyên đề của mình. Đặc biệt, em xin bày tỏ lòng kính trọng và biết ơn sâu sắc tới thầy Nghiêm Văn Hưng, giáo viên giảng dạy, và thầy Cao Xuân Trường, người đã tận tình hướng dẫn, chỉ bảo và tạo mọi điều kiện thuận lợi giúp em trong quá trình thực hiện chuyên đề. Mặc dù đã rất cố gắng cùng nhận được sự giúp đỡ tận tâm của thầy giáo hướng dẫn, xong do trình độ còn hạn chế, tài liệu chưa được phong phú, và nội dung này khá khó đối với em nên không tránh khỏi những thiếu sót trong quá trình tiếp nhận kiến thức. Em rất mong nhận được sự quan tâm giúp đỡ, chỉ dẫn của thầy cô và sự góp ý từ bạn bè để trong thời gian tới em có thể tiếp tục tìm hiểu và xây dựng chuyên đề một cách hoàn thiện nhất. Em xin chân thành cảm ơn!   GIỚI THIỆU TỔNG QUAN VỀ CHUYÊN ĐỀ Tên chuyên đề: Nghiên cứu Ngôn ngữ hình thức, Văn phạm phi ngữ cảnh và Automata đẩy xuống Sinh viên thực hiện: Hoàng Văn Thao Lớp: B3-D2B Giáo viên hướng dẫn: Thiếu úy Cao Xuân Trường Tính cấp thiết của chuyên đề: Lý thuyết ngôn ngữ hình thức và Automata đóng một vai trò rất quan trọng trong các cơ sở toán học của tin học. Ngôn ngữ hình thức được sử dụng trong việc xây dựng các ngôn ngữ lập trình, lý thuyết về các chương trình dịch. Các ngôn ngữ hình thức tạo thành một công cụ mô tả đối với các mô hình tính toán cả cho dạng thông tin vào - ra lẫn kiểu thao tác. Lý thuyết ngôn ngữ hình thức, chính vì thực chất của nó là một lĩnh vực khoa học liên ngành; nhu cầu mô tả hình thức văn phạm được phát sinh trong nhiều ngành khoa học khác nhau từ ngôn ngữ học đến sinh vật học. Do đó những khía cạnh thích hợp của lý thuyết ngôn ngữ hình thức sẽ có tầm quan trọng quyết định trong các giáo trình về Lý thuyết ngôn ngữ hình thức và Automata. Lĩnh vực mà lý thuyết ngôn ngữ hình thức nghiên cứu là những mẫu hình (pattern) có cấu trúc bên trong ngôn ngữ hình thức, và đó là những khía cạnh hoàn toàn mang tính chất có cú pháp. Ngôn ngữ hình thức không còn đơn giản chỉ là để định nghĩa ngôn ngữ tự nhiên, mà nó vượt ra ngoài khỏi phạm vi đó và nó cũng là một cách để thể hiện được những quy tắc có cú pháp của ngôn ngữ tự nhiên. Mục tiêu của chuyên đề: Nghiên cứu tổng quan về văn phạm hình thức và các Automata, là những công cụ sinh ngôn ngữ, đồng thời đề cập đến các tính chất của ngôn ngữ chính quy, ngôn ngữ phi ngữ cảnh. Ngoài ra, cũng giới thiệu sơ lược về Trình biên dịch, một phần quan trọng của học phần Chương trình dịch gắn bó chặt chẽ với Lý thuyết ngôn ngữ hình thức và Automata, trong đó Văn phạm phi ngữ cảnh là cơ sở lý thuyết để xây dựng Bộ phân tích cú pháp, là thành phần quan trọng nhất trong một Trình biên dịch. Đối tượng nghiên cứu: Ngôn ngữ hình thức và lý thuyết Automata. Phạm vi nghiên cứu:  Ngôn ngữ phi ngữ cảnh cùng hai phương tiện để xác định chúng là Văn phạm phi ngữ cảnh;  Automata đẩy xuống.   Phương pháp nghiên cứu:  Phương pháp nghiên cứu tài liệu;  Phương pháp chuyên gia;  Phương pháp thực nghiệm. Nội dung nghiên cứu:  Lý thuyết về Ngôn ngữ hình thức, Văn phạm phi ngữ cảnh và Automata đẩy xuống;  Các tính chất của Ngôn ngữ hình thức, Văn phạm phi ngữ cảnh và Automata đẩy xuống;  Ứng dụng của Ngôn ngữ hình thức và Automata với trình biên dịch. Chuyên đề gồm 5 chương: Chương I: Nhập môn về văn phạm và ngôn ngữ hình thức 1.1 Khái niệm ngôn ngữ 1.2 Văn phạm và ngôn ngữ sinh bởi văn phạm 1.3 Một số tính chất của ngôn ngữ Chương II: Văn phạm phi ngữ cảnh 2.1 Suy dẫn phi ngữ cảnh 2.2 Biến đổi các Văn phạm phi ngữ cảnh Chương III: Automata đẩy xuống 3.1 Automata đẩy xuống không tiền định 3.2 Automata đẩy xuống và Văn phạm phi ngữ cảnh Chương IV: Tổng quan về trình biên dịch 4.1 Ngôn ngữ lập trình 4.2 Trình biên dịch 4.3 Ứng dụng của Văn phạm phi ngữ cảnh và Automata đẩy xuống với trình biên dịch Chương V: Demo một bài toán 5.1 Bài toán và cơ sở lý thuyết 5.2 Demo ví dụ về sự tương đương giữa BTCQ và NFAε Sản phẩm:  Báo cáo chuyên đề;  Chương trình demo cơ bản.   MỤC LỤC LỜINÓIĐẦU 1 CHƯƠNG 1. NHẬP MÔN VỀ VĂN PHẠM VÀ NGÔN NGỮ HÌNH THỨC 3 1.1. Khái niệm ngôn ngữ 3 1.1.1. Các khái niệm cơ bản 3 1.1.2. Các phép toán trên các từ 4 1.1.3. Cácphéptoántrênngônngữ. 6 1.2. Văn phạm và ngôn ngữ sinh bởi văn phạm 9 1.2.1. Định nghĩavănphạm 10 1.2.2. Ngôn ngữ sinh bởivăn phạm 11 1.2.3. Phân loạivăn phạm theo Chomsky 12 1.3. Một số tính chất của ngôn ngữ 14 1.3.1. Một số tính chất của văn phạm và dẫn xuất 14 1.3.2. Tínhđóng của lớpngôn ngữ sinhbởi văn phạm 15 CHƯƠNG 2. VĂN PHẠM PHI NGỮ CẢNH 17 2.1. Suy dẫn phi ngữ cảnh 17 2.1.1. Các thí dụ về văn phạm phi ngữ cảnh 17 2.1.2. Tính chất cơ bản (phân rã các suy dẫn phi ngữ cảnh) 19 2.1.3. Cây suy dẫn 20 2.1.4. Suy dẫn trái, suy dẫn phải và tính nhập nhằng 23 2.2. Biến đổi các văn phạm phi ngữ cảnh 26 2.2.1. Loại bỏ các ký hiệu vô ích 27 2.2.2. Loại bỏ các ε-sản xuất 31 2.2.3. Loại bỏ các sản xuất đơn 33 2.2.4. Dạng chuẩn Chomsky 35 CHƯƠNG 3. Ô TÔ MÁT ĐẨY XUỐNG 37 3.1. Ô tô mát đẩy xuống không tiền định 37 3.1.1. Khái niệm và định nghĩa 37 3.1.2. Các tính chất cơ bản của ô tô mát đẩy xuống 38 3.1.3. Tương đương giữa hai loại ô tô mát đẩy xuống thừa nhận theo stack rỗng và thừa nhận theo trạng thái cuối 41 3.2. Tương đương giữa ô tô mát đẩy xuống và văn phạm phi ngữ cảnh 44 3.2.1. Từ văn phạm phi ngữ cảnh đến ô tô mát đẩy xuống 44 3.2.2. Từ ô tô mát đẩy xuống đến văn phạm phi ngữ cảnh 46 CHƯƠNG 4. TỔNG QUANVỀTRÌNHBIÊNDỊCH 49 4.1. Ngôn ngữ lập trình 49 4.1.1. Mởđầu 49 4.1.2. Phânloại 49 4.1.3. Cúpháp và ngữ nghĩa 50 4.2. Trình biên dịch 51 4.2.1. Định nghĩa 51 4.2.2. Cácphầncủatrìnhbiêndịch 52 4.3. Ứng dụng của ngôn ngữ hình thức và ôtômat với trình biên dịch 57 4.3.1. Bộtiềnxửlý 58 4.3.2. Trìnhbiêndịchhợpngữ 59 4.3.3. Trìnhbiêndịchhợpngữhaichuyến(twopassassembler) 59 4.3.4. Bộcấtliênkếtsoạnthảo(loader/linkeditor): 61 CHƯƠNG 5. DEMO MỘT BÀI TOÁN 63 5.1. Cơ sở lý thuyết 63 5.1.1. Bài toán chuyển từ BTCQ sang NFAε 63 5.1.2. Phương hướng giải quyết 63 5.2. Demo ví dụ về sự tương đương giữa BTCQ và NFAε 65 5.2.1. Giao diện ban đầu 65 5.2.2. Giao diện kết quả 66 KẾT LUẬN 69 TÀI LIỆU THAM KHẢO 70