Sự tương ứng giữa các loại lớp và mức ngữ pháp trong hệ thống phân cấp Chomsky

Question

Câu hỏi của tôi là về các lớp loại ứng dụng và Monad một mặt, và ngữ cảnh ngữ cảnh tự do và ngữ cảnh nhạy cảm của hệ thống phân cấp Chomsky.

Tôi đã nghe nói rằng có sự tương ứng giữa các loại lớp và cấp độ ngữ pháp. Làm thế nào chính xác là thư từ này?

Đó là, tất cả các ngữ pháp không có ngữ cảnh được phân tích bằng cách sử dụng không có gì mạnh hơn các bộ phối hợp ứng dụng, và tất cả các ngữ pháp có thể được phân tích cú pháp bằng cách sử dụng không có gì mạnh hơn Nói cách khác, loại lớp Ứng dụng có tương ứng chính xác với ngữ pháp không có ngữ cảnh không?

Và cùng một câu hỏi, ngoại trừ 'không có bối cảnh' được thay thế bằng 'bối cảnh nhạy cảm' và Áp dụng bởi Monad.

---

Bounty làm rõ: làm kiểu lớp (es) tương ứng với ngữ pháp cấp độ? Ví dụ: có một tập hợp các loại lớp cung cấp tất cả các hoạt động cần thiết cho các ngôn ngữ thông thường của biểu thức và không có gì khác không?

Động lực cho câu hỏi là tôi đang làm việc trên một trình phân tích cú pháp và muốn xác định mức độ ngữ pháp mà việc triển khai của tôi dựa trên các bộ phối hợp mà tôi đã sử dụng. Điều này có thể không?

Answer 1

Tôi không nghĩ rằng bất kỳ ai đã hiển thị chính thức điều này. Lý do là không đơn lẻ hay đơn nguyên nào cũng có thể phân tích nhiều thứ. Thay vào đó, bạn cũng cần

1. Choice (MonadPlus, Alternative)
2. Recursion

mà nói, với (không xác định) sự lựa chọn và (tùy ý) đệ quy, phân tích cú pháp applicative về cơ bản chính xác phù hợp với giao diện cho BNF (và do đó có thể phân tích tất cả các CFL), trong khi monads có thể cung cấp các hoạt động nhạy cảm theo ngữ cảnh tùy ý.