Une rapide présentation de YACC
Considérer la grammaire
S -> CC
C -> cC | d
Définir le source Yacc correspondant (sans actions) et compiler avec
l'option -v
. Vérifier que le fichier y.output
contient bien la table d'analyse LALR.
E -> E + E
E -> E * E
E -> ( E )
E -> entier
pour implanter la calculatrice de base présentée en introduction. Vérifier
que l'analyseur construit engendre de nombreux conflits. Lever les
conflits en précisant les règles de priorité et d'associativité des
opérateurs. Ajouter le moins unaire et vérifier que les priorités sont
correctement gérées.
On demande de réaliser, à l'aide des outils Lex et Yacc, un interpréteur
d'expressions ensemblistes répondant aux spécifications suivantes (on
considérera uniquement des ensembles d'entiers compris entre 1 et 32):
Vocabulaire
a..z A..Z
identificateur mono-lettre (ident) non
"case-sensitive"
délimiteurs classiques des ensembles
{ }
affectation
:=
séparateur d'éléments
,
seuls éléments possibles
1..32
fin de ligne
\n
union ensembliste
union UNION
intersection ensembliste
inter INTER
complémentaire dans {1,...,32}
comp COMP
différence ensembliste
diff DIFF
Grammaire
liste ::= <empty> // sortie de
l'interpréteur
| liste instruction '\n' // interprétation de
l'instruction
instruction ::= ident ':=' expression // calcul de l'expression et
affectation
| ident // affichage
expression ::= operande // renvoie l'opérande
| operande operateur2 operande // renvoie le résultat de
| operateur1 operande // l'opération
ensembliste
operateur2 ::= 'UNION' | 'INTER' | 'DIFF' | 'union' | 'inter' | 'diff'
operateur1 ::= 'COMP' | 'comp'
operande ::= ident
| ensemble
ensemble ::= { } // ensemble vide
| { liste-elements } // ensemble non vide
liste-elements ::= élément
| élément , liste-elements
Exemple d'exécution
A := { }
met l'ensemble vide dans A
met dans
a := { 1, 22 } A
l'ensemble {
1, 22 }
met dans
b := a UNION { 3 } B
l'union de A
et du singleton { 3 }
affiche l'ensemble
B B
:
met dans
{ 1, 3, 22 }
C := { 1, 3, 5 } C
l'ensemble {
1, 3, 5 }
met dans
A := B inter C A
l'intersection de
B
et de C
affiche l'ensemble
a A
:
{ 1, 3 }
Indication: grâce à un codage des ensembles sur des entiers
longs (32 bits), on pourra réaliser simplement les opérations
ensemblistes avec les opérateurs "bitwise" du C/C++ ( & | ~
)