Récursivité gauche

En informatique, et notamment en théorie des langages formels, en compilation et analyse syntaxique descendante, la récursivité gauche est un concept de grammaires formelles qui décrit un certain type de réapparition d'une variable dans une dérivation lors d'un processus d'analyse syntaxique. Dans la terminologie des grammaires formelles et notamment des grammaires algébriques, une variable est récursive gauche s'il existe une règle de la grammaire dont le membre droit débute par cette variable (ce cas est dit récursivité directe) ou pour laquelle un mot dérivé débute par cette variable (cas de la récursivité indirecte). L'élimination de la récursivité gauche est une étape préliminaire pour pouvoir utiliser l'analyse syntaxique descendante. Une grammaire est récursive gauche s'il existe une variable qui dérive en un mot du langage étendu qui débute par cette variable, formellement si où indique l'opération consistant à appliquer une ou plusieurs règle de grammaire, et où est une suite de symboles terminaux et non terminaux. La récursivité gauche est directe si la définition est réalisée en une étape, c'est-à-dire si la grammaire possède une règle de la forme où est une suite de symboles terminaux et non terminaux. Par exemple, la règle d'une grammaire usuelle pour les expressions arithmétiques est récursive gauche directe. Un analyseur descendant pourrait l'implémenter par une procédure du type function Expression() { Expression(); match('+'); Terme(); } ce qui provoque une boucle infinie d'appels récursifs à l’exécution. La récursivité gauche est indirecte si la définition est réalisée en plusieurs étapes. Formellement, elle demande l’existence d'une suite de règles selon le schéma suivant : où sont des mots qui chacun peuvent dériver en le mot vide et sont des mots quelconques. La dérivation produit comme premier symbole du mot dernier étendu. L'élimination de la récursivité directe procède par le remplacement de règles récursives gauche par d'autres, et l'introduction de nouveaux non-terminaux.