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;ます。

私の文法は曖昧ではないように見えるのに、なぜジソンは不平を言っているのですか?

更新: @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;"]
        ]
    }
}

つまり、この文法では、2 項演算子の後にオプションの改行を 1 つだけ使用できます。二項演算子の後に任意の数の改行が続くように書き直すにはどうすればよいですか? また、演算子ごとに 2 つのルールを記述する必要がない方法もあるはずです。

4

1 に答える 1

5

私はジソンに完全に精通しているわけではありませんが、次のようなルールを定義しているようです:

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

式を考えてみましょう1 - 2 - 3。(1 - 2) - 3それはまたはとして解釈できます1 - (2 - 3)。それはどれですか？あなたの文法はあいまいです。通常の数学的規則では、左結合である必要があります。文法に次のことを反映させる必要があります。

expression ::= number;
expression ::= expression binary number;
于 2013-04-04T03:04:09.810 に答える