ps.where à lire sur la théorie de l'analyse?
11 Réponses :
C'est toujours une bonne idée de lire le Dragon Book . Mais soyez conscient que si votre langue n'est pas triviale, il n'y a pas vraiment de «court» moyen de le faire.
Cela dépend plutôt de votre langue. Certaines langues très simples prennent très peu l'analyse afin que le codé à la main; d'autres langues utilisent des générateurs de cheville tels que rats! (PEG est la grammaire d'expression d'analyse, qui se trouve entre une regex et un analyseur LR) ou des générateurs d'analyseurs conventionnels tels que AntLR et YACC. Les langues moins formelles nécessitent des techniques probabilistes telles que link grammaires .
J'ai utilisé le Système d'analyse d'or , car il semblait plus facile à utiliser que d'AntLR pour un novice Comme moi, tout en étant toujours pleinement compatible pour mes besoins. Le site Web comprend Documentation (y compris les instructions sur Écriture grammaires , qui est la moitié du travail) ainsi que Logiciel .
Essayez Bison pour analyse et Flex pour lexing
La définition de bison de votre langue se trouve sous la forme d'un grammaire sans contexte . Le Wikipedia ArtCile sur ce sujet est assez bon et est probablement un bon endroit pour commencer.
écrire un Parser de descente récursif . C'est parfois plus facile que YACC / BISON, et généralement plus intuitif.
Son tentant d'aller au livre de dragon pour en savoir plus sur la théorie de l'analyse. Mais je ne pense pas que le livre de dragon et vous avez la même idée de ce que "théorie" signifie. Le livre de dragon explique comment construire des analyseurs à la main, des générateurs d'analyseurs, etc., mais vous souhaitez presque certainement utiliser un outil d'analyse d'analyse à la place.
Quelques personnes ont suggéré de bison et de flex (ou de leurs anciennes versions YACC et Lex).
Ce sont les vieux stalwarts, mais ce ne sont pas des outils très utilisables.
Leur documentation n'est pas médiocre en soi, c'est juste qu'il n'aidera pas tout à fait de traiter avec le Complexité accidentelle de les utiliser.
Leurs données internes ne sont pas bien encapsulées et il est très difficile de faire quelque chose d'avancé avec eux. Par exemple, dans Phc , nous n'avons toujours pas de numéros de ligne corrects car c'est très difficile. Ils se sont améliorés lorsque nous avons modifié la grammaire pour inclure des déclarations no-op, mais c'est un incroyable piratage qui ne devrait pas être nécessaire.
Ostensiblement, Bison et Flex Travailler ensemble, mais l'interface est gênante. Pire, il existe de nombreuses versions de chacun, qui ne jouent que bien avec quelques versions spécifiques de l'autre. Et, au moins j'ai vérifié au moins, la documentation dont les versions sont allées assez pauvres.
Écrire un analyseur de descente récursif est simple, mais peut être fastidieux. Antlr peut faire cela pour vous et il semble être un joli bon outil, avec l'avantage que ce que vous apprenez sur ce projet peut être appliqué sur de nombreuses autres langues et plates-formes (AntLR est très portable). Il y a aussi beaucoup de grammaires existantes à apprendre de.
Ce n'est pas clair de quelle langue vous travaillez, mais certaines langues ont d'excellents cadres d'analyse. En particulier, le Haskell Parsec Library semble très élégant. Si vous utilisez C ++, vous serez peut-être tenté d'utiliser esprit . J'ai trouvé très facile de commencer, et difficile - mais toujours possible - faire des choses avancées avec elle. Cela correspond à mon expérience de C ++ en général. Je dis que je l'ai trouvé facile de commencer, mais j'avais déjà écrit quelques analyseurs et j'ai étudié l'analyse de la classe de compilateur.
histoire longue courte: antlr, sauf si vous avez une très bonne raison.
Je ne suis pas d'accord avec toi. Bison et Flex ont une bonne documentation.
@Kinopiko: assez juste. Je suppose que ce n'est pas exactement ce que je voulais dire. J'espère que c'est mieux / plus juste maintenant.
L'utilisation d'un générateur d'analyseurs pour votre langage hôte est le moyen le plus rapide, associé à une théorie d'analyse d'un livre tel que le Dragon Book ou la construction moderne de compilateur en {C, ML} Series.
Si vous utilisez C, Mon préféré personnel à l'heure actuelle est menhir , un excellent générateur d'analyseurs pour OCAML. Les langues de style ML (OCAML, ML standard, etc.) Les dialectes en général sont très bons pour la construction de compilateurs et d'interprètes. YACC et la version GNU bison sont les générateurs standard. AntLR est largement utilisé dans de nombreuses langues, soutenant Java, C # et C ++ autant que je sache. Il y a aussi beaucoup d'autres dans presque toutes les langues.
Antlr est le plus facile pour quelqu'un sans formation théorique du compilateur à cause de:
AntlRworks (analyse visuelle et ast Débogage)
Le livre AntlR (aucune base théorie du compilateur requise)
juste 1 syntaxe pour lexer and parser.
Si vous êtes satisfait de analyse des grammaires d'expression , écrire vos propres analyseurs peut être incroyablement court . Voici un simple analyseur de packrat qui prend un sous-ensemble raisonnable de PEG:
python3 parser.py '1+2'
('expr',
[('term',
[('fact',
[('digits', [('digit', [('1', [])])])])]),
('add_op', [('+', [])]),
('expr',
[('term', [('fact', [('digits', [('digit', [('2', [])])])])])])])