Ngôn ngữ phi ngữ cảnh và Máy đẩy xuống

Ngữ pháp phi ngữ cảnh tạo ra các ngôn ngữ có cấu trúc lồng nhau, đệ quy, và máy đẩy xuống nhận dạng chính xác các ngôn ngữ này bằng cách bổ sung một bộ điều khiển hữu hạn với một ngăn xếp không giới hạn.

Definition

Một ngôn ngữ phi ngữ cảnh được tạo ra bởi một ngữ pháp mà các quy tắc của nó viết lại một ký hiệu không kết thúc duy nhất một cách độc lập với ngữ cảnh, và nó được nhận dạng bởi một máy đẩy xuống, một máy tự động hữu hạn được trang bị một ngăn xếp cung cấp bộ nhớ vào sau ra trước với độ sâu không giới hạn.

Scope

Chủ đề này bao gồm ngữ pháp phi ngữ cảnh và các dẫn xuất, cây phân tích cú pháp và tính mơ hồ, sự tương đương của ngữ pháp phi ngữ cảnh với máy đẩy xuống, các dạng chuẩn như dạng chuẩn Chomsky, bổ đề bơm cho ngôn ngữ phi ngữ cảnh, và các thuộc tính đóng và quyết định phân biệt lớp này với các ngôn ngữ chính quy.

Core questions

• Những loại mẫu lồng nhau hoặc đệ quy nào yêu cầu một ngăn xếp thay vì bộ nhớ hữu hạn?
• Tại sao ngữ pháp phi ngữ cảnh và máy đẩy xuống lại tương đương về sức mạnh?
• Khi nào một ngữ pháp mơ hồ, và tại sao tính mơ hồ lại quan trọng đối với việc phân tích cú pháp?
• Những vấn đề quyết định nào đối với ngôn ngữ phi ngữ cảnh có thể giải được, và những vấn đề nào không?

Key theories

Sự tương đương giữa ngữ pháp và máy tự động

Một ngôn ngữ là phi ngữ cảnh nếu và chỉ nếu nó được chấp nhận bởi một máy đẩy xuống nào đó, do đó quan điểm ngữ pháp sinh và quan điểm máy ngăn xếp mô tả cùng một lớp ngôn ngữ.

Dạng chuẩn Chomsky

Mọi ngữ pháp phi ngữ cảnh đều có thể được viết lại sao cho mỗi quy tắc tạo ra hoặc hai ký hiệu không kết thúc hoặc một ký hiệu kết thúc duy nhất, một dạng chuẩn làm nền tảng cho các thuật toán phân tích cú pháp và các chứng minh quy nạp về lớp này.

Bổ đề bơm cho ngôn ngữ phi ngữ cảnh

Mọi chuỗi đủ dài trong một ngôn ngữ phi ngữ cảnh đều có thể được chia sao cho hai phần của nó được bơm cùng nhau, một thuộc tính không đúng đối với các ngôn ngữ yêu cầu nhiều hơn bộ nhớ ngăn xếp và do đó chứng minh chúng không phải là phi ngữ cảnh.

Clinical relevance

Ngữ pháp phi ngữ cảnh xác định cú pháp của gần như mọi ngôn ngữ lập trình và nhiều định dạng dữ liệu, và các thuật toán phân tích cú pháp kiểu đẩy xuống biến các ngữ pháp này thành các bộ phân tích cú pháp là cốt lõi của các trình biên dịch và trình thông dịch, làm cho chủ đề này trở thành nền tảng lý thuyết của xử lý ngôn ngữ lập trình.

History

Chomsky đã giới thiệu ngữ pháp phi ngữ cảnh vào cuối những năm 1950 như một phần của hệ thống phân cấp của ông, và chúng được Backus và Naur sử dụng độc lập để định nghĩa cú pháp của ngôn ngữ lập trình ALGOL. Sự tương đương với máy đẩy xuống và lý thuyết cấu trúc của lớp này đã được phát triển trong suốt những năm 1960.

Key figures

• Noam Chomsky
• John Backus
• Seymour Ginsburg
• Sheila Greibach

Seminal works

• sipser2013
• hopcroft2006

Frequently asked questions

Tại sao việc phân tích cú pháp một ngôn ngữ lập trình cần một ngăn xếp?

Các chương trình chứa các cấu trúc lồng nhau như dấu ngoặc đơn, khối và lời gọi hàm có độ sâu khớp không giới hạn. Một ngăn xếp ghi lại mỗi cấu trúc chưa hoàn thành và loại bỏ nó khi đóng, đây chính xác là kỷ luật bộ nhớ mà một máy đẩy xuống cung cấp và một máy tự động hữu hạn thiếu.

Một ngữ pháp mơ hồ có nghĩa là gì?

Một ngữ pháp mơ hồ khi một chuỗi nào đó có nhiều hơn một cây phân tích cú pháp, nghĩa là nó có thể được dẫn xuất với các cấu trúc thực sự khác nhau. Tính mơ hồ không mong muốn đối với các ngôn ngữ lập trình vì nó làm cho ý nghĩa của mã không rõ ràng, vì vậy các nhà thiết kế ngôn ngữ tìm kiếm các ngữ pháp không mơ hồ hoặc thêm các quy tắc khử mơ hồ.