ANTLR 4: Réaliser un compilateur avec le runtime JavaScript

Démonstration de l'implémentation d'un langage de programmation grâce à ANTLR 4. Codes sources inclus.

En choisissant le langage JavaScript pour le compilateur, on dispose d'un outil portable, fonctionnant avec Node sur tout système. La démonstration explique comment mettre en oeuvre ANTLR 4 pour générer le compilateur à partir de la grammaire du langage "calc", qui effectue des opérations arithmétiques.

  1. Le langage calc dispose de règles pour assigner une expression à une variable et afficher un résultat.
  2. Le compilateur du langage charge un fichier d'extension .calc contenant un programme.
  3. Il sauvegarde le code cible dans un fichier d'extension .js.
  4. Le programme écrit en calc est compilé en JavaScript dans la démo. On pourra changer l'implémentation pour un langage cible différent, tel que wasm, C ou un bytecode.

Installer ANTLR 4 et le runtime JavaScript

Ce qu'il vous faut:

Il n'y a rien d'autre à installer, c'est l'avantage de la version JavaScript. Les utilisateurs du langage n'ont besoin que de Node et du compilateur.

Créer une grammaire

Avec ANTLR4 il n'y a pas, selon les auteurs, de limitations dans la complexité de la grammaire que l'on peut définir.

Mais pour le langage calc nous allons commencer avec une grammaire simple... 

grammar calc;

program:
   (
       print 
   |   assign 
   |   emptyline
   )*
   ;

assign:
   VARIABLE (EQCOL | EQ) expression
   EOL
   ;

print:
   PRINT expression EOL
   ;

condition: 
   expression relop expression
   ;

expression: 
   multiplyingExpression ((PLUS | MINUS) multiplyingExpression)*
   ;
   
...

EQCOL:
   ':='
   ;

EOL:
   [\r\n]+
;

WS: 
   [ \t] + -> skip
   ;

La première règle de la grammaire est program qui fait appel à assign et print.

Le générateur produit des fonctions correspondantes à chaque règle de la grammaire, donc pour démarrer le parsing le compilateur appellera la fonction program(), puis il utilisera ParseTreeWalker pour activer le listener.

Générer le compilateur

A partir de la grammaire, la génération du compilateur se fait avec une commande java et l'option JavaScript. Exemple pour le langage calc:

java org.antlr.v4.Tool -Dlanguage=JavaScript calc.g4

Pour vous simplifier la vie, vous pouvez créer un fichier batch contenant la commande comme le fichier ant.bat, pour Windows, dans la démo.

Cette commande crée les fichiers suivants:

La partie essentielle du compilateur tient en quelques lignes... 

const antlr4 = require("antlr4/index")
const fs = require("fs")
const calcLexer = require("./calcLexer.js")
const calcParser = require("./calcParser.js")
const JSListener = require("./JSListener.js").JSListener

const iName = process.argv[2]
JSListener.tFileName = iName.replace(".calc", ".js")
console.log("Compiling " + iName + " to " + JSListener.tFileName)

var input = fs.readFileSync(iName, 'UTF-8')
var chars = new antlr4.InputStream(input)
var lexer = new calcLexer.calcLexer(chars)
var tokens  = new antlr4.CommonTokenStream(lexer)
var parser = new calcParser.calcParser(tokens)
parser.buildParseTrees = true
var tree = parser.program()

var extractor = new JSListener()
antlr4.tree.ParseTreeWalker.DEFAULT.walk(extractor, tree)

On lit un fichier contenant un code source avec readFileSync. Le contenu est transmis au lexer, qui à son tour fournit une liste de tokens au parser. Le parseur crée une arborescence qui est parcourue par ParseTreeWalker.

Développer un listener

Antlr réalise automatiquement lui-même un listener, calcListener, qu'il sauve dans le fichier calcListener.js. Il contient une fonction d'entrée et de sortie pour chaque règle de la grammaire. Il reste à associer des instructions de génération de code cible pour chacune de ces règles, dans les fonctions du listener.

Mais ce n'est pas dans le fichier calcListener que nous allons les placer. En effet chaque fois que le langage est modifié, et que l'on lance la commande de génération, ce fichier est remplacé automatiquement et tout contenu ajouté serait effacé c'est pourquoi non créons un autre fichier avec des fonctions identiques, JSListener.js. 

var antlr4 = require('antlr4/index');
const calcListener = require('./calcListener.js').calcListener
const fs = require("fs")

const print = console.log

// include directly the implementation of the compiler

eval(fs.readFileSync("implement.js", "UTF-8"))

JSListener = function () {
	calcListener.call(this);
	return this;
}

JSListener.prototype = Object.create(calcListener.prototype);
JSListener.prototype.constructor = JSListener;

JSListener.tFileName = "test"

JSListener.prototype.enterProgram = function(ctx) {
    // create the target file
    openTarget()
};

JSListener.prototype.exitProgram = function(ctx) {
    // fill the target file and close it
    closeTarget()
};

JSListener.prototype.enterAssign = function(ctx) {
};

JSListener.prototype.exitAssign = function(ctx) {
    // get the variable
    var t1 = ctx.getChild(0).getText()
    // skip the := symbol to use = instead
    // get the expression
    var t2 = ctx.getChild(2).getText()
    write(t1 + "=" + t2)
};

JSListener.prototype.enterPrint = function(ctx) {
};

JSListener.prototype.exitPrint = function(ctx) {
    var temp = "console.log("
    // I skip the 'print' keyword so go to second child
    temp += ctx.getChild(1).getText()
    temp +=")"
    write(temp)
};

L'argument ctx de la fonction exitPrint par exemple, donc de la règle de grammaire print, contient une arborescence de noeuds représentant les éléments de cette règle de la grammaire. Pour la règle print on a trois noeuds enfants:

  1. Le mot-clé PRINT.
  2. L'expression.
  3. Le symbole de fin de ligne EOL.

On ignore le premier noeud puisque le langage cible utilise console.log, on transmet directement le second avec la commande ctx.getChild(1).getText(), et on ignore le dernier.

Implémenter le compilateur en JavaScript

A coté des instructions placées dans le listener qui servent à récupérer les éléments du code source pour les convertir (ou réutiliser) dans le code objet, le compilateur requiert d'autres fonctions que l'on place dans un fichier séparé, implement.js.

Ce fichier est directement inclut dans le listener avec la commande eval, pour simplifier. Dans la version de production on réaliserait plutôt un module.

var tContent = []
var tFile = undefined;

var openTarget = function() {
    try {
        tFile = fs.openSync(JSListener.tFileName, "w")
    }
    catch(err) {
        console.log("Target file not created. " + err.message)
        return;
    }
}

var closeTarget = function() {
    if(tFile==undefined) return;
    for(var line in tContent) {
        fs.writeSync(tFile, tContent[line].trim() + "\n")    
    }
}

var write = function(data) {
    tContent.push(data)
}

Il contient trois fonctions:

Un compilateur final contiendrait beaucoup d'autres fonctions, notamment pour le contrôle des types et la gestion des erreurs.

Exécuter un premier programme

Un petit programme de demonstration, test.calc, est inclut dans l'archive:

x := 10 + 5
print x + 8

Chaque instruction se termine par une fin de ligne. Y compris la dernière, la fin de fichier n'est pas prise en compte dans cette démo.

Le compilateur produit une version JavaScript dans le fichier calc.js. Essayez le sur le fichier exemple test.calc: 

node calc.js test.calc

Cela produit le fichier JavaScript test.js, à exécuter avec Node aussi. 

node test.js

Cela doit afficher: 23.

Le compilateur et tous les fichiers nécessaires à la démonstration sont disponibles dans une archive à télécharger: