La compilation, des arbres binaires vers les machines à piles

Des sujets de bac et d’agrégation de 2022 où on évoque la théorie des compilateurs
vendredi 23 septembre 2022
par  Alain BUSSER

On trouve

Dans cet article on propose des éléments de corrigés pour ces trois sujets.

Licence Creative Commons
Cet article est mis à disposition selon les termes de la Licence Creative Commons Attribution - Partage dans les Mêmes Conditions 2.0 France.

Parenthèses

Les expressions correctement parenthésées forment un langage algébrique, qui peut être reconnu par un automate à pile. Le cas de html est traité dans l’exercice 1 du sujet de NSI (jour 1) de métropole, dont voici un corrigé en ligne :

Notation polonaise

Le calcul sur une pile est ce qu’on obtient après compilation (voir plus bas). Le calcul lui-même est traité dans le premier exercice du sujet Liban-Mayotte 2022 (jour 2), dont voici un corrigé en ligne :

Dans toute la suite de cet article, on va étudier le sujet de l’agrégation d’informatique portant sur la compilation : comment, à partir d’une expression parenthésée (ou décrite par son arbre syntaxique qui est un arbre binaire), obtenir un programme similaire à ceux décrits ci-dessus ?

Compilation

1. Compilation d’expressions vers une machine à pile

1

On se propose de créer des utilitaires en Python (qui n’est pas le langage du sujet) pour lui déléguer la tâche de répondre à certaines des questions.

  1. X = 2
  2. Y = 5
  3.  
  4.  
  5. VAR('X');CONST(1);ADD();VAR('Y');MUL()
  6. print(pile)

Télécharger

1.1

Une machine à pile

Question 1

Voici une machine à pile :

Le source Python

  1. def VAR(nom,environnement=globals()):
  2.     global pile
  3.     pile.append(environnement[nom])
  4. def CONST(n):
  5.     global pile
  6.     pile.append(n)
  7. def ADD():
  8.     global pile
  9.     a = pile.pop()
  10.     b = pile.pop()
  11.     pile.append(a+b)
  12. def MUL():
  13.     global pile
  14.     a = pile.pop()
  15.     b = pile.pop()
  16.     pile.append(a*b)

Télécharger

avec

pile = []

l’exécution du code donne 15.

Question 2 : la fonction exec

Le source Python

  1. def executer(programme,environnement=globals()):
  2.     global pile
  3.     pile = []
  4.     liste_d_instructions = programme.split(';')
  5.     for k in range(len(liste_d_instructions)):
  6.         liste_d_instructions[k] = liste_d_instructions[k].split('(')
  7.         if len(liste_d_instructions[k])>1:
  8.             liste_d_instructions[k][1] = liste_d_instructions[k][1][:-1]
  9.     for i in liste_d_instructions:
  10.         kwafer = i[0]
  11.         arg = i[1]
  12.         if kwafer == 'CONST':
  13.             CONST(int(arg))
  14.         elif kwafer == 'VAR':
  15.             VAR(arg,environnement)
  16.         elif kwafer == 'ADD':
  17.             ADD()
  18.         elif kwafer == 'MUL':
  19.             MUL()
  20.         else:
  21.             raise Exception("Je ne connais pas "+kwafer)
  22.     return pile[-1]

Télécharger

Avec

  1. print(executer('VAR(X);CONST(1);ADD();VAR(Y);MUL()',{'X':2,'Y':5}))

on retrouve les 15 de la question précédente.

Question 3 : la consommation en espace

Le source Python

  1. def conso_espace(programme):
  2.     hauteur = 0
  3.     hauteur_max = 0
  4.     liste_d_instructions = programme.split(';')
  5.     for k in range(len(liste_d_instructions)):
  6.         liste_d_instructions[k] = liste_d_instructions[k].split('(')
  7.     for i in liste_d_instructions:
  8.         kwafer = i[0]
  9.         if kwafer == 'CONST':
  10.             hauteur += 1
  11.         elif kwafer == 'VAR':
  12.             hauteur += 1
  13.         elif kwafer == 'ADD':
  14.             hauteur -= 1
  15.         elif kwafer == 'MUL':
  16.             hauteur -= 1
  17.         if hauteur>hauteur_max:
  18.             hauteur_max = hauteur
  19.     return hauteur_max

Télécharger

Avec

  1. print(conso_espace('VAR(X);CONST(1);ADD();VAR(Y);MUL()'))

on obtient 2 : la pile culmine à une hauteur de 2.

1.2

Compilation simple des expressions arithmétiques

L’expression à compiler est donnée sous la forme d’un arbre binaire. Il est donc nécessaire de créer une classe BTree qui implémente les arbres binaires.

La classe BTree en Python

  1. class BTree():
  2.     def __init__(self,label=None,gauche=None,droit=None):
  3.         self.L = label
  4.         self.G = gauche
  5.         self.D = droit
  6.     def est_feuille(self):
  7.         return self.G is None and self.D is None

Télécharger

Avec

  1. e = BTree('*',BTree('+',BTree('X'),BTree('1')),BTree('Y'))

la variable e contient l’arbre de la question 1.

Dessiner les arbres

Voici une fonction Python qui, à partir d’un arbre décrit selon la syntaxe ci-dessus, produit un dessin de l’arbre :

  1. def dessiner(arbre):
  2.     global da, cptr
  3.     if arbre is not None:
  4.         cptr += 1
  5.         num = str(cptr)
  6.         da.node(num,arbre.L,shape='circle')
  7.         if arbre.G is not None:
  8.             ng = dessiner(arbre.G)
  9.             da.edge(num,ng)
  10.         if arbre.D is not None:
  11.             nd = dessiner(arbre.D)
  12.             da.edge(num,nd)
  13.     return num

Télécharger

Elle utilise la variable globale da qui est définie au début :

  1. from graphviz import *
  2.  
  3. da = Graph(format='png')
  4. cptr = 0

Télécharger

Avec

  1. dessiner(e)
  2. da.render()

Télécharger

on obtient le dessin qui ouvre cette partie :

Le code produit par cet arbre est obtenu à l’aide du compilateur ci-dessous.

Question 4

Le compilateur en Python

  1. def compiler(arbre):
  2.     if arbre.est_feuille():
  3.         label = arbre.L
  4.         try:
  5.             int(label)
  6.             s = 'CONST('+label+')'
  7.         except:
  8.             s = 'VAR('+label+')'
  9.     else:
  10.         if arbre.L=='+':
  11.             s = compiler(arbre.G)+'; '+compiler(arbre.D)+'; ADD'
  12.         elif arbre.L=='*':
  13.             s = compiler(arbre.G)+'; '+compiler(arbre.D)+'; MUL'
  14.         else:
  15.             raise Exception("Syntax error")
  16.     return s

Télécharger

Avec l’expression e ci-dessus,

compiler(e)

donne le programme de la question 1.

Question 6

Pour l’opposé on fait

C(e);OPP

Pour la soustraction on fait

C(e1);C(e2);OPP;ADD

1.3

Consommation en espace du code compilé

Question 7

La famille Gn

Elle est définie récursivement par

  1. def G(n):
  2.     if n==0:
  3.         return BTree('0')
  4.     else:
  5.         return BTree('+',G(n-1),BTree(str(n)))

Télécharger

En voici quelques représentants :

G0 :

G1 :

G2 :

G3 :

et G5 :

La famille Dn

Elle est définie récursivement par

  1. def D(n):
  2.     if n==0:
  3.         return BTree('0')
  4.     else:
  5.         return BTree('+',BTree(str(n)),D(n-1))

Télécharger

En voici quelques représentants :

D0 :

D1 :

D2 :

D3 :

et D5 :

La consommation en espace de Dn (2) étant nettement moins grande que celle de Dn (n+1), cela motive l’onglet suivant.

Question 8

Pour une constante ou une variable, la consommation en espace est 1.

Pour une somme ou un produit, la consommation en espace est

T(e1)+T(e2)+1

1.4

Compilation qui minimise la consommation en espace

Questions 9 et 17

Calcul des nombres de Strahler en Python

  1. def S(arbre):
  2.     if arbre.est_feuille():
  3.         return 1
  4.     elif S(arbre.G)==S(arbre.D):
  5.         return 1+S(arbre.G)
  6.     else:
  7.         return max(S(arbre.G),S(arbre.D))

Télécharger

Avec

  1. e = BTree('*',BTree('+',BTree('X'),BTree('1')),BTree('Y'))
  2.  
  3. print(S(e))

Télécharger

on trouve 2.

Question 10

On trouve 2 pour les graphes Gn et Dn, sauf pour G0 et D0 qui ont un nombre de Strahler égal à 1.

Questions 11 et 18

Le compilateur d’Ershov en Python

  1. def compiler(arbre):
  2.     if arbre.est_feuille():
  3.         label = arbre.L
  4.         try:
  5.             int(label)
  6.             s = 'CONST('+label+')'
  7.         except:
  8.             s = 'VAR('+label+')'
  9.     else:
  10.         if arbre.L=='+':
  11.             if S(arbre.G)>=S(arbre.D):
  12.                 s = compiler(arbre.G)+'; '+compiler(arbre.D)+'; ADD'
  13.             else:
  14.                 s = compiler(arbre.D)+'; '+compiler(arbre.G)+'; ADD'
  15.         elif arbre.L=='*':
  16.             if S(arbre.G)>=S(arbre.D):
  17.                 s = compiler(arbre.G)+'; '+compiler(arbre.D)+'; MUL'
  18.             else:
  19.                 s = compiler(arbre.D)+'; '+compiler(arbre.G)+'; MUL'
  20.         else:
  21.             raise Exception("Syntax error")
  22.     return s

Télécharger

La compilation de G5 donne

  1. CONST(0); CONST(1); ADD; CONST(2); ADD; CONST(3); ADD; CONST(4); ADD; CONST(5); ADD

et la compilation de D5 donne

  1. CONST(1); CONST(0); ADD; CONST(2); ADD; CONST(3); ADD; CONST(4); ADD; CONST(5); ADD

Question 13

Un indice : Récurrence sur l’expression e

Question 14

Une expression ayant au maximum 7 nœuds internes a nécessairement au maximum 8 feuilles, et est donc de taille maximale 7+8==15. D’après le résultat de la question précédente, son nombre de Strahler est majoré par 4 cqfd.

Question 15

Cette expression convient :

En effet elle se compile en

  1. CONST(0); CONST(1); ADD; CONST(2); CONST(3); ADD; ADD; CONST(4); CONST(5); ADD; CONST(6); CONST(7); ADD; ADD; ADD; CONST(8); CONST(9); ADD; CONST(10); CONST(11); ADD; ADD; CONST(12); CONST(13); ADD; CONST(14); CONST(15); ADD; ADD; ADD; ADD

qui fait culminer la hauteur de la pile à 5.

Question 16

Le nombre de Straheler de l’opposé d’une expression est 1 de plus que le nombre de Strahler de l’expression. Le code produit est encore

E(e)+';OPP'

Le nombre de Strahler d’une différence se calcule comme celui d’une somme. Le code produit dépend des nombres de Strahler des deux termes :

  • si le nombre de Strahler de e1 est au moins aussi grand que celui de e2 alors la compilation donne

E(e1)+';'+E(e2)+'OPP; ADD'

  • sinon la compilation donne
    E(e2)+'; OPP; '+E(e1)+'; ADD'

Questions 19 et 20

La compilation passe par un parcours suffixe de l’expression. Ce parcours est de complexité linéaire par rapport à la taille de l’arbre. Mais à chaque étape on calcule récursivement le sous-arbre considéré, pour calculer le nombre de Strahler. L’algorithme est donc de complexité quadratique. Pour l’améliorer il faudrait calculer en même temps le nombre de Strahler et l’expression compilée.

2. Compilation d’expressions vers une machine à registres

2.1

Une machine à registres

On a vu que l’algorithme d’Ershov produit un code peu gourmand en espace. Dans cette partie on reprogramme l’algorithme d’Ershov pour une pile de longueur finie, simulée par une machine à registres.

2.2

Le compilateur en Python

  1. def C(arbre,d):
  2.     if arbre.est_feuille():
  3.         label = arbre.L
  4.         try:
  5.             int(label)
  6.             s = 'MOV(R'+str(d)+','+label+')'
  7.         except:
  8.             s = 'LOAD(R'+str(d)+','+label+')'
  9.     else:
  10.         if arbre.L=='+':
  11.             s = C(arbre.G,d)+';'+C(arbre.D,d+1)+';ADD(R'+str(d)+',R'+str(d)+',R'+str(d+1)+')'
  12.         elif arbre.L=='*':
  13.             s = C(arbre.G,d)+';'+C(arbre.D,d+1)+';MUL(R'+str(d)+',R'+str(d)+',R'+str(d+1)+')'
  14.         else:
  15.             raise Exception("Syntax error")
  16.     return s

Télécharger

Question 21

En soumettant au compilateur ci-dessus l’arbre de la première question :

on obtient

  1. LOAD(R1,X)
  2. MOV(R2,1)
  3. ADD(R1,R1,R2)
  4. LOAD(R2,Y)
  5. MUL(R1,R1,R2)

Télécharger

Question 22

Une fois exécuté le code compilé, le registre Rd contient le résultat du calcul, et les registres de numéros inférieurs à d contiennent les étapes intermédiaires du calcul.

Question 23

En compilant l’arbre D5

on obtient le programme

  1. MOV(R1,5)
  2. MOV(R2,4)
  3. MOV(R3,3)
  4. MOV(R4,2)
  5. MOV(R5,1)
  6. MOV(R6,0)
  7. ADD(R5,R5,R6)
  8. ADD(R4,R4,R5)
  9. ADD(R3,R3,R4)
  10. ADD(R2,R2,R3)
  11. ADD(R1,R1,R2)

Télécharger

qui utilise 6 registres et ne peut donc s’exécuter sur une machine à 5 registres. Plus généralement, il faut n+1 registres pour calculer Dn et l’expression Dn convient pour répondre à la question.

Question 24

le nouveau compilateur en Python

  1. def C(arbre,d):
  2.     if arbre.est_feuille():
  3.         label = arbre.L
  4.         try:
  5.             int(label)
  6.             s = 'MOV(R'+str(d)+','+label+')'
  7.         except:
  8.             s = 'LOAD(R'+str(d)+','+label+')'
  9.     else:
  10.         if arbre.L=='+':
  11.             if S(arbre.G)>=S(arbre.D):
  12.                 s = C(arbre.G,d)+';'+C(arbre.D,d+1)+';ADD(R'+str(d)+',R'+str(d)+',R'+str(d+1)+')'
  13.             else:
  14.                 s = C(arbre.D,d)+';'+C(arbre.G,d+1)+';ADD(R'+str(d)+',R'+str(d)+',R'+str(d+1)+')'
  15.         elif arbre.L=='*':
  16.             if S(arbre.G)>=S(arbre.D):
  17.                 s = C(arbre.G,d)+';'+C(arbre.D,d+1)+';MUL(R'+str(d)+',R'+str(d)+',R'+str(d+1)+')'
  18.             else:
  19.                 s = C(arbre.D,d)+';'+C(arbre.G,d+1)+';ADD(R'+str(d)+',R'+str(d)+',R'+str(d+1)+')'
  20.         else:
  21.             raise Exception("Syntax error")
  22.     return s

Télécharger

L’arbre D5 se compile alors en

  1. MOV(R1,1)
  2. MOV(R2,0)
  3. ADD(R1,R1,R2)
  4. MOV(R2,2)
  5. ADD(R1,R1,R2)
  6. MOV(R2,3)
  7. ADD(R1,R1,R2)
  8. MOV(R2,4)
  9. ADD(R1,R1,R2)
  10. MOV(R2,5)
  11. ADD(R1,R1,R2)

Télécharger

qui n’utilise que deux registres.

3. Compilation d’expressions avec partage

3

Dans cette partie, on abandonne les arbres syntaxiques comme

Pour leur préférer la version DAG (graphes orientés sans cycle) :

3.1

Introduction du problème

Question 29

L’arbre précédent

se compile par l’algorithme d’Ershov en

  1. MOV(R1,3)
  2. MOV(R2,5)
  3. MUL(R1,R1,R2)
  4. MOV(R2,2)
  5. ADD(R1,R1,R2)
  6. MOV(R2,3)
  7. MOV(R3,5)
  8. MUL(R2,R2,R3)
  9. ADD(R1,R1,R2)
  10. MOV(R2,3)
  11. MOV(R3,5)
  12. MUL(R2,R2,R3)
  13. MOV(R3,2)
  14. ADD(R2,R2,R3)
  15. MUL(R1,R1,R2)

Télécharger

qui utilise 3 registres, alors que le graphe correspondant

peut être évalué par

  1. MOV(R1,3)
  2. MOV(R2,5)
  3. MUL(R1,R1,R2)
  4. MOV(R2,2)
  5. ADD(R1,R1,R2)
  6. MUL(R2,R1,R2)

Télécharger

qui n’utilise que deux registres.

Pour la suite, on considère le graphe

h0 = [[3],[3],[4],[5,4],[5,6],[6],[]]

dont le dessin est

Le dessin du graphe en Python

Le dessin ci-dessus a été obtenu à l’aide de cette fonction :

  1. def dessin(graphe):
  2.     for k in range(len(graphe)):
  3.         da.node(str(k),str(k),shape='circle')
  4.     for k in range(len(graphe)):
  5.         for j in graphe[k]:
  6.             da.edge(str(k),str(j))
  7.     da.render()

Télécharger

sur

  1. from graphviz import *
  2. da = Digraph(format='png')

Télécharger

et le graphe ci-dessus.

Question 30

La solution en Python

  1. def transpose(graphe):
  2.     nS = len(graphe)
  3.     envers = [[] for k in range(nS)]
  4.     for k in range(nS):
  5.         for x in graphe[k]:
  6.             envers[x].append(k)
  7.     return envers

Télécharger

Avec ça,

transpose(h0)

donne le graphe

Source et puits

On peut alors définir en Python les notions de source et de puits :

  1. def puits(sommet,graphe):
  2.     return graphe[sommet] == []
  3.  
  4. def source(sommet,graphe):
  5.     return puits(sommet,transpose(graphe))

Télécharger

La notion de source sera redéfinie plus tard.

Question 31

La version Python

Il suffit de traduire la définition d’un ordre topologique :

  1. def est_ordre(graphe,topo):
  2.     for i in range(len(topo)):
  3.         for j in range(i):
  4.             if j in graphe[i]:
  5.                 return False
  6.     return True

Télécharger

est_ordre(h0,[2,1,0,3,4,5,6])

s’évalue à True : il s’agit bien d’un ordre topologique.

ordre topologique

Avec l’ordre (2,1,0,3,4,5,6) le film de la compilation montre qu’à un moment on va avoir besoin de 4 registres simultanément (0,1,2 et 3) :

L’ordre (0,1,3,2,4,5,6) est un ordre topologique comme le montre

print(est_ordre(h0,[0,1,3,2,4,5,6]))

et donne une compilation ne nécessitant jamais plus de 3 registres :

Strahler

On redéfinit la notion de source à partir du nombre de prédécesseurs :

  1. def nb_pred(sommet,graphe):
  2.     return len(transpose(graphe)[sommet])
  3.  
  4. def source(sommet,graphe):
  5.     return nb_pred(sommet,graphe)==0

Télécharger

La fonction S en Python

  1. def S(s,G):
  2.     if source(s,G):
  3.         return 1
  4.     elif nb_pred(s,G)==1:
  5.         return S(transpose(G)[s][0])
  6.     else:
  7.         [t,u] = transpose(G)[s]
  8.         if S(t,G)==S(u,G):
  9.             return 1+S(t,G)
  10.         else:
  11.             return max(S(t,G),S(u,G))

Télécharger

Question 33

solution Python

  1. def strahler_graphe(graphe):
  2.     tab = [0 for k in range(len(graphe))]
  3.     for k in range(len(graphe)):
  4.         tab[k]=S(k,graphe)
  5.     return tab

Télécharger

Question 34

Ordre de Strahler d’un sommet

On définit l’ordre de Strahler d’un sommet :

  1. def S(s,G):
  2.     if source(s,G):
  3.         return 1
  4.     elif nb_pred(s,G)==1:
  5.         return S(transpose(G)[s][0])
  6.     else:
  7.         [t,u] = transpose(G)[s]
  8.         if S(t,G)==S(u,G):
  9.             return 1+S(t,G)
  10.         else:
  11.             return max(S(t,G),S(u,G))

Télécharger

Ordre de Strahler d’un graphe

L’ordre de Strahler d’un graphe est l’ordre de son unique puits :

  1. def ordre_strahler(graphe):
  2.     s = -1
  3.     for t in range(len(graphe)):
  4.         if len(graphe[t])==0:
  5.             s = t
  6.     return ordre(s,graphe)

Télécharger

Sur le graphe de l’onglet précédent, l’ordre de Strahler est l’ordre ne nécessitant que 3 registres.

Question 35

On s’intéresse au graphe suivant :

Son ordre de Strahler est

[0, 1, 3, 2, 4, 5, 6]

Mais sur ce graphe, la compilation selon cet ordre nécessite jusqu’à 5 registres :

On peut faire mieux avec cet autre odre, dont on vérifie qu’il est bien un ordre topologique :

[0,1,3,5,2,4,6]

Il ne nécessite que 4 registres :

Dans le jeu du marquage, on autorise les mouvements de jetons et dans ce jeu sur le graphe ci-dessus, on arrive en un temps 8 à placer un jeton sur le sommet 6, en utilisant au maximum 3 jetons (mouvements 2,2,2,3,1,2,3,3) :

Jeu du marquage

Règle du jeu

Le jeu se joue sur un graphe orienté. Trois sortes de mouvements sont possibles :

  1. enlever un jeton d’un sommet,
  2. ajouter un jeton sur un sommet n’ayant aucun prédécesseur non couvert de jeton,
  3. si tous les prédécesseurs d’un sommet sont couverts de jetons, glisser l’un d’entre eux sur ce sommet.

Le but du jeu est de couvrir le puits par un jeton. Une stratégie est une suite de chiffres pris parmi 1, 2 et 3 qui amène à couvrir le puits par un jeton.

Question 36

La stratégie 2,2,3,1,2,3,3,3 permet de couvrir le sommet 6 par un jeton :

Elle n’utilise que 2 jetons en temps 8. Donc pour ce graphe, Mmin est égal à 2.

Question 37

La stratégie consistant à n’utliser que le mouvement 2 (en suivant par exemple un ordre topologique comme ceux vus précédemment) permet de couvrir le puits par un jeton, en plaçant n jetons (donc en temps n).

Question 38

Voici les premiers graphes pyramidaux :

P1 :

P2 :

P3 :

P4 :

P5 :

génération de ces graphes

Les graphes pyramidaux peuvent être construits itérativement, même si leur structure est récursive :

  1. from graphviz import *
  2. da = Digraph(format='png')
  3.  
  4. def P(k):
  5.     for x in range(k):
  6.         for y in range(k-x):
  7.             da.node(str(x)+','+str(y),'',shape='circle')
  8.     for x in range(k-1):
  9.         for y in range(k-1-x):
  10.             da.edge(str(x+1)+','+str(y),str(x)+','+str(y))
  11.             da.edge(str(x)+','+str(y+1),str(x)+','+str(y))

Télécharger

Une stratégie pour un graphe pyramidal (ci-dessous, P4) consiste à placer n jetons sur les n sources puis faire glisser les n-1 premiers d’entre eux vers les sources de Pn-1 etc :

Elle prend un temps n×(n-1)/2.


Commentaires

Navigation

Articles de la rubrique

  • La compilation, des arbres binaires vers les machines à piles