En savoir plus sur l'analyse

Question

Je programme depuis 1999 pour le travail et l’amusement. Je veux apprendre de nouvelles choses. Récemment, je me suis concentré sur l'analyse syntaxique, car une grande partie de mon travail consiste à lire, à intégrer et à analyser des données. J'ai également un grand nombre de tâches répétitives que je pense pouvoir exprimer dans des langages très simples spécifiques à un domaine si le temps système était suffisamment bas. J'ai quelques questions sur le sujet.

1. La plupart de mes codes d'analyse actuels ne définissent pas une grammaire formelle. Habituellement, je pirate quelque chose dans la langue de mon choix parce que c'est facile, je sais le faire et je peux écrire ce code très rapidement. Il est également facile à entretenir pour les autres personnes avec qui je travaille. Quels sont les avantages et les inconvénients de la définition d’une grammaire et de la génération d’un véritable analyseur (comme avec ANTLR ou YACC ) pour analyser les choses par rapport aux hacks que la plupart des programmeurs utilisaient pour écrire des analyseurs syntaxiques?
2. Quels sont les meilleurs outils de génération d’analyseurs pour écrire des analyseurs syntaxiques basés sur la grammaire en C ++, Perl et Ruby? J'ai consulté ANTLR et je n'ai pas trouvé grand chose à propos de l'utilisation de ANTLRv3 avec une cible C ++, mais sinon cela semble intéressant. Quels sont les autres outils similaires à ANTLR que je devrais lire?
3. Quels sont les livres et les articles canoniques qu’une personne qui souhaite en savoir plus sur l’analyse syntaxique? Un cours sur les compilateurs ne faisait malheureusement pas partie de mon éducation, donc le matériel de base est le bienvenu. J'ai entendu de très bonnes choses sur le Dragon Book , mais qu'est-ce qu'il y a d'autre?

Answer 1

Sur 1., je dirais que le principal avantage est la maintenabilité - apporter un petit changement à la langue signifie simplement apporter un changement correspondant à la grammaire en conséquence, plutôt que de fouiller minutieusement les différentes Les points du code qui peuvent avoir quelque chose à voir avec ce que vous voulez changer sont ... des ordres de grandeur plus productifs et moins de risques de bugs.

Les 2. et 3., je ne peux pas suggérer beaucoup plus que ce que vous avez déjà trouvé (j’utilise principalement Python et pyparsing, et pourrais commenter par expérience sur de nombreux frameworks d’analyse centrés sur Python, mais pour C ++, j’utilise principalement bon vieux yacc ou bison de toute façon, et ma vieille copie noueuse du Livre du Dragon - et non la dernière édition, en fait - est tout ce que je garde à mes côtés à cette fin ...).

Answer 2

Voici mon opinion sur vos (très bonnes) questions:

1. Je pense qu'un analyseur syntaxique tire le meilleur parti de situations non triviales dans lesquelles une grammaire existe réellement. Vous devez savoir comment fonctionnent les analyseurs syntaxiques et les grammaires pour penser à cette technique, et non pas tous les développeurs.
2. lex / yacc sont des outils Unix plus anciens qui pourraient vous être utiles en tant que développeur C ++. Peut-être que Bison aussi.
3. ANTRL et son livre d’accompagnement sont très bons. & "Rédaction de compilateurs et d'interprètes &"; a C ++ des exemples qui pourraient vous plaire.

Le modèle d'interprétation GoF est une autre technique permettant d'écrire & "; petites langues &"; Regardez cela.

Answer 3

Construisons un compilateur est un didacticiel pas à pas sur la rédaction d'un script simple. compilateur. Le code est écrit en Delphi (Pascal), mais il est suffisamment basique pour être traduit facilement dans la plupart des autres langues.

Answer 4

J'examinerais sérieusement l'analyse syntaxique monadique basée sur un combinateur (qui traite souvent également de l'analyse lexicale) en Haskell. J'ai trouvé cela assez révélateur; C'est incroyable de voir avec quelle facilité vous pouvez construire un analyseur syntaxique à partir de zéro en utilisant cette méthode. C’est si facile, en fait, qu’il est souvent plus rapide d’écrire votre propre analyseur que d’essayer d’utiliser les bibliothèques existantes.

L'exemple le plus célèbre est probablement Parsec qui a un bon mode d'emploi qui explique comment l'utiliser . Il existe une liste des ports de cette bibliothèque dans d'autres langues (y compris C ++ et Ruby ) répertorié dans la liste Page Parsec du wiki Haskell , bien que je ne les connaisse pas et que je ne puisse donc pas dire à quel point ils sont proches de l’utilisation de Parsec dans Haskell.

Si vous voulez savoir comment ils fonctionnent en interne et comment écrire les vôtres, je vous recommande de commencer par le chapitre 8 (& "; Analyseurs fonctionnels &") de Graham Hutton Programmation en Haskell . Une fois que vous aurez bien compris ce chapitre (qui prendra probablement plusieurs lectures), vous serez prêt.

Answer 5

En Perl, les modules Parse :: RecDescent sont le premier endroit à commencer. Ajoutez un didacticiel au nom du module et Google devrait pouvoir trouver de nombreux didacticiels pour vous aider à démarrer.

Answer 6

Définir une grammaire à l'aide de BNF, EBNF ou quelque chose de similaire, est plus facile et plus tard, vous aurez plus de temps pour la maintenir. Vous trouverez également de nombreux exemples de définitions de grammaire. Enfin et surtout, si vous voulez parler de votre grammaire à quelqu'un d'autre sur le terrain, il est préférable que vous parliez tous les deux la même langue (BNF, EBNF, etc.).

Écrire votre propre code d’analyse revient à réinventer la roue et à éviter les erreurs. C'est aussi moins maintenable. Bien sûr, il peut être plus flexible et, dans le cas de petits projets, ce pourrait également être un bon choix, mais l’utilisation d’un générateur d’analyseur existant prenant en compte la grammaire et le code généré devrait couvrir la plupart de nos besoins.

Pour C ++, je suggérerais également lex / yacc. Pour Ruby, cela semble être un choix décent: Coco / R (uby)

.

Answer 7

Moment drôle: j'ai passé beaucoup de temps ce matin à m'interroger sur les machines d'état et les analyseurs syntaxiques, et à essayer de trouver un moyen d'en apprendre davantage sur eux.

Pour 2, vous pouvez consulter Ragel (c'est bon pour C ++ et Ruby). .

Answer 8

Voici un tutoriel sur un compilateur-compilateur entièrement portable (10 pages!) qui peut être utilisé pour concevoir et mettre en œuvre " faibles frais généraux " DSLs très rapidement:

http://www.bayfronttechnologies.com/mc_tutorial.html

Ce site vous présente le document de Val Schorre de 1964 sur MetaII. Oui, 1964. Et c'est incroyable. Voici comment j'ai appris sur les compilateurs de retour en 1970.