Как разрешить конфликт сдвига-сокращения в однозначной грамматике

Question

Я пытаюсь разобрать простую грамматику с помощью генератора синтаксического анализатора LALR(1) (Bison, но проблема не специфична для этого инструмента), и я сталкиваюсь с конфликтом сдвига-сокращения.Документы и другие источники, которые я нашел об их исправлении, обычно говорят одно или несколько из следующего:

• Если грамматика неоднозначна (например.двусмысленность if-then-else), измените язык, чтобы исправить двусмысленность.
• Если это проблема приоритета операторов, укажите приоритет явно.
• Примите разрешение по умолчанию и скажите генератору не жаловаться на это.

Однако ни один из них, похоже, не применим к моей ситуации:насколько я могу судить, грамматика однозначна (хотя, конечно, она неоднозначна только с одним символом просмотра вперед), у нее есть только один оператор, а разрешение по умолчанию приводит к ошибкам синтаксического анализа правильно сформированного ввода.Существуют ли какие-либо методы переработки определения грамматики для устранения конфликтов сдвига-сокращения, которые не попадают в вышеуказанные группы?

Для конкретности вот рассматриваемая грамматика:

%token LETTER

%%
%start input;
input:          /* empty */ | input input_elt;
input_elt:      rule | statement;
statement:      successor ';';
rule:           LETTER "->" successor ';';
successor:      /* empty */ | successor LETTER;
%%

Цель состоит в том, чтобы проанализировать разделенные точкой с запятой строки вида «[A-Za-z]+» или «[A-Za-z] -> [A-Za-z]+».

Answer 1

Использование версии Solaris yacc, Я получил:

1: shift/reduce conflict (shift 5, red'n 7) on LETTER
state 1
    $accept :  input_$end
    input :  input_input_elt
    successor : _    (7)

    $end  accept
    LETTER  shift 5
    .  reduce 7

    input_elt  goto 2
    rule  goto 3
    statement  goto 4
    successor  goto 6

Итак, проблема, как это часто бывает, в пустом правиле, а именно в пустом преемнике.Не совсем ясно, хотите ли вы разрешить точку с запятой в качестве допустимого ввода — на данный момент это так.Если вы изменили правило-преемник на:

successor: LETTER | successor LETTER;

конфликт сдвига/сокращения устраняется.

Answer 2

Спасибо, что сократили грамматику и выложили.Изменение правила преемника на -

successor:      /* empty */ | LETTER successor;

... работал у меня.ИТИМ язык выглядело однозначно.