Un compilateur a quelque chose de magique: traduire du beau code objet en une infâme bouillie assembleur exécutable par un processeur semble tenir du miracle. Bien sûr avec .NET les choses ont un peu changées puisque la bouillie infâme est du code IL objet qui est donc moins indigeste que de l'assembleur. Malgré tout écrire un compilateur semble réservé aux barbus de l'informatique.
Pourtant à part l'arrivée du code IL, une autre chose a changée avec .NET: la Common Language Specification (CLS). En effet la plate-forme .NET n'a pas été pensée pour le C# ou le VB.NET, le .NET Framework a été nativement pensé pour être multi-langage. Cela n'a l'air de rien mais ça a un impact non seulement sur la richesse du code IL mais aussi sur le .NET Framework lui-même. Ainsi avec le .NET Framework on peut facilement générer et compiler du code dynamiquement même lorsqu'on ne dispose sur son poste que du simple .NET Framework Redistributable Package, c'est à dire même pas un compilateur en ligne de commande ! Alors est-ce réellement facile d'écrire un compilateur en .NET . Est-ce réellement facile d'ajouter son propre langage à la plate-forme ? C'est ce que nous allons voir dans cet article.
Et pour illustrer cet article si on tentait l'expérience ? si on écrivait nous aussi notre compilateur ? Pour être intéressant sans être trop complexe pour tenir dans les quelques pages de cet article, il nous faut un langage suffisamment éloigné de ce que nous connaissons (C#/VB.NET) tout en restant simple. Comme les langages de script sont à la mode, je propose d'écrire un compilateur JavaScript. Bon d'accord pas tout à fait le JavaScript que l'on connait, nous allons le simplifier mais nous allons quand même garder quelques particularités du JavaScript. Etudions-les sur un exemple:
var i = 100; write(i); function foo(param1,param2) { write(param1); if (i > 50) { var k = 'Go'; write(k); } } j = 12; i = "100"; write(i+j); foo(j);
Qu'est ce qu'il y a de spécifique à JavaScript dans ce code:
Notre objectif est donc d'écrire un compilateur pour ce nouveau langage que nous appellerons modestement MyJScript.
Pour aller plus loin: MyJScript se base sur les spécifications JScript 5.6 qui est le JavaScript que l'on retrouve dans une page HTML. Microsoft propose également un JScript.NET qui prend quelque liberté par rapport au "standard" mais qui est directement compilable. |
Un compilateur est un programme qui traduit un fichier source d'un langage donné en langage assembleur. Pour l'exemple qui nous intéresse cela signifie traduire un programme MyJScript comme celui de l'exemple ci-dessus en du code IL et encore plus précisément, traduire un fichier texte avec une extension .MJS en un fichier exécutable .EXE. Sur un schéma cela donne quelque chose comme ça:
Mais pour écrire un compilateur il faut passer par plusieurs étapes. Vous avez probablement eut des cours de Compilation pendant vos études non ? Bon alors pour ceux qui étaient cachés au fond de l'amphi, voici un rappel simplifié des étapes:
Etudions chacune de ces étapes pour notre compilateur MyJScript.
L'analyse lexicale est quelque chose que tout le monde fait sans le savoir. Pour simplifier, il suffit d'imaginer que faire de l'analyse lexicale c'est simplement découper une chaîne de caractères en différentes parties. Prenons un fichier source MyJScript quelconque:
var i = 100;
Qu'est ce que signifie en faire son analyse lexicale ? Il s'agit simplement de le découper en différents "mots" ou "token" qui représentent les éléments que l'on connait. Ici: "var", l'identifiant "i", un égal, le nombre "100" et un point virgule. A noter que l'on oubli volontairement les espaces qui n'ont pas de signification particulière pour le MyJScript (mais ce n'est pas le cas de tous les langages, cf. COBOL ou Fortran).
Voici la liste des mots de notre langage MyJScript:
+ - * / = == != > < >= <= ( ) { } , ; var function if else while return <Number> <String> <Ident>
On y trouve plusieurs choses:
Excepté cette dernière catégorie, écrire un analyseur lexical est donc assez simple, il suffit de reconnaître dans une chaîne d'entrée un ensemble de chaînes connues.
La seule petite complexité est sur ce que nous appelons les "valeurs". Une valeur n'est pas décrite par une chaîne de caractères mais plutôt par un format: un nombre est une suite de chiffre, une chaîne est une suite de caractères entre des simples ou des doubles-quotes, un identifiant est une suite de caractères. Si on appelle cela des "valeurs" c'est qu'en plus de savoir quel mot nous avons rencontré, il est important de connaître la "valeur" du mot.
Pour implémenter notre analyseur lexical, la première chose à faire est d'identifier nos tokens. Pour cela, nous allons simplement créer une énumération C#. Notre analyseur n'aura donc qu'a renvoyer la bonne valeur de cette énumération. A noter que nous avons ajouté à la liste initiale un token pour la fin de fichier (EOF) et un token pour un mot non reconnu (Error).
/// <summary> /// Token types. /// </summary> public enum TokenType { EOF = 0, OperatorPlus = 257, OperatorMinus, OperatorMult, OperatorDiv, OperatorEqual, OperatorEqualEqual, OperatorNotEqual, OperatorGreater, OperatorLess, OperatorGreaterOrEqual, OperatorLessOrEqual, LeftPar, RightPar, LeftBra, RightBra, Coma, SemiColon, Number, String, Ident, Var, Function, If, Else, While, Return, Error }
Ecrivons l'interface de notre analyseur lexical en quelques lignes de C#:
// // Interface de l'analyseur lexical // public interface ILexer { // // Retourne le prochain token // int token(); // // Quelle est la valeur du token courant ? // Object value(); // // Peut-on encore avancer ? // bool advance(); }
Notre analyseur doit donc pouvoir avancer de mot en mot en utilisant la méthode "token", retourner la valeur du mot courant avec la méthode "value" et ceci jusqu'à ce que la méthode "advance" retourne "false".
Nous avons donc tout ce qu'il nous faut pour écrire les tests unitaires. En effet, s'il est bien un domaine où il est plus que pertinent de faire des tests unitaires, c'est bien l'écriture d'un compilateur. D'une part cela nous permet de garantir le bon fonctionnement des différentes couches de notre compilateur isolément et d'autres part cela nous oblige à concevoir une architecture suffisamment modulaire pour être testable.
Voilà donc le test unitaire de notre exemple de départ:
Lexer l1 = new Lexer("var i = 100;"); Assert.AreEqual((int)Lexer.TokenType.Var, l1.token()); Assert.AreEqual((int)Lexer.TokenType.Ident, l1.token()); Assert.AreEqual("i", l1.value()); Assert.AreEqual((int)Lexer.TokenType.OperatorEqual, l1.token()); Assert.AreEqual((int)Lexer.TokenType.Number, l1.token()); Assert.AreEqual(100, l1.value()); Assert.AreEqual((int)Lexer.TokenType.EOF, l1.token()); Assert.IsFalse(l1.advance());
Le but de l'article n'est pas de décrire chaque ligne de code de notre compilateur, nous nous intéresserons donc uniquement aux endroits clés. L'ensemble du code source est disponible en téléchargement. Voir à la fin de l'article.
Commençons par l'implémentation de la reconnaissance des opérateurs. Il s'agit simplement de parcourir la chaîne "source" caractère par caractère :
private bool IsOperator(out TokenType res) { char next = source[index]; int nextNextIndex = index+1; switch (next) { case '+': res = TokenType.OperatorPlus; break; // ... case '=': if (nextNextIndex < source.Length && source[nextNextIndex] == '=') { res = TokenType.OperatorEqualEqual; index++; Location.Col++; } else res = TokenType.OperatorEqual; break; // ... default: return false; } index++; Location.Col++; return true; }
On notera le cas du "=": Lorsqu'on rencontre le caractère "=" on peut considérer qu'il s'agit de l'opérateur d'affectation sauf s'il est suivi d'un autre "=" car dans ce cas il s'agit de l'opérateur d'égalité "==". Idem pour l'opérateur inférieur et inférieur ou égal.
Comment reconnaître les "valeurs" ? Tout simplement en utilisant les expressions régulières .NET qui sont précisément faites pour ça. On donne un format et on vérifie qu'une chaîne respecte ce format. Voilà ce que cela donne:
private const string patternQuotedString = "^'[^'\r\n]*'"; private const string patternDoublequotedString = "^\"[^\"\r\n]*\""; private bool IsString() { // Tester d'abord si c'est une chaine avec des simples quotes string toTest = source.Substring(index); Match match = Regex.Match(toTest, patternQuotedString); // Sinon tester si c'est une chaine avec des doubles quotes if (!match.Success) { match = Regex.Match(toTest, patternDoublequotedString); if (!match.Success) return false; } // Extraire les valeurs int length = match.Length; string stringValue = source.Substring(index+1, length-2); tokenValue = stringValue; index += length; Location.Col += length; return true; }
Pour les mots-clé et les identifiants, c'est un peu différent. En effet, si on réfléchi, on se rend compte qu'un mot-clé n'est rien d'autres qu'un identifiant réservé par le langage. Bref, les identifiants et les mots-clés ont le même format et on les reconnaît donc de la même manière. Il suffit donc de reconnaître le format d'un identifiant puis de le comparer à la liste des mots-clés connus. Voilà ce que l'on peut faire:
private const string patternIdent = "^[_A-Za-z][_A-Za-z0-9]*"; static Lexer() { keywords = new Dictionary<string, TokenType>(); keywords.Add("var", TokenType.Var); keywords.Add("function", TokenType.Function); // ... } private bool IsIdentOrKeyword(out TokenType res) { // Tester si cela correspond à un identifiant Match match = Regex.Match(source.Substring(index), patternIdent); if (!match.Success) return false; // Extraire la valeur int length = match.Length; string name = source.Substring(index, length); index += length; Location.Col += length; // Est-ce que c'est un mot connu ? if (keywords.ContainsKey(name)) { res = keywords[name]; tokenValue = name; return true; } // Sinon c'est un identifiant res = TokenType.Ident; tokenValue = name; return true; }
On commence par initialiser un dictionnaire avec tous les mots-clés et lorsqu'on rencontre un identifiant on le compare à la liste des mots-clés connus.
Voilà, notre analyseur lexical est presque fini, il suffit de tout remettre en forme dans notre méthode "token". Pour cela on se contente de supprimer les espaces puis de tester chacun des éléments reconnus. Ce qui ressemble à ceci.
public int token() { // Nettoyer les blancs StripWhiteSpace(); // Tester chaque sorte de mot if (IsOperator(out nextToken)) return (int)nextToken; else if (IsPunct(out nextToken)) return (int)nextToken; else if (IsNumber()) return (int)TokenType.Number; else if (IsString()) return (int)TokenType.String; else if (IsIdentOrKeyword(out nextToken)) return (int)nextToken; // Unknown return (int)TokenType.Error; }
Pour aller plus loin: L'analyseur
lexical décrit ici n'est pas réellement optimisé. En
effet, l'utilisation d'expressions régulières a
l'inconvénient de nécessiter de multiples comparaisons:
une pour chaque expression régulière testée. Si on recherche la performance, il est plus judicieux de construire un analyseur lexical comme un automate à état. Chaque caractère rencontré fait avancer l'automate jusqu'au point où un mot est reconnu. Sur notre exemple, cela éviterais ainsi d'avoir deux expressions régulières différentes pour reconnaître une chaîne de caractères. Ce type d'approche est d'ailleurs utilisée dans les outils dérivants de Lex. Ces outils génèrent un automate à partir de l'ensemble des expressions régulières correspondants aux mots du langage. Lex est un outil destiné au langage C mais il en existe des portages en .NET, par exemple CSLex. |
Prenons un exemple de source MyJScript comme celui ci-dessous et passons-le à notre analyseur lexical:
var } function + i 'Hello',
Chacun des mots est reconnu correctement par l'analyseur lexical: le mot-clé "var", l'accolade fermante, le mot-clé "function", le plus, l'identificateur "i", la chaine de caractères "Hello" et la virgule. L'analyseur lexical indique donc que le code source est correct. Mais évidement s'il est bien correct d'un point de vue lexical, il n'est pas "syntaxiquement" correct.
Le rôle d'un analyseur syntaxique est précisément de s'assurer que l'enchaînement des mots reconnus forme bien des séquences valides dans le langage. Bref, un analyseur syntaxique est un outil qui vérifie la syntaxe du langage.
La grammaire d'un langage est l'ensemble des séquences de mots correctes. Traditionnellement, la grammaire s'exprime en Backus Naur Form (BNF) ou, pour parler plus simplement, par compositions de règles.
Par exemple pour la grammaire de notre MyJScript nous pouvons exprimer les règles suivantes:
Bref, par simple logique, on va arriver à décrire toute la syntaxe de notre langage. Voilà ce que cela donne sur la grammaire du MyJScript.
program: opt_list_function_statement opt_list_function_statement: list_function_statement | /* Nothing */ list_function_statement: list_function_statement function_or_statement | function_or_statement function_or_statement: function_decl | statement function_decl: FUNCTION IDENT LPAR opt_list_param RPAR block opt_list_param: list_param | /* Nothing */ list_param: list_param CM IDENT | IDENT block: LBRA opt_list_statement RBRA opt_list_statement: list_statement | /* Nothing */ list_statement: list_statement statement | statement statement: decl_var | setvar | if_else | while | proc_call | return decl_var: VAR IDENT opt_init SC opt_init: EQ expr | /* Nothing */ setvar: IDENT EQ expr SC if_else: IF LPAR cond_expr RPAR block_or_statement ELSE block_or_statement | IF LPAR cond_expr RPAR block_or_statement funct_call: IDENT LPAR opt_list_expr RPAR proc_call: funct_call SC while: WHILE LPAR cond_expr RPAR block_or_statement return: RETURN expr SC | RETURN SC block_or_statement: block | statement cond_expr: expr EQEQ expr | expr NE expr | expr GT expr | expr LS expr | expr GTEQ expr | expr LSEQ expr expr: expr PLUS expr | expr MULT expr | expr MINUS expr | expr DIV expr | funct_call | literal literal: NUMBER | STRING | IDENT opt_list_expr: list_expr | /* Nothing */ list_expr: list_expr CM expr | expr
Comment lire cette construction:
L'intéressant dans cette construction c'est qu'elle nous ramène une fois de plus à la notion d'automate à état. Pour reconnaître les règles, on part de l'état initial qui est "program" et on essai d'avancer d'état en état en fonction des mots que l'on va rencontrer. Chaque fois que l'on arrive à construire une règle on "remonte" et si on arrive à une impossibilité, c'est que la suite de mots en entrée est invalide: on dit qu'il y a une erreur de syntaxe.
Ecrivons l'interface de notre analyseur syntaxique. Son rôle est simple: il doit valider qu'une chaîne d'entrée est conforme aux règles de la grammaire MyJScript et nous indiquer les erreurs si ce n'est pas le cas.
// // Interface de l'analyseur syntaxique // public class Parser { // // Constructeur, initialise la chaine à analyser // public Parser(string source); // // Lancer l'analyse // public bool Parse(); // // L'ensemble des erreurs rencontrées // public CompilerErrorCollection Errors; }
A noter l'utilisation de la classe CompilerErrorCollection du .NET Framework qui, avec la classe CompilerError, permet de représenter une erreur de compilation c'est à dire: un nom de fichier, un numéro de ligne, un numéro de colonne, un code erreur et une description. C'est exactement ce dont nous avons besoin pour représenter une erreur.
Ecrivons le test unitaire de notre exemple de départ:
Parser p1 = new Parser("var } function + i 'Hello',"); Assert.IsFalse(p1.Parse()); Assert.AreEqual(1, p1.Errors.Count); Assert.AreEqual("MJS0300", p1.Errors[0].ErrorNumber); // MJS300 = Erreur de syntaxe Assert.AreEqual(1, p1.Errors[0].Line); Assert.AreEqual(5, p1.Errors[0].Column);
Comment passer de notre grammaire MyJScript au code de l'analyseur syntaxique ? Nous l'avons dit, l'idée est d'écrire un automate à état pour passer de règle en règle. Mais construire un automate en fonction d'un ensemble de règles n'a rien de trivial.
Heureusement, nos ancêtres informaticiens ont depuis longtemps construit des outils pour nous faciliter la vie. Le plus connu d'entre eux est YACC (Yet Another Compiler Compiler: Encore un compilateur de compilateur :-). YACC génère à partir d'une grammaire BNF du type de celle ci-dessus un programme C permettant de reconnaitre la grammaire.
YACC a depuis longtemps était porté pour d'autres langages et il en existe notamment un portage pour .NET, JAY. C'est JAY que nous utiliserons ici.
JAY est un utilitaire en ligne de commande qui prend en paramètre un fichier de règles JAY qui ressemble à notre grammaire ci-dessus et génère sur la sortie standard un fichier C# contenant le code de l'analyseur syntaxique. En gros, quelque chose comme-ça:
jay Parser.jay > Parser.cs
Le code ci-dessous est un extrait de ce qui est généré par JAY. Notez que même si le code généré est complexe et trouve clairement son origine dans le langage C, il y est question de "state", "stack", "token" et "value" ce qui fait bien penser à un automate. Notez également que la méthode "yyparse" est également suivi de plusieurs tableaux représentant les états et les transitions de l'automate.
public Object yyparse(ILexer yyLex) { if (yyMax <= 0) yyMax = 256; // initial size int yyState = 0; // state stack ptr int [] yyStates = new int[yyMax]; // state stack Object yyVal = null; // value stack ptr Object [] yyVals = new Object[yyMax];// value stack int yyToken = -1; // current input int yyErrorFlag = 0; // #tks to shift int yyTop = 0; goto skip; yyLoop: yyTop++; skip: for (;; ++ yyTop) { if (yyTop >= yyStates.Length) { // dynamically increase int[] i = new int[yyStates.Length+yyMax]; System.Array.Copy(yyStates, i, 0); yyStates = i; Object[] o = new Object[yyVals.Length+yyMax]; System.Array.Copy(yyVals, o, 0); yyVals = o; } yyStates[yyTop] = yyState; yyVals[yyTop] = yyVal; ... } protected static short [] yyDgoto = { 1, 9, 2, 10, 11, 12, 80, 40, 71, 81, 89, 72, 92, 87, 93, 14, 15, 16, 17, 18, 19, 39, 41, 42, 82, 88, 32, 51, 37, 33, 52, }; ...
Comment utiliser ce code pour notre analyseur syntaxique ? En fait c'est relativement simple car c'est la méthode "yyparse" ci-dessus qui effectue le parsing. Nous devons simplement lui transmettre en paramètre l'analyseur lexical que nous avons défini au paragraphe précédent (interface ILexer) et le tour est joué. Voilà ce que cela donne sur notre interface:
public Parser(string source) { lexer = new Lexer(source); report = new Report(); // Utilisé pour stocker les erreurs } public bool Parse() { yyparse(lexer); if ( report.Errors.Count != 0 ) return false; else return true; }
La gestion des erreurs n'est pas plus complexe. Lorsque la méthode "yyparse" rencontre une erreur, elle appelle une méthode "yyerror" en lui spécifiant le mot actuel, l'état de l'automate où il se trouve et la liste des règles qu'il s'attendait à rencontrer. Dans notre cas, nous redéfinissons cette méthode pour y stocker l'erreur.
public void yyerror (int state, int token, object tokenValue, string[] expecting) { report.Error(lexer.Location, state, token, tokenValue, expecting); }
A noter que de manière à pouvoir indiquer l'endroit de l'erreur, l'analyseur lexical conserve la position courante (ligne et colonne) dans une structure "Location" qui est transmise lors de la création de l'erreur.
Pour aller plus loin: JAY n'est pas le
seul générateur existant,
d'autres outils gratuits ou payants permettent également
d'obtenir le même résultat. On notera par exemple: Attention néanmoins: la différence entre ces outils viens généralement de la forme de grammaire reconnue LALR(1) pour YACC ou CSTools, LL(k) pour ANTLR ou JavaCC (un autre outil réservé au monde Java), la facilité de construction des règles de grammaire est directement lié à ce choix de départ. Voir les liens ci-dessus pour plus de détail. |
Lorsqu'on écrit un analyseur syntaxique, c'est rarement pour se limiter à déterminer qu'une chaîne de caractères est valide. Pour notre compilateur MyJScript par exemple, nous souhaitons générer du code IL exécutable qui fait le même traitement. Plus généralement, il est courant lorsqu'on écrit un compilateur ou un interpréteur, de construire un "arbre syntaxique".
Un arbre syntaxique est la représentation en mémoire d'un ensemble d'éléments de notre langage. Prenons une instruction MyJScript simple, une affectation:
res = n * (n - 1);
L'arbre syntaxique correspondant à cette instruction pourrait être:
Pourquoi construire un arbre ? Tout simplement parce que c'est la structure la plus simple à parcourir. Si chaque nœud correspond à un objet en mémoire: pour écrire un interpréteur il suffit d'évaluer chaque nœud en remontant pour trouver le résultat de l'expression et, pour écrire un compilateur il suffit d'utiliser un visiteur pour générer le code correspondant à chaque nœud.
CodeDOM est une API du .NET Framework qui permet de représenter du code en mémoire. L'API CodeDOM propose des objets pour toutes les structures supportées par la CLS (Common Language Specification). On trouve donc dans CodeDOM des objets pour représenter les classes, les méthodes, les propriétés, les variables, les instructions, les expressions, ...
L'utilisation de CodeDOM est très simple: il suffit de connaître la classe correspondant à ce que l'on veut représenter est d'en créer des instances. Reprenons notre exemple précédent, voilà comment le représenter en CodeDOM:
CodeStatement assign = new CodeAssignStatement( new CodeVariableReferenceExpression("res"), new CodeBinaryOperatorExpression( new CodeVariableReferenceExpression("n"), CodeBinaryOperatorType.Multiply, new CodeBinaryOperatorExpression( new CodeVariableReferenceExpression("n"), CodeBinaryOperatorType.Subtract, new CodePrimitiveExpression(1))));
Ce qui donne l'arbre:
Pour notre compilateur MyJScript, nous souhaitons construire un arbre syntaxique, notre idée est donc de transformer du MyJScript en du CodeDOM. Mais cela est-il réellement possible ? Plusieurs spécificités différentient le MyJScript du C# ou du VB.NET tel qu'il sont spécifiés par la CLS. Voilà les principales caractéristiques du MyJScript non prises en charge :
Ces points sont-ils si difficiles à traiter ? N'existe t'il pas un moyen simple de faire correspondre du code MyJScript à du code "standard" .NET ? Etudions les difficultés une à une:
Les variables globales n'existent pas et les fonctions doivent être attachées à des classes: L'un des points qui différencie le MyJScript d'un langage plus objet est qu'il n'est pas nécessaire de créer une classe pour commencer à écrire du code. Et si nous supposions qu'un programme MyJScript est en fait constituée d'une classe seule qui encapsule tout le code ? Cela nous permettrais de dire que les variables globales sont les variables de classe et que les fonctions sont les méthodes de classe. Cela résout les points 1 et 2.
Les instructions doivent être attachées à des méthodes: En .NET, le point d'entrée d'un programme est par défaut la fonction Main. Pourquoi ne pas faire la même chose en MyJScript ? En fait, il suffit de considérer que toutes les instructions d'un programme MyJScript que l'on rencontre en dehors d'une fonction sont les instructions d'une méthode Main. Cela résout le point 3.
Les variables ne peuvent changer de type dynamiquement: En MyJScript une variable peut avoir une valeur entière puis être affectée à une chaine de caractères. MyJScript sait également gérer intelligemment les conversions automatique en fonction des opérateurs et des valeurs manipulées. Effectivement les types de base .NET ne se comportent pas de cette manière mais si l'on disposait d'un type qui pouvait être un numérique ou une chaîne et qui savait gérer les conversions explicitement, nous aurions résolu le point 4. Et bien il suffit d'en créer un et d'implémenter son comportement pour tous les opérateurs arithmétiques et de comparaison pour qu'il suive les règles du MyJScript.
Toutes les variables doivent être déclarées: Qu'est ce qu'un variable MyJScript non déclarée ? c'est une variable globale. Cela signifie donc que lorsque nous rencontrons une variable dans du code MyJScript, si ce n'est pas une variable locale ou une variable globale connue, il faut la déclarer. Donc, si au cours de la construction de l'arbre syntaxique, nous sommes capable de détecter ce type de variable, nous saurons également résoudre le point 5.
En résumé, en appliquant ces astuces, nous savons donc "convertir" n'importe quel code MyJScript en du code .NET. Faisons l'expérience sur le programme MyJScript du début de l'article:
var i = 100; write(i); function foo(param1,param2) { write(param1); if (i > 50) { var k = 'Go'; write(k); } } j = 12; i = "100"; write(i+j); foo(j);
Voici son équivalent en C#. Notez que j'utilise C# pour éviter d'écrire un arbre syntaxique CodeDOM complet mais, bien sûr, cela signifie que l'on peut écrire la même chose en CodeDOM ou en VB.NET, ou en J#, ...
namespace MyJScript.UserScript { using System; using MyJScript.Runtime; public class MJSProgram { public static MJSValue i = new MJSValue(); public static MJSValue j = new MJSValue(); public static MJSValue foo(MJSValue param1, MJSValue param2) { MJSValue k; Console.WriteLine(param1.ToString()); if ((MJSProgram.i > new MJSValue(50))) { k = new MJSValue("Go"); Console.WriteLine(k.ToString()); } return null; } public static void Main() { MJSProgram.i = new MJSValue(100); Console.WriteLine(MJSProgram.i.ToString()); MJSProgram.j = new MJSValue(12); MJSProgram.i = new MJSValue("100"); Console.WriteLine(((MJSProgram.i + MJSProgram.j)).ToString()); MJSProgram.foo(MJSProgram.j, new MJSValue()); } } }
Comment se fait la conversion ?
Le programme peut alors s'exécuter en .NET, sous réserve de disposer du runtime implémentant les fonctionnalités de la classe MJSValue. Ce runtime pourra par exemple se trouver dans une DLL livrée avec l'application ou enregistrée dans le GAC.
Quand doit-on construire l'arbre syntaxique ? Evidemment au moment de l'analyse syntaxique. Plus précisément, au fur et à mesure que nous rencontrons les règles de notre langage nous devons construire notre arbre et retourner l'arbre complet à la fin de l'analyse. Bref cela nous oblige à modifier l'interface de notre analyseur syntaxique:
// // Interface de l'analyseur syntaxique // public class Parser { ... // // L'arbre syntaxique généré // public CodeNamespace Result; }
Nous ajoutons à notre classe Parser une propriété Result qui correspond à la racine de l'arbre CodeDOM: le namespace. Pour reprendre l'exemple précédent, il s'agit du namespace MyJScript.UserScript.
Ajoutons un test unitaire afin de s'assurer que l'arbre syntaxique est construit correctement.
Parser p1 = new Parser("var x; x=45;"); Assert.IsTrue(p1.Parse()); Assert.IsNotNull(p1.Result); CodeNamespace cns1 = p1.Result; Assert.AreEqual("MyJScript.UserScript", cns1.Name); Assert.AreEqual(1, cns1.Types.Count); // Il y n'a qu'une classe dans le namespace CodeTypeDeclaration cl1 = cns1.Types[0]; Assert.AreEqual("MJSProgram", cl1.Name); // La classe s'appelle MJSProgram Assert.AreEqual(2, cl1.Members.Count); // Elle a une variable globale et une fonction Main // On teste si x est présent en tant que variable Assert.AreEqual("x", cl1.Members[0].Name); CodeMemberField cf1 = cl1.Members[0] as CodeMemberField; Assert.IsNotNull(cf1); Assert.AreEqual("MJSValue", cf1.Type.BaseType); Assert.AreEqual(MemberAttributes.Public | MemberAttributes.Static, cf1.Attributes); // On teste si Main est présent en tant que méthode CodeMemberMethod m1 = cl1.Members[1] as CodeMemberMethod; Assert.IsNotNull(m1); Assert.AreEqual("Main", m1.Name);
Le test concerne un programme MyJScript simple effectuant une déclaration de variable et une affectation. On s'assure qu'à la sortie de l'analyse syntaxique un arbre CodeDOM contenant une classe avec une variable globale x et une fonction Main a bien été construit. Du fait du caractère "verbeux" de CodeDOM, le test est assez long mais il est facile à comprendre.
Les règles de grammaire déclarées dans JAY ne sont pas uniquement destinées à valider qu'une règle est respectée. JAY permet également d'associer des actions aux règles, notamment afin de construire un arbre syntaxique.
Les actions dans JAY sont des blocs de code C#. Elles peuvent être insérées à n'importe quel endroit d'une règle. Lors de la génération du fichier de sortie, JAY remplace les chaînes $$ et $N (où N est un numérique) par des valeurs spécifiques. Plus précisément:
Prenons l'exemple des règles "expr" et "literal" de notre grammaire et ajoutons-y des actions:
expr: expr PLUS expr { $$ = generator.BinaryOperator($1, CodeBinaryOperatorType.Add, $3); } | expr MULT expr { $$ = generator.BinaryOperator($1, CodeBinaryOperatorType.Multiply, $3); } | expr MINUS expr { $$ = generator.BinaryOperator($1, CodeBinaryOperatorType.Subtract, $3); } | expr DIV expr { $$ = generator.BinaryOperator($1, CodeBinaryOperatorType.Divide, $3); } | funct_call { $$ = $1; } | literal { $$ = $1; } literal: NUMBER { $$ = generator.NumberConstant($1); } | STRING { $$ = generator.StringConstant($1); } | IDENT { $$ = generator.Variable($1); }
Dans la première règle de l'expression (i.e. "expr: expr PLUS expr"), l'action consiste à appeler une méthode BinaryOperator qui prend en paramètre le retour du premier membre, une valeur d'énumération CodeDOM et le retour du troisième membre de l'expression. Enfin, la valeur de retour de cette méthode est la valeur retournée par la règle.
Dans la dernière règle de l'expression ("expr: literal"), l'action consiste simplement à retourner la valeur du premier membre.
Enfin, dans les règles pour un littéral, ("literal: NUMBER" par exemple), on appelle une méthode NumberConstant qui prend en paramètre la valeur du token, c'est à dire ici, puisqu'il s'agit du token NUMBER, un entier .
Le code suivant est un extrait de la classe Generator où on retrouve les méthodes BinaryOperator et Number:
class Generator { ... public CodeExpression BinaryOperator(CodeExpression first, CodeBinaryOperatorType optype, CodeExpression second) { return new CodeBinaryOperatorExpression(first, optype, second); } public CodeExpression NumberConstant(int value) { return new CodeObjectCreateExpression("MJSValue", new CodeExpression[] { new CodePrimitiveExpression(value) }); } ... }
Que font les méthodes de la classe Generator ? Elles créent simplement les objets CodeDOM correspondants aux règles. Ainsi, en même temps que l'analyseur syntaxique reconnait l'expression, un arbre CodeDOM se construit au fur et à mesure par ajout successif de chacune des actions. A la fin de l'analyse, nous avons donc un arbre contenant la totalité des instructions.
L'objectif n'est pas de détailler ici la totalité de la génération néanmoins la classe Generator se charge également d'effectuer des vérifications "sémantiques" sur le code analysé. Ainsi, elle peut détecter des incohérences dans le code analysé:
Le générateur conserve donc un contexte: la liste des déclarations de variables globales rencontrées, la liste des déclarations de variables locales rencontrées, la listes de déclarations de fonctions rencontrées, est-on dans une fonction ou pas. Ce contexte lui permet ainsi de réagir aux incohérences en levant une erreur ou en générant du code supplémentaire. Par exemple, dans la méthode ci-dessous, on ajoute une déclaration de variable globale lorsqu'on rencontre une référence à une variable inconnue.
public CodeExpression Variable(string name) { // Une déclaration locale de cette variable existe if (localVariables.ContainsKey(name)) return new CodeVariableReferenceExpression(name); // On est dans une fonction et c'est le nom d'un des paramètres de la fonction if (currentMethod != null) { foreach (CodeParameterDeclarationExpression param in currentMethod.Parameters) if (param.Name == name) return new CodeVariableReferenceExpression(name); } // Si ce n'est pas déjà une variable globale, on ajoute sa déclaration if (!globalVariables.ContainsKey(name)) DeclareGlobalVar(name, null); return new CodeFieldReferenceExpression(new CodeTypeReferenceExpression("MJSProgram"), name); }
Pour aller plus loin: La méthode de
construction décrite ici permet de construire l'arbre "à
la volée" lors de l'analyse. Lorsque la grammaire est
plus complexe, il peut hélas arriver que l'utilisation
du contexte ne suffise pas à construire l'arbre complet
lors de l'analyse. Le cas le plus courant est l'utilisation d'une fonction dont on n'a pas encore rencontré la déclaration (ce qui n'est pas permis par le MyJScript heureusement ;-). Dans ce cas, on est obligé de construire un arbre partiel et faire un deuxième parcours de l'arbre à la fin pour générer les informations manquantes. C'est ce que l'on appelle compiler en deux "passes". |
La dernière étape de notre compilateur consiste à transformer notre arbre syntaxique en du code exécutable. Plus précisément, si nous remettons toutes les pièces dans le bon ordre, à transformer un fichier source en un fichier exécutable.
Décrivons l'interface C# de notre compilateur MyJScript:
// // La classe du compilateur MyJScript // public class Compiler { // // Compiler depuis un fichier // public static CompilerResults CompileAssemblyFromFile(CompilerParameters options, string fileName); // // Compiler depuis une chaine // public static CompilerResults CompileAssemblyFromSource(CompilerParameters options, string source); }
La méthode CompileAssemblyFromFile permet de compiler un fichier source en un fichier exécutable. Nous y ajoutons une méthode CompileAssemblyFromSource qui permet de compiler une chaîne de caractères en un assembly mémoire ce qui simplifiera les tests unitaires.
A noter que nous utilisons dans notre interface deux classes du .NET Framework: CompilerParameters et CompilerResults.
Comme nous allons le voir dans le paragraphe suivant, l'utilisation de ces classes et le nommage de nos méthodes est volontairement conforme à la classe CodeDomProvider.
Ecrivons un test unitaire pour valider le fonctionnement de notre compilateur. Essayons de compiler et d'exécuter le programme MyJScript suivant:
function hello() { write('Hello World!'); } hello();
L'écriture du test n'est pas triviale puisqu'on veut tester que la compilation fonctionne mais aussi que l'exécutable fait bien ce que l'on veut, c'est à dire écrire "Hello world!" sur la console. Comment depuis un test unitaire appeler le compilateur et tester le fonctionnement du programme compilé ? Quelques astuces permettent de résoudre le problème:
La méthode CompileAndRun suivante réalise tout cela:
private string CompileAndRun(string source) { // Appeler le compilateur MyJScript CompilerParameters options = new CompilerParameters(); options.GenerateInMemory = true; options.IncludeDebugInformation = false; CompilerResults results = Compiler.CompileAssemblyFromSource(options, source); if (results.Errors.Count > 0) return ""; // Rediriger la sortie standard vers une chaine StringWriter outputString = new StringWriter(); Console.SetOut(outputString); // Appeler la méthode Main explicitement Assembly assembly = results.CompiledAssembly; Type evaluatorType = assembly.GetType("MyJScript.UserScript.MJSProgram"); try { evaluatorType.InvokeMember("Main", BindingFlags.Public | BindingFlags.Static | BindingFlags.InvokeMethod, null, null, null); } catch (TargetInvocationException e) { throw e.InnerException; } // Remettre la sortie standard comme avant string console = outputString.ToString(); Stream outputStream = Console.OpenStandardOutput(); Console.SetOut(new StreamWriter(outputStream)); return console; }
Ainsi, les tests unitaires pour valider notre compilateur sont simples à écrire. Voici celui de notre programme:
Assert.AreEqual("Hello world!\r\n", CompileAndRun("function hello()\r\n{\r\n write('Hello World!');\r\n}\r\nhello();\r\n") );
L'objectif de notre compilateur est de générer du code IL exécutable. Pourtant, à aucun moment jusqu'à présent nous n'avons généré de code IL. Alors quand est-ce qu'on génère le code IL ? la mauvaise nouvelle c'est qu'à aucun moment nous n'allons généré de code IL, la bonne nouvelle c'est qu'en fait nous n'en avons pas besoin !
Le .NET Framework permet directement d'appeler un compilateur depuis un programme. Plus précisément, tous les compilateurs de la plate-forme .NET (C#, VB.NET, J#, C++, ...) dérivent de la même classe CodeDomProvider. Cette classe repose sur une interface ICodeCompiler qui permet de compiler un programme depuis une chaine de caractères, un fichier ou mieux, depuis du CodeDOM. Autrement dit: il est possible d'utiliser n'importe quel compilateur de la plate-forme .NET pour transformer un arbre CodeDOM en un assembly (et, par extension, un .EXE). La preuve en quelques lignes de code:
// Choisir entre le compilateur VB ou C# CodeDomProvider provider; if (options.CompilerOptions == "vb") provider = new VBCodeProvider(); // On appelle le compilateur VB else provider = new CSharpCodeProvider(); // On appelle le compilateur C# CompilerParameters parameters = new CompilerParameters(); parameters.TreatWarningsAsErrors = false; parameters.WarningLevel = 0; parameters.ReferencedAssemblies.Add("MJSCRuntime.dll"); parameters.OutputAssembly = "MonExe.EXE"; parameters.GenerateInMemory = false; parameters.GenerateExecutable = true; parameters.MainClass = "MyJScript.UserScript.MJSProgram"; CodeCompileUnit cu = new CodeCompileUnit(); cu.Namespaces.Add(namespaceCodeDOM); // On transmet l'arbre syntaxique provider.CompileAssemblyFromDom(parameters, cu); // L'exécutable est généré
Voilà qui simplifie beaucoup l'implémentation de la dernière étape de notre compilateur: il suffit d'utiliser un des compilateurs standards du .NET Framework et de lui demander gentiment de traduire notre arbre CodeDOM en du code IL. C'est exactement ce qui est fait dans les méthodes CompileAssemblyFromFile et CompileAssemblyFromSource du compilateur MyJScript.
Allons un peu plus loin: plutôt que de compiler le CodeDOM en code IL, les compilateurs .NET proposent également de générer le code source correspondant. On peut donc ajouter notre compilateur la capacité de générer le fichier source lorsque la compilation est en mode debug:
... // Choisir entre le compilateur VB ou C# CodeDomProvider provider; if (options.CompilerOptions == "vb") provider = new VBCodeProvider(); else provider = new CSharpCodeProvider(); // En debug, on génère en plus le code C# ou VB équivalent if (options.IncludeDebugInformation) { // Créer StreamWriter Stream s = File.Open(options.OutputAssembly + "." + provider.FileExtension, FileMode.Create); StreamWriter sw = new StreamWriter(s); // Generer source ICodeGenerator generator = provider.CreateGenerator(sw); CodeGeneratorOptions cop = new CodeGeneratorOptions(); generator.GenerateCodeFromNamespace(cns, sw, cop); // Fermer le StreamWriter sw.Close(); s.Close(); } // Générer le code IL ...
Pour aller plus loin: Notre compilateur
n'implémente qu'une partie des fonctionnalités des
compilateurs de la plate-forme .NET. Si nous étions
capable d'implémenter les fonctions manquantes et
notamment la génération, nous pourrions faire du
MyJScript un des nouveaux langages de la plate-forme
.NET ! |
Pour compléter notre développement, nous y ajoutons une application console qui permet de lancer le compilateur en ligne de commande. Nous ne détaillerons pas cette réalisation qui est triviale mais voilà un exemple de son exécution:
L'ensemble des sources du projet est disponible en téléchargement ici.
Le projet a été réalisé sous Visual Studio 2005. Il consiste en une solution qui contient trois projets:
La totalité du projet est placée sous licence LGPL, vous pouvez donc le réutiliser librement dans vos développements propriétaires ou non.
La méthode utilisée ici permet relativement simplement de créer un véritable compilateur pour .NET. Cette même méthode a également été utilisée avec succès pour d'autres langages que le MyJScript:
Cet article a longuement détaillé les notions d'analyse lexicale et syntaxique. Ces notions ne sont pas spécifiques à la création d'un compilateur. Elles peuvent être utilisées de la même manière pour valider qu'un texte est conforme à une grammaire.
L'API CodeDOM permet en standard de disposer d'une librairie d'objets pour représenter pratiquement n'importe quelle instruction de la CLS. Ajouté à la possibilité de piloter par API tous les compilateurs de la plate-forme, elle offre à .NET la capacité d'écrire facilement des générateurs de code. C'est incontestablement une force de la plate-forme qu'il est difficile de trouver ailleurs.
Auteur : Lionel Laské
Lionel Laské est architecte et chef du service Nouvelles Technologies à C2S, société de services du groupe Bouygues. Il est également l'auteur de Liogo, un compilateur Logo pour .NET. Il peut être joint à l'adresse llaske@c2s.fr. |