Сложность ассоциативности Flex и Bison

Question

Используя Flex и Bison, у меня есть спецификация грамматики для логического языка запросов, который поддерживает логические операции «и», «или» и «не», а также вложенные подвыражения с использованием «()».

Все было хорошо, пока я не заметил, что такие запросы, как «A и B или C и D», которые мне хотелось бы проанализировать как «(A & B) | (C & D)», на самом деле интерпретировались как «A & ( B | ( CD ) )".Я почти уверен, что это проблема ассоциативности, но, похоже, нигде не могу найти подходящего объяснения или примера - или я упускаю что-то важное.

Соответствующая информация с boolpars.y:

%token TOKEN
%token OPEN_PAREN CLOSE_PAREN
%right NOT
%left AND
%left OR

%%

query:      expression                          { ... }
            ;

expression: expression AND expression           { ... }
            | expression OR expression          { ... }
            | NOT expression                    { ... }
            | OPEN_PAREN expression CLOSE_PAREN { ... }
            | TOKEN                             { ... }
            ;

Может ли кто-нибудь найти недостаток?Я не понимаю, почему Bison не дает «или» соответствующего приоритета.

Answer 1

Из документов по бизонам:

Приоритет оператора определяется по упорядочению объявлений;Чем выше номер строки объявления (ниже на странице или экране), тем выше приоритет.

Итак, в вашем случае OR находится ниже на экране и имеет более высокий приоритет.Измените порядок на

%left OR
%left AND

(хотя я это не проверял)

Answer 2

Почему бы не разделить постановки, как в этом фрагменте с языка c-ish

logical_AND_expression:
    inclusive_OR_expression
    | logical_AND_expression ANDAND inclusive_OR_expression
            {$$ = N2(__logand__, $1, $3);}
    ;

logical_OR_expression:
    logical_AND_expression
    | logical_OR_expression OROR logical_AND_expression
            {$$ = N2(__logor__, $1, $3);}
    ;

Answer 3

Я выполнил тесты своей собственной реализации, и из моих тестов ответ марцина верно.Если я определяю приоритет как:

%left OR
%left AND

Тогда выражение A&B|C&D сократится до ((A&B)|(C&D))

Если я определяю приоритет как:

%left AND
%left OR

Тогда выражение A&B|C&D сократится до ((A&(B|C))&D)

Одним из дифференцирующих выражений может быть:

true & true | true & false

Первое определение приоритета будет считать это истинным, а второе — ложным.Я протестировал оба сценария, и оба работают, как описано.

Дважды проверьте свои тесты, чтобы убедиться.Также обратите внимание, что это порядок %left, %right и т. д.определения в заголовке, которые определяют приоритет, а не порядок, в котором вы сами определяете свои правила.Если он по-прежнему не работает, возможно, это какая-то другая область вашего кода, которая портит его, или, может быть, ваша версия bison отличается (я просто стреляю в темноте на этом этапе).