Compilation : De l'algorithme à la porte logique

Mémento d'utilisation de CUP

Ce mémento résume les fonctionnalités de 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.

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 :

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 :

CupParseMin.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
-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 :

cup.bnf

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 :

syntax.cup

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.

Tous 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. Petit 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 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 :

      terminal TOK1, TOK2;
      terminal ENTIER, 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); }

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. 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 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 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

numeration.jflex

numeration.cup

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()...)

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.

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 ::=   /* Début 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 ::=   /* Début de fichier */
        |  axiome ligne_ok {: /*...*/ :}     NL 
        |  axiome error {: System.out.println("Ligne incorrect"); :}   NL 
;

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 :

/*.....*/
[^]    { WARN("caractère invalide"); return TOKEN(error); }

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.

v ::= s1 s2 {: action :} s3 s4 ;

est équivalent à

 vv ::= s1 s2 {: action :} ;
 v ::= vv s3 s4 ;

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éaliser 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.

Dans le cas d'une action placée après le token error il faut en réalité lire au moins trois tokens valides 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 pour une utilisation interactive.

`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(), ...). 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 :

newAxiome ::= {: /* action initiale */ :} axiome {: /* action finale */ :}

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 :

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.

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.

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)

Quelle est la priorité des tokens qui n'ont pas de directives precedence ?

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.

En conséquence, quand on ajoute une règle avec un nouveau token qui génère une ambiguïté nouvelle dans une grammaire, bison signale un conflit Shift/Reduce à résoudre, alors que CUP peut considérer le nouveau conflit déjà résolu.
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

5+2+4 == (5+2)+4 == 5+(2+4)  # precedence right '+' ou left '+'
++a + ++a + a                # '+' pas si associatif en informatique!  
5-2-4 == (5-2)-4 != 5-(2-4)  # precedence left '-'
   # de même pour associativités de '*' 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 !)

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, TestEval.c.

CSC4251-52 (CSC 4536), TELECOM SudParis, P. Hennequin,Last modified: Juillet 2022