Différence entre factorisation à gauche et Recursion à gauche
Quelle est la différence entre Left Factoring et Left Recursion? Je comprends que Left factoring est une technique d'analyse prédictive top-down. Mais je m'embrouille quand j'entends ces deux termes.
6 réponses
la factorisation de gauche supprime le facteur de gauche commun qui apparaît dans deux productions du même non-terminal. Il est fait pour éviter l'arrière-traçage par l'analyseur. Supposons que l'analyseur ait un regard vers l'avenir ,considérez cet exemple-
A - > qB / qC
où A,B, C sont des non-terminaux et q est une phrase.
Dans ce cas, l'analyseur sera confus quant à laquelle des deux productions choisir et il pourrait avoir à retracer. Après factoring gauche, la grammaire est convertie -
A - > qD
D - > B / C
Dans ce cas, un analyseur avec un regard toujours choisir la bonne la production.
la récursion à gauche est un cas où le non-terminal le plus à gauche dans une production d'un non-terminal est le non-terminal lui-même( récursion directe à gauche ) ou à travers quelques autres définitions non-terminal, réécrit au non-terminal à nouveau(récursion indirecte à gauche). Considérez ces exemples -
(1) - > Aq (direct)
(2) - > Bq B - > Ar (indirect)
la recursion gauche doit être supprimée si l'analyseur effectue une analyse descendante
Factorisation De Gauche est une technique de transformation grammaticale. Elle consiste à" factoriser " des préfixes communs à deux ou plusieurs productions.
Par exemple, aller à partir de:
a → α β / α γ
à:
a → α A'
A' → β / γ
Recursion Gauche est une propriété qu'une grammaire possède chaque fois que vous pouvez dériver d'une variable donnée (non terminal) rhs qui commence par la même variable, en une ou plusieurs étapes.
Par exemple:
A → A α
ou
A → B α
B → γ
Il y a une grammaire de transformation technique appelée Elimination de la récursivité à gauche, qui fournit une méthode pour générer, étant donné une grammaire récursive à gauche, une autre grammaire qui est équivalente et qui n'est pas à gauche récursive.
la relation / confusion entre les deux termes provient probablement du fait que les deux techniques de transformation peuvent devoir être appliquées à une grammaire avant d'être en mesure de dériver un analyseur prédictif top down pour elle.
Voici comment j'ai vu les deux termes utilisés:
- recursion de gauche: quand une ou plusieurs productions peuvent être atteintes d'elles-mêmes sans jetons consommés entre les deux.
- factorisation de gauche: processus de transformation, transformant la grammaire d'une forme récursive de gauche en une forme non-récursive de gauche équivalente.
facteur de gauche:
laisser la grammaire donnée : -->Ab1 | ab2 | ab3
1) Nous pouvons voir que , pour chaque production , il y a un préfixe commun et si nous choisissons n'importe quelle production ici , il n'est pas co-confirmé que nous n'aurons pas besoin de revenir en arrière.
2) c'est non déterministe , parce que nous ne pouvons pas choisir n'importe quelle production et être assurés que nous atteindrons notre corde désirée en faisant l'arbre de parse correct.
mais si nous réécrire la grammaire d'une manière qui est déterministe et nous laisse aussi être assez flexible pour en faire n'importe quelle chaîne qui peut être possible sans retour en arrière .... il sera :
-- > aA', Un' --> b1 | b2| b3 maintenant, si on nous demande de faire l'arbre d'analyse de la chaîne de ab2.... nous n'avons pas besoin d'un suivi . Parce que nous pouvons toujours choisir la production correcte quand nous obtenons un' ainsi nous produirons l'arbre de parse correct .
récursion à Gauche :
-- > Aa | b ici, il est clair que la gauche de l'enfant de A sera toujours A si nous choisissons la première production, c'est recursion gauche .parce que, A se fait appeler encore et encore . la chaîne générée par cette grammaire est : ba* puisque ce ne peut pas être dans une grammaire ... nous éliminons la récursion de gauche en écrivant:
-- > bA' A '-- > E / aA' maintenant nous n'aurons plus de récursion et nous pouvons aussi générer ba* .
Recursion De Gauche:
Une grammaire est laissée récursive si elle a un nonterminal A tel qu'il y a une dérivation A - > Aa / β
lors de la conception d'un analyseur de haut en bas, si la récursion de gauche existe dans la grammaire alors l'analyseur tombe dans une boucle infinie, ici parce que A essaye de faire correspondre A lui-même, ce qui n'est pas possible.
Nous pouvons éliminer la récursion à gauche ci-dessus en réécrivant la production offensante. Comme- a - > ßA' A' - > aA ' / epsilon Factorisation De Gauche: l'affacturage à gauche est nécessaire pour éliminer le non-déterminisme d'une grammaire. Supposons une grammaire, s - > abS / aSb Ici, S dérive le même terminal a dans la règle de production(deux choix possibles pour S), qui suit le non-déterminisme. Nous pouvons réécrire la production pour reporter la décision de S comme- S ->' S' - > bS / Sb ainsi, S ' peut être remplacé pour bS ou Sb
récursion à gauche:= quand la main gauche non terminal est la même que la main droite non terminal. Exemple: A - >A&|B où & est alpha. Nous pouvons supprimer la ricursion gauche en réécrivant cette production comme telle.
A - > BA' A' - >&A'|€
facteur gauche moyen produit ne doit pas être non déterministe. . Exemple: A->&A|ET B|ET C