Le procédé de décompilation des arbres syntaxiques – l'évaluation d'un texte – et la langage – Lisp – suggèrent l'introduction d'une nouvelle forme de décompilation : l'exécution du programme.
On reprend ici l'exemple du langage (§ 1) et celui des fonctions (§ 2) en vue d'une interprétation effective du programme en cours d'édition.
1. L'exécution
On reprend l'exemple des fonctions.
précision de l'exemple
Ici aussi on précise mieux l'exemple :
somme.Figure 3.a : grammaire des fonctions [ << masquer ]
(def type-int
((def nom () ("integer"))
(def conv () ((STG)))))
(def type-real
((def nom () ("real"))
(def conv () ((STG)))))
(def type-bool
((def nom () ("boolean"))
(def conv () ((STG)))))
(def affect ()
((VAR) ":=" (EXP) ";"))
(def affiche ()
("write(" (EXP) ");"))
(def cond ()
("IF " (TEST) " THEN" "^M"
" " (ALORS) "^M"
"ELSE" "^M"
" " (SINON) "^M"
"END IF;" "^M"))
(def none ()
("NONE"))
(def somme ()
((EXP1) " + " (EXP2)))
(def fonction
((def return
((def VAR ()
((NOM ((bloc-fct))))))
((affect)))
(def call-rec
((def BLOC-FCT
((bloc-fct))))
((call-fct))))
("FUNCTION " (NOM ((bloc-fct))) " (" (formel ((PARAM ((bloc-fct))))) ")"
" RETURNS " (TYP ((bloc-fct))) ";" "^M"
"BEGIN" "^M"
" " (INSTR ((bloc-fct))) "^M"
"END;" "^M"))
(def call-fct ()
((NOM ((BLOC-FCT))) " (" (effect) ")"))
(def formel ()
((NOM) " : " (SNS) " " (TYP)))
(def effect ()
((EXP)))
(def var
((def lect () ((NOM)))
(def ecr () ((NOM)))))
Figure 3.b : la fonction compte [ << masquer ]
(def fct-compte ()
((fonction)
(def bloc-fct
((def NOM () ("compte"))
(def TYP () ((type-int)))
(def PARAM
((param-arbre)))
(def param-arbre
((def NOM () ("a"))
(def TYP () ((type-arbre)))
(def SNS () ("IN"))
(def VAL () ((lsp *)))
(var)))
(def INSTR
((def TEST
((def BLOC-FCT
((bloc-fct ((fct-feuille)))))
(def EXP ((param-arbre ((bloc-fct)))) ((lect))))
((call-fct)))
(def ALORS
((def EXP ((type-int))
((conv
((def STG () ("1"))))))
((return)))
(def SINON
((def EXP ()
((def EXP1
((def EXP
((def BLOC-FCT
((bloc-fct ((fct-fg)))))
(def EXP ((param-arbre ((bloc-fct)))) ((lect)))))
((call-fct))))
((call-rec)))
(def EXP2
((def EXP
((def BLOC-FCT
((bloc-fct ((fct-fd)))))
(def EXP ((param-arbre ((bloc-fct)))) ((lect)))))
((call-fct))))
((call-rec))))
((somme))))
((return))))
((cond))))))
((fonction)))
Figure 3.c : les fonctions sur les arbres [ << masquer ]
(def type-arbre
((def nom () ("arbre"))
(def conv () ((STG)))))
(def fct-feuille
((fonction)
(def bloc-fct
((def NOM () ("feuille"))
(def TYP () ((type-bool)))
(def PARAM
((param-arbre)))
(def param-arbre
((def NOM () ("a"))
(def TYP () ((type-arbre)))
(def SNS () ("IN")))
(def VAL () ((lsp *)))
(var)))
(def INSTR
((none))))))
((fonction)))
(def fct-fg
((fonction)
(def bloc-fct
((def NOM () ("fg"))
(def TYP () ((type-arbre)))
(def PARAM
((param-arbre)))
(def param-arbre
((def NOM () ("a"))
(def TYP () ((type-arbre)))
(def SNS () ("IN")))
(def VAL () ((lsp *)))
(var)))
(def INSTR
((none))))))
((fonction)))
(def fct-fg
((fonction)
(def bloc-fct
((def NOM () ("fd"))
(def TYP () "arbre"))
(def PARAM
((param-arbre)))
(def param-arbre
((def NOM () ("a"))
(def TYP () ("arbre"))
(def SNS () ("IN")))
(def VAL () ((lsp *)))
(var)))
(def INSTR
((none))))))
((fonction)))
la grammaire d'exécution
On construit la grammaire d'exécution :
empile et depile, pour gérer la pile des appels récursifs.Dans l'exemple, la fonction compte utilise les fonctions sur les arbres feuille, fg et fd, pour lesquelles on n'a pas encore écrit le corps. Au lieu d'en écrire un, et fixer alors dans le programme un certain choix de représentation du type arbre, on remplace le corps de ces fonctions par du code d'exécution – du code Lisp, introduit par l'opérateur exec.
Figure 4 : la grammaire d'exécution [ << masquer ]
(def type-int
((def nom () ("integer"))
(def conv ()
(exec
(conv-int (clean STG))))))
(def type-real
((def nom () ("real"))
(def conv ()
(exec
(conv-real (clean STG))))))
(def type-bool
((def nom () ("boolean"))
(def conv ()
(exec
(conv-real (clean STG))))))
(def affect ()
(funclean VAR () ((clean EXP))))
(def affiche ()
(exec
(print (clean EXP))))
(def cond ()
(exec
(if (clean EXP-COND) (use THEN-CLAUSE) (use ELSE-CLAUSE))))
(def none ()
())
(def somme ()
(exec
(+ (clean EXP1) (clean EXP2))))
(def fonction
((def return () ((EXP)))
(def call-rec ()
(exec
(let ((val (clean EXP)))
(use empile ((PARAM ((bloc-fct)))))
(funclean ecr ((PARAM ((bloc-fct)))) ((lsp val))))
(prog1
(clean INSTR ((bloc-fct)))
(use depile ((PARAM ((bloc-fct))))))))
())
(def call-fct ()
(exec
(use effect)
(let ((ctx (cons-env
(eval `(env (ref fonction env))
(def bloc-fct ((ref BLOC-FCT (env)) (rep))))
ctx)))
(clean INSTR ((bloc-fct))))))
(def formel ())
(def effect ()
(funclean ecr ((PARAM ((BLOC-FCT))))
((clean EXP))))
(def var
((def lect ()
(exec
(setq aux (recht 'VAL))
(setq aux (cdr (nth <fct> (repq (cdr aux)))))
(car aux)))
(def ecr ()
(exec
'(lambda (x)
(setq aux (recht 'VAL))
(setq aux (cdr (nth <fct> (repq (cdr aux)))))
(rplaca aux x))))
(def empile ()
(exec
(setq aux (recht 'VAL))
(setq aux (cdr (nth <fct> (repq (cdr aux)))))
(rplaca aux (1+ (car aux)))
(newr aux '*)))
(def depile ()
(exec
(setq aux (recht 'VAL))
(setq aux (cdr (nth <fct> (repq (cdr aux)))))
(rplaca aux (1- (car aux)))
(setq aux (nthcdr (car aux) aux))
(rplacd aux nil)))))
le type arbre
On représente très simplement un arbre par une liste à deux champs. Ce choix n'offre aucune garantie vis-à-vis du programme (typage, facilité de traduction dans le langage, etc.). Mais il permet à la fonction appelante compte d'avoir l'illusion que le type arbre a déjà été réalisé – les appels à ces fonctions retournent des valeurs qui semblent traduire un "bon comportement".
Figure 5 : le type arbre [ << masquer ]
(def type-arbre
((def nom () ("arbre"))
(def conv ()
(clean STG))))
(def fct-feuille
((fonction)
(def bloc-fct
((def NOM () ("feuille"))
(def TYP () ((type-bool)))
(def PARAM
((param-arbre)))
(def param-arbre
((def NOM () ("a"))
(def TYP () ((type-arbre)))
(def SNS () ("IN")))
(def VAL () ((lsp 1 *)))
(var)))
(def INSTR ()
(exec
(atom (clean lect ((param-arbre ((bloc-fct))))))))))
((fonction)))
(def fct-fg
((fonction)
(def bloc-fct
((def NOM () ("fg"))
(def TYP () ((type-arbre)))
(def PARAM
((param-arbre)))
(def param-arbre
((def NOM () ("a"))
(def TYP () ((type-arbre)))
(def SNS () ("IN")))
(def VAL () ((lsp 1 *)))
(var)))
(def INSTR ()
(exec
(car (clean lect ((param-arbre ((bloc-fct))))))))))
((fonction)))
(def fct-fg ()
((fonction)
(def bloc-fct
((def NOM () ("fd"))
(def TYP () "arbre"))
(def PARAM
((param-arbre)))
(def param-arbre
((def NOM () ("a"))
(def TYP () ("arbre"))
(def SNS () ("IN")))
(def VAL () ((lsp 1 *)))
(var)))
(def INSTR ()
(exec
(cadr (clean lect ((param-arbre ((bloc-fct))))))))))
((fonction)))