Comment implémenter un éliminateur de récursion gauche?

Question

Comment puis-je implémenter un éliminateur pour cela?

A := AB | 
     AC | 
     D | 
     E ; 

Answer 1

Voici un exemple de ce qu'on appelle immédiate récursivité gauche, et est retiré comme ceci:

A := DA' | 
    EA' ; 

A' := ε | 
     BA' | 
     CA' ; 

L'idée de base est d'abord noter que lors de l'analyse d'un vous A nécessairement commencer par un D ou un E. Après le D ou un E vous finirez soit (queue est ε) ou continuer (si nous sommes dans une construction AB ou AC).

L'algorithme actuel fonctionne comme ceci:

Pour toute production gauche récursif comme ceci: A -> A a1 | ... | A ak | b1 | b2 | ... | bm Remplacer la production avec A -> b1 A' | b2 A' | ... | bm A' et ajouter la production A' -> ε | a1 A' | ... | ak A'.

Voir Wikipedia: Left Recursion pour plus d'informations sur l'algorithme d'élimination (y compris l'élimination de la récursion indirecte à gauche).

Answer 2

Une autre forme est disponible:

A := (D | E) (B | C)* 

La mécanique de le faire sont à peu près les mêmes, mais certains parseurs pourraient gérer cette forme mieux. Considérez aussi ce qu'il faudra pour munir les règles d'action avec la grammaire elle-même; l'autre formulaire nécessite que l'outil de factorisation génère un nouveau type pour que la règle A' renvoie l'état où ce formulaire ne se trouve pas.