Устранить конфликты сдвига/уменьшения, вызванные производственными правилами с одинаковым префиксом

Вот упрощенный файл yaac:

%token CONTEXT_    // the corresponding string is "context"
%token CONTEXTREF_ //"contextref"
%token IS_         //"is"
%token ID_L        //"id_l"
%token ID_L1       //"id_l1"
%token LIB_

%start design_file

%%
design_file   :design_unit
              |design_file design_unit 
              ;

design_unit   :context_cl LIB_
              |context_decl
              ;

context_cl    : /* empty */  {  }
              |context_cl context_ref
              ;

context_decl  :CONTEXT_ ID_L IS_ ';'
              ;

context_ref   :CONTEXT_ ID_L1 '.' ID_L ';'
              ;

Есть 2 конфликта сдвига/уменьшения.

CONTEXT_  shift, and go to state 1

CONTEXT_  [reduce using rule 5 (context_cl)]

Правило 5 – context_cl : /* empty */ { }.

Как правило, это не имеет значения, парсер большую часть времени работает хорошо. Но в одном странном случае для исходного файла, как показано ниже:

context id_l is ...
...

Синтаксический анализатор будет не сдвигать, а уменьшать, поэтому для анализа context id_l is ... используется context_ref :CONTEXT_ ID_L1 '.' ID_L ';', что вызывает синтаксические ошибки.

Так что я должен устранить конфликты. Я предполагаю, что они вызваны правилом context_decl и context_ref, оба из которых имеют CONTEXT_ в начале.

Чтобы подтвердить свою догадку, я просто изменил context_ref :CONTEXT_ ID_L1 '.' ID_L ';' на context_ref :CONTEXTREF_ ID_L1 '.' ID_L ';'. Тогда нет конфликта и нет синтаксической ошибки.

Однако я не могу заменить context_ref таким образом. Это стандарт.

Итак, как я могу избежать этих двух конфликтов другими способами? Или есть общий метод разрешения конфликтов такого рода?

И для конфликтов сдвига/уменьшения выберет ли парсер сокращение, а не сдвиг? Потому что я думаю, что синтаксический анализатор всегда будет переключаться на сокращение.


parsing compiler-construction yacc bison shift-reduce-conflict
person Yuan Wen    schedule 09.05.2017    source источник
comment
Я не могу воспроизвести описанную вами проблему. Я использовал именно ту грамматику, которую вы указали, и получил именно тот конфликт сдвига/уменьшения, который вы цитируете, в двух состояниях. Так что все проверяется. Я догадался, как может выглядеть лексер, и запустил его с вводом context id_l is ; в режиме отладки; он распознал ввод без ошибок. Он не будет анализировать context id_l1 ... из-за разрешения конфликта сдвига/уменьшения. Это то, что вы имели в виду? Если это так, пожалуйста, отредактируйте свой вопрос, и я постараюсь ответить на него. В противном случае, минимально воспроизводимый пример, пожалуйста, с упором на полный и проверяемый.   -  person rici    schedule 10.05.2017
comment
Периодически возникали синтаксические ошибки. Поэтому я просто хочу устранить конфликты сдвига/уменьшения. @rici   -  person Yuan Wen    schedule 10.05.2017

Ответы (2)


arrow_upward
4
arrow_downward

Основная закономерность, порождающая этот конфликт:

union : x x_rest
      | y_list y_rest
y_list: /* empty */
      | y_list y

где x и y оба имеют производство, начинающееся с одного и того же символа.

Стоит отметить, что проблема исчезнет, ​​если y_list равно одному или нескольким y, а не нулю или более:

y_list: y
      | y_list y

пока x и y действительно различимы. (Есть некоторые другие требования, зависящие от остального производства, но в основном все в порядке, если они имеют одинаковый префикс. Они даже могут быть одинаковыми при условии, что продолжения различаются в первой лексеме.)

Если вам действительно нужно, чтобы y_list было потенциально пустым (или оба x и y были потенциально пустыми), вам следует выполнить обычную процедуру устранения нулевого производства, которая включает в себя факторинг потенциально пустого производства из грамматики:

union : x x_rest
      | y_rest           /* Corresponds to an empty y_list */
      | y_list y_rest
y_list: y                /* As above, this list cannot be empty */
      | y_list y
person rici    schedule 10.05.2017

arrow_upward
2
arrow_downward

Я не уверен, откуда берутся ваши «периодические» синтаксические ошибки - как написано, ваша грамматика никогда не может соответствовать входным данным, таким как context id_l1 . id_l ... поскольку сдвиг заставит его попытаться проанализировать context_decl, а не context_ref.

Тем не менее, ваш конфликт не имеет ничего общего с общими префиксами - на самом деле он исходит из /* empty */, и самое простое решение - реорганизовать его, чтобы удалить это правило:

design_unit   : context_cl LIB_
              | LIB_
              | context_decl
              ;

context_cl    : context_ref
              | context_cl context_ref
              ;

Итак, теперь context_cl означает «1 или более» context_refs вместо «0 или более», и мы продублировали правило design_unit, чтобы иметь регистр 0 отдельно.

person Chris Dodd    schedule 10.05.2017