Bonjour à tous! En tant que programmeur, je cherche toujours des moyens d'améliorer mes compétences. Un vendredi soir, la pensée m'est venue à l'esprit: «N'écrirais-je pas un compilateur?»
Qui se soucie de savoir ce qui en est arrivé, bienvenue au chat.
Sur la base de la "Théorie classique du compilateur" V. E. Karpov, on peut distinguer 5 étapes principales de compilation:
- Analyse lexicale
- Analyse
- Génération de code intermédiaire
- Optimisation
- Génération du code final, objet,
À propos de tout, cinq parties, vous pouvez écrire beaucoup de phrases et d'articles. Mais, aujourd'hui, nous allons parler des deux premiers et comment j'ai sélectionné leur structure dans une bibliothèque séparée.
Quand j'ai décidé d'écrire, même une petite partie, du compilateur, je ne pensais pas à la langue pour laquelle j'écrivais, pour cette raison, le résultat était une bibliothèque pour l'analyse lexicale et syntaxique de n'importe quelle langue.
Tokenisation
Avant de construire une syntaxe et un arbre lexical, de générer le code résultant et de faire d'autres choses savoureuses, vous devez diviser le code source en lignes, caractères, nombres.
Où chaque élément aura un type défini avec précision. Les jetons de type non défini seront considérés comme des erreurs de syntaxe lors de l'analyse.
Dans le contexte de la compilation, le code source est considéré comme une carte source, il est recommandé de le stocker dans le processus de lexical et d'analyse des commentaires du programmeur et d'indiquer des erreurs de syntaxe dans le code source.
Vous pouvez diviser le code source en un tableau de jetons à l'aide d'une simple expression régulière:
/\S+/gm
Il peut changer en fonction de conditions d'analyse supplémentaires, telles que: analyse de saut de ligne, analyse de tabulation, analyse d'espace.
Le résultat de la séparation sera un tableau de mots du code source, et les mots sont analysés d'un espace à l'autre, c'est-à-dire cette conception:
let hello = 'world';
Il sera converti en l'ensemble de jetons suivant:
["let", "hello", "=", "'world';"]
Afin d'obtenir l'ensemble final de jetons, vous devez parcourir chacun d'eux avec une expression régulière supplémentaire:
/(\W)|(\w+)/gm
Le résultat sera l'ensemble de jetons dont nous avons besoin:
["let", "hello", "=", "'", "world", "'", ";"]
Tous les jetons que nous avons reçus, nous écrivons dans le tableau, avec leurs indices dans la carte source
Analyse lexicale
Maintenant que nous avons un tableau de jetons, nous devons déterminer leur type pour les passer à l'analyse.
L'algorithme qui définit les jetons et leurs types s'appelle - Lexer
Le jeton et son type, que Lexer définit, est appelé le jeton
Chaque jeton peut avoir un type défini de manière unique, par exemple:
['let', 'const', 'var']
J'ai cependant mis en place un schéma pour déterminer les types de jetons, en utilisant ce que l'on appelle Solver'ov.
Cela fonctionne comme suit:
1. Vous définissez des constantes pour les types de jetons:
const DefaultTokenTypes = { KEYWORD: "Keyword", IDENTIFIER: "Identifier", OPERATOR: "Operator", DELIMITER: "Delimiter", LINEBREAK: "Linebreak", STRING: "String", NUMERIC: "Numeric", UNKNOWN: 'Unknown' };
2. Ensuite, il est nécessaire de déterminer le soi-disant Solver'y:
const solvers = {}; solvers[MyTokenTypes.KEYWORD] = { include: [ 'const', 'let' ] }; solvers[MyTokenTypes.NUMERIC] = { regexp: /^[0-9.]*$/gm }; solvers[DefaultTokenTypes.STRING] = { type: StringSolver, delimiters: ['"', "'", '`'] }; solvers[MyTokenTypes.IDENTIFIER] = { regexp: /^[a-zA-Z_][a-zA-Z_0-9]*$/gm }; solvers[MyTokenTypes.DELIMITER] = { default: true };
Comme vous pouvez le voir, les jetons peuvent avoir différents paramètres:
include - Un tableau de mots, par coïncidence avec lequel, le type de jeton peut être déterminé.
regexp - Une expression régulière, par coïncidence avec laquelle, le type de jeton peut être déterminé.
default - Le type standard pour les jetons non définis.
Vous pouvez également remarquer le paramètre
type , qui indique que ce solveur doit être hérité de celui spécifié dans
typeDans ce cas, le solveur définit des chaînes qui sont incluses dans l'un des caractères spécifiés dans les
délimiteurs3. Nous utilisons des solveurs pour le tableau de jetons et obtenons un tableau de jetons typés. Pour un code source donné:
let a = 50;
Nous obtenons l'arbre suivant:
[ { "type": "Keyword", "value": "let", "range": [0, 3] }, { "type": "Identifier", "value": "a", "range": [4, 5] }, { "type": "Delimiter", "value": "=", "range": [6, 7] }, { "type": "Numeric", "value": "50", "range": [8, 10] }, { "type": "Delimiter", "value": ";", "range": [10, 11] } ]
Où
plage correspond au début et à la fin du fragment dans le code source.
Analyse
Après avoir reçu un tableau de jetons, vous devez les analyser et déterminer la structure syntaxique (arborescence) du code source.
Il existe différentes options pour l'analyse, mais j'ai choisi un algorithme direct descendant.
Les jetons sont analysés un par un à l'aide d'un tableau de modèles. Si le modèle correspond à la séquence actuelle de jetons - dans l'arbre de syntaxe, une nouvelle branche est créée.
Un exemple d'un modèle d'un tableau:
let declaration = new SequenceNode({ tokenType: MyTokenTypes.KEYWORD, type: MyNodeTypes.DECLARATION, sequence: [ {type: MyTokenTypes.KEYWORD}, {type: MyTokenTypes.IDENTIFIER}, {type: MyTokenTypes.DELIMITER}, {type: [MyTokenTypes.NUMERIC, MyTokenTypes.STRING]}, ';' ], onError: (e) => {
tokenType - Décrit le jeton à partir duquel commencer à rechercher une correspondance.
type - Décrit le type de nœud, tous les types doivent également être définis, comme les types de jetons.
séquence - Un tableau d'une séquence, il contient des types de jetons, des valeurs spécifiques ou d'autres nœuds de l'arbre de syntaxe.
onError - Callback, qui fonctionnera lorsqu'une erreur de syntaxe
se produit , lors de l'analyse de ce nœud, il renvoie le type d'erreur + sa place dans le code source.
Analysons la
séquence de ce nœud:
[ {type: MyTokenTypes.KEYWORD},
J'ai implémenté plusieurs variantes de nœuds, à des fins différentes: définir des séquences de jetons, définir un groupe d'éléments (Arguments, blocs). Cela permet d'analyser les fonctions fléchées sans aucun problème.
Vous pouvez lire toutes les variantes de solveurs et de nœuds que j'ai implémentées dans la documentation de cette bibliothèque.
Matériaux
→ Lien source:
Tyk→
Théorie classique du compilateur