Premiers pas avec ANTLR4 en C#

• énumérables récursivement (type 0). Toutes les grammaires formelles: c’est à dire formées par des symboles terminaux, non terminaux et des règles de production qui définissent les symboles non terminaux). inclu tous les autres types de grammaires.
• langages récursifs (type 0-1), un mélange du type 0 et 1 (hors classement de Chomsky)
• sensible au contexte (type 1): les règles de production s’écrivent sous la forme αΑβ → αγβ avec Α un non terminal et α, β et γ des terminaux et/ou des non terminaux, avec γ non vide
• libre de contexte (type 2): règles des production sous la forme Α → γ avec Α non terminal et γ terminal et/ou non terminal. C’est le cas des principaux langages de programmation, bien que la résolution des noms est sensible aux contexte à cause des scopes. Un sous ensemble de ces grammaires est utilisé pour fabriquer des parsers plus efficaces plus facilement: les parsers LL (Left to right Leftmost derivation)
• langages réguliers (type 3) : les règles de production sont restreintes par une symbole terminal a gauche et à droite, éventuellement suivi par un non terminal. Ces langages s’obtiennent par des expressions régulières

2. Pourquoi ANTLR ?

• supporte une grammaire libre de contexte (type 2)
• supporte les grammaires de type LL(*), c’est à dire une grammaire récursive à gauche qui n’est pas limitée à un nombre k de tokens pour identifier un non terminal
• est basée sur une variante de grammaire EBNF (Extended Backus-Naur Form) habituelle et pratique
• propose un grand nombre de grammaires qui pourront servir de base à l’écriture de nouvelles grammaires
• propose les templates de visiteur et de listener pour parcourir un AST
• propose une grammaire enrichie avec par exemple des actions qui sont des méthodes écrites dans le langage cible, des prédicats sémantiques, des canaux (bloc d’un autre langage dans le langage), etc… qui permettent d’augmenter le pouvoir de description des grammaires LL
• dispose d’une extension pour Visual Studio
• produit un lexer/parser en C#
• est un projet open source bien vivant et très utilisé

3. Pourquoi faire ?

• lire / traiter / exécuter / traduire des textes ou des binaires structurés
• construire un langage de programmation
• construire un langage DDL (Data Design Language)
• construitre un langage spécifique à un domaine: DSL (Domain Specific Language)
• construire un langage de haut niveau comme Ubiquitous Language dans l’approche DDD (Domain Driven Design)
• construire des outils et des frameworks qui s’articulent autour des langages

4. Mise en oeuvre dans Visual Studio avec C#

Les exemples suivant sont utilisables sur Visual Studio 2010 et +. Ils sont présentés ici sous Visual Studio 2015.

4.1 Installation du support de langage ANTLR

Depuis le gestionnaire d’extensions, installer ANTLR Language support:

Ceci ajoute le support des grammaires g3 et g4 (coloration syntaxique, intellisense), et le panneau des propriétés des fichiers de grammaire. Il est nécessaire de référencer les codes sources ANTLR qui sont générés dans obj/ afin de faire fonctionner Intellisense sur le code généré.

4.2. Nouveau projet C# ANTLR

Pour l’exmple, on ajoute un nouveau projet application console (bureau classique) depuis le menu contextuel de l’explorateur de solution (une librairie serait plus appropriée dans un cadre plus large). On cible le framework .NET 4.6.2

4.3. Ajout du runtime ANTLR au projet

A partir de la console de gestionnaire de package NUGET, on ajoute le runtime ANTLR au nouveau projet:

ce runtime correspond au framework .NET cible, un autre est disponible (le Standard) pour cible CORE 2.

4.4. Ajout du générateur ANTLR C# au projet

A partir de la console du gestionnaire de package NUGET, on ajoute le générateur de lexer/parser C# ANTLR:

Sans cela, pas de code généré !

4.5. Ajout d’une grammaire

Les grammaires g4 sont disponibles à l’adresse: https://github.com/antlr/grammars-v4

• dans le projet, ajouter un fichier de grammaire depuis le menu contextuel de l’explorateur de solution: ajouter > nouvel élément > ANTLR4 Combined Grammar
• pour les tests, on va utiliser une grammaire simple d’expression arithmétique. Dans le fichier de grammaire vide qui vient d’être ajouté au projet, recopier le contenu du fichier exemple: calculator.g4 disponible à l’adresse: https://github.com/antlr/grammars-v4/tree/master/calculator
• dans les propriétés du fichier, placer Generate Listener à True et Generate Visitor à True pour générer tous les aspects du lexer/parser
• le générateur ANTLR s’active chaque fois que le fichier de grammaire est enregistré
• les élements de programme générés sont visibles dans obj/:

4.6. Test de la grammaire

La méthode Main du projet reçoit le code typique qui permet de parser un texte selon la grammaire calculator.g4:

while (true)
{
    try
    {
        Write("enter calculator text: ");
        var str = ReadLine();
        var inputStream = new AntlrInputStream(str);
        var lexer = new calculatorLexer(inputStream);
        var commonTokenStream = new CommonTokenStream(lexer);
        var parser = new calculatorParser(commonTokenStream);
        var ectx = parser.equation();
        WriteLine("parse tree (LISP style): " + ectx.ToStringTree(parser));
    } catch (Exception Ex)
    {
        Console.Error.WriteLine(Ex.Message);
    }
}

exemples dans la console:

enter calculator text: hello world
line 1:6 missing {'>', '<', '='} at 'world'
parse tree (LISP style): (equation (expression (multiplyingExpression (powExpression (signedAtom (atom (variable hello)))))) relop (expression (multiplyingExpression (powExpression (signedAtom (atom (variable world)))))))

enter calculator text: y=x*x+x-4
parse tree (LISP style): (equation (expression (multiplyingExpression (powExpression (signedAtom (atom (variable y)))))) (relop =) (expression (multiplyingExpression (powExpression (signedAtom (atom (variable x)))) * (powExpression (signedAtom (atom (variable x))))) + (multiplyingExpression (powExpression (signedAtom (atom (variable x))))) - (multiplyingExpression (powExpression (signedAtom (atom (scientific 4)))))))

enter calculator text: d=(sin(a)+cos(a))*r
parse tree (LISP style): (equation (expression (multiplyingExpression (powExpression (signedAtom (atom (variable d)))))) (relop =) (expression (multiplyingExpression (powExpression (signedAtom (atom ( (expression (multiplyingExpression (powExpression (signedAtom (func (funcname sin) ( (expression (multiplyingExpression (powExpression (signedAtom (atom (variable a)))))) ))))) + (multiplyingExpression (powExpression (signedAtom (func (funcname cos) ( (expression (multiplyingExpression (powExpression (signedAtom (atom (variable a)))))) )))))) )))) * (powExpression (signedAtom (atom (variable r)))))))

enter calculator text:

4.7. Utilisation du parse tree

Maintenant que la grammaire, le lexer et le parser sont en place dans le projet C#, il ne reste plus qu’à exploiter le résultat obtenu: le Parse Tree. Le parse tree est un arbre des termes des règles de production, ce n’est pas un AST logique, car il contient aussi des informations qui servent au parser. Il sagit d’un CST (Concrete Syntax Tree).
Néanmoins il permet de faire tout le travail.

4.7.1. Du parse tree vers l’AST logique

On ajoute une méthode pour représenter l’AST sour forme arborescente dans la console:

void Explore(ParserRuleContext ctx, int indentLevel = 0)
{
    var ruleName = calculatorParser.ruleNames[ctx.RuleIndex];
    var sep = "".PadLeft(indentLevel);
    WriteLine(sep + ruleName);
    sep = "".PadLeft(indentLevel+4);
    foreach ( var c in ctx.children )
    {
        if (c is ParserRuleContext)
            Explore((ParserRuleContext)c, indentLevel + 4);
        else
            WriteLine(sep + c.ToString());
    }
}

On obtient la vue arborescente dans la console, pour l’expression exemple: y=x*x+2

enter calculator text: y=x*x+2
parse tree (AST LISP style): (equation (expression (multiplyingExpression (powExpression (signedAtom (atom (variable y)))))) (relop =) (expression (multiplyingExpression (powExpression (signedAtom (atom (variable x)))) * (powExpression (signedAtom (atom (variable x))))) + (multiplyingExpression (powExpression (signedAtom (atom (scientific 2)))))))

equation
    expression
        multiplyingExpression
            powExpression
                signedAtom
                    atom
                        variable
                            y
    relop
        =
    expression
        multiplyingExpression
            powExpression
                signedAtom
                    atom
                        variable
                            x
            *
            powExpression
                signedAtom
                    atom
                        variable
                            x
        +
        multiplyingExpression
            powExpression
                signedAtom
                    atom
                        scientific
                            2

On voit immédiatement que l’AST est très pollué. Une façon simple de produire un AST logique consiste à supprimer les noeuds qui n’ont qu’un seul enfant, car ils correspondent à des règles non terminales qui servent uniquement au parser mais qui ne décrivent pas la logique de la syntaxe de l’expression analysée.

La méthode ExploreAST fait ce travail:

void ExploreAST(ParserRuleContext ctx, int indentLevel = 0)
{
    var ruleName = calculatorParser.ruleNames[ctx.RuleIndex];
    var sep = "".PadLeft(indentLevel);
    bool keepRule = ctx.ChildCount > 1;
    if (keepRule)
        WriteLine(sep + ruleName);
    foreach (var c in ctx.children)
    {
        if (c is ParserRuleContext)
            ExploreAST((ParserRuleContext)c, indentLevel + ((keepRule) ? 4 : 0));
        else
        {
            var sep2 =
                "".PadLeft(indentLevel+((keepRule)?4:0));
            WriteLine(sep2 + c.ToString());
        }
    }
}

On obtient ainsi:

equation
    y
    =
    expression
        multiplyingExpression
            x
            *
            x
        +
        2

cet AST peut alors se lire comme un arbre ternaire, chaque noeud ayant trois enfants: dans l’ordre l’opérande gauche, l’opérateur et l’opérande droit. Cela est spécifique à cette grammaire en particulier. La transformation ne fonctionne pas forcément dans tous les cas. On aura éventuellement recours à une transformation explicite du parse tree vers un autre modèle d’AST

téléchargez le projet C# VS2015 complet ici : ANTLR4 lexer parser for C# - calculator sample - VS2015 C# project