Quand utiliser un analyseur syntaxique? Quand utiliser un générateur d'analyseur?

Je me suis plongé récemment dans le monde des analyseurs syntaxiques pour créer mon propre langage de programmation.

Cependant, j’ai découvert qu’il existe deux approches quelque peu différentes d’écriture d’analyseurs: les générateurs d’analyseurs et les combinateurs d’analyseurs.

Fait intéressant, je n’ai trouvé aucune ressource qui explique dans quels cas quelle approche est la meilleure; Au contraire, de nombreuses ressources (et personnes) j'interrogés sur le sujet ne connaissait pas l'autre approche, expliquant que leur approche que l' approche et de ne pas mentionner l'autre du tout:

• Le célèbre livre de Dragon aborde le lexing / scanning et mentionne (f) lex, mais ne mentionne pas du tout les Combinators de Parser.
• Les modèles d'implémentation de langage reposent largement sur le générateur d'analyseur syntaxique ANTLR construit en Java et ne mentionnent pas du tout les combinateurs d'analyseurs.
• Le didacticiel Introduction à Parsec sur Parsec, qui est un combinateur d’analyseurs dans Haskell, ne mentionne pas du tout les générateurs d’analyseurs.
• Boost :: spirit , le plus célèbre combinateur d'analyseurs syntaxiques C ++, ne mentionne pas du tout les générateurs d'analyseurs syntaxiques.
• L'excellent article de blog explicatif que vous auriez pu inventer. Parser Combinators ne mentionne pas du tout les générateurs de parser.

Vue d'ensemble simple:

Générateur d'analyseur

Un générateur d' analyseur syntaxique prend un fichier écrit dans un DSL qui est un dialecte de la forme Extended Backus-Naur et le transforme en code source qui peut ensuite (une fois compilé) devenir un analyseur syntaxique pour le langage d'entrée décrit dans ce DSL.

Cela signifie que le processus de compilation est effectué en deux étapes distinctes. Fait intéressant, les générateurs d’analyseurs eux-mêmes sont également des compilateurs (et beaucoup d’entre eux sont en fait auto-hébergés ).

Combinateur Analyseur

Un analyseur syntaxique décrit des fonctions simples, appelées analyseurs syntaxiques, qui prennent toutes une entrée en tant que paramètre et essaient d’extraire le (s) premier (s) caractère (s) de cette entrée s’ils correspondent. Ils renvoient un tuple (result, rest_of_input), où resultpeut être vide (par exemple nilou Nothing) si l'analyseur n'a pas pu analyser quoi que ce soit à partir de cette entrée. Un exemple serait un digitanalyseur. D'autres analyseurs peuvent bien sûr prendre des analyseurs en tant que premiers arguments (l'argument final restant la chaîne d'entrée) pour les combiner : par exemple, many1tentatives de correspondance avec un autre analyseur autant de fois que possible (mais au moins une fois, ou elle échoue elle-même).

Vous pouvez maintenant bien sûr combiner (composer) digitet many1, pour créer un nouvel analyseur, par exemple integer.

En outre, il choiceest possible d’écrire un analyseur syntaxique de niveau supérieur qui prend une liste d’analyseurs, en essayant chacun d’entre eux.

De cette manière, des lexeurs / analyseurs syntaxiques très complexes peuvent être construits. Dans les langues prenant en charge la surcharge d'opérateurs, cela ressemble beaucoup à EBNF, même s'il est toujours écrit directement dans la langue cible (et que vous pouvez utiliser toutes les fonctionnalités de la langue cible de votre choix).

Différences simples

La langue:

• Les générateurs d’analyseurs sont écrits dans une combinaison de la ADSL EBNF et du code que ces instructions doivent générer lorsqu’elles correspondent.
• Les combinateurs d’analyseurs sont écrits directement dans la langue cible.

Lexing / Parsing:

• Les générateurs d’analyseurs ont une différence très nette entre le "lexer" (qui divise une chaîne en jetons pouvant être étiquetés pour indiquer le type de valeur que nous traitons) et le "analyseur" (qui prend la liste de sortie des jetons du lexer). et tente de les combiner, formant un arbre de syntaxe abstraite).
• Les combinateurs d’analyseurs n’ont pas / n’ont pas besoin de cette distinction; habituellement, de simples analyseurs effectuent le travail du "lexer" et les analyseurs syntaxiques de niveau supérieur appellent ces analyseurs plus simples pour décider du type de nœud AST à créer.

Question

Cependant, même compte tenu de ces différences (et cette liste de différences est probablement loin d'être complète!), Je ne peux pas faire un choix éclairé quant à savoir quand utiliser laquelle. Je ne vois pas quelles sont les implications / conséquences de ces différences.

Quelles propriétés de problème indiqueraient qu'un problème serait mieux résolu à l'aide d'un générateur d'analyseur syntaxique? Quelles propriétés de problème indiqueraient qu'un problème serait mieux résolu à l'aide d'un analyseur syntaxique?

J'ai fait beaucoup de recherches ces derniers jours pour mieux comprendre pourquoi ces technologies distinctes existent et quels sont leurs points forts et leurs points faibles.

Certaines des réponses déjà existantes faisaient allusion à certaines de leurs différences, mais elles ne donnaient pas une image complète et semblaient avoir une certaine opinion, c'est pourquoi cette réponse a été écrite.

Cette exposition est longue mais importante. supporter avec moi (ou si vous êtes impatient, faites défiler jusqu'à la fin pour voir un organigramme).

Pour comprendre les différences entre les combinateurs d’analyseurs et les générateurs d’analyseurs, il faut d’abord comprendre la différence entre les divers types d’analyses qui existent.

L'analyse

L'analyse syntaxique est le processus d'analyse d'une chaîne de symboles selon une grammaire formelle. (Dans l'informatique,) l'analyse est utilisée pour permettre à un ordinateur de comprendre un texte écrit dans un langage, créant généralement un arbre d'analyse représentant le texte écrit, stockant la signification des différentes parties écrites dans chaque nœud de l'arbre. Cet arbre d'analyse peut ensuite être utilisé à diverses fins, telles que le traduire dans un autre langage (utilisé par de nombreux compilateurs), interpréter directement les instructions écrites (SQL, HTML), permettant ainsi à des outils tels que Linters de fonctionner. , etc. Parfois, un arbre d'analyse n'est pas explicitementgénéré, mais plutôt l'action à exécuter sur chaque type de nœud de l'arborescence est exécutée directement. Cela augmente l'efficacité, mais il existe encore sous l'eau un arbre d'analyse implicite.

L'analyse syntaxique est un problème de calcul difficile. Il y a plus de cinquante ans de recherche sur ce sujet, mais il reste encore beaucoup à apprendre.

Grosso modo, il existe quatre algorithmes généraux permettant à un ordinateur d’analyser une entrée:

• LL analyse. (Analyse sans contexte, top-down.)
• Analyse syntaxique LR. (Analyse sans contexte et de bas en haut.)
• Analyse PEG + Packrat.
• Earley Parsing.

Notez que ces types d'analyse sont des descriptions très générales et théoriques. Il existe de nombreuses manières d'implémenter chacun de ces algorithmes sur des machines physiques, avec des compromis différents.

LL et LR ne peuvent examiner que les grammaires sans contexte (autrement dit, le contexte autour des jetons écrits n'est pas important pour comprendre comment ils sont utilisés).

L'analyse PEG / Packrat et l'analyse Earley sont beaucoup moins utilisées: l'analyse Earley est agréable en ce sens qu'elle peut gérer beaucoup plus de grammaires (y compris celles qui ne sont pas nécessairement sans contexte) mais moins efficace (comme le prétend le dragon livre (section 4.1.1); je ne sais pas si ces affirmations sont toujours exactes). Parsing Expression Grammar + Packrat-parsing est une méthode relativement efficace qui peut également traiter plus de grammaires que LL et LR, mais cache des ambiguïtés, comme nous le verrons rapidement ci-dessous.

LL (dérivation de gauche à droite, la plus à gauche)

C'est peut-être la manière la plus naturelle de penser à l'analyse syntaxique. L'idée est d'examiner le prochain jeton dans la chaîne d'entrée, puis de décider lequel des multiples appels récursifs possibles peut être pris pour générer une structure arborescente.

Cet arbre est construit «de haut en bas», ce qui signifie que nous commençons à la racine de l’arbre et parcourons les règles de grammaire de la même manière que nous parcourons la chaîne de saisie. Cela peut également être vu comme construisant un équivalent "postfix" pour le flux de jetons "infix" en cours de lecture.

Les analyseurs effectuant une analyse de style LL peuvent être écrits de manière à ressembler beaucoup à la grammaire originale spécifiée. Cela le rend relativement facile à comprendre, à déboguer et à améliorer. Les combinateurs d’analyseurs classiques ne sont rien d’autre que des «pièces de lego» qui peuvent être assemblées pour créer un analyseur de style LL.

LR (dérivation de gauche à droite, extrême droite)

L'analyse syntaxique de gauche se fait dans l'autre sens, de bas en haut: à chaque étape, le ou les éléments supérieurs de la pile sont comparés à la liste de grammaire afin de voir s'ils pourraient être réduits à une règle de niveau supérieur dans la grammaire. Sinon, le prochain jeton du flux d'entrée est décalé et placé au-dessus de la pile.

Un programme est correct si à la fin nous nous retrouvons avec un seul nœud sur la pile qui représente la règle de départ de notre grammaire.

Lookahead

Dans l'un ou l'autre de ces deux systèmes, il est parfois nécessaire de jeter un coup d'œil supplémentaire sur les jetons avant de pouvoir décider du choix à faire. C'est (0), (1), (k)ou (*)-syntax vous voyez après les noms de ces deux algorithmes généraux, tels que LR(1) ou LL(k). ksignifie généralement «autant que votre grammaire a besoin», tandis que *signifie habituellement «cet analyseur effectue un retour en arrière», qui est plus puissant / facile à mettre en œuvre, mais utilise beaucoup plus de temps et de mémoire qu'un analyseur capable de continuer à analyser linéairement.

Notez que les analyseurs syntaxiques de style LR ont déjà beaucoup de jetons sur la pile lorsqu'ils peuvent décider de «regarder en avant», ils ont donc déjà plus d'informations à envoyer. Cela signifie qu'ils ont souvent besoin de moins de "look -ead" qu'un analyseur de style LL pour la même grammaire.

LL vs. LR: Ambiguité

En lisant les deux descriptions ci-dessus, on peut se demander pourquoi l'analyse syntaxique de type LR existe, car l'analyse syntaxique de style LL semble beaucoup plus naturelle.

Cependant, l'analyse de style LL a un problème: Récursion à gauche .

C'est très naturel d'écrire une grammaire comme:

expr ::= expr '+' expr | term
term ::= integer | float

Toutefois, un analyseur de style LL reste bloqué dans une boucle récursive infinie lors de l'analyse syntaxique de cette grammaire: lors de l'essai de la possibilité la plus à gauche de la exprrègle, il y revient à nouveau sans consommer aucune entrée.

Il existe des moyens de résoudre ce problème. Le plus simple est de réécrire votre grammaire pour que ce type de récursion ne se produise plus:

expr ::= term expr_rest
expr_rest ::= '+' expr | ϵ
term ::= integer | float

(Ici, ε représente le «chaîne vide)

Cette grammaire est maintenant récursive. Notez qu'il est immédiatement beaucoup plus difficile à lire.

En pratique, la récursion à gauche peut se produire indirectement avec de nombreuses autres étapes intermédiaires. Cela rend le problème difficile à surveiller. Mais essayer de le résoudre rend votre grammaire plus difficile à lire.

Comme l'indique la section 2.5 du livre du dragon:

Nous semblons avoir un conflit: d’une part, nous avons besoin d’une grammaire facilitant la traduction, d’autre part, d’une grammaire très différente, facilitant l’analyse syntaxique. La solution consiste à commencer par la grammaire pour une traduction facile et à la transformer avec soin pour faciliter l'analyse. En éliminant la récursion gauche, nous pouvons obtenir une grammaire adaptée à un traducteur prédictif à descente récursive.

Les analyseurs syntaxiques de type LR n'ont pas le problème de cette récursion à gauche, car ils construisent l'arbre à partir de la base. Cependant , la traduction mentale d'une grammaire comme ci-dessus en un analyseur syntaxique de type LR (souvent implémenté en tant qu'automate à états finis )
est très difficile (et source d'erreurs), car il existe souvent des centaines, voire des milliers, d'états + transitions d'état à considérer. C'est pourquoi les analyseurs syntaxiques de type LR sont généralement générés par un générateur d' analyseurs syntaxiques , également appelé «compilateur compilateur».

Comment résoudre les ambiguïtés

Nous avons vu ci-dessus deux méthodes pour résoudre les ambiguïtés de la récursivité gauche: 1) réécrire la syntaxe 2) utiliser un analyseur LR.

Mais il existe d'autres types d'ambiguïtés qui sont plus difficiles à résoudre: que se passera-t-il si deux règles différentes s'appliquent également au même moment?

Quelques exemples courants sont:

• expressions arithmétiques.
• le balançant Else

Les analyseurs syntaxiques de style LL et de style LR ont des problèmes avec ceux-ci. Les problèmes d’analyse d’expressions arithmétiques peuvent être résolus en introduisant la priorité des opérateurs. De la même manière, d’autres problèmes, tels que Dangling Else, peuvent être résolus en choisissant un comportement de priorité et en s’y tenant. (En C / C ++, par exemple, le balancé appartient toujours au plus proche 'if').

Une autre "solution" consiste à utiliser la syntaxe PEG (Parser Expression Grammar): elle est similaire à la grammaire BNF utilisée ci-dessus, mais dans le cas d'une ambiguïté, choisissez toujours "le premier". Bien sûr, cela ne "résout" pas vraiment le problème, mais cache plutôt qu'une ambiguïté existe réellement: les utilisateurs finaux peuvent ne pas savoir quel choix l'analyseur fait, ce qui peut conduire à des résultats inattendus.

Plus d'informations qui sont beaucoup plus détaillées que ce billet, y compris pourquoi il est impossible en général de savoir si votre grammaire ne présente aucune ambiguïté et les implications de ceci sont les merveilleux articles de blog LL et LR dans leur contexte: Pourquoi analyser les outils sont difficiles . Je peux le recommander fortement. cela m'a beaucoup aidé à comprendre tout ce dont je parle en ce moment.

50 ans de recherche

Mais la vie continue. Il s'est avéré que les analyseurs syntaxiques «normaux» de type LR mis en œuvre en tant qu'automates à états finis nécessitaient souvent des milliers d'états + transitions, ce qui posait un problème de taille de programme. Ainsi, des variantes telles que Simple LR (SLR) et LALR (Look-ahead LR) ont été écrites et combinent d'autres techniques pour réduire la taille de l'automate, réduisant ainsi l'encombrement des disques et de la mémoire des programmes d'analyse.

Une autre façon de résoudre les ambiguïtés énumérées ci-dessus consiste à utiliser des techniques généralisées dans lesquelles, en cas d'ambiguïté, les deux possibilités sont conservées et analysées: l'une ou l'autre risque de ne pas être analysée ultérieurement (auquel 'correct'), ainsi que de renvoyer les deux (et de montrer ainsi qu’une ambiguïté existe) dans le cas où ils sont corrects.

Il est intéressant de noter qu'après la description de l' algorithme LR généralisé , il s'est avéré qu'une approche similaire pourrait être utilisée pour implémenter des analyseurs syntaxiques LL généralisés , qui est tout aussi rapide ($ O (n ^ 3) complexité complexe en temps pour les grammaires ambiguës, $ O (n) $ pour des grammaires complètement dépourvues d'ambiguïté, même si elles nécessitent plus de comptabilité qu'un simple analyseur syntaxique (LA), ce qui signifie un facteur constant plus élevé), tout en permettant à un analyseur d'être écrit dans un style de descente récursif (de haut en bas) beaucoup plus naturel écrire et déboguer.

Combinateurs d'analyseurs, générateurs d'analyseurs

Donc, avec cette longue exposition, nous arrivons maintenant au cœur de la question:

Quelle est la différence entre les combinateurs et les générateurs d'analyseurs, et quand faut-il en utiliser un par rapport à l'autre?

Ce sont vraiment différentes sortes de bêtes:

Les analyseurs syntaxiques ont été créés parce que les gens écrivaient des analyseurs syntaxiques de haut en bas et ont réalisé que beaucoup d’entre eux avaient beaucoup en commun .

Des générateurs d’analyseurs ont été créés parce que les gens cherchaient à créer des analyseurs n’ayant pas les mêmes problèmes que ceux des analyseurs de style LL (c.-à-d. Des analyseurs de style LR), ce qui s’est avéré très difficile à effectuer manuellement. Les plus courantes incluent Yacc / Bison, qui implémente (LA) LR).

Fait intéressant, de nos jours, le paysage est un peu confus:

• Il est possible d’écrire des combinateurs d’analyseurs fonctionnant avec l’ algorithme GLL , en résolvant les problèmes d’ambiguïté que rencontraient les analyseurs classiques de style LL, tout en restant aussi lisibles / compréhensibles que tous les types d’analyses descendantes.

• Des générateurs d’analyseur peuvent également être écrits pour des analyseurs de style LL. ANTLR fait exactement cela et utilise d'autres méthodes heuristiques (Adaptive LL (*)) pour résoudre les ambiguïtés des analyseurs classiques de style LL.

En général, il est difficile de créer un générateur d'analyse syntaxique LR et de déboguer la sortie d'un générateur d'analyseur syntaxique (LA) de style (LR) s'exécutant sur votre grammaire, en raison de la traduction de votre grammaire d'origine vers la forme LR «à l'envers». D'autre part, des outils tels que Yacc / Bison ont connu de nombreuses années d'optimisation et ont été utilisés à grande échelle, ce qui signifie que de nombreuses personnes le considèrent désormais comme un moyen d'analyse et sont sceptiques à l'égard de nouvelles approches.

Celui que vous devriez utiliser dépend de la dureté de votre grammaire et de la rapidité avec laquelle l'analyseur doit être. Selon la grammaire, l’une de ces techniques (/ les implémentations des différentes techniques) peuvent être plus rapides, avoir une empreinte mémoire plus petite, un empreinte disque plus petite, ou être plus extensibles ou plus faciles à déboguer que les autres. Votre kilométrage peut varier .

Note latérale: À propos de l'analyse lexicale.

L'analyse lexicale peut être utilisée à la fois pour les combinateurs d'analyseurs et les générateurs d'analyseurs. L’idée est de disposer d’un analyseur syntaxique «muet» très facile à implémenter (et donc rapide) qui effectue une première passe sur votre code source, en supprimant par exemple les espaces blancs répétés, les commentaires, etc., et éventuellement manière grossière les différents éléments qui composent votre langue.

Le principal avantage est que cette première étape simplifie beaucoup le véritable analyseur (et peut-être même plus rapidement). Le principal inconvénient est que vous avez une étape de traduction séparée et que, par exemple, le rapport d'erreur avec les numéros de ligne et de colonne devient plus difficile en raison de la suppression des espaces.

En fin de compte, un lexer n'est «qu'un» autre analyseur et peut être mis en œuvre en utilisant l'une des techniques ci-dessus. En raison de sa simplicité, d’autres techniques que celles utilisées pour l’analyseur principal sont souvent utilisées. Il existe par exemple des «générateurs de lexer» supplémentaires.

Tl; Dr:

Voici un organigramme qui s'applique à la plupart des cas:

Pour les entrées dont il est garanti qu'elles sont exemptes d'erreurs de syntaxe, ou dans lesquelles un accord correct sur la correction syntaxique est correct, les combinateurs d'analyseurs sont beaucoup plus simples à utiliser, en particulier dans les langages de programmation fonctionnels. Ce sont des situations comme programmer des énigmes, lire des fichiers de données, etc.

La fonctionnalité qui vous incite à ajouter la complexité des générateurs d’analyseur est le message d’erreur. Vous voulez des messages d'erreur qui pointent l'utilisateur vers une ligne et une colonne et qui, espérons-le, sont également compréhensibles par un humain. Il faut beaucoup de code pour le faire correctement, et les meilleurs générateurs d’analyseurs comme antlr peuvent vous aider.

Cependant, la génération automatique ne peut vous mener jusque-là, et la plupart des compilateurs open source commerciaux et de longue durée finissent par écrire manuellement leurs parseurs. Je présume que si vous vous sentiez à l'aise avec cela, vous n'auriez pas posé cette question. Je vous recommande donc d'utiliser le générateur d'analyseur syntaxique.

Sam Harwell, l'un des responsables du générateur d'analyseur syntaxique ANTLR, a récemment écrit :

J'ai trouvé que les [combinateurs] ne répondent pas à mes besoins:

1. ANTLR me fournit des outils pour gérer des choses telles que les ambiguïtés. Au cours du développement, certains outils peuvent afficher des résultats d'analyse ambigus afin d'éliminer les ambiguïtés de la grammaire. Au moment de l'exécution, je peux exploiter l'ambiguïté résultant d'une saisie incomplète dans l'EDI pour produire des résultats plus précis dans des fonctionnalités telles que la complétion de code.
2. Dans la pratique, j’ai constaté que les combinateurs d’analyseurs ne convenaient pas à mes objectifs de performance. Une partie de cela remonte
3. Lorsque les résultats d'analyse sont utilisés pour des fonctionnalités telles que les contours, la complétion de code et l'indentation intelligente, il est facile pour de subtiles modifications de la grammaire d'affecter la précision de ces résultats. ANTLR fournit des outils qui peuvent transformer ces incompatibilités en erreurs de compilation, même dans les cas où les types seraient compilés. Je peux créer avec confiance un prototype de nouvelle fonctionnalité linguistique qui affecte la grammaire, sachant que tout le code supplémentaire constituant l'EDI offrira une expérience complète de la nouvelle fonctionnalité dès le début. Mon fork d'ANTLR 4 (sur lequel la cible C # est basée) est le seul outil que je connaisse qui tente même de fournir cette fonctionnalité.

Essentiellement, les combinateurs d’analyseurs sont un jouet amusant, mais ils ne sont tout simplement pas faits pour un travail sérieux.

Comme le mentionne Karl, les générateurs d’analyseurs ont tendance à avoir un meilleur rapport d’erreurs. En outre:

• ils ont tendance à être plus rapides, car le code généré peut être spécialisé pour la syntaxe et générer des tables de saut pour le lookahead.
• ils ont tendance à avoir un meilleur outillage, à identifier la syntaxe ambiguë, à supprimer la récursion gauche, à renseigner les branches d'erreur, etc.
• ils ont tendance à mieux gérer les définitions récursives.
• ils ont tendance à être plus robustes, car les groupes électrogènes durent plus longtemps et font davantage le tour de chauffe pour vous, réduisant ainsi le risque de le perdre.

En revanche, les combinateurs ont leurs propres avantages:

• ils sont dans le code. Par conséquent, si votre syntaxe varie au moment de l'exécution, vous pouvez plus facilement transformer des éléments.
• ils ont tendance à être plus faciles à lier et à consommer (la sortie des générateurs d’analyseur a tendance à être très générique et difficile à utiliser).
• ils sont en code, ils ont donc tendance à être un peu plus faciles à déboguer lorsque votre grammaire ne répond pas à vos attentes.
• ils ont tendance à avoir une courbe d'apprentissage moins profonde puisqu'ils fonctionnent comme n'importe quel autre code. Les générateurs d’analyseurs ont tendance à avoir leurs propres bizarreries pour apprendre à faire fonctionner les choses.