Ne soyez pas déçu si je vous dis que je ne discuterai pas ici de l'implémentation d'un langage orienté-objet functionnel avec collecte de résidus 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 example,

Nous commencerons avec un programme qui lira une expression de cette forme et l'évaluera directement. Nous 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 cet arbre syntaxique. Finalement, nous sauvegarderons ces instructions sur disque et les exécuterons avec un interpréteur lorsque demandé.

Les langages de programmation sont souvent décrit à l'aide d'une notation compacte et puissante appelée grammaire sans contexte. La grammaire à contexte libre décrit un ensemble de substitutions. Voici un exemple d'une 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 occurences ». En lisant la première production, nous pouvons dire que « Une expression est un terme, suivi par aucune ou plusieurs occurences 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 ou un opérateur symbolique Le
# programme principale (main) lit une ligne d'entrée (input) et la
# sauvegarde dans un vecteur appelé Inputbuf. La fonction gettoken()
# retourne des morceaux individuels 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ées 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()

Ce serait bien de tracer l'exécution du code ci-dessus pour quelques expressions.

Le programme ci-dessus évalue l'expression arithmétique à opérateur central. Nous allons maintenant le modifier pour pour produire un arbre syntaxique à la place. Un arbre syntaxique pour l'expression 1+2*3 devrait avoir l'air de ceci :

Chaque nœud de l'arbre consistant aux éléments suivants :

L'arbre est contruit du bas vers le haut. La fonction factor crée simplement un nouveau nœud un nombre, initialise les pointeurs left et right à NULL, et retourne le nœud. La fonction éxpression() crée un nouveau nœud 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 façon similaire.

(version text)

#---------------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 adopterons une méthode différente. Nous générerons du code pour évaluer les expressions dans un ensemble d'instructions d'une simple machine hypothétique appelé « machine à pile ». Les instructions que cette machine aura sont très simples — pousse un nombre sur la pile (push), additionne deux nombres (add), multiplie 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 vecteur. push, mul, add sont des fonctions. Les instructions peuvent être directement exécutées en traversant le vecteur et en exécutant les fonctions contenues dans chacun des éléments du vecteur, ou ils peuvent être sauvegardé dans un fichier (une façon simple est d'utiliser le module pickle de Python, bien que ce soit un gaspillage d'espace). Un autre programme peut alors lire ce code dans un vecteur 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 du clavier, génère le code pour la machine virtuelle dans un vecteur et l'exécute en traversant le vecteur. Le code est aussi sauvegardé dans un fichier appelé code.out. Aussi, si vous exécuter le programme avec un nom de fichier code.out comme argument, il chargera les instructions du fichier et l'exécutera, sans lire le clavier.

(version texte)

import re, string, sys, pickle
# Les fonctions non-inclues ici doivent être incluses des examples
# 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

# defini 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 écriron 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 critiques. generate() traverse l'arbre de l'expression en créant le code pour la machine virtuelle et en l'insérant dans un vecteur Code. eval() traverse le vecteur Code et exécute les instructions, utilisant un vecteur Stack (Pile) pour retenir les résultats intermédiaires.

Il est possible d'étendre le programme ci-dessus pour qu'il supporte les variables et les assignations, les constructions de contrôles comme goto, if, etc. Bien vite, 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é une irritation mineure. 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 pour quelques erreurs de frappe. Si vous avez une variable f de type struct foo et que foo n'a pas de champ appelé next, une assignation à f.next va générer une erreur de compilation alors que l'interpréteur Python va simplement 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ésentent plusieurs algorithmes, incluant un évaluateur d'expressions, dans un style très engageant.