简单暧昧的语法与减少，减少冲突

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

从野牛状态报告有：

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 - 这取决于下一个标记的)了。如果下一个令牌是+。 -,<或>然后是它的一个expr，而如果它是AND或OR（或EOF），那么它的一个logical_expr。

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

在你的情况，如果你改变了logical_term规则

logical_term 
    : comparison 
    | expr 
    ; 

的矛盾就会消失，但你的解析器会接受的事情，不是类型正确，如 a > 3 AND 2或2 + 2 OR 7。您需要对生成的分析树（或您创建的任何数据结构）进行类型检查以确保正确性，尽管您可能需要这样做（至少您已经需要对VARIABLE进行类型检查以确保变量是数字或布尔值，取决于上下文。）