Manière informatique de faire du texte / xml / n'importe quel type d'analyse

Question

Cela fait un certain temps que je ratille dans mon cerveau.

J'ai effectué des recherches sur Compilers / Flex / Byson, mais je n'ai jamais trouvé de bonne référence qui parle en détail de la "pile d'analyse" ou de la façon de la mettre en œuvre.

Est-ce que quelqu'un connaît de bonnes références où je pourrais rattraper mon retard?

Modifier : j'apprécie toutes les références du compilateur. Certains livres sont répertoriés, mais je m'intéresse surtout à l'analyse syntaxique elle-même et non à ce que vous en ferez après. .

Answer 1

Ceci est une réponse à la réponse de Dima que vous avez acceptée comme étant la réponse correcte. Même si ce n’est pas une mauvaise réponse de dire que l’analyse syntaxique est liée à la théorie des automates, j’ai le sentiment qu’il ya un malentendu ici.

• Premièrement, les automates à états finis ne peuvent reconnaître que les langages normaux (par exemple, les expressions régulières). Pour reconnaître les langues sans contexte, vous avez besoin de automates à pile , qui sont plus puissants. Voir http://en.wikipedia.org/wiki/Automata_theory#Classes_of_automata pour plus d'automatismes et leur relation avec différentes classes de langues.

• Deuxièmement, l'analyse est différent de la reconnaissance . Reconnaître une chaîne vous indique uniquement si cette chaîne est dans la langue générée par votre grammaire. Un analyseur syntaxique a pour objectif de produire un arbre syntaxique concret, à la fois plus dur et plus utile.

Il existe une grande variété de méthodes d'analyse, il est donc difficile de vous donner une référence spécifique qui vous dira ce que vous devez savoir ... En général, vous devriez comprendre la différence entre analyse top-down et analyse ascendante . Mais voici un aperçu de quelques techniques couramment utilisées par les générateurs d’analyseurs au cas où cela vous intéresserait:

• Les articles de Wikipédia pour Analyse syntaxique , Analyse LL , Analyse des reflex , Analyse LALR , Analyse GLR
• Analyse de LT (*) d'ANTLR
• Analyse monadique en Haskell (pour la création d'analyseurs dans la programmation fonctionnelle langues)
• Et les plus exotiques Grammaires d'expression d'analyse

MODIFIER: Je suis désolé d’avoir reparlé cette question à nouveau. Je viens de tomber sur deux excellents articles décrivant la relation entre langages normaux et automates finis , langages sans contexte et automates déroulants . Cela pourrait être intéressant pour les personnes qui trouvent cette question.

Answer 2

Le Livre Dragon ! Je l'ai utilisé assez récemment pour écrire un compilateur (en PHP!) Pour un langage de traitement des fichiers de modèle écrits en RTF ...

Answer 3

Un analyseur syntaxique est fondamentalement une machine à états finis, c'est-à-dire un automate fini. Vous devriez trouver un livre sur la théorie du calcul, qui traite des automates finis et de choses comme les langages normaux, les langages sans contexte, etc.

Answer 4

essayez amazon

La construction du compilateur n'est qu'un bon exemple

Answer 5

Découvrez "Brinch Hansen sur Pascal Compilers" .. il a été écrit en 1985, mais je l’ai utilisé l’année dernière pour un cours sur les compilateurs (de Per Brinch Hansen ofcourse.) et l’a trouvé très concis et utile pour la conception de compilateurs. .