Élément techniques phases compilation

Bonsoir,

Après avoir refais un tour d’horizon des différentes phases de compilation, j’ai (encore, et toujours) de nouvelles questions. La première concerne l'analyse syntaxique. Celle-ci unifie les tokens vraisemblablement à la grammaire établie. Pour les affectations de variables, en partant des tokens suivants:

[Ident('a'), Equal, Number(2)]

On obtient ça:

Affectation('a', 2)

Jusque-là, c’est simple. Cependant, transformer une condition if de la même façon que pour l’affectation ci-dessus est un mystère pour moi. Hypothèse 1, il faudrait créer un objet If (tout comme Affectation) qui contiendrait, sous forme d’objet, le code contenue dans la condition. Ça me parait déraisonable, mais je préférai quand même exposer cette hypothèse. Hypothèse 2, If serait un bloc tel que Equal qui serait suivit des objets formants le code de la condition en question, auquel cas, je me demande de quelle façon on sait quand le code de la condition s’arrête (j’en profite pour mentionner le repository de mon futur langage qui contient pour l’instant un aperçue de ce à quoi il ressemblera. En l’occurrence, mon langage, Higgs, sera un dialecte de Lisp. Par la même occasion, en vous basant sur les exemples de code de mon repo, pouvez-vous me dire comment je devine quand le code d’une condition se termine?).

Cordialement.

Je n’y croyais pas du tout, mais en effet c’est en fait tout à fait plausible. Cependant, j’ai un trouble quant au "pourquoi des objet". En effet, vous aviez dis que l’on se servait des objets comme catégorie au contenue du code (Equal, LParen, Addition, etc). Or, ça voudrait dire que pour pour chaque objet, par exemple Addition, vous créez une classe avec éventuellement des méthodes ? Et comment ce fait-il que le nombre d’argument vous leur passez soit sans limite ? En général, lorsque on défini une classe, on défini de façon concise ses arguments.

Cordialement.

Je ne comprends pas tellement tes interrogations : dans mon code Addition est juste un nom, derrière c’est du détail d’implémentation. Que ça soit un type particulier ou une fonction qui renverrait un objet Operator ça n’y change rien en pratique. Donc non il n’y a pas besoin de méthodes particulières.

Sinon dans mes exemples le nombre d’argument est toujours fixé. Mais ça n’a rien d’insurmontable de gérer un nombre variable d’arguments, faut juste voir à quel problème ça répond.
Ici les structures de données doivent être plutôt bien définies et donc tu sais combien d’arguments sont nécessaires pour chaque (ça n’a pas de sens de faire une soustraction d’un seul élément ou de trois).

Bonjour,

A aucun moment il n’y a besoin de structures avec un nombre variables d’arguments.

A partir de ce résonnement, dans mon esprit ça se présente comme ça: Je pars du code Lisp suivant:

(if (> 2 1)
    (str 2 'higher than' 1)
    (let a 1))

En le lexant, j’obtiens:

[LParen(), If(), LParen(), Larger(), Number(2), Number(1), RParen(), LParen, Macro('str'), Number(2), String('higher than'), Number(1), RParen, LParen, Let(), Ident('a'), Number(1), RParen(), RParen()]

Ici, il y quelque chose sur quoi je butte. Vous, vous appelez ça des objets, moi, je ne suis pas d’accord, et je ne sais pas ce que c’est donc. Par exemple, ici, le terminal If est noté sans arguments alors que à la phase de parsing, lorsque on le rempliera de la condition et du bloc à exécuter, elle ne sera pas vide, ça voudrait dire que le nombre d’argument est variant, ce qui cohèrent pas avec ce que tu as dis.

Au parsing, on aurait quelque chose comme ça (les espaces sont là uniquement pour une meilleure lisibilité):

[ If( [ IsHigher(2, 1) ], [ ToString(2, 'higher than', 1), Let('a', 1) ] ) ]

Pour obtenir, cela, donc, d’après tes dires, sous forme d’algorithme ça aurait ressemblé à ça:

Si '(' et 'If()' et '(' ou '' uniquement si ça a la forme dune égalité ou comparaison et '[condition]' alors ajoute le token suivant:
   ...

C’est là que je me rend compte que je ne comprend pas comment parser. Je sais simplement que c’est la phase qui va regrouper les tokens provenant du Lexer en cherchant des motifs correspondant à un addition, par exemple. Pouvez vous m’éclairer ?

Cordialement.

Salut,

Tu fais une confusion entre deux choses. Le "if" issue du lexeur, n’est pas le même "if" que celui après le parsing.

Dans le premier cas, il s’agit d’un token, une entité qui fait sens pour le lexer, il n’y a pas de structure programmatique à ce stade. Dans ton cas, ça serait probablement juste un "identifiant" ou quelque chose du genre, parce que dans un Lisp, c’est pas très important de spécifier son rôle à ce stade. Pas besoin de savoir spécifiquement que c’est un "if". Le lexeur traite les plus petites entités qui ont un sens pour le langage sans forcément s’intéresser à ce que ça ait du sens logiquement (donc on a va trouver des identifiant, des marqueurs de blocs, etc).

Dans le second cas, c’est structuré. C’est un noeud de l’AST d’un certain type avec toutes ses spécificités. Si on voit que c’est un if, on devra lui trouver ses arguments dans le flux de tokens, on attend un certain nombre d’arguments, etc. On peut aussi gérer des erreurs.

En Python, les identifiant ça n’existe pas, c’est peut être pour ça que je ne comprend pas la notion d’identifiant.

Bonjour,

Lorsque on passe le code au compilateur, s’agit-il du fichier ou d’une chaîne de caractère contenant le code ? Car, dans le second cas, c’est plus aisé car on peut procéder avec des index, tandis qu’avec le fichier c’est pas le cas.

Et également, je vois assez souvent des "\n" comme motif à rechercher lors du lexing et je me demandai pourquoi ils sont accessible lors du traitement du code mais ne sont pas visible lorsque on l’écrit (le code).

Cordialement.

Si, un nom de variable ou de fonction est ce qu’on appelle un identifiant en Python. Je pense que ce que veux dire @Aabu est qu’en Lisp il n’y a pas de réelle différence entre un if et un identifiant quelconque, ça a la même structure (une paire de parenthèses qui contient un mot et ses arguments) donc ça se tokenise de la même manière.

C’est toi qui choisit cela. Généralement les compilateurs attendent des chemins de fichiers en arguments, mais je ne vois pas quelle différence ça fait (dans tous les cas le fichier est lu pour en extraire le code).

Comment ça accessibles ? Ils servent de marqueurs et peuvent être utiles dans certains langages (en Python c’est ce qui marque la fin d’une instruction).

Comment ça accessibles ?

Dans le code que j’observe, le développeur semble chercher \n, or, il me semble que c’est le caractère correspondant au retour à la ligne. Et ce caractère de retour à la ligne, celui là: " ", on ne le voit pas sous forme de \n.

La séquence spéciale \n est simplement interprétée par le langage en question comme le caractère de retour à la ligne.

Bonjour,

En phase de réflexion pour mon langage de programmation, je me questionne sur le principe du "retournage". Ce que j’entends par ce terme c’est ce que retourne une fonction ou encore une variable. Je me suis aperçue que c’était un principe présent à peu près partout: je suppose par exemple que pour déterminer si quelque chose est affichable dans une instruction print, le compilateur se sert de ce que retourne la variable pour vérifier qu’il ne s’agit pas d’une liste ou d’un dictionnaire, ou basiquement, de tout autre chose qui ne soit pas affichable simplement.

Pouvez vous m’expliquer comment on intègre le principe de "retournement" dans un langage de programmation ?

Cordialement.

Salut,

Ça dépend un peu des langages. Quoi qu’il en soit, c’est une histoire de typage, au sens large.

Dans un langage compilé fortement typé, c’est vérifié par le système de types à la compilation. Par exemple, dans le cas d’un print, si ce n’est pas une string ou un type convertible en string (selon certaines règles prédéterminées), alors les types sont incompatibles et la compilation échoue. On aura des messages du style « Type error: object 'trucmuche' is type blabla but should be type string » ou « Type error: type blabla cannot be converted to string ». Évidemment, on peut imaginer des variantes de ça.

Dans des langages interprétés et plus dynamiques comme Python, ça n’est pas vérifié à la compilation, mais à l’exécution. Les objets affichables vont avoir en Python une méthode __str__ et les méthodes comme print vont prendre en argument n’importe quel objet, tenté d’appeler leur méthode __str__ et on se prendra une erreur comme quoi l’appel à échouer si la méthode n’existe pas sur l’objet en question.

Il y a d’autres solutions possibles en fonction des langages, je présente là juste deux stratégies parmi tout un éventail.

Le choix exact est vraiment au choix du concepteur et selon la philosophie du langage.

Bonjour Aabu,

Dans ta réponse tu réponds à un exemple que j’avais fais dans mon précédent message et par conséquent tu as oublié l’essentiel à savoir le principe de "retournement". Est-ce que tu es en mesure d’y répondre, à celle-ci ?

C’est la même chose, ou alors je n’ai pas compris ce dont tu parles

Ma question est: comment faire pour créer le principe de retournement dans un langage de programmation. Par exemple, quand tu fais en Rust

let a = 2;

let b = match b {
     0 => "0",
     1 => "Dragon",
     _ => "MHH"
};

, le match retourne une valeur que let s’associera.

Dans un langage compilé fortement typé, c’est vérifié par le système de types à la compilation.

Dans des langages interprétés et plus dynamiques comme Python, ça n’est pas vérifié à la compilation, mais à l’exécution.

Beaucoup de confusions assez fondamentales là-dedans. Lorsque la vérification est faite à la compilation (ou avant l’exécution), on parle de typage statique. Lorsque la vérification est faite au runtime, on parle de typage dynamique. La notion de typage statique vs dynamique est orthogonale à la notion de langage compilé vs interprété (Python est d’ailleurs compilé en bytecode plutôt qu’interprété), et de typage fort vs faible (cette dernière n’ayant pas trop de sens de toute façon, c’est une notion relative mal définie). Il se trouve qu’en général, les langages compilés sont typés statiquement, et il se trouve aussi qu’en général les systèmes de types considérés forts sont statiques (mais pas réciproquement, voir C, C++, ou même Fortran qui sont typés statiquement mais pas typesafe pour deux sous).

@b4b4 : ta question est un peu double. Tu as deux composantes à cela dans un langage comme Rust :

• attribuer les types "évidents" aux diverses expressions, par exemple chaque branche du match dans ton exemple sont des &'static str et le 2 est un Integer (pas encore complètement résolu, on sait juste que c’est un entier pour l’instant) ;
• une phase d’inférence où l’on vérifie que les types sont cohérents entre eux et sont propagés le plus loin possible (ici le type de 2 et donc a et des patterns du match prennent le type i32, et b prend le type &'static str parce que toutes les branches du match sont cohérentes et de ce type) ;
• on accepte le programme seulement si tous les types sont maintenant connus et sont cohérents.

Sur un langage jouet, tu peux avoir intérêt à demander à l’utilisateur de spécifier tous les types de partout dans un premier temps, comme ça t’as pas besoin de coder la phase d’inférence et t’as juste besoin de vérifier que tout est typé et que les types sont cohérents.

Alors,

Maintenant je sais comment on détermine les type d’expression comme match ou print. Mais, je ne sais toujours pas comment implémenter le fait de retourner.. Peut être ne suis-je pas clair ?

Pas vraiment non. « retourner » ça fait habituellement partie du jargon des fonctions (comment renvoyer une valeur de l’intérieur vers l’extérieur).
Là tu sembles parler d’autre chose et je ne vois pas trop de quoi.

Ta question n’est effectivement pas claire du tout… L’analyse du typage est purement statique, il n’y a aucune notion de "retourner" ou renvoyer qui intervient.

Reprenons ton exemple, légèrement modifié pour donner un type concret à a immédiatement :

let a = 0u8;
let b = match a {
    0 => "null",
    _ => "nonzero",
};

Le système de type va attribuer des types à chaque expression dans sa représentation interne, ressemblant par exemple à ça dans un premier temps :

Assign(
    lhs = Ident("a", T_a),
    rhs = Literal(0, u8));
Assign(
    lhs = Ident("b", T_b),
    rhs = MatchStatement(
        expr = Expr(Ident("a", T_a), T_e),
        branches = [
            Branch(
                pat = Pattern(Literal(0, T_i), T_p1),
                val = Expr(Literal("null", &'static str), T_b1)
            ),
            Branch(
                pat = BlankPattern,
                val = Expr(Literal("nonzero", &'static str), T_b2)
            ),
        ],
        T_m,
    );

Les trucs en T_* sont les types pas encore connus à ce stade (i.e. qui n’étaient pas explicites). Puis le moteur d’inférence de types (ça peut paraître simple, mais en fait c’est un gros morceau !) construit un ensemble de contraintes que le code nous donne :

T_a < u8;
T_b < T_m;
T_e < T_a;
T_p1 < T_e;
T_e < T_i;
T_m < (T_b1, T_b2);
T_b1 < &'static str;
T_b2 < &'static str;

Où T_1 < T_2 veut dire que T_2 doit être cohérent avec T_1, autrement dit T_1 == T_2, ou bien T_2 est un sous-type de T_1 (en Rust, le seul cas de sous-typage est via les lifetimes) ou bien T_2 peut être coercé en T_1 implicitement (e.g. &mut T peut être coercé en &T).

Comme tu vois, tout ceci fonctionne purement par un set de contraintes que le code nous donne, la partie difficile étant d’écrire le solveur de contraintes correctement.