简单模棱两可的语法，具有减少-减少冲突的功能 [英] Simple ambiguous grammar with reduce-reduce conflict

问题描述

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

The following simple grammar to parse a logical expression results in a reduce/reduce conflict:

%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 ')'
    ;
%%

野牛的状态报告有:

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".如何消除这种语法的歧义?有可能吗?

I'm guessing the problem is that it can't figure out how to parse "(a) + 1 < 2". How does one disambiguate this grammar? Is it possible?

推荐答案

语法的基本问题是，当您看到( VARIABLE并且下一个标记是)时，解析器无法确定是否应该带括号的expr或logical_expr-取决于)之后的下一个标记.如果下一个标记是+. -，<或>然后是expr，如果是AND或OR(或EOF)，则为logical_expr.

The basic problem with your grammar is that when you seen ( VARIABLE and the next token is ), the parser can't tell whether this should be a parenthesized expr or logical_expr -- it depends on the next token AFTER the ). If that next token is +. -, < or > then its an expr, while if it's AND or OR (or EOF), then its a logical_expr.

通常的解决方案是不要尝试在语法中进行类型检查.尽管可能，但需要额外的前瞻性，并且可能需要多层语法或此类复杂性.

The usual solution to this is to NOT try to do type-checking in the grammar. While its possible, it requires extra lookahead and may require multilevel grammars or such complexity.

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

In your case, if you change the logical_term rule to

logical_term
    : comparison
    | expr
    ;

冲突消失了，但是您的解析器将接受类型不正确的内容，例如 a > 3 AND 2或2 + 2 OR 7.您需要对生成的语法分析树(或正在创建的任何数据结构)进行类型检查，以确保正确性，尽管无论如何您可能都需要这样做(至少您已经需要对类型VARIABLE进行类型检查，以确保变量为数字或布尔值，具体取决于上下文.)

the conflict goes away, but your parser will accept things that are not type correct, such as a > 3 AND 2 or 2 + 2 OR 7. You'll need to do type-checking of your resulting parse tree (or whatever data structures you are creating) for correctness, though you would likely need that anyways (at the very least you already needed to typecheck VARIABLE to ensure that the variable was numeric or boolean, depending on context.)

这篇关于简单模棱两可的语法，具有减少-减少冲突的功能的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！