Nous écrivons notre langage de programmation, partie 3: Architecture du traducteur. Analyse des structures du langage et des expressions mathématiques

Présentation

Je vous souhaite la bienvenue, développeurs de lecture intéressés dans toutes les langues dans lesquelles j'oriente ces articles et dont j'apprécie le soutien et les opinions.

Pour commencer, selon les traditions établies, je fournirai des liens vers les articles précédents:

Partie 1: écrire une machine virtuelle de langue
Partie 2: présentation intermédiaire des programmes

Pour former dans votre tête une compréhension complète de ce que nous écrivons dans ces articles, vous devez vous familiariser avec les parties précédentes à l'avance.

De plus, je devrais immédiatement publier un lien vers un article sur un projet que j'ai écrit plus tôt et sur la base duquel se déroule tout ce débriefing: Clack syudy . Peut-être vaut-il la peine de le connaître en premier lieu.

Et un peu sur le projet:

→ Petit site de projet
→ Dépôt GitHub

Eh bien, je dirai aussi tout de suite que tout est écrit en Object Pascal, à savoir en FPC.

Commençons donc.

Le principe de fonctionnement de la plupart des traducteurs

Tout d’abord, il vaut la peine de comprendre que je ne pourrais rien écrire de valable sans me familiariser avec un tas de matériel théorique et un certain nombre de statues. Je vais décrire l'essentiel en quelques mots.

La tâche du traducteur est tout d'abord de préparer le code pour l'analyse (par exemple, d'en supprimer les commentaires) et de décomposer le code en jetons (un jeton est le jeu de caractères minimum significatif pour la langue).

Ensuite, en analysant et en transformant, vous devez analyser le code en une certaine représentation intermédiaire, puis assembler l'application prête à être exécutée ou ... Que faut-il collecter en général.

Oui, je n'ai pas vraiment dit quoi que ce soit avec ce tas de texte, cependant - maintenant la tâche est divisée en plusieurs sous-tâches.

Ignorons comment le code est préparé pour l'exécution, car c'est trop ennuyeux pour décrire un processus. Supposons que nous ayons un ensemble de jetons prêts pour l'analyse.

Analyse de code

Vous avez peut-être entendu parler de la construction d'un arbre de code et de son analyse, ou encore de choses plus abstruses. Comme toujours - ce n'est rien de plus que d'encombrer les termes terribles simples. Par analyse de code, je veux dire un ensemble d'actions beaucoup plus simple. La tâche consiste à parcourir la liste des jetons et à analyser le code, chacune de sa construction.

En règle générale, dans les langages impératifs, le code est déjà présenté sous la forme d'une sorte d'arbre à partir de structures.

Vous devez admettre qu'il n'est pas acceptable de commencer le cycle "A" dans le corps du cycle "B" et de le terminer en dehors du corps du cycle "B". Un code est une structure composée d'un ensemble de constructions.
Et qu'est-ce que chaque design a? C'est vrai - le début et la fin (et peut-être quelque chose d'autre au milieu, mais pas le point).

En conséquence, l'analyse de code peut être effectuée en un seul passage, vraiment sans construire d'arbre.
Pour ce faire, vous avez besoin d'une boucle qui parcourra le code et d'un énorme boîtier de commutation qui effectuera l'analyse et l'analyse du code principal.

C'est-à-dire nous parcourons les jetons, nous avons un jeton (par exemple, que ce soit ...) "si" - je doute vraiment qu'un tel jeton puisse être dans le code comme ça -> c'est le début de la construction si..alors [.. sinon] .. fin!

Nous analysons tous les jetons suivants, respectivement, pour la construction de conditions dans notre langue.

Un peu sur les erreurs de code

Au stade de l'analyse des structures et le long du code, il vaut mieux ne pas marquer les erreurs de traitement. Il s'agit d'une fonctionnalité de traduction utile. Si une erreur se produit lors de l'analyse de la structure, alors c'est logique - la structure n'est pas construite correctement et vous devez en informer le développeur.

Maintenant à propos de Mash. Comment la langue est-elle analysée?

Ci-dessus, j'ai décrit un concept généralisé de dispositif de traduction. Il est maintenant temps de parler de mon travail.

En fait, le traducteur s'est avéré très similaire à celui décrit ci-dessus. Mais pour moi, cela ne casse pas le code en un tas de jetons pour une analyse plus approfondie.

Avant de commencer l'analyse, le code est présenté sous une forme plus belle. Les commentaires sont supprimés et toutes les constructions sont combinées en longues lignes si elles sont décrites en plusieurs lignes.

Ainsi, dans chaque ligne prise séparément, il y a une construction de langage ou sa partie. C'est cool, maintenant nous pouvons analyser chaque ligne dans notre grand boîtier de commutateur, au lieu de chercher ces constructions dans l'ensemble de jetons. De plus, l'avantage ici est que la ligne a une fin et il est plus facile de déterminer les erreurs de construction avec cette approche.

En conséquence, l'analyse des structures individuelles se fait par des méthodes distinctes, qui renvoient une représentation intermédiaire du code des structures ou de ses parties.

P.S. Dans un article précédent, j'ai décrit la construction d'un traducteur d'un langage intermédiaire en bytecode pour une VM. En fait - ce langage intermédiaire est une représentation intermédiaire.

Il faut comprendre que les structures peuvent être constituées de plusieurs structures plus simples. Parce que Puisque nous analysons chaque structure par des méthodes distinctes, nous pouvons facilement les appeler les unes des autres lors de l'analyse de chaque structure.

Échauffement sur le code

Pour commencer, le traducteur doit rapidement se familiariser avec le code, le parcourir et faire attention à certains modèles.

À ce stade, vous pouvez gérer des variables globales, utiliser des constructions, ainsi que des importations, des procédures et des fonctions et des constructions OOP.

Il est préférable de générer une vue intermédiaire en plusieurs objets pour le stockage, afin que
collez le code des variables globales après l'initialisation, mais avant le début de main ().

Le code pour les constructions OOP peut être inséré à la fin.

Designs sophistiqués

Ok, nous avons compris les conceptions simples. Il est maintenant temps pour le délicat. Je ne pense pas que vous ayez réussi à oublier l'exemple avec deux cycles. Comme nous le savons, les structures se présentent généralement sous la forme d'une sorte d'arbre. Cela signifie que nous pouvons analyser des structures complexes en utilisant la pile.

Qu'est-ce que la pile a à voir avec ça? De plus.

Tout d'abord, nous décrivons la classe que nous allons pousser sur la pile. Lors de l'analyse syntaxique de constructions complexes, nous pouvons générer une représentation intermédiaire pour le début et la fin de ce bloc, par exemple, nous analysons la boucle for, while, until, si les constructions, les méthodes et, en fait, tout dans le langage Mash.

Cette classe a besoin de champs pour stocker des représentations intermédiaires, des méta-informations (pour certaines constructions variables) et, bien sûr, pour stocker un type de bloc.

Je vais juste donner tout le code, car il n'y a pas grand-chose ici:

unit u_prep_codeblock; {$mode objfpc}{$H+} interface uses Classes, SysUtils; type TBlockEntryType = (btProc, btFunc, btIf, btFor, btWhile, btUntil, btTry, btClass, btSwitch, btCase); TCodeBlock = class(TObject) public bType: TBlockEntryType; mName, bMeta, bMCode, bEndCode: string; constructor Create(bt: TBlockEntryType; MT, MC, EC: string); end; implementation constructor TCodeBlock.Create(bt: TBlockEntryType; MT, MC, EC: string); begin inherited Create; bType := bt; bMeta := MT; bMCode := MC; bEndCode := EC; end; end. 

Eh bien, la pile est une simple TList, réinventer la roue ici est tout simplement stupide.

Ainsi, en analysant la construction, disons la même chose tandis que la boucle ressemble à ceci:

 function ParseWhile(s: string; varmgr: TVarManager): string; var WhileNum, ExprCode: string; begin Delete(s, 1, 5); //"while" Delete(s, Length(s), 1); //":" s := Trim(s); //   ,       ... //        :) WhileNum := '__gen_while_' + IntToStr(WhileBlCounter); Inc(WhileBlCounter); //   while   // ,        if IsExpr(s) then ExprCode := PreprocessExpression(s, varmgr) else ExprCode := PushIt(s, varmgr); //  ExprCode     //        //    //(      ) Result := WhileNum + ':' + sLineBreak + 'pushcp ' + WhileNum + '_end' + sLineBreak + ExprCode + sLineBreak + 'jz' + sLineBreak + 'pop'; //        //  -        //   break BlockStack.Add(TCodeBlock.Create(btWhile, '', 'pushcp ' + WhileNum + sLineBreak + 'jp' + sLineBreak + WhileNum + '_end:', WhileNum + '_end')); end; 

À propos des expressions mathématiques

Vous ne l'avez peut-être pas remarqué, mais les expressions mathématiques / logiques sont également du code structuré.

J'ai implémenté leur analyse de manière empilée. Tout d'abord, tous les éléments individuels de l'expression sont poussés sur la pile, puis en plusieurs passes, le code de la représentation intermédiaire est généré.

Plusieurs fois - parce que il y a des opérations mathématiques prioritaires, comme la multiplication.
Je ne vois pas le point ici, car c'est beaucoup et c'est ennuyeux.

P.S. /lang/u_prep_expressions.pas - ici, il est complètement et entièrement exposé pour votre examen.

Résumé

Nous avons donc implémenté un traducteur capable de convertir ... Par exemple, voici le code:

 proc PrintArr(arr): for(i ?= 0; i < len(arr); i++): PrintLn("arr[", i, "] = ", arr[i]) end end proc main(): var arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] PrintArr(arr) InputLn() end 

Qu'est-ce qui manque dans notre langue? À droite, soutenez OOP. Nous en parlerons dans mon prochain article.

Merci d'avoir lu jusqu'à la fin si vous l'avez fait.

Si quelque chose ne vous est pas clair, j'attends vos commentaires. Ou des questions sur le forum , oui ... Oui, je le vérifie parfois.

Et maintenant un petit sondage (pour que je le regarde et apprécie la signification de mes articles):