Analyse syntaxique - Définition

Analyse non contextuelle

Analyse ascendante ou descendante

Un analyseur syntaxique doit retracer le cheminement d'application des règles de syntaxe qui ont mené de l'axiome au texte analysé.

• Une analyse descendante retrace cette dérivation en partant de l'axiome et en essayant d'appliquer les règles pour retrouver le texte. Cette analyse procède en morcelant la phrase en éléments de plus en plus réduits jusqu'à atteindre les unités lexicales. L'analyse LL est un exemple d'analyse descendante.
• Une analyse ascendante retrouve ce cheminement en partant du texte, en tentant d'associer des lexèmes en syntagmes de plus en plus larges jusqu'à ce qu'il retrouve l'axiome. L'analyse LR est un exemple d'analyse ascendante.

Analyse déterministe

Un analyseur syntaxique, en tant que système de réécriture, est déterministe si une seule règle de réécriture est applicable dans chaque configuration de l'analyseur. Par extension, il ne peut alors y avoir qu'une seule séquence de règles permettant d'analyser le texte dans sa totalité, et donc celui-ci ne peut être syntaxiquement ambigu. Toutefois, il peut être fait usage de techniques telles que la pré-vision (en anglais lookahead) ou le backtracking pour déterminer quelle règle il faut appliquer à un point donné de l'analyse.

Les méthodes d'analyse déterministes sont principalement employées pour l'analyse des langages de programmation. Par exemple, les analyses LR, LL, ou LALR (employée par Yacc) sont toutes déterministes. On ne peut cependant pas construire un analyseur déterministe pour n'importe quelle grammaire non contextuelle. Dans ce cas, et si l'on souhaite n'avoir qu'une seule analyse en sortie, on est contraint de lui adjoindre des mécanismes supplémentaires, comme des « règles de désambiguïsation » ou des modèles probabilistes permettant de choisir la "meilleure" analyse.

Une méthode d’analyse descendante et déterministe est dite prédictive.

Analyse non déterministe

La taille et la complexité des langues naturelles, sans oublier leur inévitable ambiguïté, rend leur analyse déterministe totalement impossible. Une analyse non déterministe s'apparente à une résolution dans un système contraint, et s'exprime assez aisément en Prolog.

L'emploi de méthodes tabulaires, mémorisant les calculs intermédiaires, sera plus efficace qu'un simple backtracking. L'analyse CYK est un exemple d'analyse tabulée, à laquelle on préférera des méthodes plus sophistiquées

• d'analyse à chartes comme l'analyse Earley
• ou d'analyse LR généralisée (GLR).

Ces deux dernières méthodes d'analyse sont aussi appréciées pour l'analyse de langages de programmation dont la syntaxe est ambiguë, comme par exemple C++.