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

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

type:
  INT
  | ID
  | type LS RS
  ;

local_var_decl:
  type ID SEMICOLON
  ;

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

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

Вот что находится внутри файла .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. ЧИСЛО происходит здесь из правила выражения (в основном, как оно должно быть проанализировано), хотя оно пытается проанализировать его с помощью правила local_var_decl.

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

Спасибо!!

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


parsing yacc bison lalr bisonc++
person oneturkmen    schedule 04.11.2017    source источник

Ответы (1)


arrow_upward
1
arrow_downward

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

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

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

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

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
  ;
person rici    schedule 04.11.2017