Écrire un compilateur dans sa propre langue

Intuitivement, il semblerait qu'un compilateur de langage Foone puisse pas lui-même être écrit dans Foo. Plus précisément, le premier compilateur de langue Foone peut pas être écrit dans Foo, mais tout compilateur suivant pourrait être écrit pour Foo.

Mais est-ce vraiment vrai? J'ai un souvenir très vague de la lecture d'une langue dont le premier compilateur a été écrit en "lui-même". Est-ce possible, et si oui comment?

C'est ce qu'on appelle le "bootstrapping". Vous devez d'abord créer un compilateur (ou interprète) pour votre langue dans une autre langue (généralement Java ou C). Une fois cela fait, vous pouvez écrire une nouvelle version du compilateur en langage Foo. Vous utilisez le premier compilateur d'amorçage pour compiler le compilateur, puis utilisez ce compilateur compilé pour compiler tout le reste (y compris les futures versions de lui-même).

La plupart des langages sont en effet créés de cette manière, en partie parce que les concepteurs de langage aiment utiliser le langage qu'ils créent, et aussi parce qu'un compilateur non trivial sert souvent de référence utile pour savoir à quel point le langage peut être "complet".

Un exemple de ceci serait Scala. Son premier compilateur a été créé dans Pizza, un langage expérimental de Martin Odersky. Depuis la version 2.0, le compilateur a été complètement réécrit en Scala. À partir de ce moment, l'ancien compilateur Pizza pourrait être complètement éliminé, car le nouveau compilateur Scala pourrait être utilisé pour se compiler pour les futures itérations.

Je me souviens d'avoir écouté un podcast Radio Software Engineering dans lequel Dick Gabriel a parlé d'amorcer l'interpréteur LISP original en écrivant une version simple sur LISP sur papier et en l'assemblant à la main en code machine. À partir de ce moment, les autres fonctionnalités LISP ont été écrites et interprétées avec LISP.

Ajout d'une curiosité aux réponses précédentes.

Voici une citation du manuel Linux From Scratch , à l'étape où l'on commence à construire le compilateur GCC à partir de sa source. (Linux From Scratch est un moyen d'installer Linux qui est radicalement différent de l'installation d'une distribution, en ce sens que vous devez vraiment compiler chaque binaire du système cible.)

make bootstrap

La cible 'bootstrap' ne compile pas seulement GCC, mais la compile plusieurs fois. Il utilise les programmes compilés au premier tour pour se compiler une deuxième fois, puis à nouveau une troisième fois. Il compare ensuite ces deuxième et troisième compilations pour s'assurer qu'il peut se reproduire parfaitement. Cela implique également qu'il a été compilé correctement.

Cette utilisation de la cible «bootstrap» est motivée par le fait que le compilateur utilisé pour construire la chaîne d'outils du système cible peut ne pas avoir la même version du compilateur cible. En procédant de cette manière, on est sûr d'obtenir, dans le système cible, un compilateur qui peut se compiler lui-même.

Lorsque vous écrivez votre premier compilateur pour C, vous l'écrivez dans un autre langage. Maintenant, vous avez un compilateur pour C dans, disons, assembleur. Finalement, vous arriverez à l'endroit où vous devez analyser les chaînes, en particulier les séquences d'échappement. Vous écrirez du code à convertir \nen caractère avec le code décimal 10 (et \ren 13, etc.).

Une fois ce compilateur prêt, vous commencerez à le réimplémenter en C. Ce processus est appelé " bootstrapping ".

Le code d'analyse de chaîne deviendra:

...
if (c == 92) { // backslash
    c = getc();
    if (c == 110) { // n
        return 10;
    } else if (c == 92) { // another backslash
        return 92;
    } else {
        ...
    }
}
...

Lorsque cela se compile, vous avez un binaire qui comprend '\ n'. Cela signifie que vous pouvez modifier le code source:

...
if (c == '\\') {
    c = getc();
    if (c == 'n') {
        return '\n';
    } else if (c == '\\') {
        return '\\';
    } else {
        ...
    }
}
...

Alors, où est l'information que '\ n' est le code pour 13? C'est dans le binaire! C'est comme l'ADN: la compilation du code source C avec ce binaire héritera de ces informations. Si le compilateur se compile, il transmettra ces connaissances à sa progéniture. À partir de là, il n'y a aucun moyen de voir à partir de la source seule ce que fera le compilateur.

Si vous voulez cacher un virus dans la source d'un programme, vous pouvez le faire comme ceci: Obtenez la source d'un compilateur, trouvez la fonction qui compile les fonctions et remplacez-la par celle-ci:

void compileFunction(char * name, char * filename, char * code) {
    if (strcmp("compileFunction", name) == 0 && strcmp("compile.c", filename) == 0) {
        code = A;
    } else if (strcmp("xxx", name) == 0 && strcmp("yyy.c", filename) == 0) {
        code = B;
    }

    ... code to compile the function body from the string in "code" ...
}

Les parties intéressantes sont A et B. A est le code source pour compileFunctioninclure le virus, probablement crypté d'une certaine manière, il n'est donc pas évident de rechercher le binaire résultant. Cela garantit que la compilation avec le compilateur lui-même préservera le code d'injection de virus.

B est le même pour la fonction que nous voulons remplacer par notre virus. Par exemple, il pourrait s'agir de la fonction "login" dans le fichier source "login.c" qui provient probablement du noyau Linux. Nous pourrions le remplacer par une version qui acceptera le mot de passe "joshua" pour le compte root en plus du mot de passe normal.

Si vous compilez cela et le diffusez sous forme binaire, il n'y aura aucun moyen de trouver le virus en regardant la source.

La source originale de l'idée: https://web.archive.org/web/20070714062657/http://www.acm.org/classics/sep95/

Vous ne pouvez pas écrire un compilateur en soi car vous n'avez rien pour compiler votre code source de départ. Il existe deux approches pour résoudre ce problème.

Le moins favorisé est le suivant. Vous écrivez un compilateur minimal dans l'assembleur (beurk) pour un ensemble minimal du langage, puis utilisez ce compilateur pour implémenter des fonctionnalités supplémentaires du langage. Construisez votre chemin jusqu'à ce que vous ayez un compilateur avec toutes les fonctionnalités du langage pour lui-même. Un processus douloureux qui ne se fait généralement que lorsque vous n'avez pas d'autre choix.

L'approche préférée consiste à utiliser un compilateur croisé. Vous modifiez l'extrémité arrière d'un compilateur existant sur une autre machine pour créer une sortie qui s'exécute sur la machine cible. Ensuite, vous avez un bon compilateur complet et vous travaillez sur la machine cible. Le plus populaire pour cela est le langage C, car il existe de nombreux compilateurs existants qui ont des backends enfichables qui peuvent être échangés.

Un fait peu connu est que le compilateur GNU C ++ a une implémentation qui utilise uniquement le sous-ensemble C. La raison étant qu'il est généralement facile de trouver un compilateur C pour une nouvelle machine cible qui vous permet ensuite de construire le compilateur GNU C ++ complet à partir de celui-ci. Vous avez maintenant démarré vous-même pour avoir un compilateur C ++ sur la machine cible.

Généralement, vous devez avoir une coupe de travail (si primitive) du compilateur qui fonctionne d'abord - ensuite vous pouvez commencer à penser à le rendre auto-hébergé. Ceci est en fait considéré comme un jalon important dans certains langages.

D'après ce que je me souviens de "mono", il est probable qu'ils devront ajouter quelques éléments à la réflexion pour le faire fonctionner: l'équipe mono continue de souligner que certaines choses ne sont tout simplement pas possibles avec Reflection.Emit; bien sûr, l'équipe MS pourrait leur prouver le contraire.

Cela présente quelques avantages réels : c'est un assez bon test unitaire, pour commencer! Et vous n'avez qu'un seul langage à vous soucier (c'est-à-dire qu'il est possible qu'un expert C # ne connaisse pas beaucoup C ++; mais maintenant, vous pouvez réparer le compilateur C #). Mais je me demande s'il n'y a pas une grande fierté professionnelle au travail ici: ils veulent simplement qu'il soit auto-hébergé.

Pas tout à fait un compilateur, mais j'ai récemment travaillé sur un système qui s'auto-héberge; le générateur de code est utilisé pour générer le générateur de code ... donc si le schéma change je le lance simplement sur lui-même: nouvelle version. S'il y a un bug, je reviens simplement à une version antérieure et réessaye. Très pratique et très facile à entretenir.

Mise à jour 1

Je viens de regarder cette vidéo d'Anders sur PDC, et (environ une heure), il donne des raisons beaucoup plus valables - tout sur le compilateur en tant que service. Juste pour info.

Voici un vidage (sujet difficile à rechercher, en fait):

• Smalltalk

• C

C'est aussi l'idée de PyPy et Rubinius :

(Je pense que cela pourrait également s'appliquer à Forth , mais je ne sais rien de Forth.)

GNAT, le compilateur GNU Ada, nécessite un compilateur Ada pour être entièrement construit. Cela peut être pénible lors du portage sur une plateforme où aucun binaire GNAT n'est disponible.

En fait, la plupart des compilateurs sont écrits dans la langue qu'ils compilent, pour les raisons indiquées ci-dessus.

Le premier compilateur d'amorçage est généralement écrit en C, C ++ ou Assembly.

Le compilateur C # du projet Mono est "auto-hébergé" depuis longtemps, ce qui signifie qu'il a été écrit en C # lui-même.

Ce que je sais, c'est que le compilateur a été démarré en tant que code C pur, mais une fois que les fonctionnalités "de base" d'ECMA ont été implémentées, ils ont commencé à réécrire le compilateur en C #.

Je ne connais pas les avantages d'écrire le compilateur dans le même langage, mais je suis sûr que cela a à voir avec les fonctionnalités que le langage lui-même peut offrir (C, par exemple, ne prend pas en charge la programmation orientée objet) .

Vous pouvez trouver plus d'informations ici .

J'ai écrit SLIC (Système de Langages pour Implémenter des Compilateurs) en lui-même. Puis compilé à la main en assemblage. SLIC a beaucoup à offrir car il s'agissait d'un seul compilateur de cinq sous-langues:

• SYNTAX Parser Programming Language PPL
• GENERATOR LISP 2 langage de génération de code PSEUDO basé sur l'exploration d'arbres
• ISO en séquence, code PSEUDO, langage d'optimisation
• PSEUDO Macro comme langage de production de code d'assemblage.
• MACHOP Instruction d'assemblage-machine définissant le langage.

SLIC a été inspiré par CWIC (Compilateur pour l'écriture et l'implémentation de compilateurs). Contrairement à la plupart des packages de développement de compilateurs, SLIC et CWIC ont traité la génération de code avec des langages spécialisés, spécifiques au domaine. SLIC étend la génération de code CWIC en ajoutant les sous-langages ISO, PSEUDO et MACHOP séparant les spécificités de la machine cible du langage générateur d'arborescence.

LISP 2 arbres et listes

Le système de gestion de mémoire dynamique du langage générateur basé sur LISP 2 est un composant clé. Les listes sont exprimées dans le langage entre crochets, ses composants séparés par des virgules, c'est-à-dire une liste à trois éléments [a, b, c].

Des arbres:

     ADD
    /   \
  MPY     3
 /   \
5     x

sont représentés par des listes dont la première entrée est un objet nœud:

[ADD,[MPY,5,x],3]

Les arbres sont généralement affichés avec le nœud séparé précédant les branches:

ADD[MPY[5,x],3]

Annulation de l'analyse avec les fonctions de générateur basées sur LISP 2

Une fonction de générateur est un ensemble nommé de (non analysé) => action> paires ...

<NAME>(<unparse>)=><action>;
      (<unparse>)=><action>;
            ...
      (<unparse>)=><action>;

Les expressions non analysées sont des tests qui correspondent à des modèles d'arborescence et / ou à des types d'objets les séparant et affectant ces parties à une variable locale à traiter par son action procédurale. Un peu comme une fonction surchargée prenant différents types d'arguments. Sauf que les tests () => ... sont tentés dans l'ordre codé. La première analyse non réussie a exécuté son action correspondante. Les expressions non analysées sont des tests de démontage. ADD [x, y] correspond à une arborescence ADD à deux branches affectant ses branches aux variables locales x et y. L'action peut être une expression simple ou un bloc de code borné .BEGIN ... .END. J'utiliserais des blocs de style c {...} aujourd'hui. L'arborescence, [], les règles non analysées peuvent appeler des générateurs transmettant le ou les résultats renvoyés à l'action:

expr_gen(ADD[expr_gen(x),expr_gen(y)])=> x+y;

Plus précisément, l'expr_gen unparse ci-dessus correspond à un arbre ADD à deux branches. Dans le modèle de test, un générateur d'arguments unique placé dans une branche d'arbre sera appelé avec cette branche. Sa liste d'arguments est cependant des variables locales affectées aux objets retournés. Au-dessus de l'analyse non spécifiée, une branche deux est le démontage de l'arbre ADD, récursif en appuyant sur chaque branche pour expr_gen. Le retour de branche gauche placé dans dans les variables locales x. De même, la branche de droite est passée à expr_gen avec y l'objet de retour. Ce qui précède pourrait faire partie d'un évaluateur d'expression numérique. Il y avait des fonctionnalités de raccourci appelées vecteurs qui étaient au-dessus de la chaîne de nœuds, un vecteur de nœuds pouvait être utilisé avec un vecteur d'actions correspondantes:

expr_gen(#node[expr_gen(x),expr_gen(y)])=> #action;

  node:   ADD, SUB, MPY, DIV;
  action: x+y, x-y, x*y, x/y;

        (NUMBER(x))=> x;
        (SYMBOL(x))=> val:(x);

L'évaluateur d'expression plus complet ci-dessus affectant le retour de la branche gauche expr_gen à x et la branche droite à y. Le vecteur d'action correspondant exécuté sur x et y est retourné. Les dernières paires d'actions non analysées => correspondent aux objets numériques et symboles.

Symbole et attributs de symbole

Les symboles peuvent avoir des attributs nommés. val: (x) accéder à l'attribut val de l'objet symbole contenu dans x. Une pile de tables de symboles généralisés fait partie de SLIC. La table SYMBOL peut être poussée et sautée fournissant des symboles locaux pour les fonctions. Les symboles nouvellement créés sont catalogués dans la table des symboles supérieure. La recherche de symboles recherche la pile de tables de symboles à partir de la table supérieure en premier dans la pile.

Génération de code indépendant de la machine

Le langage générateur de SLIC produit des objets d'instruction PSEUDO, en les ajoutant à une liste de codes de sections. Un .FLUSH provoque l'exécution de sa liste de codes PSEUDO en supprimant chaque instruction PSEUDO de la liste et en l'appelant. Après l'exécution, une mémoire d'objets PSEUDO est libérée. Les corps procéduraux des actions PSEUDO et GENERATOR sont essentiellement le même langage, à l'exception de leur sortie. PSEUDO sont censés agir comme des macros d'assemblage fournissant une séquentialisation de code indépendante de la machine. Ils permettent de séparer la machine cible spécifique du langage du générateur d'exploration d'arbres. Les PSEUDO appellent les fonctions MACHOP pour sortir le code machine. Les MACHOP sont utilisés pour définir des pseudo-opérations d'assemblage (comme dc, définir une constante, etc.) et des instructions machine ou une famille d'instructions formées similaires utilisant une entrée vectorisée. Ils transforment simplement leurs paramètres en une séquence de champs de bits constituant l'instruction. Les appels MACHOP sont censés ressembler à un assembly et fournir une mise en forme d'impression des champs lorsque l'assembly est affiché dans la liste de compilation. Dans l'exemple de code, j'utilise des commentaires de style c qui pourraient être facilement ajoutés mais qui n'étaient pas dans les langues d'origine. Les MACHOP produisent du code dans une mémoire adressable par bits. L'éditeur de liens SLIC gère la sortie du compilateur. Un MACHOP pour les instructions du mode utilisateur DEC-10 utilisant une entrée vectorisée: Les MACHOP produisent du code dans une mémoire adressable par bits. L'éditeur de liens SLIC gère la sortie du compilateur. Un MACHOP pour les instructions du mode utilisateur DEC-10 utilisant une entrée vectorisée: Les MACHOP produisent du code dans une mémoire adressable par bits. L'éditeur de liens SLIC gère la sortie du compilateur. Un MACHOP pour les instructions du mode utilisateur DEC-10 utilisant une entrée vectorisée:

.MACHOP #opnm register,@indirect offset (index): // Instruction's parameters.
.MORG 36, O(18): $/36; // Align to 36 bit boundary print format: 18 bit octal $/36
O(9):  #opcd;          // Op code 9 bit octal print out
 (4):  register;       // 4 bit register field appended print
 (1):  indirect;       // 1 bit appended print
 (4):  index;          // 4 bit index register appended print
O(18): if (#opcd&&3==1) offset // immediate mode use value else
       else offset/36;         // memory address divide by 36
                               // to get word address.
// Vectored entry opcode table:
#opnm := MOVE, MOVEI, MOVEM, MOVES, MOVS, MOVSI, MOVSM, MOVSS,
         MOVN, MOVNI, MOVNM, MOVNS, MOVM, MOVMI, MOVMM, MOVMS,
         IMUL, IMULI, IMULM, IMULB, MUL,  MULI,  MULM,  MULB,
                           ...
         TDO,  TSO,   TDOE,  TSOE,  TDOA, TSOA,  TDON,  TSON;
// corresponding opcode value:
#opcd := 0O200, 0O201, 0O202, 0O203, 0O204, 0O205, 0O206, 0O207,
         0O210, 0O211, 0O212, 0O213, 0O214, 0O215, 0O216, 0O217,
         0O220, 0O221, 0O222, 0O223, 0O224, 0O225, 0O226, 0O227,
                           ...
         0O670, 0O671, 0O672, 0O673, 0O674, 0O675, 0O676, 0O677;

Le .MORG 36, O (18): $ / 36; aligne l'emplacement sur une limite de 36 bits en imprimant l'adresse de l'emplacement $ / 36 mots de 18 bits en octal. L'opcd à 9 bits, le registre à 4 bits, le registre indirect et l'index à 4 bits sont combinés et imprimés comme s'il s'agissait d'un seul champ de 18 bits. L'adresse 18 bits / 36 ou la valeur immédiate est sortie et imprimée en octal. Un exemple MOVEI s'imprime avec r1 = 1 et r2 = 2:

400020 201082 000005            MOVEI r1,5(r2)

Avec l'option d'assemblage du compilateur, vous obtenez le code d'assemblage généré dans la liste de compilation.

Reliez-les ensemble

L'éditeur de liens SLIC est fourni sous forme de bibliothèque qui gère les résolutions de liaison et de symbole. Le formatage du fichier de chargement de sortie spécifique à la cible doit cependant être écrit pour les machines cibles et lié à la bibliothèque de la bibliothèque de l'éditeur de liens.

Le langage générateur est capable d'écrire des arborescences dans un fichier et de les lire permettant d'implémenter un compilateur multipass.

Bref résumé de la génération et des origines du code

J'ai parcouru la génération de code en premier pour m'assurer qu'il est entendu que SLIC était un véritable compilateur compilateur. SLIC a été inspiré par CWIC (Compilateur pour les compilateurs d'écriture et d'implémentation) développé à Systems Development Corporation à la fin des années 1960. CWIC n'avait que les langages SYNTAX et GENERATOR produisant un code d'octet numérique à partir du langage GENERATOR. Le code d'octet a été placé ou planté (le terme utilisé dans la documentation CWIC) dans des tampons de mémoire associés aux sections nommées et écrit par une instruction .FLUSH. Un article de l'ACM sur CWIC est disponible dans les archives de l'ACM.

Implémentation réussie d'un langage de programmation majeur

À la fin des années 1970, SLIC a été utilisé pour écrire un compilateur croisé COBOL. Terminé en environ 3 mois, principalement par un seul programmeur. J'ai travaillé un peu avec le programmeur au besoin. Un autre programmeur a écrit la bibliothèque d'exécution et les MACHOP pour le mini-ORDINATEUR TI-990 cible. Ce compilateur COBOL a compilé beaucoup plus de lignes par seconde que le compilateur COBOL natif DEC-10 écrit en assembleur.

Plus à un compilateur puis parlait généralement

Une grande partie de l'écriture d'un compilateur à partir de zéro est la bibliothèque d'exécution. Vous avez besoin d'une table des symboles. Vous avez besoin d'entrée et de sortie. Gestion dynamique de la mémoire, etc. Il peut facilement être plus de travail d'écrire la bibliothèque d'exécution pour un compilateur que d'écrire le compilateur. Mais avec SLIC, cette bibliothèque d'exécution est commune à tous les compilateurs développés dans SLIC. Notez qu'il existe deux bibliothèques d'exécution. Un pour la machine cible de la langue (COBOL par exemple). L'autre est la bibliothèque d'exécution des compilateurs du compilateur.

Je pense avoir établi qu'il ne s'agissait pas de générateurs d'analyseurs. Alors maintenant, avec un peu de compréhension du back-end, je peux expliquer le langage de programmation de l'analyseur.

Langage de programmation de l'analyseur

L'analyseur est écrit à l'aide d'une formule écrite sous la forme d'équations simples.

<name> <formula type operator> <expression> ;

L'élément de langage au niveau le plus bas est le caractère. Les jetons sont formés à partir d'un sous-ensemble des caractères de la langue. Les classes de caractères sont utilisées pour nommer et définir ces sous-ensembles de caractères. L'opérateur définissant la classe de caractères est le caractère deux-points (:). Les caractères qui sont membres de la classe sont codés sur le côté droit de la définition. Les caractères imprimables sont enfermés dans des chaînes simples de nombres premiers. Les caractères non imprimables et spéciaux peuvent être représentés par leur ordinal numérique. Les membres de la classe sont séparés par une alternative | opérateur. Une formule de classe se termine par un point-virgule. Les classes de caractères peuvent inclure des classes définies précédemment:

/*  Character Class Formula                                    class_mask */
bin: '0'|'1';                                                // 0b00000010
oct: bin|'2'|'3'|'4'|'5'|'6'|'7';                            // 0b00000110
dgt: oct|'8'|'9';                                            // 0b00001110
hex: dgt|'A'|'B'|'C'|'D'|'E'|'F'|'a'|'b'|'c'|'d'|'e'|'f';    // 0b00011110
upr:  'A'|'B'|'C'|'D'|'E'|'F'|'G'|'H'|'I'|'J'|'K'|'L'|'M'|
      'N'|'O'|'P'|'Q'|'R'|'S'|'T'|'U'|'V'|'W'|'X'|'Y'|'Z';   // 0b00100000
lwr:  'a'|'b'|'c'|'d'|'e'|'f'|'g'|'h'|'i'|'j'|'k'|'l'|'m'|
      'n'|'o'|'p'|'q'|'r'|'s'|'t'|'u'|'v'|'w'|'x'|'y'|'z';   // 0b01000000
alpha:  upr|lwr;                                             // 0b01100000
alphanum: alpha|dgt;                                         // 0b01101110

La skip_class 0b00000001 est prédéfinie mais peut être en cours de définition d'une skip_class.

En résumé: une classe de caractères est une liste d'alternatives qui ne peuvent être qu'une constante de caractère, un ordinal de caractère ou une classe de caractères précédemment définie. Comme j'ai implémenté les classes de caractères: la formule de classe se voit attribuer un masque de bits de classe. (Montré dans les commentaires ci-dessus) Toute formule de classe ayant un caractère littéral ou ordinal entraîne l'allocation d'un bit de classe. Un masque est créé en orant le (s) masque (s) de classe de la (des) classe (s) incluse (s) avec le bit alloué (le cas échéant). Une table de classes est créée à partir des classes de caractères. Une entrée indexée par l'ordinal d'un caractère contient des bits indiquant les appartenances à la classe du caractère. Les tests de classe se font en ligne. Un exemple de code IA-86 avec l'ordinal du caractère en eax illustre les tests de classe:

test    byte ptr [eax+_classmap],dgt

Suivi d'un:

jne      <success>

ou

je       <failure>

Des exemples de code d'instructions IA-86 sont utilisés parce que je pense que les instructions IA-86 sont plus largement connues aujourd'hui. Le nom de classe évaluant son masque de classe est AND de manière non destructive avec la table de classe indexée par les caractères ordinaux (en eax). Un résultat différent de zéro indique l'appartenance à une classe. (EAX est mis à zéro, sauf pour al (les 8 bits les plus bas de EAX) qui contient le caractère).

Les jetons étaient un peu différents dans ces anciens compilateurs. Les mots clés n'ont pas été expliqués comme des jetons. Ils étaient simplement mis en correspondance par des constantes de chaîne entre guillemets dans le langage de l'analyseur. Les chaînes entre guillemets ne sont normalement pas conservées. Des modificateurs peuvent être utilisés. A + conserve la chaîne correspondante. (c'est-à-dire + '-' correspond à un caractère - en gardant le caractère en cas de succès) L'opération, (c'est-à-dire 'E') insère la chaîne dans le jeton. Les espaces blancs sont gérés par la formule du jeton en sautant les premiers caractères SKIP_CLASS jusqu'à ce qu'une première correspondance soit établie. Notez qu'une correspondance explicite de caractère skip_class arrêtera le saut permettant à un jeton de commencer par un caractère skip_class. La formule de jeton de chaîne ignore les principaux caractères skip_class correspondant à un caractère guillemet simple ou à une chaîne entre guillemets doubles. Il est intéressant de faire correspondre un "caractère dans une" chaîne entre guillemets:

string .. (''' .ANY ''' | '"' $(-"""" .ANY | """""","""") '"') MAKSTR[];

La première alternative correspond à tout caractère entre guillemets simples. L'alternative droite correspond à une chaîne entre guillemets doubles qui peut inclure des caractères de guillemet double en utilisant deux "caractères ensemble pour représenter un seul" caractère. Cette formule définit les chaînes utilisées dans sa propre définition. L'alternative intérieure droite '"' $ (-" "" ".ANY |" "" "" "", "" "") '"' correspond à une chaîne entre guillemets doubles. Nous pouvons utiliser un seul caractère "entre guillemets pour correspondre à un caractère". Par exemple dans l'alternative intérieure gauche correspondant à n'importe quel caractère sauf une citation:

-"""" .ANY

un coup d'œil négatif - "" "" est utilisé qui, en cas de succès (ne correspond pas à un "caractère), correspond alors au caractère .ANY (qui ne peut pas être un" caractère car - "" "" a éliminé cette possibilité). La bonne alternative prend - "" "" correspondant à un "caractère et à défaut était la bonne alternative:

"""""",""""

essaie de faire correspondre deux "caractères en les remplaçant par un double double" en utilisant, "" "" pour insérer le seul caractère ". Les deux alternatives internes qui échouent à la fermeture du guillemet de chaîne sont mises en correspondance et MAKSTR [] est appelé pour créer un objet chaîne. Le $ séquence, boucle en cas de réussite, l'opérateur est utilisé pour faire correspondre une séquence. Formule de jeton ignorer les principaux caractères de la classe de saut (avec espace). Une fois la première correspondance établie, skip_class est désactivé. Nous pouvons appeler des fonctions programmées dans d'autres langues à l'aide de []. MAKSTR [], MAKBIN [], MAKOCT [], MAKHEX [], MAKFLOAT [] et MAKINT [] sont des fonctions de bibliothèque fournies qui convertissent une chaîne de jeton correspondante en objet typé. La formule numérique ci-dessous illustre une reconnaissance de jeton assez complexe:

number .. "0B" bin $bin MAKBIN[]        // binary integer
         |"0O" oct $oct MAKOCT[]        // octal integer
         |("0H"|"0X") hex $hex MAKHEX[] // hexadecimal integer
// look for decimal number determining if integer or floating point.
         | ('+'|+'-'|--)                // only - matters
           dgt $dgt                     // integer part
           ( +'.' $dgt                  // fractional part?
              ((+'E'|'e','E')           // exponent  part
               ('+'|+'-'|--)            // Only negative matters
               dgt(dgt(dgt|--)|--)|--)  // 1 2 or 3 digit exponent
             MAKFLOAT[] )               // floating point
           MAKINT[];                    // decimal integer

La formule de jeton numérique ci-dessus reconnaît les nombres entiers et à virgule flottante. Les alternatives sont toujours couronnées de succès. Les objets numériques peuvent être utilisés dans les calculs. Les objets jetons sont poussés sur la pile d'analyse en cas de succès de la formule. L'exposant en tête (+ 'E' | 'e', ​​'E') est intéressant. Nous souhaitons toujours avoir un E majuscule pour MAKEFLOAT []. Mais nous autorisons un «e» minuscule en le remplaçant par «E».

Vous avez peut-être remarqué des consistances de classe de caractères et de formule de jeton. La formule d'analyse continue d'ajouter des alternatives de retour en arrière et des opérateurs de construction d'arbre. Les opérateurs alternatifs avec retour arrière et sans retour arrière ne peuvent pas être mélangés au sein d'un niveau d'expression. Vous ne pouvez pas avoir (a | b \ c) un mélange sans retour arrière | avec l'alternative \ backtracking. (a \ b \ c), (a | b | c) et ((a | b) \ c) sont valides. Une alternative \ backtracking enregistre l'état d'analyse avant de tenter son alternative gauche et en cas d'échec restaure l'état d'analyse avant de tenter l'alternative droite. Dans une séquence d'alternatives, la première alternative réussie satisfait le groupe. Aucune autre alternative n'est tentée. L'affacturage et le regroupement permettent une analyse en continu. L'alternative de retour en arrière crée un état enregistré de l'analyse avant d'essayer son alternative de gauche. Le retour en arrière est requis lorsque l'analyse peut effectuer une correspondance partielle puis échouer:

(a b | c d)\ e

Dans ce qui précède, en cas d'échec de retour, le CD alternatif est tenté. Si c renvoie l'échec, l'alternative de retour en arrière sera tentée. Si a réussit et b échoue, l'analyse sera inversée et e tentée. De même, un échec c réussi et b échoue l'analyse est inversée et l'alternative e prise. Le retour en arrière ne se limite pas à une formule. Si une formule d'analyse effectue une correspondance partielle à tout moment, puis échoue, l'analyse est réinitialisée sur la première piste et son alternative est prise. Un échec de compilation peut se produire si du code a été généré, la piste arrière a été créée. Un retour en arrière est défini avant de démarrer la compilation. Renvoyer l'échec ou revenir en arrière est un échec du compilateur. Les backtracks sont empilés. Nous pouvons utiliser négatif - et positif? jeter un œil aux opérateurs à venir pour tester sans faire avancer l'analyse. être un test de chaîne est un coup d'œil qui n'a besoin que de l'état d'entrée enregistré et réinitialisé. Un regard vers l'avenir serait une expression d'analyse qui établit une correspondance partielle avant d'échouer. Un regard en avant est mis en œuvre en utilisant le retour arrière.

La langue de l'analyseur n'est ni un analyseur LL ni LR. Mais un langage de programmation pour écrire un analyseur décent récursif dans lequel vous programmez la construction de l'arborescence:

:<node name> creates a node object and pushes it onto the node stack.
..           Token formula create token objects and push them onto 
             the parse stack.
!<number>    pops the top node object and top <number> of parstack 
             entries into a list representation of the tree. The 
             tree then pushed onto the parse stack.
+[ ... ]+    creates a list of the parse stack entries created 
             between them:
              '(' +[argument $(',' argument]+ ')'
             could parse an argument list. into a list.

Un exemple d'analyse couramment utilisé est une expression arithmétique:

Exp = Term $(('+':ADD|'-':SUB) Term!2); 
Term = Factor $(('*':MPY|'/':DIV) Factor!2);
Factor = ( number
         | id  ( '(' +[Exp $(',' Exp)]+ ')' :FUN!2
               | --)
         | '(' Exp ')" )
         (^' Factor:XPO!2 |--);

Exp et Term utilisant une boucle crée un arbre pour gaucher. Le facteur utilisant la récursivité droite crée un arbre droitier:

d^(x+5)^3-a+b*c => ADD[SUB[EXP[EXP[d,ADD[x,5]],3],a],MPY[b,c]]

              ADD
             /   \
          SUB     MPY
         /   \   /   \
      EXP     a b     c
     /   \
    d     EXP     
         /   \
      ADD     3
     /   \
    x     5

Voici un peu du compilateur cc, une version mise à jour de SLIC avec des commentaires de style c. Les types de fonctions (grammaire, jeton, classe de caractères, générateur, PSEUDO ou MACHOP sont déterminés par leur syntaxe initiale suivant leur identifiant. Avec ces analyseurs descendants, vous commencez avec une formule de définition de programme:

program = $((declaration            // A program is a sequence of
                                    // declarations terminated by
            |.EOF .STOP)            // End Of File finish & stop compile
           \                        // Backtrack: .EOF failed or
                                    // declaration long-failed.
             (ERRORX["?Error?"]     // report unknown error
                                    // flagging furthest parse point.
              $(-';' (.ANY          // find a ';'. skiping .ANY
                     | .STOP))      // character: .ANY fails on end of file
                                    // so .STOP ends the compile.
                                    // (-';') failing breaks loop.
              ';'));                // Match ';' and continue

declaration =  "#" directive                // Compiler directive.
             | comment                      // skips comment text
             | global        DECLAR[*1]     // Global linkage
             |(id                           // functions starting with an id:
                ( formula    PARSER[*1]     // Parsing formula
                | sequencer  GENERATOR[*1]  // Code generator
                | optimizer  ISO[*1]        // Optimizer
                | pseudo_op  PRODUCTION[*1] // Pseudo instruction
                | emitor_op  MACHOP[*1]     // Machine instruction
                )        // All the above start with an identifier
              \ (ERRORX["Syntax error."]
                 garbol);                    // skip over error.

// Notez comment id est factorisé et combiné ultérieurement lors de la création de l'arborescence.

formula =   ("==" syntax  :BCKTRAK   // backtrack grammar formula
            |'='  syntax  :SYNTAX    // grammar formula.
            |':'  chclass :CLASS     // character class define
            |".." token   :TOKEN     // token formula
              )';' !2                // Combine node name with id 
                                     // parsed in calling declaration 
                                     // formula and tree produced
                                     // by the called syntax, token
                                     // or character class formula.
                $(-(.NL |"/*") (.ANY|.STOP)); Comment ; to line separator?

chclass = +[ letter $('|' letter) ]+;// a simple list of character codes
                                     // except 
letter  = char | number | id;        // when including another class

syntax  = seq ('|' alt1|'\' alt2 |--);

alt1    = seq:ALT!2 ('|' alt1|--);  Non-backtrack alternative sequence.

alt2    = seq:BKTK!2 ('\' alt2|--); backtrack alternative sequence

seq     = +[oper $oper]+;

oper    = test | action | '(' syntax ')' | comment; 

test    = string | id ('[' (arg_list| ,NILL) ']':GENCALL!2|.EMPTY);

action  = ':' id:NODE!1
        | '!' number:MAKTREE!1
        | "+["  seq "]+" :MAKLST!1;

//     C style comments
comment  = "//" $(-.NL .ANY)
         | "/*" $(-"*/" .ANY) "*/";

Il convient de noter comment le langage de l'analyseur gère les commentaires et la récupération d'erreur.

Je pense avoir répondu à la question. Ayant écrit une grande partie du successeur des SLIC, le langage cc en soi ici. Il n'y a pas encore de compilateur pour cela. Mais je peux le compiler à la main en code assembleur, en fonctions nues asm c ou c ++.

Oui, vous pouvez écrire un compilateur pour une langue dans cette langue. Non, vous n'avez pas besoin d'un premier compilateur pour que cette langue démarre.

Ce dont vous avez besoin pour démarrer est une implémentation du langage. Cela peut être un compilateur ou un interprète.

Historiquement, les langues étaient généralement considérées comme des langues interprétées ou des langues compilées. Les interprètes n'ont été écrits que pour les premiers et les compilateurs n'ont été écrits que pour les seconds. Donc, généralement, si un compilateur devait être écrit pour une langue, le premier compilateur serait écrit dans une autre langue pour l'amorcer, puis, facultativement, le compilateur serait réécrit pour la langue du sujet. Mais écrire un interprète dans une autre langue est plutôt une option.

Ce n'est pas seulement théorique. Il se trouve que je le fais moi-même actuellement. Je travaille sur un compilateur pour un langage, Salmon, que j'ai développé moi-même. J'ai d'abord créé un compilateur Salmon en C et maintenant j'écris le compilateur dans Salmon, donc je peux faire fonctionner le compilateur Salmon sans jamais avoir de compilateur pour Salmon écrit dans un autre langage.

Vous pouvez peut-être écrire un BNF décrivant le BNF.