这个语法有什么歧义吗？

Question

这个语法有什么歧义吗？

javascriptparsingbisonparser-generatorjison

4

我正在使用Jison编写一个简单的表达式解析器。以下是我的语法：

{
    "operators": [
        ["left", "+", "-"],
        ["left", "*", "/", "%"]
    ],
    "bnf": {
        "program": [
            ["statement EOF", "return $1;"]
        ],
        "statement": [
            ["expression NEWLINE", "$$ = $1 + ';';"]
        ],
        "expression": [
            ["NUMBER",                       "$$ = yytext;"],
            ["expression binary expression", "$$ = $1 + $2 + $3;"]
        ],
        "binary": [
            ["+",              "$$ = ' + ';"],
            ["-",              "$$ = ' - ';"],
            ["*",              "$$ = ' * ';"],
            ["/",              "$$ = ' / ';"],
            ["%",              "$$ = ' % ';"],
            ["binary NEWLINE", "$$ = $1;"]
        ]
    }
}

当我尝试运行它时，会出现以下错误：

Conflict in grammar: multiple actions possible when lookahead token is + in state
13
- reduce by rule: expression -> expression binary expression
- shift token (then go to state 8)
Conflict in grammar: multiple actions possible when lookahead token is - in state
13
- reduce by rule: expression -> expression binary expression
- shift token (then go to state 9)
Conflict in grammar: multiple actions possible when lookahead token is * in state
13
- reduce by rule: expression -> expression binary expression
- shift token (then go to state 10)
Conflict in grammar: multiple actions possible when lookahead token is / in state
13
- reduce by rule: expression -> expression binary expression
- shift token (then go to state 11)
Conflict in grammar: multiple actions possible when lookahead token is % in state
13
- reduce by rule: expression -> expression binary expression
- shift token (then go to state 12)

States with conflicts:
State 13
  expression -> expression binary expression . #lookaheads= NEWLINE + - * / %
  expression -> expression .binary expression
  binary -> .+
  binary -> .-
  binary -> .*
  binary -> ./
  binary -> .%
  binary -> .binary NEWLINE

然而，最终它仍会产生正确的输出。例如：2 + 3 * 5 / 7 % 11将被正确转换为2 + 3 * 5 / 7 % 11;。

我认为我的语法似乎是无歧义的，那么为什么Jison会抱怨呢？

更新：正如@icktoofay所解释的那样，这是一个操作符结合性问题。通过将操作符解析为非终端符号，操作符优先级和结合性信息就会丢失。因此，我按照以下方式解决了这个问题：

{
    "operators": [
        ["left", "+", "-"],
        ["left", "*", "/", "%"]
    ],
    "bnf": {
        "program": [
            ["statement EOF", "return $1;"]
        ],
        "statement": [
            ["expression NEWLINE", "$$ = $1 + ';';"]
        ],
        "expression": [
            ["NUMBER",                          "$$ = yytext;"],
            ["expression + expression",         "$$ = $1 + ' + ' + $3;"],
            ["expression - expression",         "$$ = $1 + ' - ' + $3;"],
            ["expression * expression",         "$$ = $1 + ' * ' + $3;"],
            ["expression / expression",         "$$ = $1 + ' / ' + $3;"],
            ["expression % expression",         "$$ = $1 + ' % ' + $3;"],
            ["expression + NEWLINE expression", "$$ = $1 + ' + ' + $4;"],
            ["expression - NEWLINE expression", "$$ = $1 + ' - ' + $4;"],
            ["expression * NEWLINE expression", "$$ = $1 + ' * ' + $4;"],
            ["expression / NEWLINE expression", "$$ = $1 + ' / ' + $4;"],
            ["expression % NEWLINE expression", "$$ = $1 + ' % ' + $4;"]
        ]
    }
}

话虽如此，这个语法仅允许二元运算符后跟一个可选换行符。我该如何重写它以允许任意数量的换行符跟在二元运算符后面？另外，必须有一种方式可以不必为每个运算符编写两个规则。

- Aadit M Shah

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- icktoofay · Accepted Answer

我不完全熟悉Jison，但看起来你正在定义一个规则，它看起来像这样：

expression ::= number;
expression ::= expression binary expression;

考虑表达式1 - 2 - 3。它可以理解为(1 - 2) - 3或1 - (2 - 3)。那应该是哪个呢？你的语法不明确。正常数学规则认为它应该是左结合的。你需要让你的语法反映这一点：

expression ::= number;
expression ::= expression binary number;