[Grammaire LALR(1)] Qu'est ce qui est le mieux? - %left vs un tas de règles

Logiciel & apps Programmation
1

Pour un projet particulier, j’ai besoin de Bison :

Je voudrais au final ne pas avoir trop de règles pour éviter d’avoir un script bourrin (puisque je dois le convertir en PHP au final) j’ai donc ceci :

%left OR
%left XOR
%left AND
expr: expr OR expr
      | expr XOR expr
      | expr AND expr
      | variable
     ;

Cela fonctionne bien, et ça ne fait que 4 règles (même si derrière va y avoir beaucoup d’états dans l’automate, ce que j’aimerai réduire, mais passons).

Maintenant, je peux aussi faire ça :

expr: expr_xor OR expr | expr_xor;
expr: expr_and OR expr_xor | expr_and;
expr: variable OR expr_and | variable;

Ce qui passe le nombre de règles à 6 mais qui est tout aussi valide.

Sauf que je ne sais pas lequel est le mieux. Dans le peu de grammaire que j’ai vu, -* celle de PHP, mySQL - ils utilisent la première techniques : mais j’aimerai éviter d’avoir un truc bourrin (c’est à convertir en PHP, et j’ai pas envie que ce soit super lent).

Des connaisseurs?

2

Les grammaires LALR1 c’est loin pour moi, mais j’ai fait quelques gramaires LL1 récemment.
L’avantage c’est que tu n’as pas besoin d’analyseur gramatical, tu peux l’écrire simplement par des fonctions récursives: une fonction par règle, et avec minimum 2 fonctions de bases de ton analyseur lexical (getLastWord() et next() ), même si c’est pas la question, ça te permet de maîtriser les perfs

Maintenant si bison existe en PHP, c’est sûr que c’est peut-êter plus facile de s’en servir.
Et la 1ere ecriture me paraît beaucoup plus claire, j’ai pas compris quel était l’intérêt de séparer en plusieurs règles: est-ce que ça te permet de réduire la profondeur de l’arbre d’analyse?
Pour moi l’intérêt de développer des règles c’est de réduire la profondeur: passer d’un LALR(n) en LALR(n-1) mais comme je l’ai déjà dit, c’est trop loin pour moi pour savoir comment ça se calcule…

3

heu justement :o moi je ne sais faire que du SLR(1) apparemment :x
La deuxième a un avantage : elle permet de séparer les opérateurs par précédence, et d’éviter des conflits.
Je ne veux pas faire du LL(1) car ça va me donner des résultats un peu gros (le but reste quand même d’automatiser mon langage).

4

Si c’est pour définir des règles de priorité, ça ressemble malgré tout à ce que je faisait avec des expressions arthmétiques.
Les priorités: AND > XOR = OR ?
avec + et *, je donne mon exemple, il suffit de transposer pour AND et OR et XOR


exemple d'expression : (a+b)*c+(d)
id, idsum et idmul sont des mots du langage ([+-]pour idsum et [*/] pour idmul) epsilon est le "vide"

S->Sum
Sum ->Mul idsum Mul|Mul
Expr->(Sum)|id
Mul ->Expr idmul Expr|Expr

en LL(1)
Sum  -> Mul Sum2
Sum2 -> idsum Mul | epsilon
Mul  -> Expr Mul2
Mul2 -> idmul Expr | epsilon
Expr -> (Sum)|id

La 2ème écriture, même si elle est faite pour le LL(1) a l’avantage de de te permettre d’analyser les args de gauche avant ceux de droite.

5

and > xor > or

Donc : a and b xor c or d => (( a and b ) xor c ) or d

Bref. Mes opérateurs ajoutent trop de conflits, vais faire avec les précédences (1. ça marche 2. ça me donne un bon fichier output que je peux traduire vers du php).

6

Soit, le but c’est que ça marche! mais en 3 règles tu peux définir tes priorités:


expr:expr_or
expr_or: expr_xor OR expr_or | expr_xor
expr_xor: expr_and OR expr_xor | expr_and
expr_and expr_final AND expr_and | expr_final
expr_final: id

C’est peut-être aussi simple, et tu utilise la puissance de bison pour gérer les problèmes. :neutre:

7

hé :slight_smile: c’est justement ce que j’ai fait, c’est ma grammaire 2 :smiley:

8

:super:
Et c’est plus beau, donc ça doit être plus logique. :wink:

9

C’est plus simple aussi.