grammar - 具有reduce-reduce冲突的简单歧义语法

Question

以下用于解析逻辑表达式的简单语法会导致归约/归约冲突:

%token AND OR
%token NUMBER VARIABLE
%%
logical_expr
    : logical_expr AND logical_term
    | logical_expr OR logical_term
    | logical_term
    ;
logical_term
    : VARIABLE
    | comparison
    | '(' logical_expr ')'
    ;
comparison
    : expr '<' expr
    | expr '>' expr
    ;
expr
    : expr '+' term
    | expr '-' term
    | term
    ;
term
    : NUMBER
    | VARIABLE
    | '(' expr ')'
    ;
%%

bison 的状态报告有:

state 2

    4 logical_term: VARIABLE .
   13 term: VARIABLE .

    ')'       reduce using rule 4 (logical_term)
    ')'       [reduce using rule 13 (term)]
    '<'       reduce using rule 13 (term)
    '>'       reduce using rule 13 (term)
    '+'       reduce using rule 13 (term)
    '-'       reduce using rule 13 (term)
    $default  reduce using rule 4 (logical_term)

我猜问题是它无法弄清楚如何解析“(a) + 1 < 2”。如何消除这种语法的歧义？可能吗？

Answer 1

你语法的基本问题是，当你看到 ( VARIABLE下一个标记是 ) , 解析器无法判断这是否应该是带括号的 expr或 logical_expr -- 这取决于 ) 之后的下一个标记.如果下一个标记是 + . - , <或 >那么它是一个表达式，而如果它是 AND或 OR (或 EOF)，然后它是一个 logical_expr .

通常的解决方案是不要尝试在语法中进行类型检查。虽然这是可能的，但它需要额外的前瞻性，并且可能需要多级语法或类似的复杂性。

在您的情况下，如果您更改 logical_term规则为

logical_term
    : comparison
    | expr
    ;

冲突消失了，但是你的解析器会接受类型不正确的东西，比如 a > 3 AND 2或 2 + 2 OR 7 .您需要对生成的解析树(或您正在创建的任何数据结构)进行类型检查以确保正确性，尽管您可能无论如何都需要它(至少您已经需要进行类型检查 VARIABLE 以确保变量是数字或 bool 值，具体取决于上下文。)