Implantation d'un analyseur sémantique en une passe

Un analyseur en une passe est basé sur un parseur couplé à un lexeur. On peut utiliser le script EBNF pour typer les tokens lus et les non-terminaux de la grammaire. Lors de la construction de l'analyseur, il est alors possible de passer deux objets en paramètres :

• un TerminalEvaluator qui permet de donner la valeur de chaque token typé lu.
• un GrammarEvaluator qui permet, à chaque réduction donnée, d'effectuer certaines opérations et, quand le non-terminal résultant est typé, de construire la valeur de non-terminal, en fonction des valeurs, fournies par le TerminalEvaluator, des terminaux et des valeurs, fournies par le GrammarEvaluator (donc this), des non-terminaux présents dans le membre droit de la production.

Le TerminalEvaluator contient une méthode tok(B data) pour chaque token typé tok. L'argument data est le buffer contenant le token reconnu.

Le GrammarEvaluator contient, pour chaque production p, une méthode p(...) appelée lorsqu'il y a une réduction par p. Ses arguments sont les valeurs des différents terminaux et non-terminaux typés de la partie droite de p. Sa valeur de retour est du type du non-terminal résultant de la réduction, s'il est typé.

Soit l'exemple simple d'EBNF ci-dessous :

Le parseur décrit reconnaît des expressions arithmétiques. On note que l'on associe au token value et au non-terminal expr, le type de base int.

Dans le fichier EvaluationAnalyzer.java qui implémente l'analyseur, un TerminalEvaluator et un GrammarEvaluator sont instanciés. Ils sont passés en paramètre lors de la construction de l'analyseur comme montré ci-dessous. L'analyseur affiche la valeur de l'expression arithmétique tapée en entrée standard.

L'exemple ci-dessous montre un analyseur qui convertit une expression arithmétique sous une autre forme et affiche son résultat. Vous trouverez son code dans l'exemple translation. Par exemple, l'expression 12 + 34 - 6 est analysée comme:

				Translation is: - + 12 34 6
				Result is: 40
			

Le parseur décrit reconnaît des expressions arithmétiques. On note que l'on associe au token/terminal value, le type de base int. On observe aussi que l'on type un non-terminal expr par un ExprContent, classe Java qui est importée dans la section imports. Un ExprContent est formé d'un string (traduction) et d'un entier (valeur).

L'analyseur est codé dans la classe TranslationAnalyzer.java:

Comme indiqué dans la description du format EBNF, il est possible de séparer la partie syntaxique de la partie sémantique en écrivant deux fichiers EBNF. La génération des classes de base de l'analyseur est configurée dans le build.xml (fichier build2.xml exemple translation)

EBNF pour la syntaxe

EBNF pour la sémantique

build.xml

Lorsque que l'on souhaite avoir un analyseur en plusieurs passes, on peut générer automatiquement l'AST puis le parcourir à l'aide de visiteurs. Pour cela, il faut ajouter l'attribut generateast="true" de l'élément ebnf dans le build.xml (cf exemple ci-dessous). A la génération des classes de base de l'analyseur, tatoo génère un ASTGrammarEvaluator qui est un GrammarEvaluator chargé de construire l'AST de l'expression analysée. Les noeuds de l'AST sont des instances de classes qui correspondent aux productions de la grammaire. Ces classes sont générées automatiquement. Leurs noms correspondent aux noms des productions associées. Les fils de ces noeuds sont excessibles à l'aide de getters des éléments pertinents de la partie droite de la production associée: terminaux typés et non-terminaux. Elles sont visitables par leur méthode accept. Cette méthode prend en argument un Visitor<R,P,E> qui contient une méthode visit par noeud de l'AST. R, P et E sont respectivement les types de retour, des paramètres (deuxième argument) et des exceptions levées dans ces méthodes. L'exemple ci-dessous correspond à un analyseur qui évalue des expressions arithmétiques entières à l'aide d'un visiteur. Il instancie un ASTGrammarEvaluator (pour créer l'AST) et un TerminalEvaluator (pour évaluer les terminaux) qui sont utilisés dans l'analyseur (méthode Analyszer.run). La racine de l'AST est récupérée grâce à la méthode getStart() de l'ASTGrammarEvaluator, une fois l'analyse terminée. Il s'agit ensuite d'écrire un visiteur et de l'utiliser pour parcourir l'AST en fonction de la tâche que l'on a à effectuer.

EBNF

build.xml

Visiteur pour l'évaluation d'une expression arithmétique

Analyseur