Ê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
Analyse syntaxique ascendante
Résumé
En informatique, l'analyse syntaxique révèle la structure grammaticale d'un texte. C'est la première étape dans l'étude de son sens. À l'inverse de l'analyse descendante, l'analyse ascendante reconnaît d'abord les plus petites unités du texte (les unités lexicales) analysé avant d'en reconnaître la structure grammaticale en le confrontant à des règles de syntaxe.
La notion d'analyse ascendante provient de la notion d'arbre syntaxique, dans lequel la plupart des unités lexicales sont au bas de l'arbre (nœuds terminaux), et où les plus grosses structures sont placées successivement dans des couches supérieures, jusqu'au sommet ou à la « racine » de l'arbre : un seul nœud décrivant l'intégralité du flux d'entrée. L'analyse ascendante construit l'arbre en commençant par le bas à l'extrémité gauche, et fait progressivement son chemin vers le haut et vers la droite. Un analyseur peut (ou non) agir implicitement sur la structure hiérarchique de l'arbre sans jamais le représenter en mémoire ; les nœuds de l'arbre représentent des appels de fonction (parfois récursifs) dans lesquels la structure environnante de l'arbre peut-être dérivée. L'analyse ascendante attend la construction finie en mémoire de l'arbre pour agir en conséquence de sa structure.
À l'opposé on retrouve l'analyse descendante, où l'ensemble de la structure de l'entrée est décidé avant même et au fur et à mesure que les unités lexicales ne soient consommées, avant de passer aux niveaux inférieures de l'arbre toujours en suivant les règles de syntaxe. Un analyseur de ce type commence par le haut de l'arbre (le nœud racine) et construit successivement ses niveaux inférieurs vers le bas et vers la droite. L'analyse descendante permet de dériver la structure de l'arbre syntaxique au fur et à mesure.
Si une grammaire contient plusieurs règles dont les symboles les plus à gauche sont identiques, mais dont les terminaisons sont différentes, alors la grammaire peut être efficacement gérées par un analyseur ascendant déterministe, mais ne peuvent pas être traitées de manière descendante sans tâtonnements et retours sur trace.
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.