Python sous le capot — Chapitre 2 : Fonctionnement du compilateur CPython

Avant-propos

Ceci est la traduction du second article de Victor Skvortsov du 20 septembre 2020 : Python behind the scenes #2: how the CPython compiler works.

Sujet d’aujourd’hui

Dans le premier article de cette série, nous avons vu le fonctionnement de la VM CPython. Nous avons vu qu’elle fonctionnait en exécutant une série d’instructions appelé bytecode. Nous avons également vu que le bytecode Python n’est pas suffisant pour décrire tout ce qu’un morceau de code fait. C’est la raison pour laquelle il existe une notion de code object. Exécuter un code block, comme un module ou une fonction, signifie exécuter un code object correspondant. Un code object contient le bytecode du bloc, les constantes et les noms des variables utilisées dans le bloc et les diverses propriétés du bloc.

Généralement, un développeur Python n’écrit pas de bytecode et ne crée pas de code object, mais écrit du code Python normal. CPython doit donc être capable de créer un code object à partir d’un code source. Ce travail est effectué par le compilateur CPython. Dans cette partie, nous allons voir son fonctionnement.

Note : Dans cet article, je me réfère à CPython 3.9. Certains détails d’implémentation changeront sûrement au fil des évolutions de CPython. J’essaierai de faire un suivi des modifications d’ajouter des notes de mise à jour.

Qu’est-ce que le compilateur CPython

Nous comprenons maintenant quelles sont les responsabilités du compilateur CPython, mais avant de regarder comment il est implémenté, voyons d’abord pourquoi il porte le nom de « compilateur ».

Un compilateur tel qu’on l’entend généralement est un programme traduisant un programme écrit dans un langage en un programme équivalent écrit dans un autre langage. Il existe de nombreux types de compilateurs, mais la plupart du temps on parle de compilateur statique, qui traduit un programme dans un langage de haut niveau vers du code machine. Est-ce que le compilateur CPython entre dans cette catégorie ? Pour répondre à cette question, jetons un œil au trois étapes habituelles d’un compilateur statique.

L’interface¹ du compilateur transforme un code source en une représentation intermédiaire (IR). L’optimiseur prend alors cet IR, l’optimise et la transmet au backend qui génère le code machine. Si nous avons un IR qui n’est spécifique à aucun langage source et à aucune machine cible, alors nous bénéficions de cette conception en trois étapes : La prise en en charge d’un nouveau langage nécessite simplement l’ajout d’une nouvelle interface et il suffit d’ajouter un backend pour prendre en charge une nouvelle architecture.

La toolchain LLVM est un parfait exemple de la réussite de ce modèle. Il dispose d’interfaces pour le C, Rust, Swift et de nombreux autres langages qui s’appuient sur dessus pour s’occuper des parties plus compliquées du compilateur. Chris Lattner, le créateur de LLVM, donne un bon aperçu de son architecture.

CPython n’a besoin de prendre en charge ni plusieurs langages sources ni architectures cibles, mais uniquement du code Python et la VM CPython. Le compilateur CPython implémente néanmoins une conception en trois étapes. Pour comprendre ce choix, nous allons voir plus en détail chaque étape d’un compilateur en trois étapes.

L’image ci-dessus schématise l’architecture d’un compilateur classique. Comparons-le maintenant à l’architecture du compilateur CPython ci-dessous.

Ressemblant, n’est-ce pas ? La structure du compilateur CPython devrait sembler familière à quiconque a déjà étudié un compilateur. Si ce n’est pas votre cas, le célèbre Dragon Book est une excellente introduction à la théorie derrière la construction d’un compilateur. Il est long, mais vous avez tout intérêt à le lire, ne serait-ce que les premiers chapitres.

Notre comparaison mérite quelques précisions. Premièrement, depuis la version 3.9, CPython utilise un nouveau parser par défaut qui génère un AST (Abstract Syntax Tree) directement, sans l’étape de construction d’un arbre d’analyse². L’architecture du compilateur CPython est de ce fait simplifié. Deuxièmement, certaines des étapes du compilateur CPython font si peu de choses, comparé à leurs homologues des compilateurs statiques que certains développeurs de compilateurs hardcore affirme que CPython n’est rien de plus qu’une interface. Nous n’adopterons pas cette vision.

Aperçu de l’architecture du compilateur

Ces diagrammes sont bien jolis, mais ils cachent de nombreux détails qui peuvent être trompeurs, examinons donc la conception globale du compilateur CPython.

Les deux principaux composants du compilateur CPython sont :

• L’interface.
• Le backend.

L’interface prend du code Python et génère un AST. Le backend prends un AST et génère un code object. Dans le code source de CPython, les termes « parser » et « compiler » sont respectivement utilisés pour l’interface et le backend. Cela vient ajouter une nouvelle définition du mot « compilateur ». Il aurait probablement été plus simple de l’appeler code object generator, mais nous allons garder « compilateur », car il ne semble pas poser de problèmes particuliers.

Le travail du parser est de s’assurer que l’entrée soit un code Python syntaxiquement correct. Si ce n’est pas le cas, il remonte une erreur comme ici :

x = y = = 12
        ^
SyntaxError: invalid syntax

Si l’entrée est correcte, le parser l’organise alors selon les règles de la grammaire. La grammaire définie la syntaxe du langage. La notion de grammaire formelle est si importante pour la suite de la discussion que je pense que nous devrions faire une petite digression pour nous rappeler de sa définition formelle³.

Selon la définition classique, une grammaire est un ensemble de quatre éléments :

• Σ – un ensemble fini de symboles terminaux, ou simplement « terminaux » (habituellement noté par des lettres minuscules).
• 𝛮 – un ensemble fini de symboles non terminaux, ou simplement « non-terminaux » (habituellement noté par des lettres majuscules)⁴.
• 𝑃 – un ensemble de règles de production. Dans le cas d’une grammaire non contextuelle⁵, ce qui est le cas de la grammaire Python, une règle de production est simplement une relation entre un non terminal et n’importe quelle séquence de terminaux et non-terminaux, comme 𝐴 → 𝑎𝐵.
• 𝑆 – un non terminal distingué.

Une grammaire définit un langage constitué de séquences de terminaux pouvant être générées en appliquant des règles de production. Pour générer une séquence, on commence par le symbole 𝑆 puis on remplace récursivement chaque non-terminal par une séquence selon les règles de production, jusqu’à ce que la séquence entière soit composée uniquement de terminaux. En utilisant la convention établie pour la notation, il suffit de lister les règles de production pour spécifier la grammaire. Par exemple, voici une grammaire simple qui génère des séquences alternant des uns et des zéros :

𝑆 → 10𝑆 ∣ 10

Nous continuerons de parler des grammaires lorsque nous verrons le parser plus en détail.

L’Abstract Syntax Tree

La finalité du parser est de générer un AST. Un AST est une structure de données en arbre qui sert de représentation de haut niveau du code source. Voici un exemple d’un morceau de code et d’un dump de l’AST correspondant généré par le module standard ast :

x = 123
f(x)

$ python -m ast example1.py
Module(
   body=[
      Assign(
         targets=[
            Name(id='x', ctx=Store())],
         value=Constant(value=123)),
      Expr(
         value=Call(
            func=Name(id='f', ctx=Load()),
            args=[
               Name(id='x', ctx=Load())],
            keywords=[]))],
   type_ignores=[])

Les types des nœuds de l’AST sont définis par le Zephyr Abstract Syntax Definition Language (ASDL). L’ASDL est un langage déclaratif simple créé afin de décrire des IRs en forme d’arbre, ce qui est le cas de l’AST. Voici les définitions des nœuds Assign et Expr tel que décrient dans Parser/Python.asdl :

``` text stmt = ... | Assign(expr targets, expr value, string? type_comment) | ... expr = ... | Call(expr func, expr args, keyword* keywords) | ...

La spécification *ASDL* devrait nous donner une idée de ce à quoi ressemble l’AST en Python. Le *parser* doit cependant représenter l’*AST* en code C. Heureusement, il est facile de générer les structures C pour les nœuds *AST* à partir de leurs descriptions *ASDL*. C’est ce que fait CPython, et le résultat ressemble à ceci :

``` c
struct _stmt {
    enum _stmt_kind kind;
    union {
        // ... other kinds of statements
        struct {
            asdl_seq *targets;
            expr_ty value;
            string type_comment;
        } Assign;
        // ... other kinds of statements
    } v;
    int lineno;
    int col_offset;
    int end_lineno;
    int end_col_offset;
};

struct _expr {
    enum _expr_kind kind;
    union {
        // ... other kinds of expressions
        struct {
            expr_ty func;
            asdl_seq *args;
            asdl_seq *keywords;
        } Call;
        // ... other kinds of expressions
    } v;
    // ... same as in _stmt
};

Un AST est une représentation avec laquelle il est pratique de travailler. Il décrit ce que le programme fait en cachant toutes les informations non essentielles comme l’indentation, la ponctuation et autres fonctionnalités syntaxiques de Python.

Celui qui bénéficie le plus de la représentation AST est le compilateur, qui peut parcours l’AST et émettre du bytecode de façon relativement simple. En plus du compilateur, de nombreux outils Python utilisent l’AST pour manipuler du code Python. Par exemple, pytest fait des modifications sur l’AST pour remonter des informations utiles lorsque l’instruction assert échoue, cette dernière étant supposée lever un simple AssertionError si l’expression est évaluée à False. Un autre exemple est Bandit qui détecte les problèmes de sécurité fréquents dans le code Python en analysant l’AST.

Maintenant que nous avons étudié un peu l’AST de Python, nous pouvons voir comment le parser le génère à partir du code source.

Du code source vers l’AST

Comme mentionné plus tôt, depuis la version 3.9, CPython n’a pas un mais deux parsers. Le nouveau est activé par défaut. Il est également possible d’utiliser l’ancien en passant l’argument -X oldparser. En revanche il sera complètement supprimé en dans CPython 3.10.

Les deux parsers sont très différents. Nous allons nous concentrer sur le nouveau, mais jeter un œil également à l’ancien.

L’ancien parser

Pendant longtemps, la syntaxe de Python était définie par de la grammaire générative. C’est le genre de grammaire dont nous avons parlé plus tôt. Elle nous indique comment générer des séquences correspondant au langage. Le problème est qu’une grammaire générative ne correspond pas directement à l’algorithme capable d’analyser ces séquences. Heureusement, des gens intelligents ont pu séparer les grammaires génératives en classes pour chacune desquelles on peut générer un parser correspondant. Celles-ci incluent les grammaires non contextuelles, LL(k), LR(k), LALR et de nombreux autres types de grammaires. La grammaire de Python est LL(1). Elle est définie en utilisant une sorte d’Extended Backus–Naur Form (EBNF). Pour avoir une idée de la façon dont elles peuvent décrire la syntaxe de Python, jetez un œil aux règles de l’instruction while.

file_input: (NEWLINE | stmt)* ENDMARKER
stmt: simple_stmt | compound_stmt
compound_stmt: ... | while_stmt | ...
while_stmt: 'while' namedexpr_test ':' suite ['else' ':' suite]
suite: simple_stmt | NEWLINE INDENT stmt+ DEDENT
...

CPython étend la notation habituelle avec des caractéristiques comme :

• regroupement des alternatives : (a | b)
• parties facultatives : [a]
• zéro ou plus et une ou plusieurs répétitions : a * et a +.

Nous pouvons voir pourquoi Guido van Rossum a choisi d’utiliser des expressions régulières. Elles permettent d’exprimer la syntaxe d’un langage de programmation de manière plus naturelle (pour un programmeur). Au lieu d’écrire 𝐴 → 𝑎𝐴|𝑎, nous pouvons simplement écrire 𝐴 → 𝑎+. Ce choix a eu un coût : CPython a dû développer une méthode pour supporter cette notation étendue.

The parsing of an LL(1) grammar is a solved problem. The solution is a Pushdown Automaton (PDA), which acts as a top-down parser. A PDA operates by simulating the generation of an input string using a stack. To parse some input, it starts with the start symbol on the stack. Then it looks at the first symbol in the input, guesses which rule should be applied to the start symbol and replaces it with the right-hand side of that rule. If a top symbol on the stack is a terminal that matches the next symbol in the input, a PDA pops it and skips the matched symbol. If a top symbol is a nonterminal, a PDA tries to guess the rule to replace it with based on the symbol in the input. The process repeats until the whole input is scanned or if a PDA can't match a terminal on the stack with the next symbol in the input, resulting in an error.

TODO: Difficile à traduire pour l’instant.

L’analyse d’une grammaire LL(1) est un problème résolu. La solution est le Pushdown Automaton (PDA)<sup>6</sup>, qui agit comme un parser de haut en bas. Le PDA fonctionne en simulant la génération d’une string d’entrée à l’aide d’une pile. Pour analyser certaines entrées, il commence par le symbole du début de la pile. Il regarde ensuite le premier symbole de l’entrée, devine quelle règle doit être appliquée au symbole du début et le remplace avec l’élément de cette règle. Si un symbole du haut de la pile est un terminal correspondant au symbole suivant dans l’entrée, le PDA le fait apparaître et ignore le symbole correspondant. Si un symbole du haut n’est pas un terminal, le PDA tente de deviner la règle par laquelle le remplacer en fonction du symbole dans l’entrée. Le processus se répète jusqu’à ce que toute l’entrée soit analysée ou si le PDA ne peut pas faire correspondre un terminal de la pile avec le symbole suivant dans l’entrée, ce qui entraîne une erreur.

CPython ne pouvait pas utiliser cette méthode directement en raison de la façon dont les règles de production sont écrites, une nouvelle méthode a donc dû être développée. Pour prendre en charge la notation étendue, l’ancien parser représentait chaque règle de la grammaire avec un Deterministic Finite Automaton (DFA), réputé pour être équivalent à une expression régulière. Le parser lui-même est un automate basé sur une pile comme le PDA, mais au lieu de pousser des symboles sur la pile, il pousse les états des DFA. Voici les principales structures de données utilisées par l’ancien parser :

typedef struct {
    int              s_state;       /* State in current DFA */
    const dfa       *s_dfa;         /* Current DFA */
    struct _node    *s_parent;      /* Where to add next node */
} stackentry;

typedef struct {
    stackentry      *s_top;         /* Top entry */
    stackentry       s_base[MAXSTACK];/* Array of stack entries */
                                    /* NB The stack grows down */
} stack;

typedef struct {
    stack           p_stack;        /* Stack of parser states */
    grammar         *p_grammar;     /* Grammar to use */
                                    // basically, a collection of DFAs
    node            *p_tree;        /* Top of parse tree */
    // ...
} parser_state;

Et le commentaire de Parser/parser.c résumant cette approche :

Une règle d’analyse prend la forme d’un Deterministic Finite-state Automaton (DFA). Un nœud dans un DFA représente un état du parser ; un arc représente une transition. Les transitions sont soit étiquetées avec des symboles terminaux, soit avec des non-terminaux. Lorsque le parser décide de suivre un arc étiqueté avec un non-terminal, il est appelé récursivement avec, comme état initial, le DFA représentant la règle d’analyse ; lorsque ce DFA accepte, le parser qui l’a appelé continue. L’arbre d’analyse généré récursivement par le parser est inséré en tant qu’enfant dans l’arbre d’analyse courant.

The parser builds a parse tree, also known as Concrete Syntax Tree (CST), while parsing an input. In contrast to an AST, a parse tree directly corresponds to the rules applied when deriving an input. All nodes in a parse tree are represented using the same node struct:

Le parser crée donc un arbre d’analyse, également connu sous le nom de Concrete Syntax Tree (CST), en analysant la string d’entrée. Contrairement à un AST, un arbre d’analyse correspond directement aux règles appliquées lors de la dérivation d’une entrée. Les nœuds d’un arbre d’analyse sont représentés à l’aide d’une même structure node :

typedef struct _node {
    short               n_type;
    char                *n_str;
    int                 n_lineno;
    int                 n_col_offset;
    int                 n_nchildren;
    struct _node        *n_child;
    int                 n_end_lineno;
    int                 n_end_col_offset;
} node;

A parse tree, however, is not what the compiler waits for. It has to be converted to an AST. This work is done in Python/ast.c. The algorithm is to walk a parse tree recursively and translate its nodes to the AST nodes. Hardly anyone finds these nearly 6,000 lines of code exciting.

Un arbre d’analyse n’est cependant pas ce qu’attend le compilateur. Il doit être converti en AST d’abord. Ce travail est fait par Python/ast.c. L’algorithme consiste à traverser récursivement l’arbre d’analyse et à traduire ces nœuds en nœuds AST. Peu de gens trouve passionnantes ces près de 6 000 lignes de code.

tokenizer

D’un point de vue syntaxique, Python n’est pas un langage simple. La grammaire de Python est en revanche simple à lire et tiens dans quelque 200 lignes avec ces commentaires. En effet, les symboles de la grammaire sont des tokens<sup>7</sup> et non des caractères individuels. Un token est représenté par le type, comme NUMBER, NAME, NEWLINE, la valeur et la position dans le code source. CPython distingue 63 types de tokens, tous répertoriés dans Grammaire/Tokens. Nous pouvons voir à quoi ressemble un programme « tokenisé » en utilisant le module standard tokenize :

def x_plus(x):
    if x >= 0:
        return x
    return 0

$ python -m tokenize example2.py
0,0-0,0:            ENCODING       'utf-8'
1,0-1,3:            NAME           'def'
1,4-1,10:           NAME           'x_plus'
1,10-1,11:          OP             '('
1,11-1,12:          NAME           'x'
1,12-1,13:          OP             ')'
1,13-1,14:          OP             ':'
1,14-1,15:          NEWLINE        '\n'
2,0-2,4:            INDENT         '    '
2,4-2,6:            NAME           'if'
2,7-2,8:            NAME           'x'
2,9-2,11:           OP             '>='
2,12-2,13:          NUMBER         '0'
2,13-2,14:          OP             ':'
2,14-2,15:          NEWLINE        '\n'
3,0-3,8:            INDENT         '        '
3,8-3,14:           NAME           'return'
3,15-3,16:          NAME           'x'
3,16-3,17:          NEWLINE        '\n'
4,4-4,4:            DEDENT         ''
4,4-4,10:           NAME           'return'
4,11-4,12:          NUMBER         '0'
4,12-4,13:          NEWLINE        '\n'
5,0-5,0:            DEDENT         ''
5,0-5,0:            ENDMARKER      ''

Voici comment un programme est perçu par le parser. Lorsque qu’il a besoin d’un token, il en demande un au tokenizer. Le tokenizer lit un caractère à la fois dans le buffer et essaie de faire correspondre le préfixe lu avec un type de token. Comment le tokenizer fonctionne-t-il avec différents encodages ? Il s’appuie sur le module io. Tout d’abord, le tokenizer détecte l’encodage. Si aucun encodage n’est spécifié, la valeur par défaut est UTF-8. Ensuite, le tokenizer ouvre un fichier avec un appel C, qui équivaut à open(fd, mode='r', encoding=enc) en Python, et lit son contenu en appelant la fonction readline. Cette fonction renvoie une string Unicode. Les caractères que le tokenizer lit ne sont que des octets dans la représentation UTF-8 de cette chaîne (ou EOF).

Nous pourrions définir ce qu’on entend par NUMBER et NAME directement dans la grammaire, mais cela la rendrait plus complexe. Ce qu’on ne pourrait en revanche pas faire c’est exprimer la signification de l’indentation dans la grammaire sans la rendre sensible au contexte et par conséquent, difficile à parser. Le tokenizer simplifie le travail du parser en fournissant les tokens INDENT et DEDENT. Leur signification est celle des accolades en C. Le tokenizer est suffisamment puissant pour gérer l’indentation, car il dispose d’états. Le niveau d’indentation courant est gardé au-dessus de la pile. Quand ce niveau augmente, il est poussé sur la pile. Quand il diminue, les niveaux supérieurs sont jetés de la pile.

L’ancien parser est un élément non trivial du code source de CPython. Les DFAs des règles de grammaire sont générés automatiquement, mais les autres parties du parser sont écrient à la main. Cela contraste avec le nouveau parser, qui semble être une solution beaucoup plus élégante au problème d’analyse du code Python.

Le nouveau parser

Le nouveau parser utilise une nouvelle grammaire. Cette grammaire est Parsing Expression Grammar (PEG). Il est important de comprendre qu’une PEG n’est pas une catégorie de grammaires, mais une façon de définir une grammaire. Les PEG ont été présentées en 2004 par Bryan Ford comme un outil permettant de décrire un langage de programmation et de générer un parser s’appuyant sur cette description. Une PEG est différente d’une grammaire formelle traditionnelle dans la mesure où ses règles font correspondre des non-terminaux avec des expressions d’analyse plutôt qu’à des séquences de symboles, dans l’esprit de CPython. Une expression d’analyse est définie de façon inductive. Si 𝑒, 𝑒₁, et 𝑒₂ sont des expressions d’analyse, avec :

1. la string vide.
2. n’importe quel terminal.
3. n’importe quel non-terminal.
4. 𝑒₁𝑒₂, une séquence.
5. 𝑒₁/𝑒₂, un choix une séquence.
6. 𝑒*, aucune-ou-plusieurs répétitions.
7. !𝑒, un non-prédicat.

Les PEGs sont des grammaires analytiques, ce qui veut dire qu’elles ne sont pas seulement conçues pour générer des langages, mais aussi pour les analyser. Ford a formalisé ce qu’il faut pour qu’une expression d’analyse 𝑒 reconnaisse une entrée 𝑥. Fondamentalement, toute tentative de reconnaissance d’une entrée avec une expression d’analyse peut réussir ou échouer, et consommer une entrée ou non. Par exemple, l’application de l’expression d’analyse 𝑎 à l’entrée 𝑎𝑏 aboutit à un succès et consomme 𝑎.

Cette formalisation permet de convertir n’importe quel PEG en un parser à descente récursive. Un tel parser associe chaque non-terminal d’une grammaire à une fonction d’analyse. Dans le cas d’un PEG, le corps d’une fonction d’analyse est une implémentation de l’expression d’analyse correspondante. Si une expression d’analyse contient des non-terminaux, leurs fonctions d’analyse sont appelées de manière récursive.

Un parser à descente récursive doit choisir entre les différentes règles de production, si un non-terminal en a plus d’une. Si une grammaire est LL(k), le parser peut lire les k prochains tokens de l’entrée et prédire la bonne règle. Un tel parser est dit prédictif. Si la prédiction est impossible, la méthode du « rétropédalage » est utilisée. Un parser utilisant une telle méthode essai une règle, si cette dernière échoue, il revient en arrière et tente la règle suivante. Il fait cela jusqu’à ce qu’une règle réussisse. C’est exactement ce que l’opérateur de choix prioritaire fait dans le cas d’une PEG. Une PEG est donc un parser à descente récursive avec rétropédalage.

La méthode du rétropédalage est puissante mais peut être coûteuse en opération. Prenons un exemple simple. Appliquons l’expression 𝐴𝐵/𝐴 à l’entrée réussissant sur 𝐴, mais échouant sur 𝐵. Selon l’interprétation de l’opérateur de choix prioritaire, le parser essaie d’abord de reconnaître 𝐴, réussit, puis essai de reconnaître 𝐵. Il échoue sur 𝐵, puis ré-essai de reconnaître 𝐴. Du fait de cette redondance d’opérations, le temps d’analyse peut être exponentiel à la taille de l’entrée. Pour remédier à ce problème, Ford suggère d’utiliser une technique de mémorisation, c’est-à-dire caché les résultats des appels des fonctions. En utilisant cette technique d’analyse, le parser, appelé packrat parser, a la garantie d’être sur une complexité algorithmique linéaire au prix d’une consommation de mémoire plus élevée. Et c’est ce que fait le nouveau parser CPython. C’est un packrat parser !

Quelle que soit la qualité du nouveau parser, les raisons du remplacement de l’ancien parser doivent être données. C’est à ça que servent les PEP. PEP 617 -- New PEG parser for CPython donne des détails sur l’ancien et le nouveau parser et explique les raisons de cette transition. En un mot, le nouveau parser supprime la restriction LL(1) sur la grammaire et devrait être plus facile à maintenir. Guido van Rossum a écrit une excellente série de billets, dans laquelle il entre plus en détail et montre comment implémenter un parser PEG simple. Nous allons à notre tour jeter un œil à son implémentation CPython.%

Vous serez peut-être surpris d’apprendre que le nouveau code source de grammaire est plus de trois fois plus gros que l’ancien. Cette nouvelle grammaire n’est plus seulement une grammaire mais un schéma de traduction syntaxique (SDTS). Un SDTS est une grammaire avec des actions attachées aux règles. Une action est un morceau de code. Le parser tente d’appliquer une règle sur l’entrée. Si elle réussit, le parser exécute l’action correspondant a cette règle. CPython utilise des actions pour créer l’AST. Pour voir comment, voyons à quoi ressemble la nouvelle grammaire. Nous avons déjà vu les règles de l’ancienne grammaire pour l’instruction while, voici donc leurs nouvelles analogues :

file[mod_ty]: a=[statements] ENDMARKER { _PyPegen_make_module(p, a) }
statements[asdl_seq*]: a=statement+ { _PyPegen_seq_flatten(p, a) }
statement[asdl_seq*]: a=compound_stmt { _PyPegen_singleton_seq(p, a) } | simple_stmt
compound_stmt[stmt_ty]:
    | ...
    | &'while' while_stmt
while_stmt[stmt_ty]:
    | 'while' a=named_expression ':' b=block c=[else_block] { _Py_While(a, b, c, EXTRA) }
...

Chaque règle commence par le nom d’un non-terminal, suivi du type C du résultat renvoyé par la fonction d’analyse. La partie de droite est une expression d’analyse. Le code entre accolades indique une action. Les actions sont de simples appels de fonction qui renvoient des nœuds AST ou leurs paramètres.

Le nouveau parser est Parser/pegen/parse.c. Ce fichier est généré automatiquement par le générateur de parser. Le générateur de parser est écrit en Python. C’est un programme qui prend une grammaire et génère un parser PEG en C ou Python. Une grammaire est représentée par une instance de la classe Grammar. Mais pour construire un objet Grammar, il doit y avoir un parser pour le fichier de grammaire. Ce parser est lui aussi généré automatiquement par le générateur de parser à partir du fichier de méta-grammaire. C’est pourquoi le générateur de parser peut générer un parser en Python. Mais qui parse la méta-grammaire ? Eh bien, c’est dans la même notation que la grammaire, donc le parser de grammaire généré est également capable de parser la méta-grammaire. Bien sûr, le parser de grammaire doit être bootstrapé, c’est-à-dire que la première version doit être écrite à la main. Une fois cela fait, tous les parsers peuvent être générés automatiquement.

Tout comme l’ancien parser, le nouveau reçoit les tokens du tokenizer. C’est inhabituel pour un parser PEG, ces derniers permettant d’unifier la tokenization et l’analyse. Mais nous avons pu voir que le tokenizer faisait un travail complexe, les développeurs de CPython ont donc décidé de l’utiliser.

Sur cette note, nous terminons notre discussion sur l’analyse pour voir ce qui se passe à côté d’un AST.

Optimisation de l’AST

Le diagramme de l’architecture du compilateur CPython nous montre l’optimiseur AST aux côtés du parser et du compilateur. Cela donne probablement trop d’importance à l’optimiseur AST. Ce dernier n’étant assigné qu’au constant folding et n’a été introduit que dans CPython 3.7. Avant CPython 3.7, le constant folding était effectué à un stade ultérieur par le peephole optimizer. Néanmoins, grâce à l’optimiseur AST, nous pouvons écrire des choses comme :

n = 2 ** 32 # easier to write and to read

Et espérer qu’elles soient calculées au moment de la compilation. Un exemple d’optimisation moins évidente est la conversion respective d’une liste de constantes et d’un set de constantes en un tuple et un frozenset.

Passage de l’AST vers du code object

Jusqu’à présent, nous avons étudié comment CPython convertis un code source en AST, mais comme nous l’avons vu dans le premier article, la VM CPython n’a aucune notion de ce qu’est un AST et ne sait exécuter que du code object. La conversion d’un AST en code object est faite par le compilateur. Plus exactement, le compilateur doit renvoyer le code object du module contenant le bytecode du module accompagné des code objects des autres blocs de code de modules comme les définitions des fonctions et des classes.

Parfois, la meilleure façon de comprendre la solution à un problème est de se mettre en situation. Réfléchissons à ce que nous ferions si nous étions le compilateur. Nous commençons par le nœud racine d’un AST qui représente un module. Les enfants de ce nœud sont des déclarations. Supposons que la première instruction soit une simple affectation comme x = 1. C’est représenté par le nœud de l’AST Assign : Assign(targets=[Name(id='x', ctx=Store())], value=Constant(value=1)). Pour convertir ce nœud en code object, nous devons créer le code object, stocker 1 dans sa liste des constantes, stocker le nom de la variable x dans la liste des noms utilisés dans ce code object puis émettre l’instruction LOAD_CONST et STORE_NAME. On pourrait écrire une fonction pour faire ça, mais même une simple assignation peut être délicate. Par exemple, imaginez que la même assignation soit effectuée à l’intérieur du corp de la fonction. Si x est une variable locale, il nous faudra emmètre l’instruction STORE_FAST. Si x est une variable globale, il nous faudra emmètre l’instruction STORE_GLOBAL. Enfin, si x est référencé par une fonction imbriquée, il nous faudra emmètre l’instruction STORE_DEREF. La question est alors de savoir de quel type est la variable x. CPython résout ce problème en générant une table de symboles avant la compilation.

Table de symboles

Une table de symboles contient les informations sur les blocs de code et les symboles qu’ils utilisent. Elle est représentée par une unique struct symtable et une collection de struct _symtable_entry, une pour chaque code block d’un programme. Une entrée dans la table de symboles contient les propriétés d’un code block, à savoir son nom, son type (module, classe ou fonction), et un dictionnaire faisant la relation entre les noms des variables utilisées dans le code block et les flags indiquant leur portée et leur utilisation. Voici une définition complète de la struct _symtable_entry :

typedef struct _symtable_entry {
    PyObject_HEAD
    PyObject *ste_id;        /* int: key in ste_table->st_blocks */
    PyObject *ste_symbols;   /* dict: variable names to flags */
    PyObject *ste_name;      /* string: name of current block */
    PyObject *ste_varnames;  /* list of function parameters */
    PyObject *ste_children;  /* list of child blocks */
    PyObject *ste_directives;/* locations of global and nonlocal statements */
    _Py_block_ty ste_type;   /* module, class, or function */
    int ste_nested;      /* true if block is nested */
    unsigned ste_free : 1;        /* true if block has free variables */
    unsigned ste_child_free : 1;  /* true if a child block has free vars,
                                     including free refs to globals */
    unsigned ste_generator : 1;   /* true if namespace is a generator */
    unsigned ste_coroutine : 1;   /* true if namespace is a coroutine */
    unsigned ste_comprehension : 1; /* true if namespace is a list comprehension */
    unsigned ste_varargs : 1;     /* true if block has varargs */
    unsigned ste_varkeywords : 1; /* true if block has varkeywords */
    unsigned ste_returns_value : 1;  /* true if namespace uses return with
                                        an argument */
    unsigned ste_needs_class_closure : 1; /* for class scopes, true if a
                                             closure over __class__
                                             should be created */
    unsigned ste_comp_iter_target : 1; /* true if visiting comprehension target */
    int ste_comp_iter_expr; /* non-zero if visiting a comprehension range expression */
    int ste_lineno;          /* first line of block */
    int ste_col_offset;      /* offset of first line of block */
    int ste_opt_lineno;      /* lineno of last exec or import * */
    int ste_opt_col_offset;  /* offset of last exec or import * */
    struct symtable *ste_table;
} PySTEntryObject;

Dans le cas des tables de symboles, CPython utilise le terme namespace comme un synonyme de code block. On peut alors dire qu’une entrée dans la table des symboles est la description d’un namespace. Les entrées de la table des symboles forme la hiérarchie de tous les namespaces d’un programme via le champs ste_children, qui est une liste de namespaces enfants. Nous pouvons introspecter cette hiérarchie en utilisant le module standard symtable :

# example3.py
def func(x):
    lc = [x+i for i in range(10)]
    return lc

>>> from symtable import symtable
>>> f = open('example3.py')
>>> st = symtable(f.read(), 'example3.py', 'exec') # module's symtable entry
>>> dir(st)
[..., 'get_children', 'get_id', 'get_identifiers', 'get_lineno', 'get_name',
 'get_symbols', 'get_type', 'has_children', 'is_nested', 'is_optimized', 'lookup']
>>> st.get_children()
[<Function SymbolTable for func in example3.py>]
>>> func_st = st.get_children()[0] # func's symtable entry
>>> func_st.get_children()
[<Function SymbolTable for listcomp in example3.py>]
>>> lc_st = func_st.get_children()[0] # list comprehension's symtable entry
>>> lc_st.get_symbols()
[<symbol '.0'>, <symbol 'i'>, <symbol 'x'>]
>>> x_sym = lc_st.get_symbols()[2]
>>> dir(x_sym)
[..., 'get_name', 'get_namespace', 'get_namespaces', 'is_annotated',
 'is_assigned', 'is_declared_global', 'is_free', 'is_global', 'is_imported',
 'is_local', 'is_namespace', 'is_nonlocal', 'is_parameter', 'is_referenced']
>>> x_sym.is_local(), x_sym.is_free()
(False, True)

Cet exemple montre que chaque blocs de code a une table de symboles dédiée. Nous some accidentellement tombé sur le symbole étrange .0 à l’intérieur du namespace de la list comprehension. Ce namespace ne contient pas le symbole range, ce qui est tout aussi bizarre. En fait, la list comprehension est implémenté sous forme de fonction anonyme et range(10) lui est passé comme argument. Cet argument est représenté par .0. Que CPython nous cache-t-il d’autre ?

Les entrées de table de symboles sont généré en deux passes. Durant la première passe, CPython traverse l’AST et créé une table de symboles pour chaque code block qu’il rencontre. Il recueille également des informations qui peuvent être collectées à la volée, par exemple, si un symbole est défini ou utilisé dans le bloc. Mais certaines informations sont difficiles à déduire lors du premier passage. Prenons l’exemple :

def top():
    def nested():
        return x + 1
    x = 10
    ...

Quand on génère l’entrée de table de symboles de la fonction nested, nous ne pouvons pas dire si x est une variable globale ou libre, c’est à dire défini dans la fonction parent, car nous n’avons pas vu encore rencontré d’affectation.

CPython résout ce problème en effectuant une seconde passe. Au début de cette seconde passe il sait déjà où sont défini les symbols et comment ils sont utilisés. L’information manquante est récupéré en visitant récursivement chacune des entrées de table des symboles, en commençant par le haut. Les symboles défini dans la portée englobante sont passé au namespace inférieur, et les noms des variables libres de la porté englobé sont remontés.

Les entrées de la table des symboles sont géré en utilisant la struct symtable. Elle est utilisé à la fois pour construire les entrées de table des symboles et y accéder durant la compilation. Jetons un œil à sa définition :

struct symtable {
    PyObject *st_filename;          /* name of file being compiled,
                                       decoded from the filesystem encoding */
    struct _symtable_entry *st_cur; /* current symbol table entry */
    struct _symtable_entry *st_top; /* symbol table entry for module */
    PyObject *st_blocks;            /* dict: map AST node addresses
                                     *       to symbol table entries */
    PyObject *st_stack;             /* list: stack of namespace info */
    PyObject *st_global;            /* borrowed ref to st_top->ste_symbols */
    int st_nblocks;                 /* number of blocks used. kept for
                                       consistency with the corresponding
                                       compiler structure */
    PyObject *st_private;           /* name of current class or NULL */
    PyFutureFeatures *st_future;    /* module's future features that affect
                                       the symbol table */
    int recursion_depth;            /* current recursion depth */
    int recursion_limit;            /* recursion limit */
};

Les champs st_stack et st_blocks sont les plus importants. st_stack est une pile d’entrées de tables de symboles. Durant la première passe de la construction de la table des symboles, CPython pousse une entrée dans la pile quand il y entre, et la fait sauter quand il la quitte. st_blocks est un dictionnaire utilisé par le compilateur pour récupérer une entrée de table de symboles pour un nœud AST donné. Les champs st_cur et st_top sont également important mais leur signification sont évidentes.

Pour en apprendre plus sur les tables de symboles et leur construction, je vous recommande vivement la lecture des articles de Eli Bendersky.

basic blocks

Une table de symboles nous permet de traduire des instructions impliquant des variables, tel que x = 1. Mais un problème apparaît si on essai de traduire une instruction d’un control flow plus complexe. Prenons ce morceau de code :

if x == 0 or x > 17:
    y = True
else:
    y = False
...

Le sous arbre de l’AST correspondant a la structure suivante :

If(
  test=BoolOp(...),
  body=[...],
  orelse=[...]
)

Que le compilateur traduit dans le bytecode suivant :

1           0 LOAD_NAME                0 (x)
            2 LOAD_CONST               0 (0)
            4 COMPARE_OP               2 (==)
            6 POP_JUMP_IF_TRUE        16
            8 LOAD_NAME                0 (x)
           10 LOAD_CONST               1 (17)
           12 COMPARE_OP               4 (>)
           14 POP_JUMP_IF_FALSE       22

2     >>   16 LOAD_CONST               2 (True)
           18 STORE_NAME               1 (y)
           20 JUMP_FORWARD             4 (to 26)

4     >>   22 LOAD_CONST               3 (False)
           24 STORE_NAME               1 (y)
5     >>   26 ...

La génération du bytecode est linéaire, Les instructions du nœud test arrivent en premier, et les instructions du bloc body arrivent avant celles du bloc orelse. Le problème c’est que le control flow implique des sauts, et un saut est souvent émit avant l’instruction vers laquelle il pointe. Dans notre exemple, si le premier test réussi, on saute immédiatement vers la première instruction de body, mais nous ne savons pas encore où elle sera. Si le second test échoue, nous devons sauter par dessus le bloc body, vers le bloc orelse, mais la position de la première instruction orelse ne sera connu qu’après avoir traduit le bloc body.

On peut résoudre ce problème en déplaçant les instructions de chaque bloc dans des structures séparées. Puis, au lieu de spécifier la position exacte des cibles des sauts dans le bytecode, on pointe vers ces structures. Enfin, quand tous les blocs sont traduit et leur taille connu, on calcul les arguments des sauts et on assemble les blocs en une unique séquence d’instructions. Et c’est ce que fait le compilateur.

The blocks we're talking about are called basic blocks. They are not specific to CPython, though CPython's notion of a basic block differs from the conventional definition. According to the Dragon book, a basic block is a maximal sequence of instructions such that:

Les blocs dont nous parlons sont appelés « blocs de base »<sup>10</sup>. Ils ne sont pas spécifiques à CPython, bien que la notion de bloc de base de CPython diffère de la définition conventionnelle. Selon le livre Dragon, un bloc de base est une séquence maximale d’instructions, telle que :

1. Le control flow ne peut entrer que dans la première instruction du bloc.
2. Le control flow quitte le bloc sans s’arrêter ni brancher<sup>11</sup>, sauf, éventuellement, à la dernière instruction.

CPython n’a pas cette seconde exigence. En d’autres termes, aucune instruction d’un bloc de base ne peut être la cible d’un saut, à l’exception de la première, mais un bloc de base peut contenir des instructions de saut. Pour traduire l’AST de notre exemple, le compilateur crée quatre blocs de base :

1. Les instruction 0-14 pour test.
2. Les instruction 16-20 pour body.
3. Les instruction 22-24 pour orelse.
4. Les instruction 26-… pour tout ce qui vient après l’instruction if.

A basic block is represented by the basicblock_ struct that is defined as follows : Un bloc de base est représenté par la structure basicblock_ :

typedef struct basicblock_ {
    /* Each basicblock in a compilation unit is linked via b_list in the
       reverse order that the block are allocated.  b_list points to the next
       block, not to be confused with b_next, which is next by control flow. */
    struct basicblock_ *b_list;
    /* number of instructions used */
    int b_iused;
    /* length of instruction array (b_instr) */
    int b_ialloc;
    /* pointer to an array of instructions, initially NULL */
    struct instr *b_instr;
    /* If b_next is non-NULL, it is a pointer to the next
       block reached by normal control flow. */
    struct basicblock_ *b_next;
    /* b_seen is used to perform a DFS of basicblocks. */
    unsigned b_seen : 1;
    /* b_return is true if a RETURN_VALUE opcode is inserted. */
    unsigned b_return : 1;
    /* depth of stack upon entry of block, computed by stackdepth() */
    int b_startdepth;
    /* instruction offset for block, computed by assemble_jump_offsets() */
    int b_offset;
} basicblock;

Et voici la définition le la structure instr :

struct instr {
    unsigned i_jabs : 1;
    unsigned i_jrel : 1;
    unsigned char i_opcode;
    int i_oparg;
    struct basicblock_ *i_target; /* target block (if jump instruction) */
    int i_lineno;
};

Nous pouvons voir que les blocs de base sont connectés non seulement par des instructions de saut mais aussi par les champs b_list et b_next. Le compilateur utilise b_list pour accéder à tous les blocs alloués, par exemple pour libérer la mémoire. b_next est le champs qui nous intéresse. Comme le dit le commentaire, il pointe vers le prochain bloc, atteint par le control flow, ce qui veut dire qu’il peut être utilisé pour assembler des blocs dans le bon ordre. Pour revenir une fois de plus à notre exemple, le bloc test pointe vers le bloc body, le bloc body pointe vers le bloc orelse et le bloc orelse pointe vers le bloc venant après l’instruction if. Des blocs de base pointant les uns vers les autres forment un graphique appelé Control Flow Graph (CFG).

frame blocks

Frame blocks are also useful when dealing with statements such as try-except-finally, but we will not dwell on this now. Let's instead have a look at the definition of the fblockinfo struct:

Il reste un dernier problème à résoudre : Comment savoir où sauter lors de la compilation d’instructions comme continue et break ? Le compilateur résout ce problème en introduisant un autre type de bloc appelé frame block. Il existe différents types de frame block. Par exemple, le frame block WHILE_LOOP pointe vers deux blocs de base : Le bloc body et le bloc qui suit l’instruction while. Ces blocs de base sont utilisés respectivement lors de la compilation des instructions continue et break. Dans la mesure où les frame blocks peuvent s’emboîter, le compilateur les tracks à l’aide de piles, une pile de frame block par code block. Les frame blocks sont également utiles pour les instructions try-except-finally, mais nous ne nous attarderons pas là-dessus maintenant. Jetons plutôt un coup d’œil à la définition de la structure fblockinfo :

enum fblocktype { WHILE_LOOP, FOR_LOOP, EXCEPT, FINALLY_TRY, FINALLY_END,
                  WITH, ASYNC_WITH, HANDLER_CLEANUP, POP_VALUE };

struct fblockinfo {
    enum fblocktype fb_type;
    basicblock *fb_block;
    /* (optional) type-specific exit or cleanup block */
    basicblock *fb_exit;
    /* (optional) additional information required for unwinding */
    void *fb_datum;
};

Nous avons identifié trois problèmes importants et nous avons vu comment le compilateur les résout. Assemblons maintenant tout ça pour voir comment le compilateur fonctionne du début à la fin.

compiler units, compiler and assembler

Comme nous l’avons vu, le compilateur effectue deux étapes supplémentaires après avoir créé une table de symboles, pour convertir l’AST en code object :

1. Il crée le CFG de blocs de base.
2. Il assemble le CFG en un code object.

Ce processus en deux étapes est exécuté pour chaque code block présent dans le programme. Pour un module donné, le compilateur commence par construire son CFG et fini par l’assemblage du CFG en code object. Entre les deux, il parcourt l’AST en appelant récursivement les fonctions compiler_visit_* et compiler_*, où * désigne ce qui est visité ou compilé. Par exemple, compiler_visit_stmt délègue la compilation d’une instruction donnée à la fonction compiler_* appropriée, et la fonction compiler_if sait comment compiler le nœud AST If. Si un nœud ajoute de nouveaux blocs de base, le compilateur les créés. Si un nœud commence un code block, le compilateur crée une nouvelle unité de compilation et y entre. Une unité de compilation est une structure de données qui capture l’état de compilation du code block. Il agit comme le prototype mutable d’un code object et pointe vers un nouveau CFG. Le compilateur assemble ce CFG lorsqu’il quitte un nœud qui a commencé le code block courant. Le code object assemblé est stocké dans l’unité de compilation parent. Comme toujours, je vous encourage à regarder la définition de la structure :

struct compiler_unit {
    PySTEntryObject *u_ste;

    PyObject *u_name;
    PyObject *u_qualname;  /* dot-separated qualified name (lazy) */
    int u_scope_type;

    /* The following fields are dicts that map objects to
       the index of them in co_XXX.      The index is used as
       the argument for opcodes that refer to those collections.
    */
    PyObject *u_consts;    /* all constants */
    PyObject *u_names;     /* all names */
    PyObject *u_varnames;  /* local variables */
    PyObject *u_cellvars;  /* cell variables */
    PyObject *u_freevars;  /* free variables */

    PyObject *u_private;        /* for private name mangling */

    Py_ssize_t u_argcount;        /* number of arguments for block */
    Py_ssize_t u_posonlyargcount;        /* number of positional only arguments for block */
    Py_ssize_t u_kwonlyargcount; /* number of keyword only arguments for block */
    /* Pointer to the most recently allocated block.  By following b_list
       members, you can reach all early allocated blocks. */
    basicblock *u_blocks;
    basicblock *u_curblock; /* pointer to current block */

    int u_nfblocks;
    struct fblockinfo u_fblock[CO_MAXBLOCKS];

    int u_firstlineno; /* the first lineno of the block */
    int u_lineno;          /* the lineno for the current stmt */
    int u_col_offset;      /* the offset of the current stmt */
};

Une autre structure de données cruciale pour la compilation est la structure du compilateur. Elle représente l’état global de la compilation. Voici sa définition :

struct compiler {
    PyObject *c_filename;
    struct symtable *c_st;
    PyFutureFeatures *c_future; /* pointer to module's __future__ */
    PyCompilerFlags *c_flags;

    int c_optimize;              /* optimization level */
    int c_interactive;           /* true if in interactive mode */
    int c_nestlevel;
    int c_do_not_emit_bytecode;  /* The compiler won't emit any bytecode
                                    if this value is different from zero.
                                    This can be used to temporarily visit
                                    nodes without emitting bytecode to
                                    check only errors. */

    PyObject *c_const_cache;     /* Python dict holding all constants,
                                    including names tuple */
    struct compiler_unit *u; /* compiler state for current block */
    PyObject *c_stack;           /* Python list holding compiler_unit ptrs */
    PyArena *c_arena;            /* pointer to memory allocation arena */
};

Et le commentaire avant la définition, qui explique à quoi servent les deux champs les plus importants :

Le pointeur u pointe sur l’unités de compilation courante, tandis que les unités des blocs englobants sont stockées dans c_stack. u et c_stacksont gérés parcompiler_enter_scope()et `compiler_exit_scope().

To assemble basic blocks into a code object, the compiler first has to fix the jump instructions by replacing pointers with positions in bytecode. On the one side, it's an easy task, since the sizes of all basic blocks are known. On the other side, the size of a basic block can change when we fix a jump. The current solution is to keep fixing jumps in a loop while the sizes change. Here's an honest comment from the source code on this solution:

Pour assembler les blocs de bases en code object, le compilateur doit d’abord corriger les instructions de saut en remplaçant les pointeurs par des positions dans le bytecode. D’un côté, c’est une tâche facile, puisque les tailles de tous les blocs de base sont connues. D’un autre côté, la taille d’un bloc de base peut changer lorsque nous corrigeons un saut. La solution actuelle est de continuer à fixer les sauts en boucle pendant que les tailles changent. Voici un commentaire honnête du code source sur cette solution :

C’est un hock épouvantable qui peut affecter les performances, mais d’un côté, il devrait fonctionner jusqu’à ce que nous trouvions une meilleure solution.

Le reste est simple. Le compilateur effectue une itération sur les blocs de base et émet les instructions. La progression est conservée dans la structure assembler :

struct assembler {
    PyObject *a_bytecode;  /* string containing bytecode */
    int a_offset;              /* offset into bytecode */
    int a_nblocks;             /* number of reachable blocks */
    basicblock **a_postorder; /* list of blocks in dfs postorder */
    PyObject *a_lnotab;    /* string containing lnotab */
    int a_lnotab_off;      /* offset into lnotab */
    int a_lineno;              /* last lineno of emitted instruction */
    int a_lineno_off;      /* bytecode offset of last lineno */
};

À ce stade, l’unité de compilation en court ainsi que l’assembleur contiennent toutes les données nécessaires à la création d’un code object. Félicitation ! On l’a fait ! Enfin, presque.

Le peephole optimizer

La dernière étape de la création du code object est l’optimisation du bytecode. C’est le travail du peephole optimizer. Voici le genre d’optimisation qu’il effectue :

• Les déclarations comme if True: ... et while True: ... génère une séquence d’instructions LOAD_CONST trueconst et POP_JUMP_IF_FALSE. Le peephole optimizer élimine de tels instructions.
• Les déclarations comme a, = b, génère un bytecode construisant un tuple qu’il unpack ensuite. Le peephole optimizer le remplace par une simple assignation.
• Le peephole optimizer supprime les instructions inatteignable après RETURN.

En fait, le peephole optimizer supprime les instructions redondantes, diminuant la taille finale du bytecode. Une fois que le bytecode est optimisé, le compilateur créé le code object et la VM est prête à l’exécuter.

Résumé

Cet article était long, résumer ce que nous avons appris est probablement une bonne idée. L’architecture du compilateur CPython suit une conception traditionnelle. Ses deux parties principales sont l’interface et le backend. L’interface est également appelée parser. Son travail est de convertir un code source en AST. Le parser obtient des tokens par le tokenizer, qui est responsable de la production d’un flux d’unités de langage depuis le texte. Historiquement, le parser se composait de plusieurs étapes, dont la génération d’un arbre d’analyse et sa conversion en AST. Dans CPython 3.9, le nouveau parser a été introduit. Il est basé sur une parsing expression grammar (PEG) et génère un AST directement. Le backend, paradoxalement appelé le « compilateur », prend un AST et produit un code object. Il le fait en construisant d’abord une table de symboles, puis en créant une autre représentation intermédiaire d’un programme appelé Control Flow Graph. Ce CFG est assemblé en une unique séquence d’instructions, qui est ensuite optimisée par le peephole optimizer. Enfin, le code object est créé.

À ce stade, nous avons suffisamment de connaissances pour nous familiariser avec le code source de CPython et comprendre certaines des choses qu’il fait. Et c’est ce que nous allons voir la prochaine fois.

Le troisième chapitre est disponible.

Dernière mise à jour : jeu. 17 décembre 2020