Analyse syntaxique ascendante
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.
Analyse ascendante en comparaison à l'analyse descendante
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. De manière ascendante un analyseur peut gérer une plus grande gamme de grammaires qu'un analyseur descendant déterministe.L'analyse ascendante est parfois effectuée par de multiples retours sur trace. Plus généralement néanmoins, elle est achevée par un analyseur codé sur le modèle shift-reduce tel que le LALR (Look-Ahead Left Reversed Rightmost Derivation).
Notes et références
Portail de l’informatique