简单的模棱两可的语法与减少-减少冲突

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进行类型检查以确保变量是数字或布尔值，具体取决于上下文。