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

Question

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

statement_list
  : statement_list statement 
  | 
  ;

statement
  : lvalue '=' expression
  | function
  ;

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

expression
  : lvalue
  | function
  ;

function
  : IDENTIFIER '(' ')'
  ;

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

state 2

    lvalue  ->  IDENTIFIER .   (rule 5)
    function  ->  IDENTIFIER . '(' ')'   (rule 9)

    '('  shift, and go to state 7

    '('  [reduce using rule 5 (lvalue)]
    $default reduce using rule 5 (lvalue)

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

Answer 1

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

ID = ID ( ID ) = ID

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

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

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