Comment supprimer la récursion de gauche selon la règle suivante:Suppression de la récursivité à gauche avec des terminaux
S -> aSAbb | J'ai compris comment l'exécuter sur S -> SA | A
qui devient S -> A | COMME'; S '-> A | AS ', mais les terminaux me jettent dans cette question.
EDIT:
Désolé, semble-t-je confus quant à ce qui reste est récursivité. J'aurais dû demander comment enlever le symbole de la main gauche du côté droit.
La règle
S -> aSAbb | aA
n'est pas laissé récursive. Une règle récursive gauche a la forme
A -> Au
où u est une séquence de terminaux et non-terminaux. Pour supprimer le symbole S du côté droit des règles S, tenez compte:
S => aSAbb
=> a(aSAbb)Abb
=> a^n(aA)(Abb)^n
Le rôle de la récursivité sur S est de produire cette séquence. Une grammaire équivalente est:
S -> aKAbb | aA
K -> aSAbb | aA
Les grammaires sont équivalentes, puisque toute dérivation
S => aSAbb
=> a(aSAbb)Abb
=> a(a(aSAbb)Abb)Abb
est maintenant juste une dérivation
S => aKAbb
=> a(aSAbb)Abb
=> a(a(aKAbb)Abb)Abb
et chaque dérivation se termine par aA (je pense: Corrigez-moi si j'ai tort, s'il-vous plait).
Il n'y a pas de récursion à gauche, c'est pourquoi vous avez du mal. La récursivité gauche nécessite que la règle commence avec le même non-terminal qu'elle essaie de produire, par exemple, S-> S ...; –
Je ne pense pas que ce soit possible. La grammaire semble être 'a^n aA (Abb)^n' et je ne pense pas qu'il existe un moyen de lier ces deux' n 'sans récursion. – BCS