Introduction

Nous allons réaliser un transpileur, ou compilateur source à source, pour un sous-ensemble du langage Java, le langage MiniJava. La représentation d’entrée pour notre compilateur sera donc le langage MiniJava. La représentation en sortie de notre compilateur sera le langage C.
Une exemple de programme permettant de calculer une factorielle est donné ci-dessous.

class Factorial {
    public static void main(String[] a) {
         System.out.println(new Fac().computeFac(10));
    }
}

class Fac {
    public int computeFac(int num) {
        int numAux;
        if (num < 1) numAux = 1;
        else numAux = num * (this.computeFac(num-1));
        return numAux;
    }
}

Comme Minijava est un sous-ensemble de Java, nous pourrons compiler nos fichiers MiniJava en utilisant le compilateur Java javac ce qui sera pratique pour tester la validité de nos traductions en langage C. En effet, nous pourrons comparer la sortie du programme obtenu en utilisant le compilateur Java, avec la sortie obtenue par l’exécutable obtenu grâce à notre transpileur.

Vue d’ensemble du transpileur

Nous allons considérer le programme MiniJava suivant pour illustrer cette section. 

class Print42 {
    public static void main(String[] a) {
            System.out.println(35 + 2 * 3 + 1);
    }
}

La figure suivante montre les différentes étapes permettant de passer du fichier source en MiniJava au fichier source transpilé en C.

graph LR; A[source en MiniJava] -->|caractères| B(fa:fa-tools
Analyse
lexicale) B -->|unités lexicales| C(fa:fa-tools
Analyse
syntaxique) C -->|arbre syntaxique abstrait| D(fa:fa-tools
Analyse
de types) D -->|arbre syntaxique abstrait| E(fa:fa-tools
Générateur
de code C) E -->|caractères| F[source en C]

Nous allons maintenant décrire les différentes étapes de la figure ci-dessus.
Pour suivre les démos dans les différentes vidéos qui vont suivre, commencer par installer les dépendances comme indiqué ici. Télécharger ensuite le code en faisant

git clone --recurse-submodules https://github.com/lascar-pacagi/MiniJava.git
cd MiniJava
git checkout v1.0
make

La branche master est la version avec le ramasse miettes et le tag v1.0 est une version sans ramasse miettes. Si vous voulez apporter des modifications à la version 1.0, vous pouvez créer une nouvelle branche (from_v1.0 par exemple) en faisant

git checkout -b from_v1.0 v1.0

Le code que je vais utiliser pendant les démos se trouve ci-dessous.

  • demo_code.tgz (3 ko)

    • Analyse lexicale

    La première étape est l’analyse lexicale qui va permettre de découper un flot de caractères en mots. Ces mots sont appelés unités lexicales. On obtient alors une information plus structurée où les mots clés du langage, les identifiants, les entiers et les booléens ont été identifiés. Cette phase va aussi nous permettre de supprimer les commentaires et les blancs (espaces et retours à la ligne).
    Pour le programme ci-dessus, l’analyse lexicale va produire le flot d’unités lexicales suivantes. On peut voir, par exemple, que le mot clé CLASS a été identifié, que la constante entière INT_CONST 35 aussi.

    CLASS
IDENT ‘Print42‘
LBRACE
PUBLIC
STATIC
VOID
MAIN
LPAREN
STRING
LBRACKET
RBRACKET
IDENT ‘a‘
RPAREN
LBRACE
SYSO
LPAREN
INT_CONST ‘35‘
PLUS
INT_CONST ‘2‘
TIMES
INT_CONST ‘3‘
PLUS
INT_CONST ‘1‘
RPAREN
SEMICOLON
RBRACE
RBRACE
EOF

    Dans la vidéo suivante, nous allons donner une vue d’ensemble du transpileur, et nous présenterons l’analyseur lexical de MiniJava.

    Analyse syntaxique

    La deuxième étape, l’analyse syntaxique, prend en entrée le flot d’unités lexicales et va construire un arbre syntaxique abstrait permettant de représenter la structure du programme sous la forme d’un arbre.
    Pour le programme ci-dessus, on obtient l’arbre suivant. On peut y voir, par exemple, l’expression arithmétique avec de manière explicite la priorité des opérateurs (plus c’est bas dans l’arbre et plus c’est prioritaire).

    program
  ├name Print42
  ├main_args a
  └main
     └ISyso
        └EBinOp OpAdd
          ├EBinOp OpAdd
          │  ├EConst (ConstInt 35)
          │  └EBinOp OpMul
          │    ├EConst (ConstInt 2)
          │    └EConst (ConstInt 3)
          └EConst (ConstInt 1)

    L’analyse syntaxique a besoin de connaître la structure d’un programme MiniJava. Cette structure est donnée sous la forme d’une grammaire. La grammaire de MiniJava, dans sa forme EBNF est donnée ci-dessous. Une version sûrement plus lisible pour nous en diagramme syntaxique est donnée ici.1

    Program = MainClass { ClassDeclaration } 'eof' ;

MainClass = 'class' Identifier '{' 'public' 'static' 'void' 'main' '(' 'String' '[' ']' Identifier ')' '{' Statement '}' '}' ;

ClassDeclaration = 'class' Identifier [ 'extends' Identifier ] '{' { VarDeclaration } { MethodDeclaration } '}' ;

VarDeclaration = Type Identifier ';' ;

MethodDeclaration = 'public' Type Identifier '(' [ Type Identifier { ',' Type Identifier } ] ')' '{' { VarDeclaration } { Statement } 'return' Expression ';' '}' ;

Type = 'int' '[' ']'
        | 'boolean'
        | 'int'
        |  Identifier ;

Statement = '{' { Statement } '}'
        | 'if' '(' Expression ')' Statement 'else' Statement
        | 'while' '(' Expression ')' Statement
        | 'System.out.println' '(' Expression ')' ';'
        | Identifier '=' Expression ';'
        | Identifier '[' Expression ']' '=' Expression ';' ;

Expression = Expression ( '&&' | '<' | '+' | '-' | '*' ) Expression
        | Expression '[' Expression ']'
        | Expression '.' 'length'
        | Expression '.' Identifier '(' [Expression {',' Expression}] ')'
        | Integer
        | 'true'
        | 'false'
        | Identifier
        | 'this'
        | 'new' 'int' '[' Expression ']'
        | 'new' Identifier '(' ')'
        | '!' Expression
        | '(' Expression ')' ;

Letter = 'A' | 'B' | 'C' | 'D' | 'E' | 'F' | 'G'
       | 'H' | 'I' | 'J' | 'K' | 'L' | 'M' | 'N'
       | 'O' | 'P' | 'Q' | 'R' | 'S' | 'T' | 'U'
       | 'V' | 'W' | 'X' | 'Y' | 'Z' | 'a' | 'b'
       | 'c' | 'd' | 'e' | 'f' | 'g' | 'h' | 'i'
       | 'j' | 'k' | 'l' | 'm' | 'n' | 'o' | 'p'
       | 'q' | 'r' | 's' | 't' | 'u' | 'v' | 'w'
       | 'x' | 'y' | 'z' ;

Digit = '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9' ;

Integer = Digit { Digit } ;

Character = Letter | Digit | '_' ;

Identifier = Letter { Letter | Digit | '_' } ;

    La vidéo suivante va présenter l’analyseur syntaxique de MiniJava.

    Typage

    La troisième étape, l’analyse de types, va prendre en entrée l’arbre abstrait et va vérifier si le typage est correct. Par exemple, on va vérifier qu’on utilise les méthodes avec le bon nombre de paramètres, que les opérateurs + et * sont utilisés avec des opérandes entières, qu’une classe est compatible avec une autre via la relation d’héritage, …

    La vidéo suivante va présenter une vue d’ensemble du typage dans MiniJava.

    Génération de code

    La dernière étape va consister à générer le code en C. On va de nouveau parcourir l’arbre syntaxique abstrait pour générer ce code. Pour notre example, on obtient le fichier C ci-dessous.

    #include <stdio.h>
int main(int argc, char *argv[]) {
  printf("%d\n", ((35 + (2 * 3)) + 1));
  return 0;
}

    La vidéo suivante va décrire succinctement la génération de code C dans MiniJava.

    Sémantique de MiniJava

    La sémantique de MiniJava est donnée par sa sémantique en tant que programme Java 2. Les principales restrictions sont

    • Les classes n’héritent pas de la classe Object.
    • Le mot clé super n’existe pas.
    • Il y a simplement un constructeur par défaut.
    • Les seuls types autorisés sont,
      • int.
      • boolean.
      • int[].
      • Les classes définies par l’utilisateur.
    • La surcharge d’opérateurs n’est pas autorisée.
    • L’instruction System.out.printl() ne peut imprimer que des entiers.
    • Toutes les méthodes doivent retourner une valeur.
    • Il n’y a pas d’interface, d’exception, de généricité, de lambda.

    Nous expliquons dans la vidéo suivante les principales différences entre MiniJava et Java.

    Nous avons décrit rapidement l’initialisation par défaut en Java (et MiniJava) dans la vidéo. Nous apportons quelques précisions ci-dessous. Vous pouvez regarder ici pour tous les détails.

    Soit le programme Java Init.java suivant.

    1class Init {
2    public static void main(String[] args) {
3        int i;
4        boolean b;
5        int[] a;
6        System.out.println(i + " " + b + " " + a);
7    }
8}

    Si on le compile, on obtient les messages d’erreur suivants.

    $ javac Init.java
Init.java:6: error: variable i might not have been initialized
        System.out.println(i + " " + b + " " + a);
                           ^
Init.java:6: error: variable b might not have been initialized
        System.out.println(i + " " + b + " " + a);
                                     ^
Init.java:6: error: variable a might not have been initialized
        System.out.println(i + " " + b + " " + a);
                                               ^
3 errors

    En effet, les trois variables i, b et a sont situées sur la pile, et leurs valeurs vont dépendre des valeurs qui sont situées sur la pile lors de l’appel du main. Java n’initialisant pas les variables locales avec une valeur par défaut, le compilateur refuse le programme en nous indiquant que l’on cherche à utiliser des variables non initialisées.

    Par contre, le programme suivant est correct car les attributs ont des valeurs par défaut.

     1class Init {
 2    public static void main(String[] args) {
 3        new Default().print();
 4    }
 5}
 6
 7class Default {
 8    private int i;
 9    private boolean b;
10    private int[] a;
11
12    public void print() {
13        System.out.println(i + " " + b + " " + a);
14    }
15}

    Et on obtient la sortie suivante.

    $ javac Init.java
$ java Init
0 false null

    Rappels sur la liaison dynamique en Java

    Nous allons faire quelques rappels sur la liaison dynamique en Java dans la vidéo ci-dessous, car la gestion de la liaison dynamique sera un des points difficiles à gérer dans notre transpileur.

    Questions

    Reprenons la grammaire de MiniJava. Nous voudrions ajouter la possibilité d’avoir

    • L’opérateur de comparaison ==.
    • Des constructeurs.
    • Des constructeurs et méthodes private.
    Quelles sont les modifications à apporter à cette grammaire pour incorporer ces nouveaux éléments ?
    Dans la question précédente, quels terminaux avez-vous dû ajouter à la grammaire (un terminal dans la grammaire deviendra une unité lexicale) ?

    Soit le programme Java suivant.

     1class A {
 2    public int m1(int n) {
 3        System.out.println("int A:m1(int n)");
 4        return 0;
 5    }
 6}
 7
 8class B extends A {
 9    public boolean m1(int n) {
10        System.out.println("boolean B:m1(int n)");
11        return false;
12    }
13}
    Ce code compile-t-il ?

    Soit le programme Java suivant.

     1class A {
 2    public int m1(int n) {
 3        System.out.println("int A:m1(int n)");
 4        return 0;
 5    }
 6    public boolean m1(int n) {
 7        System.out.println("boolean A:m1(int n)");
 8        return false;
 9    }
10}
    Ce code compile-t-il ?

    Soit le programme Java suivant.

     1class A {
 2    public int m1(A a) {
 3        System.out.println("int A:m1(A a)");
 4        return 0;
 5    }
 6    public boolean m1(B b) {
 7        System.out.println("boolean A:m1(B b)");
 8        return false;
 9    }
10}
11
12class B extends A {
13}
    Ce code compile-t-il ?

    Ressources

    Cours sur Java de Coursera partie 1
    Cours sur Java de Coursera partie 2
    Cours sur Java de Coursera partie 3
    Cours sur Java de Princeton
    Spécifications du langage Java
    Page de MiniJava
    Diagramme syntaxique de MiniJava
    Cours sur le langage C partie 1
    Cours sur le langage C partie 2
    Cours sur le langage C partie 3
    Cours sur le langage C partie 4
    Apprendre le C en construisant un Lisp
    Cours sur le C moderne
    Spécifications du langage C (norme C11)

    1. La description de la grammaire qui permet de générer le diagramme ne suit pas strictement la forme EBNF. Les détails sont donnés ici. [return]
    2. Voir ici pour la sémantique du langage Java. [return]