Mémento d'utilisation de CUP
On se reportera aux pages du manuel CUP, pour des informations plus complètes.
Exécution
L'outil CUP est fourni sous la forme d'une archive JAVA exécutable java-cup.jar et d'une librairie java-cup-runtime.jar. Il prend en entrée une spécification CUP et produit en sortie une classe parser.java contenant la méthode d'analyse syntaxique parse(), et une classe sym.java contenant l'énumération des tokens utilisés. La classe parser.java utilise de plus une méthode d'analyse lexicale java-cup.runtime.Symbol next_token() générée par JFlex.
Si l'on suppose une classe exécutable CupParse.java qui utilise la méthode parse(), on aura l'exécution :
Un exemple minimal pour la classe CupParse.java :
| --nosummary | moins verbeux |
| --nowarn | moins verbeux |
| -destdir <directory> | génère les classes dans directory |
| -interface | sym.java est une interface au lieu d'une classe |
| -nonterms | ajoute les symboles non terminaux dans sym.java |
| -dump | affichage des tables de l'automate |
| -locations | gestion de la position dans le source pour les symboles |
Format d'une spécification
Huit sections éventuellement optionnelles ou répétées, mais obligatoirement ordonnées. Dans un style BNF étendu, on a la syntaxe :
- Les sections package et import fournissent, selon la syntaxe JAVA, le préambule de la classe générée.
- La section class et la sous-section code.scanwith sont inutiles dans le cours.
- La section code permet d'instrumenter l'analyseur avec du code utilisateur.
- Les sections symbol et production sont obligatoires et fournissent la définition de la grammaire.
- L'axiome de la grammaire est défini par la section start ou à défaut par la première production.
Symboles
Les symboles de la grammaire se déclinent en :
- Terminaux, ou Constantes, ou Tokens, qui sont les catégories lexicales reconnues par l'analyseur,
- Non-Terminaux, ou Variables, qui dans la grammaire, servent à définir les formes syntaxiques valides.
Pour une bonne lisibilité, on prendra soin de différencier le nommage ou la typographie des deux types de symboles.
Il existe de plus 3 symboles conventionnels prédéfinis :
-
terminal EOF qui signifie : il n'y a plus
de tokens.
Petit bugue : EOFn'est pas utilisable dans la grammaire (error undefined), et pas déclarable (error redefined), - terminal error qui signifie : il y a une erreur de syntaxe mais je veux essayer de continuer l'analyse (cf. section Traitements d'erreurs),
- non terminal $START indique la fin positive de l'analyse. Conventionnellement, CUP ajoute une règle de la forme : $START ::= start_symb EOF;.
Couplage JFlex/CUP
De façon générale, l'interaction entre l'analyse lexicale et
l'analyse syntaxique est réalisée en donnant le contrôle à
l'analyseur syntaxique qui appelle une fonction fournie par
l'analyseur lexical pour obtenir les tokens
successifs en entrée.
L'interface entre les 2 niveaux d'analyse repose donc
principalement sur la définition de la valeur de retour de cette
fonction. La définition des tokens est réalisée
par l'analyseur syntaxique, mais l'instanciation des
nouveaux tokens est faîte par l'analyseur
lexical.
En terme de structure de données, un token contient :
- toujours la catégorie lexicale codée par une valeur entière (~ type énuméré),
- parfois une valeur sémantique,
- de façon optionnelle, d'autres informations de débogage comme la position dans le fichier source.
Dans le cas de CUP et JFlex, et à travers la configuration fournie par le fichier JflexCup.include :
- java-cup.runtime.Symbol next_token() est la méthode d'analyse lexicale utilisée par CUP et produite par JFlex.
- Le type Symbol est configurable à travers la classe java-cup.runtime.SymbolFactory. Ceci sera transparent (ou opaque !) pour le cours.
- Les méthodes Symbol TOKEN(int code) et Symbol TOKEN(int code, Object value) créent les valeurs de retour pour la méthode Symbol next_token().
- La classe sym.java produite par CUP contient la définition des catégories lexicales.
- La classe Yylex.java hérite de la classe sym.java pour utiliser cette définition.
Par exemple, on déclare dans CUP des tokens :
Avec une utilisation dans JFlex sous la forme :
Valeurs sémantiques des symboles
Il est utile ou nécessaire de pouvoir associer à des symboles une valeur représentant leur signification. Ces valeurs ne sont pas utilisées pour l'analyse syntaxique, mais seront nécessaires ultérieurement dans l'analyse sémantique.
Pour les symboles terminaux, le token représente la catégorie lexicale. La valeur sémantique permet alors de décrire la valeur dans la catégorie pour différents fragments de la même catégorie. Par exemple :
| Unité lexicale (Lexème) | Identifiant de Catégorie (Token) | Valeur dans la catégorie |
| "234" | ENTIER | valeur entière 234 |
| "+" | OP_PLUS | null |
| "+" | OP_BINAIRE | enum PLUS |
| "ma_Variable" | ID | String ou référence dans table de symbole |
Pour les symboles non-terminaux, associer une valeur sémantique permet :
- la construction explicite de l'arbre de syntaxe abstraite au cours de l'analyse. À l'application d'une production, on associe, au symbole en membre gauche, le nouveau nœud de l'arbre de syntaxe en cours de construction,
- l'évaluation à la volée de type calculatrice. Chaque production correspond à une évaluation partielle dont le résultat est stocké comme valeur sémantique du membre gauche,
- ou différents types de traitements intermédiaires entre les 2 cas précédents.
On associe une valeur sémantique à un symbole, en ajoutant un nom de type dans la déclaration du symbole. Tout type non primitif de JAVA est utilisable :
Une valeur sémantique est utilisable :
-
en lecture dans une action sémantique pour un
symbole quelconque en membre droit de la règle de
production. Ceci est réalisé en créant une variable locale
pour l'action :
axiome ::= exp DIVISE ENTIER:maVar {: if (maVar=0) Error("division par zéro"); :} ;Il existe aussi les variables maVarxleft, maVarxright qui contiennent des informations de localisation dans le source.
-
en écriture dans une action sémantique pour le
symbole non-terminal en membre gauche de la règle de
production. On utilise alors la variable locale
conventionnelle RESULT :
axiome ::= exp:e1 PLUS exp:e2 {: RESULT = new Arbre("+", e1, e2); :} ;
-
en écriture dans l'analyseur lexical pour un
symbole terminal. On utilise pour cela la
méthode TOKEN(int code, Object value)
[0-9]+ { return TOKEN(ENTIER, Integer.parseInt(yytext())); } [a-zA-Z]+ { return TOKEN(IDENT, yytext()); }Il n'y a pas de contrôle de type à la compilation sur les valeurs sémantiques entre le niveau lexical et le niveau syntaxique.
Exemple complet de couplage JFlex/CUP avec valeurs sémantiques
Traitements d'erreurs
Erreur de syntaxe
L'analyseur syntaxique produit une erreur de syntaxe dès que la lecture d'un token rend impossible toutes constructions d'un arbre de syntaxe valide. La méthode surchargeable void report_fatal_error(String message, Object info) est alors utilisée pour imprimer un message d'erreur et terminer l'exécution avec une exception JAVA.
CUP définit aussi une méthode void done_parsing(), qui permet de terminer l'analyse depuis une action sémantique et ainsi de gérer des erreurs « utilisateurs » dans l'analyse.
Resynchronisation sur erreur et symbole error
Le but est d'essayer de continuer l'analyse syntaxique après une erreur de syntaxe pour par exemple détecter plusieurs erreurs dans la même exécution. Un autre exemple d'utilisation est de faire un interpréteur ligne à ligne qui se contente de signaler et d'ignorer les lignes incorrectes.
CUP définit le symbole terminal conventionnel error utilisable dans les règles de production. Ce symbole est considéré comme reconnu dès qu'un token provoque une erreur de syntaxe. L'analyseur acceptera alors les tokens successifs comme appartenant au même symbole error et ceci jusqu'à lire un token qui peut suivre le symbole error selon la grammaire. L'analyse reprend alors un fonctionnement normal.
Exemples :
Ou une autre écriture :
Erreur lexicale
Une solution usuelle pour la gestion des erreurs lexicales (« caractère invalide ) est de renvoyer les erreurs lexicales vers le niveau syntaxique. Pour cela, il suffit d'utiliser au niveau lexical un ramasse-miettes sous la forme :
Instrumentation du code JAVA
CUP reprend un schéma semblable à JFlex pour intégrer du code utilisateur dans l'analyseur. On ne donne dans cette section que quelques éléments utiles et l'on se reportera au manuel officiel CUP pour une utilisation avancée de l'API.
Actions sémantiques "internes"
Les actions sémantiques sont possibles en milieu de règle. Il faut éviter d'en abuser car cela peut augmenter les risques de conflits dans l'analyse LR.
Une action en milieu de règle est en réalité une abréviation de la grammaire.
Une action est exécutée quand l'ensemble des symboles qui précédent sont reconnus et que le token suivant est lu en entrée. En effet, le lookahead est systématique dans CUP contrairement à Bison ou Yacc. Ce lookahead peut être gênant pour une utilisation interactive de l'analyseur. Il est par exemple utile de placer une action avant la reconnaissance de la fin de ligne, si l'on veut que l'action soit réalisée au moment où l'on tape la fin de ligne alors que la règle ne sera réellement réduite qu'après la lecture du premier token de la ligne suivante.
parser code vs action code
CUP offre deux variantes pour intégrer des méthodes ou des attributs utilisateurs dans l'analyseur.
CUP génère une classe parser qui contient une classe interne parser$CUP$parser$actions. Cette classe interne encapsule l'ensemble des actions sémantiques dans les règles de la grammaire. Ces actions sont ainsi isolées du moteur de l'analyseur qui est dans la classe parser proprement dite.
La directive action code {: :} permet de définir des méthodes et attributs utilisables dans les actions sémantiques. La directive parser code {: :} est dédiée pour du code utilisateur qui touche le moteur de l'analyseur LR. Cela permet par exemple de personnaliser le fonctionnement de l'analyseur, ou d'accéder à l'automate LR, ou de surcharger les méthodes de rapport d'erreur (report_fatal_error(), etc.). La préférence est d'utiliser la classe action pour ajouter du code utilisateur dans l'analyseur CUP, mais pour des raisons de visibilité on s'autorise aussi à utiliser la classe parser pour cela.
Action initiale ou finale
CUP fournit une directive init with {: :} pour réaliser une action initiale dans le constructeur de la classe, mais pas de moyen direct pour définir une action finale.
On peut facilement ajouter des actions initiales ou finales dans une spécification existante, en ajoutant une nouvelle première règle de la forme :
Priorité et Associativité
Imposer qu'une grammaire soit non ambiguë ou sans conflit dans une résolution LR est parfois impossible, souvent très contraignant, et généralement complexifie énormément l'écriture de la grammaire. Une solution est d'accepter certaines ambiguïtés dans la grammaire et de rajouter des règles de résolution de conflit externes à la définition des grammaires algébriques.
Grammaire ambiguë
Soit l'exemple d'une grammaire d'expressions avec des opérateurs binaires :
Il y a ambiguïté si l'on analyse ATOM OP1 ATOM OP2 ATOM qui peut produire deux arbres de syntaxe abstraite :
La même ambiguïté existe aussi pour l'expression ATOM OP1 ATOM OP1 ATOM.
Dans une résolution LR, le conflit se produit donc dans la position ATOM OP1 ATOM . OP2 avec le choix :
- réduire OP1 avec la première règle,
- décaler OP2 pour espérer appliquer la deuxième règle avant la première.
Résolution du conflit
Les règles de priorité et d'associativité s'appliquent pour résoudre un conflit Shift/Reduce avec un Shift qui empile un token OP2 et un Reduce qui "mange" un token OP1.
- Priorité, "OP1 != OP2".
Le conflit est résolu par :- Reduce, si OP1 est prioritaire sur OP2,
- Shift, si OP2 est prioritaire sur OP1,
- application de l'Associativité si les priorités sont égales,
- reste un conflit, sinon.
Des tokens avec la même priorité doivent avoir la même associativité. -
Associativité,
« OP1 == OP2 »
ou priorités égales.
Le conflit est résolu par :- Reduce, si OP1 est déclaré associatif gauche (precedence left OP1;),
- Shift, si OP1 est déclaré associatif droit (precedence right OP1;),
- une erreur de syntaxe, si OP1 est déclaré non associatif (precedence nonassoc OP1;),
- reste un conflit, sinon.
- Dans Yacc ou bison, les règles de priorité ne s'appliquent qu'entre des tokens avec une priorité définie explicitement. Le conflit Shift/Reduce reste non résolu sans priorité explicite de OP1 et de OP2.
- Dans CUP, les tokens sans priorité explicite sont considérés comme moins prioritaires que les tokens avec une precedence. Il y a donc résolution du conflit dès que OP1 ou OP2 a une priorité explicite.
Par exemple : avec une règle exp ::= exp PLUS exp, il y a un conflit signalé et résolu avec precedence left PLUS; si on ajoute ensuite une règle exp ::= exp FOIS exp, il y a un nouveau conflit, non signalé par CUP car résolu par FOIS sans precedence est moins prioritaire que PLUS avec precedence.
Exemples sur des opérateurs usuelles
Test de priorité et associativité (bonus)
Un exemple de programmes (en JAVA ou en C) pour tester les règles d'évaluation d'un langage, ou d'un compilateur du langage : TestEval.java,
.CSC4251_4252, Télécom SudParis, Pascal Hennequin, J.Paul Gisbon, Denis Conan Last modified: December 2024
