En termes simples, qu'est-ce qui reste récursif?

Selon une page de code.google.com, la "récursion à gauche" est définie comme suit:

La récursion gauche fait simplement référence à tout non-terminal récursif qui, lorsqu'il produit une forme sententielle se contenant, cette nouvelle copie de lui-même apparaît à gauche de la règle de production.

Wikipedia propose deux définitions différentes:

1. En termes de grammaire sans contexte, un r non terminal est récursif à gauche si le symbole le plus à gauche dans l'une des productions de r (`` alternatives '') soit immédiatement (direct / immédiat à gauche récursif), soit via un autre non terminal définitions (indirect / caché récursif à gauche) réécrit en r à nouveau.

2. "Une grammaire est récursive à gauche si nous pouvons trouver un A non terminal qui finira par dériver une forme sententielle avec elle-même comme symbole de gauche."

Je commence à peine avec la création de langage ici, et je le fais pendant mon temps libre. Cependant, lorsqu'il s'agit de sélectionner un analyseur de langue, si la récursion gauche est prise en charge par cet analyseur ou cet analyseur est un problème qui vient immédiatement au premier plan. La recherche de termes comme «forme sententielle» ne mène qu'à d'autres listes de jargon, mais la distinction de la récursion «gauche» doit presque être quelque chose de très simple. Traduction s'il vous plait?

Une règle Rest récursive à gauche si, pour savoir si elle Rcorrespond, vous devez d'abord savoir si elle Rcorrespond. Cela se produit lorsque Rapparaît, directement ou indirectement, comme le premier terme dans une production de lui-même.

Imaginez une version jouet de la grammaire pour les expressions mathématiques, avec seulement l'addition et la multiplication pour éviter la distraction:

Expression ::= Multiplication '+' Expression
            || Multiplication

Multiplication ::= Term '*' Term
                 || Term

Term ::= Number | Variable

Comme écrit, il n'y a pas de récursion gauche ici - nous pourrions passer cette grammaire à un analyseur de descente récursive.

Mais supposons que vous ayez essayé de l'écrire de cette façon:

Expression ::= Expression '*' Expression
            || Expression '+' Expression
            || Term

Term ::= Number | Variable

Il s'agit d'une grammaire, et certains analyseurs peuvent y faire face, mais les analyseurs de descente récursive et les analyseurs LL ne le peuvent pas - car la règle pour Expressioncommence par Expressionelle-même. Il devrait être évident pourquoi, dans un analyseur à descente récursive, cela conduit à une récursivité illimitée sans consommer réellement d'entrée.

Peu importe que la règle se réfère directement ou indirectement à elle-même; si Aa une alternative qui commence par B, et Ba une alternative qui commence par A, alors Aet Bsont tous deux indirectement récursifs à gauche, et dans un analyseur de descente récursive, leurs fonctions de correspondance conduiraient à une récursion mutuelle sans fin.

Je vais essayer de le mettre en termes simples.

Si vous pensez en termes d'arbre d'analyse (pas l'AST, mais la visite de l'analyseur et l'expansion de l'entrée), la récursivité gauche se traduit par un arbre qui croît vers la gauche et vers le bas. La récursion droite est exactement le contraire.

Par exemple, une grammaire courante dans un compilateur est une liste d'éléments. Prenons une liste de chaînes ("rouge", "verte", "bleue") et analysons-la. Je pourrais écrire la grammaire de plusieurs façons. Les exemples suivants sont directement récursifs à gauche ou à droite, respectivement:

arg_list:                           arg_list:
      STRING                              STRING
    | arg_list ',' STRING               | STRING ',' arg_list 

Les arbres pour ces analyses:

         (arg_list)                       (arg_list)
          /      \                         /      \
      (arg_list)  BLUE                  RED     (arg_list)
       /       \                                 /      \
   (arg_list) GREEN                          GREEN    (arg_list)
    /                                                  /
 RED                                                BLUE

Notez comment il croît dans le sens de la récursivité.

Ce n'est pas vraiment un problème, c'est correct de vouloir écrire une grammaire récursive gauche ... si votre outil d'analyse peut le gérer. Les analyseurs de bas en haut le gèrent très bien. Il en va de même pour les analyseurs LL plus modernes. Le problème avec les grammaires récursives n'est pas la récursivité, c'est la récursivité sans faire avancer l'analyseur, ou, récursif sans consommer de jeton. Si nous consommons toujours au moins 1 jeton lorsque nous récursions, nous atteignons finalement la fin de l'analyse. La récursion gauche est définie comme récursive sans consommer, ce qui est une boucle infinie.

Cette limitation est purement un détail d'implémentation de l'implémentation d'une grammaire avec un analyseur LL descendant naïf (analyseur de descente récursif). Si vous voulez vous en tenir aux grammaires récursives gauches, vous pouvez y faire face en réécrivant la production pour consommer au moins 1 jeton avant de récurser, ce qui garantit que nous ne serons jamais coincés dans une boucle non productive. Pour toute règle de grammaire qui est récursive à gauche, nous pouvons la réécrire en ajoutant une règle intermédiaire qui aplatit la grammaire à un seul niveau d'anticipation, consommant un jeton entre les productions récursives. (REMARQUE: je ne dis pas que c'est la seule façon ou la façon préférée de réécrire la grammaire, en soulignant simplement la règle généralisée. Dans cet exemple simple, la meilleure option est d'utiliser la forme récursive droite). Cette approche étant généralisée, un générateur d'analyseur peut l'implémenter sans impliquer le programmeur (théoriquement). Dans la pratique, je crois que ANTLR 4 fait maintenant exactement cela.

Pour la grammaire ci-dessus, l'implémentation LL affichant la récursion gauche ressemblerait à ceci. L'analyseur commencerait par prédire une liste ...

bool match_list()
{
    if(lookahead-predicts-something-besides-comma) {
       match_STRING();
    } else if(lookahead-is-comma) {
       match_list();   // left-recursion, infinite loop/stack overflow
       match(',');
       match_STRING();
    } else {
       throw new ParseException();
    }
}

En réalité, nous avons vraiment affaire à une «mise en œuvre naïve», c'est-à-dire. nous avons d'abord prévu une phrase donnée, puis appelé récursivement la fonction pour cette prédiction, et cette fonction appelle naïvement à nouveau la même prédiction.

Les analyseurs ascendants n'ont pas le problème des règles récursives dans les deux sens, car ils n'analysent pas le début d'une phrase, ils travaillent en remontant la phrase.

La récursivité dans une grammaire n'est un problème que si nous produisons de haut en bas, c'est-à-dire. notre analyseur fonctionne en "élargissant" nos prévisions lorsque nous consommons des jetons. Si au lieu de s'étendre, nous nous effondrons (les productions sont "réduites"), comme dans un analyseur ascendant LALR (Yacc / Bison), alors la récursivité de chaque côté n'est pas un problème.