Как разрешить конфликт сдвига-сокращения в однозначной грамматике
-
12-09-2019 - |
Вопрос
Я пытаюсь разобрать простую грамматику с помощью генератора синтаксического анализатора 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]+».
Решение
Использование версии 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;
конфликт сдвига/сокращения устраняется.
Другие советы
Спасибо, что сократили грамматику и выложили.Изменение правила преемника на -
successor: /* empty */ | LETTER successor;
... работал у меня.ИТИМ язык выглядело однозначно.