Pourquoi les analyseurs en ligne semblent-ils s'arrêter aux expressions rationnelles?

Question

Je me demande depuis longtemps pourquoi il ne semble pas exister d'analyseur pour, par exemple, BNF , qui se comportent comme des expressions régulières dans diverses bibliothèques.

Bien sûr, il existe des éléments tels que ANTLR , Yacc et beaucoup d’autres qui génèrent du code qui, à son tour, peut analyser un CFG , mais il ne semble pas exister de bibliothèque capable de le faire sans passer par l'étape intermédiaire.

Je souhaiterais écrire un analyseur Packrat , pour initialiser tous ceux qui sont imbriqués. -parenthesis-bizarreries associées aux expressions rationnelles (et peut-être encore plus, pour le sport), mais j'ai quand même le sentiment que je suis en train de marcher dans une autre classe de marécages qui ressemble à un problème.

Existe-t-il une limite technique / théorique pour ces analyseurs, ou manque-t-il simplement quelque chose?

Answer 1

Je pense que c'est plus une chose culturelle. L'utilisation de grammaires sans contexte est principalement limitée aux compilateurs, qui ont généralement un code associé à chaque règle de production. Dans certaines langues, il est plus facile de générer du code que de simuler des rappels. Dans d’autres, vous verrez des bibliothèques d’analyseurs: des combinateurs d’analyseurs dans Haskell, par exemple. D'autre part, les expressions régulières sont largement utilisées dans des outils tels que grep, où il est gênant d'exécuter le compilateur C chaque fois que l'utilisateur donne une nouvelle expression régulière.

Answer 2

Boost.Spirit ressemble à ce que vous recherchez.

Si vous souhaitez créer le vôtre, j'ai utilisé BNFC pour mon dernier projet de compilateur et fournit la grammaire utilisée dans sa propre implémentation . Cela pourrait être un bon point de départ ...

Answer 3

Il n’ya pas de limite technique / théorique cachée dans l’ombre. Je ne peux pas dire pourquoi elles ne sont pas plus populaires, mais je connais au moins une bibliothèque qui propose ce type de "ligne". l'analyse que vous recherchez.

SimpleParse est une bibliothèque python qui vous permet simplement de coller votre grammaire EBNF poilue dans votre programme et de l'utiliser pour analyser les choses tout de suite, pas d'étapes immédiates. Je l'ai utilisé pour plusieurs projets pour lesquels je voulais un langage de saisie personnalisé, mais je ne voulais vraiment pas m'engager dans un processus de construction formel.

Voici un petit exemple qui me vient à l’esprit:

decl = r"""
    root := expr
    expr := term, ("|", term)*
    term := factor+
    factor := ("(" expr ")") / [a-z]
"""
parser = Parser(decl) 
success, trees, next = parser.parse("(a(b|def)|c)def")

Les bibliothèques de combinateurs d’analyseurs pour Haskell et Scala vous permettent également d’exprimer votre grammaire pour votre analyseur dans le même bloc de code que celui qui l’utilise. Cependant, vous ne pouvez pas, par exemple, laisser l'utilisateur saisir une grammaire au moment de l'exécution (ce qui pourrait intéresser uniquement les personnes qui créent des logiciels pour les aider à comprendre les grammaires de toute façon).

Answer 4

Pyparsing ( http://pyparsing.wikispaces.com ) prend en charge de manière intégrée l'analyse et la c'est du pur Python, vous pouvez donc voir l'implémentation réelle.

Answer 5

Parce que les grammaires sans contexte complètes sont assez déroutantes car elles sont dépourvues de syntaxe cryptiquement dense et incompréhensible pour les rendre encore plus déroutantes?

Il est difficile de savoir ce que vous demandez. Essayez-vous de créer quelque chose comme une expression régulière, mais pour les grammaires sans contexte? Comme, en utilisant $ var = ~ / expr = expr + expr / (en Perl) et en ayant cette correspondance "1 + 1" ou "1 + 1 + 1 " ou " 1 + 1 + 1 + 1 + 1 + ... "? Je pense que l’une des limites de cette situation sera la syntaxe: le fait d’avoir plus de trois règles au plus rendra votre "expression de grammaire". encore plus illisible que n'importe quelle expression régulière moderne.

Answer 6

Les effets secondaires sont la seule chose que je vois qui puisse vous aider. La plupart des générateurs d’analyseurs incluent du code incorporé pour le traitement et vous auriez besoin d’un eval pour que cela fonctionne.

Une façon de procéder serait de nommer des actions, puis de créer une "action". fonction qui prend le nom de l'action à faire et les arguments avec lesquels le faire.

Answer 7

Vous pourriez théoriquement le faire avec Boost Spirit en C ++, mais il est principalement conçu pour les grammaires statiques. Je pense que la raison pour laquelle cela n'est pas courant est que les CFG ne sont pas aussi utilisés que les regex. Je n'ai jamais eu à utiliser de grammaire, sauf pour la construction du compilateur, mais j'ai utilisé des regex plusieurs fois. Les CFG sont généralement beaucoup plus complexes que les regex, il est donc logique de générer du code de manière statique avec un outil tel que YACC ou ANTLR.

Answer 8

tcllib a quelque chose comme ça, si vous pouvez supporter Grammaires d'expression Parse et également TCL. Si vous aimez Perl, CPAN a Parse :: Earley . . Voici une version pure de Perl qui semble prometteuse. PLY semble être une solution plausible pour Python