Не удается устранить следующую ошибку уменьшения-уменьшения (синтаксический анализ LALR)

Question

В настоящее время я реализую часть грамматики Decaf (язык программирования). Вот соответствующий фрагмент кода бизона:

type:
  INT
  | ID
  | type LS RS
  ;

local_var_decl:
  type ID SEMICOLON
  ;

name:
  THIS
  | ID
  | name DOT ID
  | name LS expression RS
  ;

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

Вот что находится внутри файла .output (генерируется Bison):

State 84

   23 type: ID .
   61 name: ID .

    ID        reduce using rule 23 (type)
    LS        reduce using rule 23 (type)
    LS        [reduce using rule 61 (name)]
    $default  reduce using rule 61 (name)

Итак, если мы дадим следующий вклад { abc[1] = abc; }это говорит о том, что syntax error, unexpected NUMBER, expected RS, NUMBER происходит от правила выражения (в основном, как он должен был его проанализировать), хотя он пытается проанализировать его с помощью правила local_var_decl.

Как вы думаете, что следует изменить, чтобы решить эту проблему? Потратил около 2 часов, пробовал разные вещи, не работал.

Спасибо!!

PS. Вот ссылка на полный исходный код .y

Answer 1

Это частный случай распространенной проблемы, когда парсер вынужден принимать решение, прежде чем у него будет достаточно информации. В некоторых случаях, таких как этот, необходимая информация находится недалеко, и было бы достаточно увеличить прогноз, если бы это было возможно. (К сожалению, немногие генераторы парсеров производят парсеры LR(k) с k > 1, и бизон не является исключением.) Обычное решение - просто позволить продолжить анализ без принятия решения. Другое решение, с bison (но только в режиме C), чтобы попросить %glr-parser, что гораздо более гибко, когда необходимо разрешить сокращения за счет дополнительного времени обработки.

В этом случае контекст позволяет type или nameоба из которых могут начинаться с ID с последующим [ (LS). В случае name, [ должен сопровождаться номером; в случае type, [ должно сопровождаться ], Так что, если бы мы могли увидеть второй токен после IDмы могли бы сразу решить.

Но мы можем видеть только один токен впереди, который является ], И грамматика настаивает на том, что мы сможем принять немедленное решение, потому что в одном случае мы должны уменьшить ID к name а в другом случае, к type, Таким образом, у нас есть конфликт уменьшения-уменьшения, который разрешается бизоном, всегда используя то, что сокращение идет первым в файле грамматики.

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

type_other:
  INT
  | ID LS RS
  | type_other LS RS
  ;
type: ID
  | type_other
  ;

name_other:
  THIS
  | ID LS expression RS
  | name_other DOT ID
  | name_other LS expression RS
  ;
name: ID
  | name_other
  ;