Сдвинуть / уменьшить конфликт в yacc из-за ограничения токенов прогнозирования? - PullRequest
Новая
       42

Сдвинуть / уменьшить конфликт в yacc из-за ограничения токенов прогнозирования?

3 голосов
/ 14 января 2011

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

statement_list
  : statement_list statement 
  | 
  ;

statement
  : lvalue '=' expression
  | function
  ;

lvalue
  : IDENTIFIER
  | '(' expression ')'
  ;

expression
  : lvalue
  | function
  ;

function
  : IDENTIFIER '(' ')'
  ;

С опцией verbose в yacc я получаю этот выходной файл, описывающий состояние с упомянутым конфликтом:

Спасибо за любую помощь.

1 Ответ

5 голосов
/ 14 января 2011

Проблема состоит в том, что для этого требуется 2-х жетонный просмотр, чтобы узнать, когда он достиг конца оператора.Если у вас есть ввод формы: 

ID = ID ( ID ) = ID

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

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

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

...