dificuldade Flex e Bison Associativity

Question

Usando Flex e Bison, eu tenho uma especificação de gramática para uma linguagem de consulta booleana, que suporta lógica "e", "ou", e "não" de operações, bem como subexpressões aninhadas usando "()".

Tudo estava bem até que eu notei que as consultas como "A e B ou C e D", que eu gostaria analisados ??como "(A & B) | (C & D)" foi realmente a ser interpretado como "A & ( B | (C & D))". Estou quase certo de que este é um problema associatividade, mas não consigo encontrar uma explicação ou exemplo apropriado em qualquer lugar - que ou eu estou faltando alguma coisa importante

.

Informações pertinentes a partir 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                             { ... }
            ;

alguém pode encontrar a falha? Eu não posso ver por que Bison não está dando "ou" prioridade adequada.

Answer 1

De docs Vega:

A precedência do operador é determinada pela a ordenação linha das declarações; quanto maior for o número da linha do declaração (baixar na página ou tela), maior a prioridade.

Assim, no seu caso, ou é mais baixo na tela e tem maior precedência. Alterar a ordem para

%left OR
%left AND

(eu não testei embora)

Answer 2

Por que não dividir as produções, como neste trecho de uma linguagem 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

Eu já realizados testes na minha própria implementação, e dos meus testes, Marcin resposta está correto. Se eu definir a precedência como:

%left OR
%left AND

Em seguida, a expressão de A e B | C & D vai ser reduzida para ((A & B) | (C & D))

Se eu definir a precedência como:

%left AND
%left OR

Em seguida, a expressão de A e B | C & D vai ser reduzida para ((A & (B | C)) & D)

Uma expressão de diferenciação seria:

true & true | true & false

O ex-definição precedência tornaria isso como verdade, enquanto o segundo seria torná-la como falsa. Eu testei ambos os cenários e tanto trabalho como explicou.

Verifique seus testes para ter certeza. Também nota que é a ordem do% esquerda, direita%, etc. definições na parte de cabeçalho que definem a prioridade, não a fim de que você definir suas próprias regras. Se ele ainda não está funcionando, talvez seja alguma outra área em seu código que é estragar tudo, ou talvez a sua versão do bisonte é diferente (eu estou apenas atirando no escuro neste momento).