Сложность и сложность ассоциаций бизонов - PullRequest
Новая
       37

Сложность и сложность ассоциаций бизонов

4 голосов
/ 26 июня 2009

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

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

Соответствующая информация от 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                             { ... }
            ;

Кто-нибудь может найти изъян? Я не понимаю, почему Бизон не дает "или" соответствующего приоритета.

Ответы [ 3 ]

4 голосов
/ 26 июня 2009

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

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

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

%left OR
%left AND

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

1 голос
/ 29 июня 2009

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

%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 и т. Д. В части заголовка, которые определяют приоритет, а не порядок, который вы сами определяете свои правила. Если он все еще не работает, возможно, это какая-то другая область в вашем коде, которая испортила его, или, может быть, ваша версия бизона отличается (я просто стреляю в темноте).

1 голос
/ 26 июня 2009

Почему бы не разделить производство, как в этом фрагменте из 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);}
    ;
...