Analyseur syntaxique

Analyse syntaxique

Page d'aide sur l'homonymie Pour les articles homonymes, voir Analyseur.

L'analyse syntaxique consiste à mettre en évidence la structure d'un texte, généralement un programme informatique ou du texte écrit dans une langue naturelle. Un analyseur syntaxique (parser, en anglais) est un programme informatique qui réalise cette tâche. Cette opération suppose une formalisation du texte, qui est vu le plus souvent comme un élément d'un langage formel, défini par un ensemble de règles de syntaxe formant une grammaire formelle. La structure révélée par l'analyse donne alors précisément la façon dont les règles de syntaxe sont combinées dans le texte. Cette structure est souvent une hiérarchie de syntagmes, représentable par un arbre syntaxique dont les nœuds peuvent être décorés (dotés d'informations complémentaires).

L'analyse syntaxique fait habituellement suite à une analyse lexicale qui découpe le texte en un flux (parfois un DAG) de lexèmes, et sert à son tour de préalable à une analyse sémantique. Connaître la structure syntaxique d'un énoncé permet d'expliciter les relations de dépendance (par exemple entre sujet et objet) entre les différents lexèmes, puis de construire une représentation du sens de cet énoncé.

En pratique, et sauf dans les cas très simples, des coroutines sont en général nécessaires pour lier les deux. Ainsi, en FORTRAN où les espaces n'étaient pas significatifs, GOTO5=1 ou DO1I=3, affectations autorisées par la syntaxe bien que perverses, auraient été par erreur considérées comme des fautes de syntaxe si l'opération d'analyse lexicale avait été réalisée totalement avant que ne commence la syntaxique. Dans la pratique, les compilateurs de bas de gamme les refusaient.

Sommaire

Liens avec les langages formels

Les méthodes employées pour réaliser une analyse syntaxique dépendent largement du formalisme employé pour la syntaxe du langage mais aussi du langage lui-même. Toutefois, il est souvent fait usage, pour modéliser un langage ou une langue, de grammaires de réécriture, parmi lesquelles les plus populaires sont les grammaires non contextuelles.

Ainsi, les langages de programmation sont habituellement décrits par ces grammaires, et ce depuis la formalisation d'Algol en BNF. De même, si les grammaires non contextuelles sont jugées peu adaptées pour la description des langues naturelles, les algorithmes d'analyse syntaxique inventés pour les langages non contextuels peuvent parfois être adaptés aux formalismes plus complexes utilisés en traitement des langues naturelles, comme les grammaires d'arbres adjoints (TAG).

L'équivalence entre les langages définissables par certaines classes de grammaires et ceux que reconnaissent certaines classes d'automates permettent de construire des analyseurs syntaxiques à l'aide d'automates. Ainsi, les langages définissables par une grammaire non contextuelle sont aussi ceux qui sont reconnaissables par un automate à pile.

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++.

Récupération sur erreur

En analyse syntaxique des langages de programmation, il faut être capable de continuer l'analyse même lorsque le code source contient des erreurs, pour éviter des cycles de compilation/correction fastidieux pour le développeur. De même, en analyse syntaxique des langues naturelles, il faut pouvoir analyser des énoncés même s'ils ne sont pas couverts par la grammaire, inévitablement incomplète. La récupération sur erreur, ou rattrapage d'erreur, doit être suffisamment efficace pour détecter les problèmes, et "faire avec", moyennant une correction du source ou la faculté de produire des analyses (légèrement) déviantes par rapport à la grammaire. On peut citer quatre approches qui vont dans ce sens, à savoir

Voir aussi

Articles connexes

Wiktprintable without text.svg

Voir « parser » sur le Wiktionnaire.

Bibliographie

  • Alfred V. Aho, Ravi Sethi, Jeffrey D. Ullman, Compilers: Principles, Techniques, and Tools, Addison Wesley Publishing Company, 1986.
  • Dick Grune, Ceriel J.H. Jacobs, Parsing Techniques - A Practical Guide, Ellis Horwood, Chichester, England, 1990.
  • Dick Grune, Henri E. Bal, Ceriel J.H. Jacobs, Koen G. Langendoen, Modern Compiler Design, John Wiley & Sons, Ltd., 2000.

Liens externes

  • Portail de la programmation informatique Portail de la programmation informatique
Ce document provient de « Analyse syntaxique ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Analyseur syntaxique de Wikipédia en français (auteurs)

Regardez d'autres dictionnaires:

  • analyseur syntaxique — sintaksės analizatorius statusas T sritis automatika atitikmenys: angl. parser; syntactic analyser; syntax analyser vok. syntaktischer Analysator, m; Syntaxanalyseprogramm, n; Syntaxanalysierer, m rus. синтаксический анализатор, m pranc.… …   Automatikos terminų žodynas

  • analyseur syntaxique — ● loc. m. ►CIEL Programme réalisant une analyse syntaxique d un code source …   Dictionnaire d'informatique francophone

  • Analyseur — Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom. Sur les autres projets Wikimedia : « Analyseur », sur le Wiktionnaire (dictionnaire universel) De manière générale, le mot analyseur… …   Wikipédia en Français

  • Analyseur lexical — Analyse lexicale L analyse lexicale est la transformation d’un flot de caractères en un flot de lexèmes ou jetons (de l anglais token). Généralement, les lexèmes ont eux mêmes une structure. Ils forment un sous langage. Les techniques utilisées… …   Wikipédia en Français

  • syntaxique — ● adj. ►PROG Relatif à la syntaxe, ainsi un analyseur syntaxique vérifie la syntaxe d un programme (en gros, si les mots clés sont écrits correctement, avec les bons signes cabalistiques tout autour) …   Dictionnaire d'informatique francophone

  • Analyse Syntaxique — Pour les articles homonymes, voir Analyseur. L analyse syntaxique consiste à mettre en évidence la structure d un texte, généralement un programme informatique ou du texte écrit dans une langue naturelle. Un analyseur syntaxique (parser, en… …   Wikipédia en Français

  • Analyse syntaxique — Pour les articles homonymes, voir Analyseur. L analyse syntaxique consiste à mettre en évidence la structure d un texte, généralement un programme informatique ou du texte écrit dans une langue naturelle. Un analyseur syntaxique (parser, en… …   Wikipédia en Français

  • Arbre Syntaxique Abstrait — Pour les articles homonymes, voir AST. En informatique, un arbre syntaxique abstrait (abstact syntax tree ou AST en anglais) est un arbre avec des labels dont les nœuds internes sont marqués par des opérateurs et dont les nœuds fils ( feuilles ou …   Wikipédia en Français

  • Arbre syntaxique abstrait — Pour les articles homonymes, voir AST. En informatique, un arbre syntaxique abstrait (abstract syntax tree, ou AST, en anglais) est un arbre dont les nœuds internes sont marqués par des opérateurs et dont les feuilles (ou nœuds externes)… …   Wikipédia en Français

  • Analyse LR — En informatique, un analyseur LR (pour Left to right, Rightmost derivation) est un analyseur pour les grammaires non contextuelles qui lit l entrée de gauche à droite et produit une dérivation droite. On parle aussi d analyseur LR(k) où k… …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”