En linguistique informatique ou en TALN, l'analyse syntaxique (syntactic parsing) réfère au processus d'analyse automatisé d'une chaine de mots — représentant une phrase — dans le but d'obtenir les relations coexistant entre ces mots, par l'intermédiaire d'un arbre syntaxique. Lorsqu’on part de texte brut, ce dernier doit avoir été segmenté en unités lexicales au préalable (tokenization). Habituellement, une analyse lexicale (lemmatisation, analyse morphosyntaxique...) est exécutée avant l'analyse syntaxique proprement dite, afin d'identifier les unités lexicales et leurs propriétés. Le résultat de l'analyse est typiquement utilisé comme base dans l'analyse sémantique, construisant une représentation du sens du texte, ou directement dans des applications telles que la correction grammaticale.
Pour un système de réponse aux questions ou de recherche d'informations, il serait par exemple difficile de répondre correctement à la demande « quels ouvrages ont été écrits par des auteurs francophones avant 1900 ? » sans reconnaitre le sujet « ouvrages », car il faut notamment comprendre que l'utilisateur désire une liste d'ouvrages et non une liste d'auteurs.
Le processus d'analyse peut se reposer sur une grammaire formelle et/ou faire appel à des méthodes statistiques.
Historique L’analyse syntaxique remonte aux débuts de la recherche en TALN, puisqu’un des premiers algorithmes d’analyse fut introduit par Victor Yngve en 1955, avant même le développement de la théorie des langages formels par Noam Chomsky en 1956. Dès lors, les analyseurs créés vont se fonder sur les grammaires formelles, particulièrement celles dites hors contexte ou de type 2. Entre autres, John Cocke a inventé un algorithme de programmation dynamique en 1960, qui fut ensuite formalisé par T. Kasami (1965)Tadao Kasami, « An efficient recognition and syntax algorithm for context-free languages », Technical Report AFCLR-65-758, Air Force Cambridge Research Laboratory, 1965 et D. H. Younger (1967)D. H. Younger, « Recognition of context-free languages in time n3 », Information and Control, 10, , 1967, 189-208. : le célèbre algorithme CKY, analysant une séquence en temps cubique grâce aux grammaires en Forme normale de Chomsky. Ce dernier est de type mixte, c’est-à-dire combinant les stratégies ascendantes et descendantes, individuellement moins efficaces.
Parallèlement, dans les années 1960, plusieurs autres formalismes destinés à l’analyse syntaxique voient le jour, dont les grammaires de dépendances inspirées par Lucien Tesnière (1959) et formalisées avant tout par David Hays (1960). Peu après N. Chomsky, John Backus (1959) et Peter Naur (1960) ont indépendamment réinventé les grammaires hors contexte dans leur description du langage ALGOL, donnant lieu à la célèbre forme de Backus-Naur. En 1968, Jay Earley inventa le premier algorithme d’analyse syntaxique en temps cubique pour toutes les grammaires hors contexte (pas nécessairement en forme normale)Jay Earley, « An efficient context-free parsing algorithm », In : Communications of the ACM 13 (2), p. 94-102, 1970. À la même époque, R. KaplanRonald M. Kaplan, « A general syntactic processor », In : Natural Language Processing, Sous la dir. de R. Rustin, Algorithmics Press, p. 193-241, 1973 et M. KayMartin Kay, « Algorithm Schemata and Data Structures in Syntactic Processing », Report CSL–80–12, Xerox PARC, 1980 ont généralisé l’algorithme CKY à toutes les grammaires hors contexte pour en faire le chart parser, utilisant un graphe. Parmi les algorithmes similaires aux deux précédents, on peut encore citer celui du coin gauche (left-corner parser), en référence au premier symbole de la partie droite d’une règle de productionAlan Demers, « Generalized Left Corner Parsing », In : Proceedings of the 4th ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages, ACM, p. 170-182, 1977.
Beaucoup d’autres formalismes ont été développés durant les années 1970-1980, dont les réseaux de transition augmentés (ATN), et les grammaires d’unification (Constraint-Based Grammars). Une représentation en dépendances de ces dernières a été originairement proposée par H. MaruyamaHiroshi Maruyama, « Structural disambiguation with constraint propagation », In : Proceedings of the 28th Meeting of the Association for Computational Linguistics, Association for Computational Linguistics, p. 31-38, 1990. Durant les années 1990, les développements furent principalement tournés vers les méthodes statistiques, dont un travail important autour des grammaires hors contexte probabilistes (PCFG)T. L. Booth et R. A. Thompson, « Applying Probability Measures to Abstract Languages », In : IEEE Transactions on Computers 22.5, p. 442-450, 1973 — un des modèles d’analyse statistique parmi les plus influents, qui est basé sur une grammaire formelle — dont les problèmes principaux sont l’ignorance des informations sémantiques et l’hypothèse d’indépendance de l’attachement structurel des syntagmes. Certaines approches plus récentes ont permis d’améliorer les faiblesses des PCFG par la lexicalisation de la grammaireEugene Charniak, « Statistical parsing with a context-free grammar and word statistics », In : Proceedings of 14th National Conference on Artificial Intelligence, Association for Computational Linguistics, p. 598-603, 1997, ou l’utilisation d’un jeu plus précis de symboles non terminauxDan Klein et Christopher D. Manning, « Accurate unlexicalized parsing », In : Proceedings of the 41st Annual Meeting on Association for Computational Linguistics, Association for Computational Linguistics., 2003, entre autres. Du côté de la représentation en dépendances, le premier algorithme stochastique influant fut proposé par Jason EisnerJason M. Eisner, « Three New Probabilistic Models for Dependency Parsing : An Exploration », In : Proceedings of the 16th International Conference on Computational Linguistics, Association for Computational Linguistics, p. 340-345, 1996.
Pour les méthodes qui ne requièrent pas l’intervention d’une grammaire, les modèles sont directement induits depuis des données annotées (corpus), ce qui facilite le portage des systèmes à de nouvelles langues ou domaines. Bien que cette dernière possibilité soit majoritairement utilisée de nos jours, les méthodes basées sur des grammaires restent utilisées lorsqu’il n’existe pas suffisamment de données annotées nécessaires au fonctionnement des méthodes supervisées. Notons au passage qu’une grammaire peut très bien être extraite de données linguistiques ; les méthodes basées sur les grammaires (grammar-based parsing) et celles guidées par des données (data-driven parsing) ne sont donc pas mutuellement exclusives. La catégorisation suggérée des méthodes statistiques d’analyse est très répandue dans le domaine du TALNJoakim Nivre, « Statistical Parsing », In : Handbook of Natural Language Processing, Sous la dir. de Nitin Indurkhya et Fred J. Damerau, 2nd, Chapman & Hall/CRC, Chap. 11, p. 237-266, 2010.
Difficultés L'analyse syntaxique est une tâche non triviale, principalement en raison de l’ambiguïté intrinsèque de la langue et de sa diversité. Un énoncé est dit ambigu si plusieurs structures linguistiques peuvent y être associées.
Voici quelques exemples d’ambiguïtés structurelles : Dans cette phrase, l'attachement du syntagme prépositionnel est ambigu, et on ne sait pas si Jean a utilisé un télescope pour voir l'homme, ou si Jean a vu un homme utilisant lui-même un télescope. La question précédente pourrait être paraphrasée de deux façons: « Vous avez promis d’écrire à qui ? » ou « Vous avez promis à qui d’écrire ? » ; on ne sait pas si la personne en question va écrire à quelqu'un, ou si elle a promis à quelqu'un d'écrire (quelque chose).
Lien avec l'analyse d'un langage formel Même si le but de l'analyse syntaxique d'un langage formel déterministe (p. ex. langage de programmation) est identique à celui de l'analyse syntaxique de la langue naturelle, la tâche est nettement plus ardue dans le second cas.
Premièrement, la capacité générative d’une grammaire — sa puissance — est beaucoup plus faible dans le cas des langages informatiques, car ceux-ci doivent être strictement non ambigus et rapidement analysables (donc la grammaire est restreinte). Comparativement, une grammaire prévue pour la langue naturelle doit permettre par exemple d’exprimer des dépendances entre des mots éloignés les uns des autres ; elle est donc plus complexe.
Deuxièmement, comme la langue naturelle souffre d’une ambiguïté structurelle, à chaque étape de l’analyse, plusieurs règles de la grammaire seront probablement applicables. Ainsi, une phrase telle que « Jean a vu l’homme [sur la colline] [avec un télescope] [accompagné de sa fille] [...] » verra le nombre de ses analyses possibles augmenter exponentiellement avec le nombre de constituants ajoutésKenneth Church et Ramesh Patil, « Coping with syntactic ambiguity or how to put the block in the box on the table », Comput. Linguist. 8, 3-4, 139-149, 1982. Au passage, c’est une des raisons qui a poussé le développement des méthodes statistiques.
La dernière différence notable se situe au niveau de la validité de la séquence d’entrée : un langage de programmation possède un nombre fini de constructions valides, alors qu’il est illimité pour une langue naturelle. De ce fait, l’impossibilité de produire une analyse existe dans le cas du TALN, erreur qui n’est d'ailleurs pas nécessairement due à une grammaire inadéquate, mais possiblement à une erreur grammaticale, une faute de frappe, un mot inconnu, etc.
Outre ces dissemblances caricaturales, de nombreuses autres existent, comme la délimitation stricte des « phrases » (déclarations, blocs) et mots dans le cas des langages formels avec des caractères bien définis.
Méthodes classiques
Méthodes purement basées sur une grammaire La majorité des premiers systèmes d'analyse syntaxique se fondent exclusivement sur une grammaire indépendante de contexte (context-free grammar) pour générer des structures syntaxiques correctes, bien que ce type de grammaire ne soit pas suffisant pour engendrer la langue naturelle dans son ensembleTypiquement, les dépendances croisées (ou non-projectives) — apparaissant dans certaines langues — ne peuvent pas être obtenues avec une grammaire de type 2. La langue naturelle est par conséquent de type 1 (contextuelle), mais néanmoins très proche du type 2.. Conjointement, il est nécessaire d'avoir un algorithme qui dicte comment ces structures seront efficacement produites. Dans ce cadre-là, l’algorithme de programmation dynamique CKY est énormément utilisé, dans lequel les sous-problèmes — maintenus dans un tableau — sont représentés par les arbres syntaxiques partiels enracinés sur les syntagmes de la phrase d'entrée. Grâce à la nature indépendante du contexte des grammaires, il est possible de réutiliser une sous-structure dans les dérivations suivantes qui la demande, rendant possible la programmation dynamique. Les algorithmes concurrents à CKY sont celui d'Earley et le chart parsing.
Méthodes aidées par la statistique Le problème des algorithmes assimilés à CKY est leur incapacité à résoudre les ambiguïtés structurelles (voir section « difficultés »), bien qu'il soit possible de les détecter. Pour pallier ce manque, il est nécessaire d'ajouter une composante statistique au modèle; si chaque règle est accompagnée d'une probabilité, il suffit de sélectionner celle avec la probabilité la plus haute en cas d'ambiguïté. À ce titre, le formalisme le plus usité est la grammaire indépendante de contexte probabiliste (probabilistic context-free grammar ou PCFG). Une version probabiliste de l'algorithme CKY existe, décrit avant tout par H. NeyH. Ney, « Dynamic programming parsing for context-free grammars in continuous speech recognition », IEEE Transactions on Signal Processing, 39(2), 336–340, 1991.. L'inférence exacte nécessite un temps en , où représente le nombre de règles de la grammaire.