Rédaction d'un compilateur Compilateur - Aperçu sur l'utilisation et les fonctionnalités

Cela fait partie d'une série de questions qui se concentre sur le projet frère du projet Abstraction, qui vise à résumer les concepts utilisés dans la conception du langage sous la forme d'un cadre. Le projet sœur s'appelle OILexer, qui vise à construire un analyseur à partir de fichiers de grammaire, sans utiliser d'injection de code sur les correspondances.

Quelques autres pages associées à ces questions, liées au typage structurel, peuvent être consultées ici , et la facilité d'utilisation, ici . Le méta-sujet associé à une enquête sur le cadre et le bon endroit pour publier peut être trouvé ici .

J'arrive au point où je suis sur le point de commencer à extraire l'arbre d'analyse d'une grammaire donnée, suivi d'un analyseur de descente récursive qui utilise DFA pour discerner les chemins avant (similaire à LL (*) d'ANTLR 4, donc je pensé que je l'ouvrirais pour avoir un aperçu.

Dans un compilateur d'analyseur, quels types de fonctionnalités sont idéales?

Jusqu'à présent, voici un bref aperçu de ce qui est mis en œuvre:

1. Modèles
2. Anticipez la prévision, sachant ce qui est valable à un moment donné.
3. Règle de «délitéralisation» prenant les littéraux dans les règles et déterminant de quel jeton ils proviennent.
4. Automates non déterministes
5. Automates déterministes
6. Machine d'état lexicale simple pour la reconnaissance des jetons
7. Méthodes d'automatisation des jetons:
   • Scan - utile pour les commentaires: Commentaire: = "/ *" Scan ("* /");
   • Soustraire - Utile pour les identifiants: Identifier: = Soustraire (IdentifierBody, Keywords);
     • Garantit que l'identifiant n'accepte pas les mots clés.
   • Encode - Encode une automatisation sous la forme d'un décompte série X des transitions N de base.
     • UnicodeEscape: = "\\ u" BaseEncode (IdentifierCharNoEscape, 16, 4);
       • Fait un échappement unicode en hexadécimal, avec 4 transitions hexadécimales. La différence entre ceci et: [0-9A-Fa-f] {4} est que l'automatisation résultante avec Encode limite l'ensemble autorisé de valeurs hexadécimales à la portée d'IdentifierCharNoEscape. Donc, si vous lui donnez \ u005c, la version d'encodage n'acceptera pas la valeur. Des choses comme celle-ci ont une sérieuse mise en garde: utilisez avec parcimonie. L'automatisation qui en résulte pourrait être assez complexe.

Ce qui n'est pas implémenté est la génération CST, j'ai besoin d'ajuster les automatisations déterministes pour conserver le contexte approprié pour que cela fonctionne.

Pour toute personne intéressée, j'ai téléchargé une jolie copie de la forme originale du projet T * y♯ . Chaque fichier devrait être lié à un autre, j'ai commencé à lier les règles individuelles pour les suivre, mais cela aurait pris beaucoup trop de temps (cela aurait été plus simple à automatiser!)

Si plus de contexte est nécessaire, veuillez poster en conséquence.

Edit 5-14-2013 : J'ai écrit du code pour créer des graphiques GraphViz pour les machines à états dans une langue donnée. Voici un digraphe GraphViz du AssemblyPart . Les membres liés dans la description de la langue doivent avoir un rulename.txt dans leur dossier relatif avec le digraphe de cette règle. Une partie de la description de la langue a changé depuis que j'ai posté l'exemple, cela est dû à la simplification des choses sur la grammaire. Voici une image graphique intéressante .

Ceci est une excellente question.

J'ai travaillé sur beaucoup d'analyses récemment, et à mon humble avis, certaines des fonctionnalités clés sont:

• une API de programmation - afin qu'elle puisse être utilisée à partir d'un langage de programmation, idéalement en important simplement une bibliothèque. Il peut également avoir une interface GUI ou BNF, mais la programmation est la clé, car vous pouvez réutiliser vos outils, IDE, analyse statique, tests, installations d'abstraction de langage, familiarité avec les programmeurs, générateur de documentation, processus de construction, etc. De plus, vous pouvez jouer de manière interactive avec de minuscules analyseurs, ce qui réduit considérablement la courbe d'apprentissage. Ces raisons le placent en haut de ma liste des "fonctionnalités importantes".

• rapport d'erreurs, comme l'a mentionné @guysherman. Lorsqu'une erreur est trouvée, je veux savoir où était l'erreur et ce qui se passait quand elle s'est produite. Malheureusement, je n'ai pas pu trouver de bonnes ressources pour expliquer comment générer des erreurs décentes lorsque le retour en arrière entre en jeu. (Bien que notez le commentaire de Sk-logic ci-dessous).

• résultats partiels. Lorsque l'analyse échoue, je veux pouvoir voir ce qui a été analysé avec succès à partir de la partie de l'entrée qui se trouvait avant l'emplacement de l'erreur.

• abstraction. Vous ne pouvez jamais créer suffisamment de fonctions, et l'utilisateur en aura toujours besoin de plus, donc essayer de comprendre toutes les fonctions possibles à l'avance est voué à l'échec. Est-ce ce que vous entendez par modèles?

• Je suis d'accord avec votre n ° 2 (prédiction prospective). Je pense que cela aide à générer de bons rapports d'erreur. Est-ce utile pour autre chose?

• prise en charge de la construction d'un arbre d'analyse au fur et à mesure de l'analyse, peut-être:

  • un arbre de syntaxe concret, pour lequel la structure de l'arbre correspond directement à la grammaire et comprend des informations de mise en page pour le rapport d'erreurs des phases ultérieures. Dans ce cas, le client ne devrait pas avoir à faire quoi que ce soit pour obtenir la structure de l' arbre droit - il devrait dépendre directement de la grammaire.
  • un arbre de syntaxe abstraite. Dans ce cas, l'utilisateur peut jouer avec tous les arbres d'analyse

• une sorte de journalisation. Je ne suis pas sûr de celui-ci; peut-être pour afficher une trace des règles que l'analyseur a essayées, ou pour garder une trace des jetons indésirables tels que les espaces ou les commentaires, au cas où (par exemple) vous souhaitez utiliser les jetons pour générer de la documentation HTML.

• capacité à gérer des langages contextuels. Je ne sais pas non plus à quel point celui-ci est important - en pratique, il semble plus propre d'analyser un sur-ensemble d'une langue avec une grammaire sans contexte, puis de vérifier les contraintes contextuelles dans des passages ultérieurs supplémentaires.

• messages d'erreur personnalisés, afin que je puisse régler les rapports d'erreur dans des situations spécifiques et peut-être plus rapidement comprendre et résoudre les problèmes.

D'un autre côté, je ne trouve pas la correction d'erreurs particulièrement importante - bien que je ne sois pas au courant des progrès actuels. Les problèmes que j'ai remarqués sont que les corrections potentielles fournies par les outils sont: 1) trop nombreuses et 2) ne correspondent pas aux erreurs réelles commises et ne sont donc pas très utiles. Espérons que cette situation s'améliorera (ou peut-être l'a déjà fait).

Je n'ai pas d'expérience en conception de langage, mais j'ai déjà essayé d'écrire un analyseur, quand je créais et IDE pour un moteur de jeu.

À mon avis, ce qui est important pour vos utilisateurs finaux ultimes, ce sont les messages d'erreur qui ont du sens. Ce n'est pas un point particulièrement bouleversant, je sais, mais en le suivant à l'envers, l'une des principales implications de cela est que vous devez être en mesure d'éviter les faux positifs. D'où viennent les faux positifs? Ils proviennent de l'analyseur tombant à la première erreur et ne se remettant jamais tout à fait. C / C ++ est connu pour cela (bien que les nouveaux compilateurs soient un peu plus intelligents).

Alors, de quoi avez-vous besoin à la place? Je pense que plutôt que de simplement savoir ce qui est / n'est pas valide à un moment donné, vous devez savoir comment prendre ce qui n'est pas valide et apporter une modification minimale pour le rendre valide - afin que vous puissiez continuer l'analyse sans générer de fausses erreurs concernant à votre descente récursive se confondre. Être capable de construire un analyseur qui peut générer ces informations vous donne non seulement un analyseur très robuste, mais il ouvre des fonctionnalités fantastiques pour le logiciel qui utilise l'analyseur.

Je me rends compte que je suggère peut-être quelque chose de vraiment difficile, ou stupidement évident, désolé si c'est le cas. Si ce n'est pas le genre de chose que vous recherchez, je supprimerai volontiers ma réponse.

La grammaire ne doit pas avoir de restrictions comme "ne pas laisser de règles récursives". Il est ridicule que les outils largement utilisés aujourd'hui aient cela et ne puissent comprendre que les grammaires de succion LL - près de 50 ans après que yacc l' ait fait correctement.

Un exemple de récursivité droite (en utilisant la syntaxe yacc):

list: 
      elem                  { $$ = singleton($1); }
    | elem ',' list         { $$ = cons($1, $2);  }
    ;

Un exemple pour la récursion gauche (en utilisant le synatx yacc):

funapp:
    term                    { $$ = $1; }
    | funapp term           { $$ = application($1, $2); }
    ;

Maintenant, cela pourrait peut-être "refactoriser" quelque chose d'autre, mais dans les deux cas, le type spécifique de récursivité est juste la "bonne" façon d'écrire ceci, car (dans l'exemple de langage) les listes sont récursives à droite tandis que l'application de fonction est récursive à gauche .

On peut s'attendre à ce que les outils avancés prennent en charge la manière naturelle d'écrire des trucs, au lieu d'exiger que l'on "refactorise" tout pour qu'il soit récursif gauche / droite sous la forme imposée par l'outil.