Ê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 GraphSearch.
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.
Concepts associés (8)
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).
Parsing expression grammar
In computer science, a parsing expression grammar (PEG) is a type of analytic formal grammar, i.e. it describes a formal language in terms of a set of rules for recognizing strings in the language. The formalism was introduced by Bryan Ford in 2004 and is closely related to the family of top-down parsing languages introduced in the early 1970s. Syntactically, PEGs also look similar to context-free grammars (CFGs), but they have a different interpretation: the choice operator selects the first match in PEG, while it is ambiguous in CFG.
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.
Cours associés (1)
CS-320: Computer language processing
We teach the fundamental aspects of analyzing and interpreting computer languages, including the techniques to build compilers. You will build a working compiler from an elegant functional language in