Sự cố giải quyết xung đột giảm-giảm trong ngữ pháp của tôi

Question

Tôi đang cố viết một trình phân tích cú pháp nhỏ với Irony. Thật không may tôi nhận được một "xung đột giảm thiểu". Grammars không phải là điểm mạnh của tôi, và tôi chỉ cần thực hiện điều này một chút. Đây là ngữ pháp bị giảm gây lỗi:

ExpressionTerm := "asd" 
LogicalExpression := 
    ExpressionTerm | 
    LogicalExpression "AND" LogicalExpression | 
    LogicalExpression "OR" LogicalExpression 

"xung đột giảm thiểu" có nghĩa là gì và làm cách nào để giải quyết? Tôi thu thập rằng nó có nghĩa là ngữ pháp của tôi là mơ hồ, nhưng tôi không thể xoay logic của tôi đủ để xem như thế nào.

Đã thêm: Để làm rõ - "asd" chỉ đơn giản là chuỗi chữ "asd". Vì vậy, tôi hy vọng rằng các từ ngữ sau đây được phân tích bằng ngữ pháp này:

asd 
asd AND asd 
asd AND asd OR asd 
asd OR asd AND asd OR asd 

Added 2: Quên nói, thư mục gốc của ngữ pháp là LogicalExpression.

Đã thêm 3: Ahh, tôi hiểu rồi! Sự mơ hồ là bởi vì một biểu thức như

asd AND asd OR asd 

có thể được hiểu theo hai cách khác nhau:

(asd AND asd) OR asd 
asd AND (asd OR asd) 

Nhưng làm thế nào tôi có thể giải quyết này? OK, tôi có thể đặt một AND hoặc OR để mạnh hơn cái kia (dù tôi đã tham gia). Nhưng bây giờ tôi thấy rằng lỗi xuất hiện ngay cả khi chỉ có một toán tử. Nói cách khác, điều này cũng tạo ra những lỗi tương tự:

LogicalExpression := "asd" | LogicalExpression "OR" LogicalExpression 

Trong trường hợp này, tôi muốn điều này:

asd OR asd OR asd 

để được phân tích như sau:

(asd OR asd) OR asd 

các phi là gì cách mơ hồ để làm điều này?

Đã thêm 4: OK!

LogicalExpression1 := LogicalExpression1 "OR" LogicalExpression2 | LogicalExpression2 
LogicalExpression2 := LogicalExpression2 "AND" LogicalExpression3 | LogicalExpression3 
LogicalExpression3 := "NOT" LogicalExpression4 | LogicalExpression4 
LogicalExpression4 := "asd" | "(" LogicalExpression1 ")" 

Điều này phân tích tất cả biểu thức boolean, với toán tử ưu tiên là NOT-> AND-> OR. "asd" có thể được thay thế bằng biểu thức dành cho các cụm từ của bạn.

Answer 1

Ngữ pháp của bạn không rõ ràng, nếu bạn chỉ sử dụng một cái nhìn duy nhất. Để minh họa, "asd" là gì? Có phải đó là một ExpressionTerm hoặc một thuật ngữ dài hơn. Đó là xung đột giảm dần. Tôi nghi ngờ một cuộc xung đột giảm thiểu ở đây.

Hầu hết các máy phát LL (1)/LALR (1) sẽ cung cấp một số cách để giải quyết xung đột giảm-giảm thông qua các toán tử ưu tiên. Hầu hết cũng sẽ mặc định cho chuỗi dài nhất trong sự hiện diện của một cuộc xung đột giảm-thay đổi, do đó, thường xuyên hơn những điều này có thể được bỏ qua (sau khi một số giám sát). (Trong trường hợp này có thể bạn cần phải di chuyển một thuật ngữ đến cuối để nó hoạt động chính xác).

Answer 2

Xung đột Shift-Reduce có nghĩa là ngữ pháp của bạn không rõ ràng. Với quy tắc đệ quy của bạn, mã thông báo "asd" có thể được hiểu là một phần của ExpressionTerm hoặc LogicalExpression và trình phân tích cú pháp không thể quyết định điều gì. Cần một quy tắc bổ sung để phá vỡ cà vạt.

Answer 3

Thay đổi giảm xung đột là một trong những điều khó khăn hơn để có được bộ não của bạn xung quanh khi nói đến các trình phân tích cú pháp. Cách dễ nhất để minh họa xung đột là trong mã giả này:

if (a) then 
    if (b) then 
    printf('a + b'); 
    else 
    print('this could be a + !b or !a'); 

Tuyên bố khác có thể liên kết với thứ nhất hoặc thứ hai nếu. Trong trường hợp các ngữ pháp không rõ ràng, bạn thường xác định một giá trị để cho biết số cảnh báo thay đổi-giảm mong đợi trong ngữ pháp của bạn.

Hoặc, bạn có thể sử dụng trình phân tích cú pháp LL (k) hoặc LL (*). Các loại trình phân tích cú pháp này không có sự thay đổi/giảm sự mơ hồ. Tùy thuộc vào ứng dụng của bạn, chúng có thể dễ dàng hơn hoặc khó hơn trình phân tích cú pháp LALR (1).

Answer 4

ngữ pháp là mơ hồ trong LL(1) hoặc LALR(1) từ asd thẻ có thể được thay thế trong ExpressionTerm và cũng LogicalExpression flatten các quy tắc ngữ pháp để giải quyết sự thay đổi/giảm xung đột