Difficulté d'associativité entre le bison et le bison

Question

En utilisant Flex et Bison, j'ai une spécification de grammaire pour un langage de requête booléen, qui prend en charge les " et ", " ou " et & logiques. "pas &"; opérations, ainsi que les sous-expressions imbriquées utilisant " () & ";.

Tout allait bien jusqu'à ce que je remarque que des requêtes comme & "A et B ou C et D &"; que j'aimerais analyser comme " (A & amp; B) | (C & Amp; D) & Quot; était en fait interprété comme " A & amp; (B | (C & Amp; D)) & Quot ;. Je suis presque certain qu'il s'agit d'un problème d'associativité, mais je n'arrive pas à trouver une explication ou un exemple approprié où que ce soit - cela ou quelque chose d'important me manque.

Informations pertinentes provenant de 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                             { ... }
            ;

Quelqu'un peut-il trouver la faille? Je ne vois pas pourquoi Bison ne donne pas & "Ou &"; préséance appropriée.

Answer 1

D'après les documents sur les bisons:

  

La priorité de l'opérateur est déterminée par   l'ordre en ligne des déclarations;   plus le numéro de ligne du   déclaration (plus bas sur la page ou   écran), plus la priorité est élevée.

Donc, dans votre cas, OU est plus bas à l'écran et a une priorité plus élevée. Changer l'ordre en

%left OR
%left AND

(je ne l'ai pas encore testé)

Answer 2

Pourquoi ne pas séparer les productions, comme dans cet extrait de un langage 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

J'ai effectué des tests sur ma propre implémentation et, à partir de mes tests, La réponse de Marcin est correcte. Si je définis la priorité comme:

%left OR
%left AND

Ensuite, l'expression A & et B | C & et D sera réduite à ((A & B; B) | (C & et D))

Si je définis la priorité comme:

%left AND
%left OR

Ensuite, l'expression A & et B | C & et D sera réduite à ((A &; B (C)) & et D)

Une expression de différenciation serait:

true & true | true & false

La première définition de priorité rendrait ceci vrai, alors que la seconde le rendrait faux. J'ai testé les deux scénarios et les deux fonctionnent comme expliqué.

Vérifiez vos tests pour vous en assurer. Notez également que c’est l’ordre des définitions% gauche,% droite, etc. dans la partie en-tête qui définit la priorité, et non l’ordre dans lequel vous définissez vos règles elles-mêmes. Si cela ne fonctionne toujours pas, c'est peut-être un autre domaine de votre code qui le gâche, ou peut-être que votre version du bison est différente (je tire juste dans le noir à ce stade).