Le C est évidemment le premier choix pour qui s'intéresse à la conception d'un compilateur ou d'un interprêteur destiné à la production. Mais dans le cas de la conception d'un « petit langage », juste pour la beauté du geste (ou peut-être pour des objectifs plus sérieux) ? Pourquoi se poser des questions alors que nous avons Python – et des outils vraiment pratiques qui l'accompagne !

Nous utiliserons Python Lex-Yacc (PLY) pour reconnaître les symboles et la construction de l'analyseur. Ces outils ont étés conçus au plus proche des traditionnels lex/yacc. Si vous savez comment utiliser ces outils en C, vous ne serez pas dépaysés avec PLY. PLY peut être téléchargé sur le site http://www.dabeaz.com/ply/.

Nous aurons besoin des modules lex.py et yacc.py dans notre répertoire de travail. Nous aurons également besoin de Python en version 2.1 ou supérieur.

Qu'est-ce qu'un symbole ? Les symboles sont des éléments tels que +, -, * ou / ou des mots tels que début, fin, si ou tant que – que nous voulons identifier en tant qu'opérateurs, mots réservés, mots-clefs, etc. Les symboles doivent être utilisés en tant qu'expressions régulières.

Étant donné que nous écrivons un compilateur pour un langage particulier avec les constructions que nous voudrions inclure, la première chose à faire est de définir le langage. Ceci est obtenu en écrivant un ensemble de règles de grammaire pour ce langage. Par exemple, si l'on souhaite que votre langage fournisse la construction si-alors-sinon alors une manière simple d'en décrire la règle serait :

instruction_si : SI PARENTG instruction PARENTD plusieurs_instructions SINON plusieurs_instruction FINSI

où (1) SI, PARENTG, PATENTD, SINON et FINSI sont des symboles pour reconnaître respectivement si, (, ), sinon et finsi. (2) instruction et bloc_instructions sont des constructions différentes pour lesquelles les règles sont écrites.

En termes simples, l'analyse est la méthode de vérification que le programme en entrée respecte les règles données à l'analyseur. Il existe différentes méthodes d'analyse. Mais nous n'avons pas besoin d'entrer dans les détails. Il suffit de savoir qu'en fonction d'un ensemble de règles donné (tel que présenté en exemple ci-dessus), l'analyseur détermine si les constructions en entrée correspondent aux règles définies.

Comme nous l'avons vu précédemment, la première étape est de définir le langage que vous souhaitez pour votre compilateur. Vous devez être sûr des constructions et des opérateurs que vous voulez proposer. Les constructions telles que les instructions tant_que, si, les instructions d'assignation, etc sont communes. Ainsi que les opérateurs +, -, *, /, etc. Vous devez écrire les règles pour votre langage. Un ensemble de règles pour un langage acceptant les instructions d'assignation sont données ci-dessous.

      instruction_assignation  : instruction VAR EGAL
      instruction              : terme instruction OPADD
                               | terme instruction OPMOINS
			       | terme
      terme                    : terme OPMUL facteur
                               | terme OPDIV facteur
			       
      facteur                  : VAR
                               | NUM
			       | GPAREN instruction DPAREN
    

Tout au long de notre discussion, nous avons pris comme convention que les mots en majuscules (NUM, VAR, EGAL, OPADD, OPMOINS, OPMUL, OPDIV, GPAREN, DPAREN) sont les symboles et ceux en minuscules (instruction_assignation, instruction, terme, facteur) sont les règles.

Nous devons ensuite définir les symboles que nous utilisons. Nous avons neuf symboles dans notre exemple – NUM, VAR, EGAL, OPADD, OPSOUS, OPMUL, OPDIV, PARENG et PAREND. Le programme suivant implémente un simple analyseur lexical pour segmenter notre notre langage [version texte]

import lex

# Liste des noms des symboles. C'est obligatoire.
symboles = (
                'NUM',
                'VAR',
                'EGAL',
                'OPADD',
                'OPSOUS'
                'OPMUL',
                'OPDIV',
                'PARENG',
                'PAREND'
        )

# Règles de déclaration régulières pour les symboles.
t_VAR           = r'[a-zA-Z_][\w_]*'
t_EGAL          = r'='
t_OPADD         = r'\+'
t_OPSOUS         = r'-'
t_OPMUL         = r'\*'
t_OPDIV         = r'/'
t_PARENG        = r'\('
t_PAREND        = r'\)'

# Une règle de déclaration régulière avec du code d'action.
def t_NUM(t) :
    r'\d+'
    try:
         t.valeur = int(t.valeur)
    except ErreurValeur:
         print "Ligne %d: Numéro %s est trop grand!" % (t.numLigne, t.valeur)
    t.valeur = 0
    return t

# Définit une règle de sorte que l'on puisse suivre les numéros de lignes.
def t_nouvelleligne(t):
    r'\n+'
    t.numLigne += len(t.valeur)

# Une chaîne contenant les caractères ignorés (espaces and tabulations).
t_ignore  = ' \t'

# Règle de gestion des erreurs
def t_erreur(t):
    print "caractère invalide '%s'" % t.valeur[0]
    t.ignore(1)

# Construit l'analyseur syntaxique
lex.lex()

# Récupère l'entrée
donnees = entree_brute()

lex.entree(donnees)

# Segmente
while 1 :
        tok = lex.token()
        if not tok :
                break
        print tok
    

Si vous souhaitez inclure des mots réservés, il est en général plus facile de faire correspondre un nom de variable (identifiant) et d'effectuer une résolution de nom particulière dans une fonction telle que :

reserve = {
   'si' : 'SI',
   'alors' : 'ALORS',
   'sinon' : 'SINON',
   'tant que' : 'TANT QUE',
   ...
}

def t_VAR(t):
    r'[a-zA-Z_][\w_]*'
    t.type = reserve.get(t.value,'ID')    # Vérification des mots réservés
    return t
    

L'analyse est assez facile grâce à yacc.py. L'analyseur invoke l'analyseur lexical pour obtenir les symboles. Nous devons donc importer le module lex que nous avons écrit précédemment. À présent, pour chaque règle correspodante, on définit une fonction et on écrit la règle elle-même en tant que document. Au sein de la fonction on peut écrire les actions sémantiques nécessqires. Dans notre langage exemple, l'analyse peut être effectuée tel que montré ci-dessous.[version texte]

# Yacc example

import yacc

# Obtient la carte des symboles grâce à l'analyseur syntaxique que nous avons défini
# précédemment. C'est obligatoire.

from notreanalyseur import tokens

__var_noms = {}

def p_instruct_assignation(t) :
    'instruct_assignation : instruction VAR EGAL'
    __noms_var[t[1]] = t[3]

def p_instruct_plus(t) :
    'instruction : instruction terme OPADD'
    t[0] = t[1] + t[3]

def p_instruct_moins(t) :
    'instruction : instruction terme OPSOUS'
    t[0] = t[1] - t[3]

def p_instruct_terme(t) :
    'instruction : terme'
    t[0] = t[1]

def p_terme_mul(t) :
    'terme : terme OPMUL facteur'
    t[0] = t[1] * t[3]

def p_terme_div(t) :
    'terme : terme OPDIV facteur'
    t[0] = t[1] / t[3]

def p_terme_facteur(t) :
    'terme : facteur'
    t[0] = t[1]

def p_facteur_num(t) :
    'facteur : NUM'
    t[0] = t[1]

def p_facteur_var(t) :
    'facteur : VAR'
    if __var_noms.has_key(t[1]) :
        t[0] = __var_noms[t[1]]
    else :
        print "Variable Indéfinie ", t[1], "à la ligne no.", t.lineno(1)

def p_facteur_expr(t):
    'facteur : PARENG instruction PAREND'
    t[0] = t[2]

# Règle d'erreur pour les erreurs de syntaxe
def p_erreur(t):
    print "Erreur de syntaxe en entrée!"

# Construit l'analyseur
yacc.yacc()

while 1:
   try:
       s = raw_input('entrer > ')
   except EOFError:
       break
   if not s: continue
   yacc.parse(s)
    

Ici; chaque fonction accepte un seul argument, t qui est un multiplet. Les valeurs de t[i] sont associées aux symboles grammaticaux tel que présenté ici :

def p_instruct_plus(t):
    'instruction : instruction OPADD terme'
    #   ^            ^           ^     ^
    #  t[0]         t[1]        t[2]  t[3]

    t[0] = t[1] + t[3]
    

Les actions sémantiques sont les étapes que l'analyseur effectue lorsqu'il réduit l'entrée à une règle particulière. Dans l'exemple ci-dessus, les actions correspondent à celles d'un interprêteur. Pour un compilateur simple, l'action sémantique peut être la production de code assembleur correspondant à une règle.

Supposons que l'on souhaite produire des instructions assembleur 8086 en sortie. Imaginons que bx soit un registre temporaire. À présent, dès que l'on rencontre une opérande, on le contenu de l'accumulateur dans le registre temporaire et on place l'opérande elle-même dans l'accumulateur. Ainsi, la dernière opérande vue (ou le résulat d'une évaluation) sera toujours dans l'accumulateur.

 def p_facteur_num(t) :
    'facteur : NUM'
    __pf_sortie.write("\tmov bx,ax\n"%f)      # bx <-- [ax]
    __pf_sortie.write("\tmov ax,0x%x\n"%t[1]) # ax <-- t[1]
    

où, __pf_sortie est un pointeur de fichier sur un fichier de sortie

Puisque les opérandes d'une opération (qu'elle soit binaire ou unaire) est à présent disponible, nous pouvons écrire les actions sémantiques pour l'addtion ainsi :

def p_instruct_plus(t) :
    'instruction : instruction OPADD terme'
    __pf_sortie.write("\tadd ax,bx\n")
   # ax <-- [ax] + [bx]
    

De même, dès que l'on trouve une nouvelle variable, on peut lui allouer un registre (une place dans la pile est un meilleur choix pour enregistrer les variables locales), et mémoriser le registre alloué au moyen d'un dictionnaire. Le nom de la variable est la clé et le nom du registre la valeur. Chaque fois qu'un nom de variable est référencé, le dictionnaire est consulté avec le nom de la variable comme clé afin d'obtenir le nom du registre correspondant.

Pour un compilateur C, les instructions assembleur ne sont pas produites aussi tôt que l'on l'avons décrit ici. En réalité, un code intermédiaire est généré. Ensuite ce code intermédiaire est optimisé et enfin le code assembleur est généré.

L'optimisation étant en elle-même un vaste sujet, nous aborderons uniquement une technique simple d'optimisation, nommée optimisation par judas. La façon la plus simple d'implémenter l'optimisation par judas est d'écrire manuellement un programme assembleur donné et de le comparer avec le code produit par votre compilateur.

Par exemple, si votre jeu d'instructions assembleur ne possède pas d'instruction pour la multiplication, alors on peut faire en sorte que votre compilateur produise du code pour la multiplication en répétant des additions. Une optimisation simple que l'on peut faire ici : si une opérande vaut 1, alors on peut stocker l'autre opérande en tant que résultat ; plutôt que partir dans une addition répétitive, qui est bien évidemment une boucle. De même, puisque le multicateur détermine le compteur de la boucle, on peut prendre la plus petite opérande en tant que multicateur.

Un autre exemple d'optimisation par judas est l'utilisation de sauts. Regardez l'exemple suivant :

            jmp .L1
               .
               .
               .
               .
               .
.L1         jmp .L2
               .
               .
               .
               .
               .

.L2         add ax,bx
    

Ici, le premier saut peut être modifié afin de réduire le nombre de sauts, comme montré c-dessous.

            jmp .L2
               .
               .
               .
               .
               .
.L1         jmp .L2
               .
               .
               .
               .
               .
.L2         add ax,bx 
    

Il existe différents algorithmes pour produire des code optimisés. Les méthodes discutées précédemment ne sont que le débuts des étapes vers des techniques complexes d'optimisation du temps et de l'espace.