Ici, j'ai essayé de montrer dans la pratique quels sont certains concepts importants du domaine de la création de compilateurs. Il est possible que de telles histoires terminées de 15 minutes puissent être un bon moyen de plonger dans des sujets complexes. Seulement ce serait bien de ne pas lire passivement ce qui est présenté ci-dessous, mais aussi de vérifier le code en cours.
Si la première expérience est réussie, à l'avenir, vous pouvez vous attendre à d'autres "croquis" de 15 minutes sur le sujet des compilateurs.
Ce qui sera discuté
Faisons un compilateur d'expression arithmétique. Celui qui traduit le texte source en notation polonaise inverse (il est également appelé RPN ou POLIZ) en code intermédiaire qui fonctionne avec la pile. Mais nous pouvons nous passer d'interprètes ici. Ensuite, nous traduisons immédiatement le résultat en une représentation C. Autrement dit, nous obtenons un compilateur de RPN à C.
Soit dit en passant, nous allons écrire le compilateur en Python. Mais ne laissez pas cela arrêter ceux qui préfèrent un autre langage de programmation. Voici un exercice utile pour vous: traduisez le code ci-dessous dans votre langue préférée. Ou utilisez une traduction déjà terminée:
Implémentation F # (par gsomix ):
première version
Version SSA
Commençons par l'analyse
def scan(source): tokens = source.split() return [("Push", int(x)) if x[0].isdigit() else ("Op", x) for x in tokens]
Qu'avons-nous fait ici? La fonction de numérisation reçoit une chaîne de l'utilisateur en notation polonaise inverse ("2 2 +").
Et à la sortie, nous obtenons sa représentation intermédiaire. Voici un exemple:
[ ('Push', 2), ('Push', 2), ('Op', '+') ]
Donc, nous avons déjà le compilateur. Mais il est très frivole. Rappelons qu'il s'agissait initialement de code C.
Diffusons en C
def trans(ir): code = [] for tag, val in ir: if tag == "Push": code.append("st[sp] = %d;" % val) code.append("sp += 1;") elif tag == "Op": code.append("st[sp - 2] = st[sp - 2] %s st[sp - 1];" % val) code.append("sp -= 1;") return "\n".join(code)
Que se passe-t-il ici? Regardons la sortie de cette fonction (en utilisant le même exemple avec "2 2 +").
st[sp] = 2; sp += 1; st[sp] = 2; sp += 1; st[sp - 2] = st[sp - 2] + st[sp - 1]; sp -= 1;
Oui, il ressemble déjà au code C. Array st joue le rôle de la pile et sp en est le pointeur. Habituellement, les machines de pile virtuelles fonctionnent avec ces choses.
C'est juste la machine elle-même - l'interprète, nous ne l'avons pas. Il y a un compilateur. Que nous reste-t-il? Il est nécessaire d'ajouter les trames nécessaires pour le programme C.
Notre premier compilateur fini
ST_SIZE = 100 C_CODE = r"""#include <stdio.h> int main(int argc, char** argv) { int st[%d], sp = 0; %s printf("%%d\n", st[sp - 1]); return 0; }""" def scan(source): tokens = source.split() return [("Push", int(x)) if x[0].isdigit() else ("Op", x) for x in tokens] def trans(ir): code = [] for tag, val in ir: if tag == "Push": code.append("st[sp] = %d;" % val) code.append("sp += 1;") elif tag == "Op": code.append("st[sp - 2] = st[sp - 2] %s st[sp - 1];" % val) code.append("sp -= 1;") return "\n".join(code) def rpn_to_c(source): return C_CODE % (ST_SIZE, trans(scan(source))) print(rpn_to_c("2 2 +"))
Il reste à compiler la sortie de ce programme avec le compilateur C.
Êtes-vous toujours prêt à continuer? Discutons ensuite de ce que nous avons fait. Il y a un moment douteux - notre compilateur traduit des expressions constantes, et vous pouvez les calculer simplement au stade de la compilation. Cela n'a aucun sens de les traduire en code. Mais prenons pour le moment que certains arguments peuvent entrer dans la pile de l'extérieur. Insistons sur le fait que le sens pratique de notre développement peut être donné plus tard. Maintenant, il est important d'avoir une idée générale de la construction des compilateurs les plus simples, non?
Aimez-vous le titre? SSA - cela semble très solide pour tout compilateur. Et maintenant, nous allons utiliser ce même SSA. Qu'est-ce que c'est? Avançons dans l'ordre.
Nous générons actuellement du code C, sans aucune machine virtuelle. Mais pourquoi avons-nous besoin d'un rudiment sous la forme d'opérations de pile? Remplaçons ces opérations en travaillant avec des variables ordinaires de C. De plus, nous n'enregistrerons pas de variables - nous aurons un nouveau nom pour chaque expression. Laissez le compilateur C gérer tout cela. Il s'avère qu'avec nous, chaque variable ne reçoit une valeur qu'une seule fois. Et c'est d'ailleurs la forme de l' ASS .
Voici notre nouveau compilateur.
C_CODE = r"""#include <stdio.h> int main(int argc, char** argv) { %s printf("%%d\n", %s); return 0; }""" def scan(source): tokens = source.split() return [("Push", int(x)) if x[0].isdigit() else ("Op", x) for x in tokens] def trans(ir): stack, code = [], [] name_cnt = 0 for tag, val in ir: if tag == "Push": code.append("int t%d = %d;" % (name_cnt, val)) stack.append("t%d" % name_cnt) name_cnt += 1 elif tag == "Op": a, b = stack.pop(), stack.pop() code.append("int t%d = %s %s %s;" % (name_cnt, b, val, a)) stack.append("t%d" % name_cnt) name_cnt += 1 return "\n".join(code), stack.pop() def rpn_to_c(source): return C_CODE % trans(scan(source)) print(rpn_to_c("2 2 +"))
Veuillez noter qu'il n'y a plus de pile dans le code C et que son utilisation est simulée pendant la traduction. La pile utilisée dans le processus de compilation ne contient pas de valeurs, mais des noms de variables.
Voici le résultat final:
#include <stdio.h> int main(int argc, char** argv) { int t0 = 2; int t1 = 2; int t2 = t0 + t1; printf("%d\n", t2); return 0; }
Résumé
Il semble que le temps de notre leçon commune soit écoulé. Nous étions engagés dans la traduction du programme d'une langue à une autre. C'est ce qu'on appelle la traduction de source à source. Ou - juste une traduction, qui peut être considérée comme un synonyme de compilation, mais généralement le compilateur traduit le programme d'une représentation de haut niveau à une représentation de bas niveau. Il existe également le mot à la mode «transpilateur» pour le traducteur de source à source. Mais la mention du «transpiler» peut être gênante pour les experts du compilateur, soyez prudent!
Expérimentez avec le code. En attente de commentaires!