Devrais-je utiliser un générateur d’analyseur ou devrais-je lancer mon propre lexer et code d’analyseur personnalisés?

Quels avantages et inconvénients spécifiques de chaque manière de travailler sur une grammaire de langage de programmation?

Pourquoi / Quand devrais-je rouler le mien? Pourquoi / quand devrais-je utiliser un générateur?

Il y a vraiment trois options, toutes les trois préférables dans des situations différentes.

Option 1: générateurs d’analyseurs, ou "vous devez analyser une langue et vous voulez juste que cela fonctionne, bon sang"

Dites, on vous demande de créer un analyseur syntaxique pour un ancien format de données MAINTENANT. Ou vous avez besoin que votre analyseur soit rapide. Ou vous avez besoin que votre analyseur soit facilement maintenable.

Dans ces cas, vous feriez probablement mieux d'utiliser un générateur d'analyseur syntaxique. Vous n'avez pas besoin de bricoler avec les détails, vous n'avez pas besoin d'utiliser beaucoup de code compliqué pour bien fonctionner, vous écrivez simplement la grammaire à laquelle l'entrée va adhérer, vous écrivez du code de manipulation et un analyseur instantané.

Les avantages sont clairs:

• Il est (généralement) assez facile d'écrire une spécification, en particulier si le format d'entrée n'est pas trop étrange (l'option 2 serait préférable si c'est le cas).
• Vous vous retrouvez avec un travail très facilement maintenable et facile à comprendre: une définition grammaticale coule généralement beaucoup plus naturellement que le code.
• Les analyseurs générés par de bons générateurs d’analyseurs sont généralement beaucoup plus rapides que le code écrit à la main. Le code écrit à la main peut être plus rapide, mais seulement si vous connaissez votre matériel - c'est pourquoi les compilateurs les plus utilisés utilisent un analyseur syntaxique de descente récursif écrit à la main.

Il y a une chose à laquelle vous devez faire attention avec les générateurs d’analyseurs: ils peuvent parfois rejeter vos grammaires. Pour avoir un aperçu des différents types d’analyseurs et de la façon dont ils peuvent vous mordre, vous voudrez peut-être commencer ici . Ici vous trouverez un aperçu d'un grand nombre de mises en œuvre et les types de grammaires qu'ils acceptent.

Option 2: analyseurs manuscrits, ou "vous voulez créer votre propre analyseur, et vous tenez à être convivial"

Les générateurs d’analyseurs sont bien, mais ils ne sont pas très conviviaux (l’utilisateur final, pas vous). En règle générale, vous ne pouvez pas donner de bons messages d'erreur, vous ne pouvez pas non plus fournir de récupération d'erreur. Votre langue est peut-être très étrange et les analyseurs syntaxiques rejettent votre grammaire ou vous avez besoin de plus de contrôle que le générateur ne vous en donne.

Dans ces cas, utiliser un analyseur syntaxique à descente récursif écrit à la main est probablement le meilleur. Bien que cela puisse sembler compliqué, vous avez le contrôle total de votre analyseur. Vous pouvez ainsi effectuer toutes sortes de choses intéressantes que vous ne pouvez pas utiliser avec des générateurs d'analyseur, comme les messages d'erreur et même la récupération sur erreur (essayez de supprimer tous les points-virgules d'un fichier C #. : le compilateur C # se plaindra, mais détectera la plupart des autres erreurs malgré la présence de points-virgules).

Les analyseurs manuscrits fonctionnent généralement mieux que ceux générés, en supposant que la qualité de l’analyseur est suffisamment élevée. D'un autre côté, si vous ne parvenez pas à écrire un bon analyseur (généralement en raison d'un manque d'expérience, de connaissances ou d'une conception insuffisante), les performances sont généralement plus lentes. Le contraire est toutefois vrai pour les lexers: les lexeurs généralement générés utilisent des recherches dans les tables, ce qui les rend plus rapides que celles (la plupart) manuscrites.

Sur le plan de l’éducation, écrire votre propre analyseur vous en apprendra plus que d’utiliser un générateur. Après tout, vous devez écrire du code de plus en plus compliqué, en plus de comprendre exactement comment vous analysez une langue. D'autre part, si vous voulez apprendre à créer votre propre langue (pour acquérir de l'expérience en conception de langue), l'option 1 ou l'option 3 est préférable: si vous développez une langue, cela changera probablement beaucoup, et les options 1 et 3 vous facilitent la tâche.

Option 3: des générateurs d'analyseurs manuscrits, ou "vous essayez d'apprendre beaucoup de ce projet et vous voudriez bien vous retrouver avec un morceau de code astucieux que vous pourrez réutiliser beaucoup"

C’est le chemin que je suis en train de parcourir: vous écrivez votre propre générateur d’analyseur. Bien que cela ne soit pas trivial, cela vous en apprendra probablement le plus.

Pour vous donner une idée de ce que fait un projet comme celui-ci, je vais vous parler de mes propres progrès.

Le générateur de lexer

J'ai d'abord créé mon propre générateur de lexer. En général, je conçois un logiciel en commençant par l'utilisation du code. J'ai donc réfléchi à la façon dont je voulais utiliser mon code et j'ai écrit ce morceau de code (en C #):

Lexer<CalculatorToken> calculatorLexer = new Lexer<CalculatorToken>(
    new List<StringTokenPair>()
    { // This is just like a lex specification:
      //                    regex   token
        new StringTokenPair("\\+",  CalculatorToken.Plus),
        new StringTokenPair("\\*",  CalculatorToken.Times),
        new StringTokenPair("(",    CalculatorToken.LeftParenthesis),
        new StringTokenPair(")",    CalculatorToken.RightParenthesis),
        new StringTokenPair("\\d+", CalculatorToken.Number),
    });

foreach (CalculatorToken token in
             calculatorLexer.GetLexer(new StringReader("15+4*10")))
{ // This will iterate over all tokens in the string.
    Console.WriteLine(token.Value);
}

// Prints:
// 15
// +
// 4
// *
// 10

Les paires chaîne / jeton en entrée sont converties en une structure récursive correspondante décrivant les expressions régulières qu’elles représentent en utilisant les idées d’une pile arithmétique. Celui-ci est ensuite converti en un NFA (automate fini non déterministe), qui est à son tour converti en un DFA (automate fini déterministe). Vous pouvez ensuite faire correspondre les chaînes avec le DFA.

De cette façon, vous aurez une bonne idée du fonctionnement exact des lexers. En outre, si vous le faites correctement, les résultats de votre générateur de lexer peuvent être à peu près aussi rapides que ceux d’implémentations professionnelles. Vous ne perdez pas non plus d'expressivité par rapport à l'option 2 et peu d'expressivité par rapport à l'option 1.

J'ai implémenté mon générateur Lexer dans un peu plus de 1600 lignes de code. Ce code rend le travail ci-dessus, mais il génère toujours le lexer à la volée chaque fois que vous démarrez le programme: je vais ajouter du code pour l'écrire sur le disque à un moment donné.

Si vous voulez savoir comment écrire votre propre lexer, c'est un bon endroit pour commencer.

Le générateur d'analyseur

Vous écrivez ensuite votre générateur d'analyseur. Je me réfère ici à nouveau pour un aperçu des différents types d’analyseurs. En règle générale, plus ils peuvent analyser, plus ils sont lents.

La vitesse n'étant pas un problème pour moi, j'ai choisi de mettre en œuvre un analyseur Earley. Les implémentations avancées d'un analyseur Earley se sont révélées environ deux fois plus lentes que les autres types d'analyseurs.

En contrepartie de cette rapidité, vous avez la possibilité d'analyser toutes les sortes de grammaires, même ambiguës. Cela signifie que vous n'avez jamais à vous soucier de savoir si votre analyseur contient une récursivité à gauche ou un conflit de réduction de décalage. Vous pouvez également définir plus facilement les grammaires à l'aide de grammaires ambiguës, indépendamment du résultat de l'arbre syntaxique. Par exemple, le fait que vous analysiez 1 + 2 + 3 comme étant indifférent (1 + 2) +3 ou 1 + (2 + 3).

Voici à quoi peut ressembler un morceau de code utilisant mon générateur d'analyseur syntaxique:

Lexer<CalculatorToken> calculatorLexer = new Lexer<CalculatorToken>(
    new List<StringTokenPair>()
    {
        new StringTokenPair("\\+",  CalculatorToken.Plus),
        new StringTokenPair("\\*",  CalculatorToken.Times),
        new StringTokenPair("(",    CalculatorToken.LeftParenthesis),
        new StringTokenPair(")",    CalculatorToken.RightParenthesis),
        new StringTokenPair("\\d+", CalculatorToken.Number),
    });

Grammar<IntWrapper, CalculatorToken> calculator
    = new Grammar<IntWrapper, CalculatorToken>(calculatorLexer);

// Declaring the nonterminals.
INonTerminal<IntWrapper> expr = calculator.AddNonTerminal<IntWrapper>();
INonTerminal<IntWrapper> term = calculator.AddNonTerminal<IntWrapper>();
INonTerminal<IntWrapper> factor = calculator.AddNonTerminal<IntWrapper>();

// expr will be our head nonterminal.
calculator.SetAsMainNonTerminal(expr);

// expr: term | expr Plus term;
calculator.AddProduction(expr, term.GetDefault());
calculator.AddProduction(expr,
                         expr.GetDefault(),
                         CalculatorToken.Plus.GetDefault(),
                         term.AddCode(
                         (x, r) => { x.Result.Value += r.Value; return x; }
                         ));

// term: factor | term Times factor;
calculator.AddProduction(term, factor.GetDefault());
calculator.AddProduction(term,
                         term.GetDefault(),
                         CalculatorToken.Times.GetDefault(),
                         factor.AddCode
                         (
                         (x, r) => { x.Result.Value *= r.Value; return x; }
                         ));

// factor: LeftParenthesis expr RightParenthesis
//         | Number;
calculator.AddProduction(factor,
                         CalculatorToken.LeftParenthesis.GetDefault(),
                         expr.GetDefault(),
                         CalculatorToken.RightParenthesis.GetDefault());
calculator.AddProduction(factor,
                         CalculatorToken.Number.AddCode
                         (
                         (x, s) => { x.Result = new IntWrapper(int.Parse(s));
                                     return x; }
                         ));

IntWrapper result = calculator.Parse("15+4*10");
// result == 55

(Notez qu'IntWrapper est simplement un Int32, sauf que C # exige que ce soit une classe. J'ai donc dû introduire une classe wrapper.)

J'espère que vous voyez que le code ci-dessus est très puissant: toute grammaire que vous pouvez créer peut être analysée. Vous pouvez ajouter des bits de code arbitraires dans la grammaire capables d'effectuer de nombreuses tâches. Si vous parvenez à ce que tout fonctionne, vous pouvez réutiliser le code résultant pour effectuer très facilement de nombreuses tâches: imaginez simplement la création d'un interpréteur de ligne de commande à l'aide de cette partie de code.

Si vous n'avez jamais écrit d'analyseur syntaxique, je vous recommande de le faire. C’est amusant, et vous apprenez comment les choses fonctionnent, et vous apprenez à apprécier les efforts que les générateurs d’analyseur et de lexer vous évitent de faire la prochaine fois que vous aurez besoin d’un analyseur.

Je vous suggère également d'essayer de lire http://compilers.iecc.com/crenshaw/ car il a une attitude très terre-à-terre quant à la façon de le faire.

L'avantage d'écrire votre propre analyseur récursif de descente est que vous pouvez générer des messages d'erreur de haute qualité sur les erreurs de syntaxe. À l'aide de générateurs d'analyse, vous pouvez générer des productions d'erreur et ajouter des messages d'erreur personnalisés à certains moments, mais ces générateurs ne correspondent tout simplement pas à la puissance d'un contrôle total sur l'analyse.

Un autre avantage de l'écriture de votre propre est qu'il est plus facile d'analyser une représentation plus simple qui n'a pas de correspondance un à un avec votre grammaire.

Si votre grammaire est corrigée et que les messages d'erreur sont importants, envisagez de faire rouler les vôtres, ou du moins d'utiliser un générateur d'analyseur qui vous fournira les messages d'erreur dont vous avez besoin. Si votre grammaire change constamment, vous devriez plutôt utiliser des générateurs d’analyseur.

Bjarne Stroustrup explique comment il a utilisé YACC pour la première implémentation de C ++ (voir Conception et évolution de C ++ ). Dans ce premier cas, il aurait souhaité écrire son propre analyseur de descente récursif!

Option 3: ni l'un ni l'autre (lancez votre propre générateur d'analyseur syntaxique)

Ce n'est pas parce qu'il y a une raison de ne pas utiliser ANTLR , bison , Coco / R , Grammatica , JavaCC , citron , étuvé , SableCC , Quex , etc. que vous devez lancer immédiatement votre propre analyseur syntaxique + lexer.

Identifiez pourquoi tous ces outils ne sont pas assez bons - pourquoi ne vous laissent-ils pas atteindre votre objectif?

Sauf si vous êtes certain que les particularités de la grammaire à laquelle vous faites face sont uniques, vous ne devez pas simplement créer un analyseur syntaxique + lexer personnalisé. Créez plutôt un outil qui créera ce que vous voulez, mais peut également être utilisé pour répondre à vos besoins futurs, puis publiez-le en tant que logiciel libre pour éviter que d’autres personnes ne rencontrent le même problème que vous.

Rouler votre propre analyseur vous oblige à réfléchir directement à la complexité de votre langue. Si le langage est difficile à analyser, il sera probablement difficile à comprendre.

Au début, il y avait beaucoup d'intérêt pour les générateurs d'analyseurs syntaxiques, motivés par une syntaxe de langage extrêmement compliquée (certains diraient "torturée"). JOVIAL était un exemple particulièrement déplorable: il fallait deux symboles avant l’affichage, à un moment où tout le reste nécessitait au plus un symbole. Cela a rendu la génération de l'analyseur syntaxique pour un compilateur JOVIAL plus difficile que prévu (car la division General Dynamics / Fort Worth a appris à ses dépens quand elle a acheté des compilateurs JOVIAL pour le programme F-16).

De nos jours, la descente récursive est universellement la méthode préférée, car elle est plus facile pour les auteurs de compilateur. Les compilateurs de descente récursive récompensent fortement la conception de langage simple et propre, en ce sens qu’il est beaucoup plus facile d’écrire un analyseur syntaxique à descente récursive pour un langage simple et propre que pour un langage compliqué et désordonné.

Enfin: avez-vous envisagé d'intégrer votre langue dans LISP et de laisser un interprète du LISP se charger de la tâche la plus ardue? AutoCAD a fait cela et a trouvé que cela leur facilitait la vie beaucoup plus facilement. Il existe de nombreux interprètes LISP légers, certains intégrables.

J'ai écrit un analyseur pour une application commerciale une fois et j'ai utilisé yacc . Il y avait un prototype concurrent où un développeur écrivait le tout à la main en C ++ et cela fonctionnait environ cinq fois plus lentement.

En ce qui concerne le lexer de cet analyseur, je l'ai écrit entièrement à la main. Il a fallu - excusez - moi, il était presque il y a 10 ans, donc je ne me souviens pas exactement - environ 1000 lignes en C .

La raison pour laquelle j'ai écrit le lexer à la main était la grammaire de saisie de l'analyseur. C'était une exigence, quelque chose que mon implémentation de l'analyseur devait respecter, par opposition à quelque chose que j'avais conçu. (Bien sûr, je l'aurais conçu différemment. Et mieux!) La grammaire était fortement dépendante du contexte et même duxisme dépendait de la sémantique à certains endroits. Par exemple, un point-virgule pourrait faire partie d'un jeton à un endroit, mais d'un séparateur à un endroit différent - basé sur une interprétation sémantique de certains éléments analysés auparavant. J'ai donc "enterré" de telles dépendances sémantiques dans le lexer écrit à la main, ce qui m'a laissé un BNF assez simple, facile à implémenter dans yacc.

ADDED en réponse à Macneil : yacc fournit une abstraction très puissante qui permet au programmeur de penser en termes de terminaux, de non-terminaux, de productions et de choses du genre. En outre, lors de la mise en œuvre de la yylex()fonction, cela m'a aidé à me concentrer sur le renvoi du jeton actuel et à ne pas m'inquiéter de ce qui se passait avant ou après. Le programmeur C ++ a travaillé au niveau des caractères, sans l'avantage d'une telle abstraction, et a fini par créer un algorithme plus complexe et moins efficace. Nous avons conclu que la vitesse plus lente n'avait rien à voir avec C ++ ni avec aucune bibliothèque. Nous avons mesuré la vitesse d’analyse pure avec des fichiers chargés en mémoire; si nous avions un problème de mise en mémoire tampon de fichiers, yacc ne serait pas notre outil de choix pour le résoudre.

VOULEZ ÉGALEMENT AJOUTER : ce n’est pas une recette pour écrire des analyseurs en général, mais un exemple de la façon dont cela a fonctionné dans une situation donnée.

Cela dépend entièrement de ce que vous devez analyser. Pouvez-vous rouler vous-même plus vite que vous ne pourriez atteindre la courbe d'apprentissage d'un lexer? Le contenu à analyser est-il suffisamment statique pour que vous ne regrettiez pas la décision plus tard? Trouvez-vous les implémentations existantes trop complexes? Si c'est le cas, amusez-vous à rouler vous-même, mais seulement si vous ne perdez pas une courbe d'apprentissage.

Dernièrement, je me suis mis à aimer vraiment l’ analyseur de citron , qui est sans doute le plus simple et le plus simple que j’ai jamais utilisé. Afin de rendre les choses faciles à entretenir, je l’utilise seulement pour la plupart des besoins. SQLite l'utilise aussi bien que d'autres projets notables.

Mais, je ne suis pas du tout intéressé par les lexers, à part cela, ils ne me gênent pas quand j'ai besoin d'en utiliser un (d'où le citron). Vous pourriez être, et si oui, pourquoi ne pas en faire un? J'ai le sentiment que vous reviendrez en utiliser un qui existe, mais grattez-le si vous devez :)

Cela dépend de votre objectif.

Êtes-vous en train d'essayer d'apprendre comment fonctionnent les analyseurs syntaxiques / compilateurs? Puis écrivez votre propre à partir de zéro. C’est la seule façon pour vous d’apprendre à apprécier tous les tenants et les aboutissants de ce qu’ils font. J'en ai écrit un au cours des deux derniers mois, et ce fut une expérience intéressante et précieuse, en particulier les moments «ah, alors c'est pour ça que la langue X fait ça…».

Avez-vous besoin de mettre quelque chose en place rapidement pour une application dans les délais? Ensuite, utilisez peut-être un outil d'analyse.

Avez-vous besoin de quelque chose que vous voudrez développer au cours des 10, 20, voire 30 prochaines années? Ecrivez le vôtre et prenez votre temps. Ça en vaudra la peine.

Avez-vous envisagé une approche de l'atelier de travail linguistique de Martin Fowlers ? Citation de l'article

Le changement le plus évident apporté par un workbench de langage à l'équation est la facilité de création de DSL externes. Vous n'avez plus besoin d'écrire un analyseur. Vous devez définir une syntaxe abstraite, mais il s’agit en fait d’une étape assez simple de modélisation des données. De plus, votre DSL reçoit un IDE puissant, même si vous devez passer un certain temps à définir cet éditeur. Le générateur est toujours quelque chose que vous devez faire, et j’ai le sentiment que ce n’est pas plus simple que jamais. Mais la construction d’un générateur pour une bonne et simple DSL est l’une des parties les plus faciles de l’exercice.

En lisant cela, je dirais que l'écriture de votre propre analyseur est terminée et qu'il est préférable d'utiliser l'une des bibliothèques disponibles. Une fois que vous avez maîtrisé la bibliothèque, toutes les DSL que vous créerez à l'avenir bénéficient de ces connaissances. En outre, les autres n'ont pas à apprendre votre approche de l'analyse syntaxique.

Modifier pour couvrir le commentaire (et la question révisée)

Avantages de rouler soi-même

1. Vous serez propriétaire de l'analyseur et obtiendrez toute cette belle expérience de réflexion à travers une série de problèmes complexes
2. Vous pouvez trouver quelque chose de spécial auquel personne n'a pensé (peu probable, mais vous semblez être un type intelligent)
3. Ça vous occupera d'un problème intéressant

En bref, vous devriez vous lancer vous-même lorsque vous voulez vraiment vous plonger dans les entrailles d'un problème vraiment difficile que vous vous sentez fortement motivé à maîtriser.

Avantages d'utiliser la bibliothèque de quelqu'un d'autre

1. Vous éviterez de réinventer la roue (un problème courant en programmation que vous accepterez)
2. Vous pouvez vous concentrer sur le résultat final (votre nouvelle langue brillante) et ne pas trop vous soucier de la façon dont il est analysé, etc.
3. Vous verrez votre langue en action beaucoup plus rapidement (mais votre récompense sera moins, car ce n'était pas tout vous)

Par conséquent, si vous voulez un résultat final rapide, utilisez la bibliothèque de quelqu'un d'autre.

Globalement, cela revient à choisir dans quelle mesure vous voulez posséder le problème, et donc la solution. Si vous voulez tout, lancez le vôtre.

Le gros avantage de l’écriture de la vôtre est que vous saurez écrire la vôtre. Le gros avantage d'utiliser un outil comme yacc est que vous saurez utiliser cet outil. Je suis fan de cime des arbres pour l'exploration initiale.

Pourquoi ne pas créer un générateur d’analyseur open-source et le personnaliser? Si vous n'utilisez pas de générateurs d'analyseurs, votre code sera très difficile à gérer, si vous faites de gros changements dans la syntaxe de votre langue.

Dans mes analyseurs syntaxiques, j'ai utilisé des expressions régulières (je veux dire, du style Perl) pour segmenter et utiliser certaines fonctions pratiques pour améliorer la lisibilité du code. Cependant, un code généré par un analyseur peut être plus rapide en créant des tables d’état et des long switch- cases, ce qui peut augmenter la taille du code source à moins que vous ne les .gitignoreutilisiez.

Voici deux exemples de mes analyseurs syntaxiques personnalisés:

https://github.com/SHiNKiROU/DesignScript - un dialecte BASIC, parce que j'étais trop paresseux pour écrire des expressions anormales en notation tableau, j'ai sacrifié la qualité des messages d'erreur https://github.com/SHiNKiROU/ExprParser - Un calculateur de formule. Remarquez les étranges astuces de métaprogrammation

"Dois-je utiliser cette roue éprouvée ou la réinventer?"