Bison Shift/Reduce Conflict для грамматики языка программирования

Я пишу парсер языка программирования и застрял в этом конфликте сдвига / уменьшения.

Вот конфликтное состояние в файле parser.output, полученном при запуске bison с -v

State 1

   24 ident: TIDENT .
   26 call: TIDENT . TLPAREN args TRPAREN

    TLPAREN  shift, and go to state 24

    TLPAREN   [reduce using rule 24 (ident)]
    $default  reduce using rule 24 (ident)

Конфликт возникает, когда я пытаюсь реализовать правило для вызова, похоже, он конфликтует с нормальным правилом идентификации.

Вот некоторые части грамматики (действия удалены для простоты, но они не должны быть необходимы. Также я не уверен, имеет ли значение порядок, в котором определяются правила, исправьте меня, если я ошибаюсь)

(заглавные буквы являются токенами)

Правило идентификации просто

ident: TIDENT
          ;

Арги, используемые по вызову.

args: /* empty */
        |
        expr
        |
        args TCOMMA expr
        ;

Вызов для вызова функции

call:
       TIDENT TLPAREN args TRPAREN
       ;

Экспр для выражений

expr:
    number
    |
    ternary
    |
    bool
    |
    string
    |
    ident
    |
    call
    |
    TLPAREN expr TRPAREN
    |
    expr TPLUS expr
    |
    expr TMINUS expr
    |
    expr TSLASH expr
    |
    expr TSTAR expr
    |
    expr TGT expr
    |
    expr TGE expr
    | 
    expr TLT expr
    |
    expr TLE expr
    ;

Вопрос: почему у грамматики конфликт сдвига / уменьшения и как вы это исправляете? Я видел похожие парсеры стиля, у которых нет конфликтов, это действительно странно.

Если вам нужно увидеть полную грамматику для воспроизведения, вот вам хастин https://hasteb.in/zozifopi.shell

Если вам нужно больше информации о чем-либо еще, пожалуйста, дайте мне знать в комментариях, и я соответствующим образом отредактирую вопрос.

Источник

3 ответа

Решение

Основная проблема здесь в том, что ваша грамматика неоднозначна, потому что операторы не должны заканчиваться (stmts: stmts stmt) и утверждение может быть выражением. Таким образом, два выражения могут появляться одно за другим без пунктуации. Это означает, что f(3) может быть одно выражение (вызов функции) или два выражения (f а также (3)).

Если вы рады, что синтаксический анализатор всегда интерпретирует это как вызов функции (что является его поведением по умолчанию, так как он предпочитает сдвиг), тогда вы можете просто добавить пару объявлений предшествования, чтобы вызов имел более высокий приоритет, чем сокращение:

%precedence TIDENT
//...
%precedence TLPAREN
// ...
%%
expr : ident %prec TIDENT

Это только бумаги из-за двусмысленности, и может вызвать неожиданные разборы. Но единственное другое решение - сделать язык однозначным.

Источник

Проблема в том, что когда анализатор сместил токен TIDENT и смотрит вперед, TLPAREN Таким образом, грамматика допускает две альтернативы:

  1. Уменьшить TIDENT для ident, или же
  2. сдвинуть TLPAREN,

Зубр обычно разрешает конфликты смещения / уменьшения, выбирая смещение, и если это то, что вам нужно в этом случае, вы можете просто проигнорировать предупреждение.

В этом конкретном случае, однако, вы сможете решить конфликт, изменив правило для call производство:

call:
       ident TLPAREN args TRPAREN
       ;

С этим правилом больше нельзя переместить TLPAREN без предварительного уменьшения TIDENT для ident,

В качестве альтернативы, вы можете рассмотреть возможность удаления ident нетерминал в целом, и вместо того, чтобы использовать TIDENT прямо там, где вы сейчас используете ident, Могут быть и другие альтернативы. То, что лучше всего работает для вас, может зависеть от того, что вы пытаетесь делать со своими семантическими действиями. Я не могу более подробно это прокомментировать, поскольку вы решили оставить семантические действия вне нашего рассмотрения.

Источник

По умолчанию Bison генерирует синтаксический анализатор LR, который представляет собой анализатор снизу вверх, который может определять каждое состояние, перемещая токен или уменьшая его.

Конфликт действительно прост и хорошо объясняется самим выводом (интересно, что не ясно), он говорит вам:

Если я найду IDENTIFIER я должен уменьшить его через правило 24 до ident не терминал или я должен сдвинуть его, как в call править?

Это потому, что когда-то уменьшается, вы не можете сдвинуть и наоборот, что создало действительно конфликт.

Чтобы разрешить конфликт, вам нужно переместить этот выбор в то же состояние синтаксического анализатора, чтобы он мог определяться контекстом.

поскольку ident только терминал IDENT Правило и то же относится к вызову, вы можете легко переместить все на одном уровне, чтобы он всегда сдвигался:

expr: 
  IDENT | 
  IDENT LPAREN args RPAREN |
  ...

или используйте то же самое ident нетерминал для обоих call а также expr сам по себе, так что всегда будет уменьшать его.

Источник
Другие вопросы по тегам