Par Pramode C E iclabs@vnsl.com
La conception de compilateurs et d'interpréteurs est un domaine rempli de défis - un de ceux qui offrent beaucoup d'occasions pour une exploration théorique autant que pour le code lui-même. Étant un amateur de Python, j'ai essayé d'implémenter quelques idées que j'ai appris au sujet des compilateurs et interpréteurs dans ce langage magnifique. Comme je ne suis ni un gourou de Python, ni un expert en compilateur, l'implémentation peut être imparfaite. Mais cela a été en tous cas une vraie partie de plaisir!
Ne soyez pas déçu si je vous dis que je ne discuterai pas ici de l'implémentation d'un langage orienté-objet fonctionnel avec ramasse-miette automatique et tout le reste! Le langage dont je vous parlerai ici est le langage que nous apprenons enfant, celui des expressions arithmétiques. Par exemple,
1+2*3-4
1/2+3-4/5
.....
Nous commencerons avec un programme qui va lire une
expression de cette forme et l'évaluera directement. Nous le
modifierons ensuite pour générer une structure de donnée appelée un
arbre syntaxique qui pourra ensuite être évalué par des
algorithmes récursifs. La prochaine étape sera de générer des
instructions pour une machine virtuelle en utilisant cet arbre
syntaxique. Finalement, nous sauvegarderons ces instructions sur
disque et les exécuterons à la demande avec un interpréteur.
Les langages de programmation sont souvent décrits à l'aide d'une notation compacte et puissante appelée grammaire sans contexte. La grammaire décrit un ensemble de substitutions. Voici un exemple de grammaire pour les expressions arithmétiques
E ::= T { ADDOP T }
T ::= F { MULOP F }
F ::= 0 | 1 | 2 | 3 | .....
ADDOP ::= + | -
MULOP ::= * | /
Considérez que E désigne une expression, T un terme et F désigne un facteur. Les accolades signifient aucune ou plusieurs occurrences. En lisant la première production, nous pouvons dire que Une expression est un terme, suivi par aucune ou plusieurs occurrences d'une opérateur d'addition et d'un terme. La troisième production déclare qu'un facteur est soit 0 ou 1 ou 2 ou 3 ou 4 et ainsi de suite, ie, l'ensemble des entiers positifs. Ça prend un certain temps pour s'habituer à des définitions ésotériques comme celle-ci, mais si vous avez une compréhension de base des structures récursives comme celles-ci, ce n'est pas très difficile.
Voici le source pour un évaluateur d'expression simple en Python. ( version texte)
#------------------Un évaluateur d'expression simple---------------#
import re, string
Inputbuf = []
# Un morceau (token) est soit un nombre soit un opérateur symbolique. Le
# programme principale (main) lit une ligne en entrée (input) et la
# sauvegarde dans un vecteur appelé Inputbuf. La fonction gettoken()
# retourne les différents morceaux de ce vecteur.
def gettoken():
global Inputbuf
p = re.search('^\W*[\+\-\*/]|^\W*[0-9]+', Inputbuf)
token = p.string[p.regs[0][0]:p.regs[0][1]]
token = string.strip(token)
if token not in ['+', '-', '*', '/']:
token = int(token)
Inputbuf = Inputbuf[p.regs[0][1]:]
return token
# lookahead() cherche dans le flot d'entrée et vous dit quel est le
# prochain morceau d'entrée.
def lookahead():
global Inputbuf
try:
p = re.search('^\W*[\+\-\*/]|^\W*[0-9]+', Inputbuf)
token = p.string[p.regs[0][0]:p.regs[0][1]]
token = string.strip(token)
if token not in ['+', '-', '*', '/']:
token = int(token)
return token
except:
return None
def factor():
return gettoken()
def term():
e1 = factor()
tmp = lookahead()
while (tmp in ['*', '/']):
gettoken()
if (tmp == '*'):
e1 = e1 * factor()
else:
e1 = e1 / factor()
tmp = lookahead()
return e1
def expression():
e1 = term()
tmp = lookahead()
while (tmp in ['+', '-']):
gettoken()
if (tmp == '+'):
e1 = e1 + term()
else:
e1 = e1 - term()
tmp = lookahead()
return e1
def main():
global Inputbuf
Inputbuf = raw_input()
print expression()
if __name__=='__main__':
main()
Il serait bon de tracer l'exécution du code ci-dessus pour quelques expressions.
Le programme ci-dessus évalue l'expression arithmétique à opérateur infixe fournie. Nous allons maintenant le modifier pour produire un arbre syntaxique à la place. Un arbre syntaxique pour l'expression 1+2*3 devrait ressembler à ceci
+
/ \
/ \
1 *
/ \
/ \
2 3
Chaque noeud de l'arbre comprend les éléments suivants
L'arbre est construit de bas en haut. La fonction factor crée simplement un nouveau noeud contenant un nombre, initialise les pointeurs left et right à NULL, et retourne le noeud. La fonction expression() crée un nouveau noeud avec un opérateur + ou - pour le champ op, et assigne les pointeurs left et right aux valeurs obtenues en appelant term(). La fonction term() fonctionne d'une manière similaire.
#---------------Produire un arbre syntaxique--------------------#
# gettoken() et lookahead() sont les mêmes que dans le premier
# programme
NULL = 0
import re, string
Inputbuf = []
class Tree:
pass
def factor():
newnode = Tree()
newnode.number = gettoken()
newnode.left = newnode.right = 0
return newnode
def term():
left = factor()
tmp = lookahead()
while (tmp in ['*', '/']):
gettoken()
right = factor()
newnode = Tree()
newnode.op = tmp
newnode.left = left
newnode.right = right
left = newnode
tmp = lookahead()
return left
def expression():
left = term()
tmp = lookahead()
while (tmp in ['+', '-']):
gettoken()
right = term()
newnode = Tree()
newnode.op = tmp
newnode.left = left
newnode.right = right
left = newnode
tmp = lookahead()
return left
def treeprint(ptree):
if (ptree):
try:
print ptree.op
except:
print ptree.number
treeprint(ptree.left)
treeprint(ptree.right)
def main():
global Inputbuf
Inputbuf = raw_input()
ptree = expression()
return ptree
if __name__=='__main__':
ptree = main()
treeprint(ptree)
L'arbre syntaxique que nous avons créé peut être facilement évalué grâce à une fonction récursive. Mais nous allons adopter une méthode différente. Nous allons générer du code pour évaluer les expressions dans le jeu d'instructions d'une machine simple hypothétique appelé machine à pile. Les instructions dont cette machine disposera sont très simples - pousser un nombre sur la pile (push), additionner deux nombres (add), multiplier deux nombres (mul), etc. Ainsi, l'évaluation de l'expression 1+2*3 nous donne le code suivant
push 1
push 2
push 3
mul
add
Ces instructions sont chargées dans un tableau. push, mul, add sont des fonctions. Les instructions peuvent être directement exécutées en parcourant le vecteur et en exécutant les fonctions contenues dans chacun des éléments du vecteur, ou elles peuvent être sauvegardées dans un fichier (une façon simple de le faire est d'utiliser le module pickle de Python, bien que ce soit un gaspillage d'espace). Un autre programme peut alors lire ce code, le charger dans un tableau et l'exécuter. Le code que j'ai écrit fonctionne ainsi si vous exécutez le programme sans aucun argument, il lit l'expression au clavier, génère le code pour la machine virtuelle dans un tableau et l'exécute en parcourant ce tableau. Le code est aussi sauvegardé dans un fichier appelé code.out. Ainsi, si vous exécutez le programme avec un nom de fichier code.out comme argument, il chargera les instructions du fichier et les exécutera, sans lire les entrées du clavier.
import re, string, sys, pickle
# Les fonctions non-inclues ici doivent être recopiées des exemples
# précédents.
NULL = 0
Inputbuf = []
NCODE = 100
NSTACK = 100
Code = []
Stack = [0] * NSTACK
Pc = 0
Stackp = 0
class Tree:
pass
class CodeItem:
pass
def initcode():
global Code
for i in range(0, NCODE):
t = CodeItem()
Code.append(t)
def pushop():
global Stack, Stackp, Code, Pc
Stack[Stackp] = Code[Pc].number
Stackp = Stackp + 1
Pc = Pc + 1
def addop():
global Stack, Stackp, Code, Pc
Stackp = Stackp - 1
right = Stack[Stackp]
Stackp = Stackp - 1
left = Stack[Stackp]
Stack[Stackp] = left + right
Stackp = Stackp + 1
# définit subop, mulop et divop.
def generate(codep, ptree):
try:
# si le champ numérique 'number' n'est pas présent,
# la ligne suivante génère une exception.
n = ptree.number
Code[codep].op = pushop
codep = codep + 1
Code[codep].number = n
codep = codep + 1
return codep
except:
if (ptree.op == '+'):
codep = generate(codep, ptree.left)
codep = generate(codep, ptree.right)
Code[codep].op = addop
codep = codep + 1
return codep
# elif (ptree.op == '-'): nous allons écrire ici la
# génération des actions pour '-', '*' et '/'.
def eval(ptree): # Génère les instructions puis les exécute.
global Pc, Stackp, Code, Stack
Pc = generate(0, ptree)
Code[Pc].op = NULL
Stackp = 0
Pc = 0
while Code[Pc].op != NULL:
tmp = Pc
Pc = Pc + 1
Code[tmp].op()
return Stack[0]
def eval2(): # Exécute directement le code chargé.
global Pc, Stackp, Code, Stack
Stackp = 0
Pc = 0
while Code[Pc].op != NULL:
tmp = Pc
Pc = Pc + 1
Code[tmp].op()
return Stack[0]
def main():
global Inputbuf, Code
try:
f = open(sys.argv[1])
Code = pickle.load(f)
f.close()
result = eval2()
print 'Le résultat est:', result
return result
except:
print 'Pas de fichier ouvert, lecture du clavier'
initcode()
Inputbuf = raw_input()
ptree = expression()
result = eval(ptree)
f = open('code.out', 'w')
pickle.dump(Code, f)
print 'Code inséré dans un fichier nommé code.out'
print 'le résultat est:', result
return result
if __name__=='__main__':
result = main()
generate() et eval() sont les fonctions les plus importantes. generate() parcourt l'arbre de l'expression en créant le code pour la machine virtuelle et en l'insérant dans un tableau appelé Code. eval() parcourt le tableau Code et exécute les instructions, en utilisant un tableau appelé Stack (Pile) pour stocker les résultats intermédiaires.
Il est possible d'étendre le programme ci-dessus pour qu'il supporte les variables et les assignations ainsi que les structures de contrôles comme goto, if, etc. En peu de temps, vous aurez bâti un langage simple ressemblant au Basic.
Étant habitué au C, l'absence de certaines constructions comme l'opérateur ++ dans Python a été un problème mineur. L'absence de déclarations de type à la compilation semble aussi avoir eu quelques effets nuisibles sur la lisibilité du code. Aussi, vous allez payer cher la moindre erreur de frappe. Si vous avez une variable f de type struct foo et que foo n'a pas de champ appelé next, une assignation de f.next va générer une erreur de compilation en C alors que l'interpréteur Python va sans problème permettre l'assignation.
Le livre habituel sur la conception de compilateur est Principles of Compiler Design par Aho A.V et Ullman J.D. L'inspiration pour cet article provient de The Practice of Programming, un autre excellent livre de Brian Kernighan et Rob Pike. Les fonctions generate et eval sont les versions Python de code provenant de ce livre. A Second course in Computer Science with Pascal par Daniel D. McCracken présente plusieurs algorithmes, incluant un évaluateur d'expressions, dans un style très engageant.
Copyright © 2000, Pramode C E. Paru dans le numéro 52 de la Linux Gazette d'avril 2000.
Traduction française de Fabien Niñoles.