Не удается исправить конфликт сдвига / уменьшения зубров - PullRequest
Новая
       43

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

1 голос
/ 16 апреля 2020

Я пытаюсь добавить больше правил для этой вещи, и это продолжает давать мне этот конфликт сдвига / уменьшения, я не понимаю, почему это происходит, и я пытался исправить это в течение последних 24 часов 

FuncDecl        : RetType ID LPAREN Formals {
                    //code here
                    function($1, $2, $4);

                } RPAREN LBRACE Statements RBRACE {
                    //some code here
                    function($1, $2, $4);
                }   
                | RetType ID LPAREN Formals RPAREN SC 
                {
                    // some code here
                    function($1, $2, $4);
                }
                ;

parser.ypp:94.45-100.17: warning: rule useless in parser due to conflicts [-Wother]
 FuncDecl        : RetType ID LPAREN Formals {
                                             ^
g++ -std=c++11 -o test *.c *.cpp -Wno-deprecated

Может кто-нибудь объяснить мне, что происходит? и как я могу исправить эту вещь ?? примечание: мне нужно иметь код до RBRACE в первом правиле ...

Большое спасибо, ребята

1 Ответ

1 голос
/ 16 апреля 2020

В качестве упражнения давайте создадим минимальный воспроизводимый пример из этого, как всегда подсказывает помощь SO. Это действительно не так сложно. Поскольку при обработке фрагмента с помощью зубра возникает проблема, нет необходимости, чтобы MRE действительно компилировался или выполнялся, в этом случае.

Вот файл (conan.c): 

%token ID
%token RetType Formals Statements
%%
FuncDecl: RetType ID '(' Formals { funcdecl($1, $2, $4); } ')' 
                     '{' Statements '}' { funcdef($1, $2, $4, $8); }
        | RetType ID '(' Formals ')' ';'  { funcdecl($1, $2, $4) }

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

  • Нетерминалы, которые не имеют отношения, были преобразованы в терминалы. (строка 2) (Если бы они были релевантными, преобразование их в терминалы позволило бы устранить проблему go. Поскольку это не так, мы знаем, что они не имеют значения.)

  • Либерал используются односимвольные токены, чтобы сделать грамматику более читабельной и избежать необходимости объявлять их как токены. (Я бы превратил многосимвольные токены, такие как T_FOR, в строки в кавычках ("for") по той же причине.)

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

$ bison -o conan.c conan.y
conan.y: warning: 1 shift/reduce conflict [-Wconflicts-sr]
conan.y:4.34-58: warning: rule useless in parser due to conflicts [-Wother]
 FuncDecl: RetType ID '(' Formals { funcdecl($1, $2, $4); } ')' 
                                  ^^^^^^^^^^^^^^^^^^^^^^^^^

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

RetType ID ( Formals   )
                     ^
                     |------- lookahead

, он должен решить, следует ли выполнить действие среднего правила (funcdecl($1, $2, $4);). Но он еще не знает, какое из двух альтернативных произведений будет применяться. Первый требует выполнения MRA; второй нет. Но компилятор не будет знать, пока не увидит токен, следующий за закрывающей скобкой, и к тому времени он будет слишком поздно (согласно алгоритму LALR (1)).

Как представлено во фрагменте, MRA в первом варианте то же самое, что и окончательное действие во втором варианте. Если это действительно так, то парсер на самом деле не должен решать. Он может просто выполнить последнее действие для второй альтернативы чуть раньше. Но это простое решение не так просто, как кажется, потому что Bison не пытается определить, являются ли два MRA одинаковым кодом. Это просто предполагает, что они все разные, и это приведет к тому, что все равно придется что-то менять.

С другой стороны, существует гораздо более простое решение, потому что оно действительно не может иметь никакого значения, является ли MRA вызывается до или после закрывающей скобки. Ничего не может произойти при чтении токена (кроме продвижения счетчика строк, и если это проблема, вы должны использовать объекты местоположения). Перемещение MRA приведет к: 

%token RetType Formals Statements
%token ID
%%
FuncDecl: RetType ID '(' Formals ')'  { funcdecl($1, $2, $4); }
                     '{' Statements '}' { funcdef($1, $2, $4, $8); }
        | RetType ID '(' Formals ')' ';'  { funcdecl($1, $2, $4) }

Теперь конфликт исчез: 

$ bison -o conan.c conan.y
$

Это потому, что решение MRA принимается в точке, когда анализ достиг 

RetType ID ( Formals )   {
                       ^
                       |----- lookahead

и теперь предвидения достаточно, чтобы решить. (В другой альтернативе прогноз - 1043 *).

...