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

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

0 голосов
/ 14 февраля 2019

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

Вот состояние конфликта в файле parser.output, полученном при запуске бизона с -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 для выражений 

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 ]

0 голосов
/ 14 февраля 2019

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

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

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

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

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

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

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

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

0 голосов
/ 15 февраля 2019

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

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

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

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

0 голосов
/ 14 февраля 2019

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

  1. уменьшает TIDENT до identили
  2. смещение TLPAREN.

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

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

call:
       ident TLPAREN args TRPAREN
       ;

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

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

...