La grammaire suivante a laissé la récursion Comment supprimer? Y a-t-il une procédure générale pour cela?
4 Réponses :
Comme d'autres ont souligné, il existe une procédure générale pour remplacer la récursion de gauche avec une récursion droite. Les autres réponses montrent comment utiliser cette procédure générale pour éliminer la récursion de gauche dans la grammaire donnée.
Voici une solution qui restructure la grammaire donnée de manière spécifique à cette grammaire. P>
E= T+E|T T= F*T|F F= a|b|c
Donc, vous dites réellement que votre grammaire proposée dans la récursion de gauche libre? Je me demande parce que je l'ai rencontré dans un cours dans des langues formelles et il a été déclaré à gauche récursif?
Oui, il y a une procédure générale, voir par ex. Wikipedia . Il convient de mentionner que Cela modifie l'associativité de Ce n'est pas un problème pour l'addition et la multiplication, mais ce serait un problème de soustraction et de division, par exemple. L'article Wikipedia a plus de détails sur le Procédure de retrait de gauche-récursion et ses subtilités. + et * de gauche à droite. C'est-à-dire que, avant A + B + C a été analysé comme (A + B) + C , il est maintenant analysé comme A + (B + C) .
Alors, comment résoudre ce problème? (d'inverser l'associativité) Je vois de nombreuses copies (directement d'indirects) de cet algorithme de retrait de la récursion de gauche, et ils écrivent toujours l'avertissement sur la rupture de l'associativité, mais je n'avais encore vu aucune solution à ce problème dans aucun de ces articles. . y-a-t'il une solution? Ou seulement le problème? Et l'autre question est la suivante: pourquoi cela fonctionne-t-il?
Je demande parce que je n'ai pas vu de preuve fiable de cet algorithme. Il y avait des "épreuves" qui montraient que la langue obtenue de la grammaire transformée est toujours la même, mais pour moi, il y a une erreur dans de telles preuves: une hypothèse que si la syntaxe génère la même sortie, c'est la même chose. Parce que ce n'est pas! C'est une langue complète, car elle a un arbre d'analyse différent, il est donc "compris" différemment par la machine. La même différence qu'entre interpréter "Tree de syntaxe abstraite" comme "Abstrait (Syntaxe Tree)" et "(syntaxe abstraite)" - Deux choses différentes.
Il en va de même pour les syntaxes de gauche-récursives et récursives à droite. L'un est laissé-associatif, l'autre est associatif à droite. Et je ne sais pas de quelque manière que ce soit pour avoir une syntaxe gauche récursive avec une associativité droite. Savez-vous?
En mathématiques (que je considère comme un superset de l'informatique), nous sommes prudents de définir "idem" "similaire" "similaire" "égal," équivalent "" isomorphe ", etc. Avant d'utiliser les termes. Les langues sont ensembles de chaînes, qui sont finies de séquences de symboles d'un alphabet. L'égalité de set est bien définie. Nous disons deux ensembles a et b sont égaux si a est un sous-ensemble de B et b < / code> est un sous-ensemble de A . Et nous pouvons montrer que c'est le cas, apparemment, avec ces algorithmes. Ainsi, deux grammaires qui génèrent différents arbres d'analyse peuvent être montrées rigoureusement pour décrire les langues égales, en termes de jeux.
Si vous souhaitez dire que: A -> AA | @ n'est pas le même que a -> aa | @ puis par tous les moyens le faire. Vous avez la liberté de définir vos termes comme vous le voyez. Donnez-moi une définition rigoureuse et précise de «la similitude», cependant, quand il s'agit de grammates, cependant. Je soupçonne que votre notion peut être quelque chose dans le sens de: "Deux grammaires sont structurellement isomorphes s'il y a une bijection d'arbres d'analyse pour chaque élément de la langue. Deux arbres d'analyse sont isomorphes si leurs graphiques dirigés naturellement définis sont Isomorpic." C'est une bête de faire quoi que ce soit, mais commencez à faire des preuves avec quelque chose
comme ça et je serai intéressé :)
Cette réponse pourrait être améliorée en expliquant e . Sans cela, c'est assez opaque à ceux qui ne sont pas déjà familiers avec la théorie des analyseurs. (Bien sûr, vous avez fourni un lien vers une page Wikipedia, mais ladite page commence par "Cet article peut être trop technique pour la plupart des lecteurs à comprendre", ce qui est certainement le cas pour moi).
La procédure générale est trouvée chez Wikipedia , par exemple. Je vais démontrer pour Nous créons un nouveau non mortminal pour le "repos", c'est-à-dire. la séquence non nulle. Cela gère la récursion.
Et nous modifions la règle d'origine pour utiliser le nouveau non mortminal pour gérer la récursion.
e = e + t | t :
E est le non-terminal gauche-récursif.
+ t est la séquence non nulle (alpha).
t est la séquence qui ne démarre pas par e (bêta).
e '= epsilon | + te'
e = te '
La production va à pour maintenir le même traitement où le poing E Disjunct est traité avec A (E, t) . La nouvelle version utilise: