Как эта грамматика неоднозначна?

Я пишу простой парсер выражений в 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 правила для каждого оператора.


javascript parsing bison parser-generator jison
person Aadit M Shah    schedule 04.04.2013    source источник

Ответы (1)


arrow_upward
5
arrow_downward

Я не совсем знаком с Джисоном, но похоже, что вы определяете правило, которое выглядит так:

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

Рассмотрим выражение 1 - 2 - 3. Это можно интерпретировать как (1 - 2) - 3 или 1 - (2 - 3). Что это? Ваша грамматика неоднозначна. Обычные математические правила говорят, что он должен быть левоассоциативным. Вам нужно, чтобы ваша грамматика отражала следующее:

expression ::= number;
expression ::= expression binary number;
person icktoofay    schedule 04.04.2013
comment
Ты прав. Ассоциативность операторов действительно была проблемой. Спасибо. Могу я побеспокоить вас еще кое о чем? Я отредактировал свой вопрос и хотел бы узнать ваше мнение об этом. Может быть, я должен опубликовать это как отдельный вопрос? - person Aadit M Shah; 04.04.2013
comment
@AaditMShah: я бы просто изменил лексер, чтобы объединить последовательные символы новой строки. Что касается необходимости двух продукций с NEWLINE/без NEWLINE, возможно, вы могли бы создать новую maybe_newline с двумя продукциями: одну пустую и одну для NEWLINE. (На самом деле, если вы не хотите модифицировать лексер, у вас может быть maybe_newline с одним пустым производством и одним производством maybe_newline NEWLINE.) - person icktoofay; 04.04.2013