CSC4536– Compilation : De l'algorithme à la porte logique

Portail informatique
Ce mémento résume les fonctionnalités de java-cup et les illustre avec des exemples. On suppose l'utilisation des fichiers Jflex.include, JflexCup.include, et CupParse.java qui définissent le contexte d'utilisation de JFlex et CUP pour le cours.
On se reportera aux pages du manuel CUP, pour des informations plus complètes.
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 : java -jar jflex.jar foo.jflex # => Yylex.java java -jar java-cup.jar foo.cup # => parser.java sym.java javac -cp .:java-cup-runtime.jar *.java # => *.class java -cp .:java-cup-runtime.jar CupParse

Un exemple minimal pour la classe CupParse.java :

Options utiles de CUP:
--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
-nontermsajoute 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
Huit sections ordonnées, éventuellement optionnelles ou répété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

Un exemple générique :
Les symboles de la grammaire se déclinent en :
  • Symboles Terminaux ou constantes ou tokens qui correspondent aux catégories lexicales reconnues par l'analyseur lexical
  • Symboles Non-Terminaux ou variables qui définissent à travers les règles de production les formes syntaxiques valides
Pour une bonne lisibilité, on prendra soin de différencier le nommage ou la typographie des deux types de symboles.

Tout les symboles doivent être déclarés dans la spécification CUP: terminal ENTIER, PLUS, L_PARENT, R_PARENT; nonterminal axiome, expr; non terminal instruction; Il existe de plus 3 symboles conventionnels prédéfinis :
  • terminal "EOF" qui signifie : il n'y a plus de tokens. ( Bugue : EOF n'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 (cf. plus loin)
  • nonterminal "$START" indique la fin positive de l'analyse. Conventionnellement, CUP ajoute une règle de la forme :"$START ::= start_symb EOF;".

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 debugging 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 (directive %cup)
  • 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 (directive %extends sym)

Par exemple, on déclare dans CUP des tokens : terminal TOK1, TOK2; terminal ENTIER; terminal IDENT; La classe sym.java ressemble alors à : public class sym { /* terminals */ public static final int EOF = 0; public static final int error = 1; public static final int TOK1 = 2; public static final int TOK2 = 3; public static final int ENTIER = 4; public static final int IDENT = 5; public static final String[] terminalNames = new String[] { "EOF", "error", "TOK1", "TOK2", "ENTIER", "IDENT", }; Avec une utilisation dans JFlex sous la forme: %% %include Jflex.include %include JflexCup.include /*....*/ %% {EXP1} { return TOKEN(TOK1); } [0-9]+ { return TOKEN(ENTIER); } [a-zA-Z]+ { return TOKEN(IDENT); }
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é lexicaleIdentifiant de Catégorievaleur dans la catégorie
"234" Token ENTIERvaleur entière 234
"+" Token OP_PLUSnull
"+" Token OPBINenum PLUS
"maVariable" Token IDENTString 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. A 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 (Object) de Java est utilisable : terminal Integer ENTIER; terminal String IDENT; nonterminal Arbre exp, axiome; nonterminal Map<? extends String , Integer> symb ; 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 nonterminal 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.
Réaliser la numération au niveau syntaxique est conceptuellement légitime mais n'est pas une bonne idée en pratique. Dans la "vraie vie", la numération est réalisée au niveau lexical en écrivant explicitement le calcul ou en utilisant les fonctions ad hoc disponibles partout (atoi(), sscanf(), parseInt() ...)

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.

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 En réalité l'analyseur attend 3 tokens valides pour décider de la resynchronisation. Ceci sera gênant dans une utilisation interactive!

Exemples : /* resynchronisation sur ; */ instruction ::= ... | error SEMICOLON /* on error, skip until ';' is read */ ; /* resynchronisation sur parenthèse fermante */ Parent_expr ::= LEFTPAR expr RIGHTPAR | LEFTPAR error RIGHTPAR /* may be not the matching one */ ; /* Schéma d'analyse ligne a ligne avec erreur */ // NL est un token fin de ligne axiome ::= /* Debut de fichier */ | axiome ligne NL ; ligne ::= ligne_ok {: /*...*/:} | error {: System.out.println("Ligne incorrect"); :} /* seul NL peut suivre error => resynchronisation sur fin de ligne */ ; ligne_ok ::= /* ... */ Ou une autre écriture : /* Schéma d'analyse ligne a ligne avec erreur */ axiome ::= /* Debut de fichier */ | axiome ligne_ok {: /*...*/ :} NL | axiome error {: System.out.println("Ligne incorrect"); :} NL ; ligne_ok ::= /* ... */

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-miette sous la forme : /*.....*/ [^] { WARN("caractère invalide"); return TOKEN(INCONNU); } // ou return TOKEN(error) pour éviter de déclarer INCONNU dans CUP

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.
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 : v ::= s1 s2 {: action :} s3 s4 ; est équivalent à v ::= vv s3 s4 ;
vv ::= s1 s2 {: action :} ;

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. Dans ce cas, il est par exemple utile de placer une action avant la reconnaissance de la fin de ligne. Dans le cas d'une action placée après le token error il faut en réalité lire au moins trois token valide en avance pour décider de la resynchronisation et donc exécuter l'action. Il n'y a pas de moyen de corrigé ce défaut dans l'utilisation interactive.

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 action. Cette classe action 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 les 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 customiser 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(), ...)

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 : newAxiome ::= {: /* action initiale */ :} axiome {: /* action finale */ :}
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.
Soit l'exemple d'une grammaire d'expressions avec des opérateurs binaires : expr ::= expr OP1 expr | expr OP2 expr | ATOM ; Il y a ambiguïté si l'on analyse ATOM OP1 ATOM OP2 ATOM qui peut produire deux arbres de syntaxe abstraite :
Dérivations :  Gauche     ou    Droite      
                 OP2	         OP1        
                 / \	        /  \       
               OP1  ATOM      ATOM  OP2     
               / \   	           / \     
            ATOM  ATOM	        ATOM  ATOM 
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.

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.
  1. 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é
  2. 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
    • Erreur de syntaxe, si OP1 est déclaré non associatif, precedence nonassoc OP1
    • Reste un conflit sinon.

La priorité est fixée par l'ordre des directives precedence dans la spécification. Dans un même precedence, les tokens ont la même priorité et la même associativité. Entre des precedence successifs les tokens sont de priorité croissante. precedence left OP1 OP2 // OP1 et OP2 même priorité precedence right OP3 // OP3 prioritaire sur OP1 et OP2 precedence left OP4 // OP4 prioritaire sur OP1,OP2,OP3 il existe aussi la possibilité de définir une priorité sur une règle plutôt que sur un token. L'exemple de base est le cas d'un token MINUS dont la priorité est différente dans l'utilisation comme opérateur unaire ou binaire (cf. %prec dans le manuel)
5+2+4 == (5+2)+4 == 5+(2+4)  precedence right '+' ou left '+'
   NB : ++a + ++a + a == ?   '+' pas si associatif en informatique!  
5-2-4 == (5-2)-4 != 5-(2-4)  precedence left '-'
idem pour '*' et '/'

A=B=5  == A=(B=5)            precedence right '='

5+2*4 == 5+(2*4) != (5+2)*4  '*' prioritaire sur '+'
5-2+4 == (5-2)+4 != 5-(2+4)  même priorité et associativité gauche
-3^2 == 9  ou -9 ?           '^' prioritaire sur '-' unaire (ou pas !)

CSC 4536, TELECOM SudParis, P Hennequin, Last modified: Nov 2018