Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Récursivité gauche
Résumé
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.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.