Comme expliqué dans Retrait de la récursion de gauche , il existe deux façons de supprimer la récursion de gauche.
Quelles personnes utilisent normalement pour supprimer (ne pas avoir) la récursion de gauche avec antlr? J'ai utilisé Flex / Bison pour Parser, mais je dois utiliser Antlr. La seule chose à laquelle je suis préoccupée par l'utilisation d'AntLR (ou d'un analyseur LL dans le génaral) est la suppression de la récursivité gauche. P>
J'ai fait une certaine expérience avec la grammaire suivante. p> Après le retrait de la récursion, je reçois le suivant
grammar T;
options {
language=Python;
}
start returns [value]
: e {$value = $e.value};
e returns [value]
: t ep
{
$value = $t.value
if $ep.value != None:
$value += $ep.value
}
;
ep returns [value]
: {$value = None}
| '+' t r = ep
{
$value = $t.value
if $r.value != None:
$value += $r.value
}
;
t returns [value]
: f tp
{
$value = $f.value
if $tp.value != None:
$value *= $tp.value
}
;
tp returns [value]
: {$value = None}
| '*' f r = tp
{
$value = $f.value;
if $r.value != None:
$value *= $r.value
}
;
f returns [int value]
: INT {$value = int($INT.text)}
| '(' e ')' {$value = $e.value}
;
INT : '0'..'9'+ ;
WS: (' '|'\n'|'\r')+ {$channel=HIDDEN;} ;
5 Réponses :
Si vous écrivez la grammaire, alors bien sûr, vous essayez de l'écrire pour éviter les pièges de votre générateur d'analyseurs.
Habituellement, dans mon expérience, je reçois un manuel de référence pour le langage d'intérêt (hérité) et contient déjà des diagrammes de grammaire ou de chemin de fer, et c'est ce que c'est.
Dans ce cas, l'élimination de la récursion à tout type d'une grammaire est effectuée à la main. Il n'y a pas de marché pour les outils de suppression de gauche à gauche, et si vous en aviez un, il serait spécialisé dans une syntaxe de grammaire qui ne correspondait pas à la syntaxe de la grammaire que vous avez.
Ce renvoi est principalement une question de sueur dans de nombreux cas, et il n'ya généralement pas de tonnes. Donc, l'approche habituelle est de sortir de votre couteau de grammaire et d'y avoir.
Je ne pense pas comment vous supprimez les changements de récursivité de gauche comment ANTLR obtient des arbres. Vous devez d'abord faire la suppression de la récursion de gauche, ou AntlR (ou tout autre générateur d'analyseurs que vous utilisez) n'acceptera pas simplement votre grammaire.
Il y a ceux d'entre nous qui ne veulent pas que le générateur d'analyseur mettait des contraintes sérieuses sur ce que nous pouvons écrire pour une grammaire sans contexte. Dans ce cas, vous souhaitez utiliser quelque chose comme un générateur d'analyseurs de GLR, qui gère la récupération de gauche ou de droite avec facilité. Les personnes déraisonnables peuvent même insister sur la génération AST automatisée sans aucun effort de la part de l'écrivain de la grammaire. Pour un outil capable de faire les deux, voir Toolkit de réengagement logiciel DMS .
en sens pratique, à quel point Supprimer la récursion de gauche en Antlr? Est Ceci est un showstopper à utiliser antlr? p>
Je pense que vous avez un malentendu de la récursion de gauche. Il s'agit d'une propriété de la grammaire, non du générateur d'analyseurs ni de l'interaction entre le générateur d'analyseurs et la spécification. Il arrive lorsque le premier symbole du côté droit d'une règle est égal à la non-déterminante correspondant à la règle elle-même. P>
Comprendre le problème inhérent ici, vous devez savoir quelque chose sur la manière dont une analyse de descente récursive (LL) fonctionne. Dans un analyseur LL, la règle de chaque symbole non mortal est mise en œuvre par une fonction correspondant à cette règle. Alors, supposons que j'ai une grammaire comme ceci: p>
xxx pré> alors, l'analyseur regarderait (à peu près) comme ceci: p>
boolean A() { if (!eat('c')) return true; A(); return true; }
joliment écrit. Je suis assez nouveau à Antlr, c'est assez utile.
Dans la dernière fonction a (), vous retournez vrai deux fois, ne devriez-vous pas être faux? Je dirais le premier. (UPS c'est 8 ans plus tard)
Considérez quelque chose comme une liste de paramètres typique: Puisque vous ne vous souciez de rien comme priorité ou associativité avec des paramètres, cela est assez facile à convertir en récursivité droite, à la dépense d'ajouter une production supplémentaire: pour les cas les plus graves, vous voudrez peut-être passer du temps dans le livre de dragon. Faire un chèque rapide, ceci est principalement couvert au chapitre 4. Autant que le sérieux se passe, je suis tout à fait sûr qu'Arlr n'acceptera pas simplement une grammaire contenant la récursion de gauche, ce qui le mettrait dans le Catégorie "Nécessité absolue".
Je ne peux pas parler d'antlr, mais en général, les étapes pour éliminer une récursion de gauche de la forme: est de le changer pour être: p> A -> B B'
B' -> B B'
->
Ceci n'est que de pertinence orthogonalement, mais je viens de publier une pré-empreinte d'un document sur une nouvelle méthode d'analyse que j'appelle "Pika analysant" (analyse Packrat CF) qui gère directement les grammaires récursif sans la réécriture des règles.
Belle petite ttraite. L'analyseur lui-même était trop technique pour moi, mais votre examen du problème / des progrès de la récursion de gauche dans les grammaires a été utile.