Đây có phải là ngữ pháp mơ hồ không? Tôi nên giải quyết nó như thế nào?

Question

Để làm nổi bật điều này, kiến ​​thức của tôi về loại nội dung này là rất nhỏ.

Dù sao thì, tôi đã phát triển ngữ pháp ngữ cảnh để mô tả cấu trúc của các biểu thức bất hợp pháp để tôi có thể tự dạy thuật toán phân tích CYK hoạt động như thế nào. Tôi hiểu làm thế nào một cấu trúc như vậy có thể làm việc chỉ với các biểu thức đại số infix, nhưng tôi không thể hiểu làm thế nào để phát triển một ngữ pháp có thể xử lý cả hai định nghĩa đơn nhất và nhị phân của toán tử "-".

Để tham khảo, đây là ngữ pháp tôi đã viết (trong đó S là biểu tượng start) trong CNF:

S -> x
A -> OS
S -> LB
B -> SR
S -> KS
O -> +
O -> -
O -> *
O ->/
O ->^
K -> -
L -> (
R ->)

Vấn đề là như thế nào CYK phân tích thuật toán có thể biết trước thời hạn hay không để quyết định giữa S -> KS và A -> OS khi nó gặp toán tử "-"? Ngữ pháp này có miễn phí nữa không? Và quan trọng nhất, vì ngôn ngữ lập trình có thể xử lý ngôn ngữ với cả dấu nhị phân và dấu trừ đơn, nên tôi phân tích cú pháp này như thế nào?

Answer 1

Điều này có vẻ như một vấn đề liên quan đến automata hữu hạn nhà nước và tôi không nhớ tất cả mọi thứ từ khóa học của tôi, nhưng tôi đã viết một phân tích cú pháp CYK trong OCaml , vì vậy tôi sẽ đi trước và chụp :)

Nếu bạn đang cố gắng để phân tích một biểu thức như 3- -4 ví dụ, bạn sẽ có quy tắc S -> K S bạn tiêu thụ -4 và sau đó quy tắc A -> O S của bạn sẽ hấp thụ - -4. Điều này cuối cùng sẽ hoạt động theo quy tắc sản xuất hàng đầu nhất của S. Bạn nên cẩn thận với ngữ pháp bạn đang sử dụng, vì quy tắc sản xuất A mà bạn liệt kê không thể đạt được từ S và bạn có thể có quy tắc S -> S O S của một số loại.

Cách các thuật toán phân tích cú pháp CYK hoạt động là thông qua phản hồi ngược, không phải thông qua "biết trước" mà bạn đã đề cập trong câu hỏi của mình. Thuật toán CYK của bạn nên phân tích cú pháp -4 là quy tắc S -> K S và sau đó nó sẽ cố gắng hấp thụ lại quy tắc - thứ hai với quy tắc S -> K S vì quy tắc sản xuất này cho phép chuỗi dài một cách tùy ý -. Nhưng khi thuật toán của bạn nhận ra rằng nó bị mắc kẹt với phân tích cú pháp trung gian 3 S, nó nhận ra rằng nó không có biểu tượng sản xuất mà nó có thể sử dụng để phân tích cú pháp này. Khi nó nhận ra rằng điều này không còn phân tích được nữa, nó sẽ quay trở lại và thay vào đó, hãy thử phân tích cú pháp - làm quy tắc S -> O S và tiếp tục theo cách vui vẻ.

Điều này có nghĩa là ngữ pháp của bạn vẫn không có bối cảnh vì ngữ pháp ngữ cảnh có nghĩa là bạn có các đầu cuối ở phía bên trái của quy tắc sản xuất, vì vậy bạn rất tôn trọng. HTH!

Answer 2

Ngữ pháp không rõ ràng và trình phân tích cú pháp không thể quyết định trường hợp cần thực hiện.

Bạn có lẽ nên sử dụng một ngữ pháp như sau:

S -> EXPR 
EXPR -> (EXPR) 
EXPR -> - EXPR 
EXPR -> EXPR + EXPR 
EXPR -> EXPR - EXPR 
// etc... 

Answer 3

Ngữ pháp dựa trên biểu thức đại số khá khó phân biệt. Dưới đây là một số ví dụ về các vấn đề cần được giải quyết:

a + b + c tự nhiên tạo ra hai cây phân tích cú pháp. Để giải quyết vấn đề này, bạn cần phải giải quyết sự mơ hồ về tính kết hợp của +. Bạn có thể muốn cho phép một chiến lược phân tích cú pháp từ trái sang phải đảm bảo điều này cho bạn, nhưng cẩn thận: lũy thừa có thể liên kết từ phải sang trái.

a + b * c tự nhiên tạo hai cây phân tích cú pháp. Để khắc phục vấn đề này, bạn cần phải đối phó với quyền ưu tiên của toán tử.

phép nhân tiềm ẩn (a + bc), nếu được phép, tạo ra tất cả các loại ác mộng, chủ yếu là thông báo.

trừ thống nhất là vấn đề, như bạn đề cập đến.

Nếu chúng ta muốn giải quyết những vấn đề này, nhưng vẫn có ngữ pháp phân tích nhanh chuyên về đại số, một cách tiếp cận là có nhiều "mức" khác nhau của EXPR, một cho mỗi mức ràng buộc theo mức ưu tiên. Ví dụ,

TERM -> (S) 
EXPO -> TERM^EXPO 
PROD -> PROD * EXPO 
PROD -> PROD/EXPO 
PROD -> -PROD 
SUM -> SUM + PROD 
SUM -> SUM - PROD 
S -> SUM 

Điều này đòi hỏi bạn cũng cho phép "xúc tiến" của các loại: SUM -> PROD, PROD -> EXP, EXP -> HẠN, vv, do đó điều này có thể chấm dứt.

Hy vọng điều này sẽ hữu ích!