Worldlex Wiki Ce terme revêt des significations légèrement différentes selon les branches de la linguistique et de l'informatique . L'analyse syntaxique traditionnelle est souvent utilisée pour comprendre le sens précis d'une phrase ou d'un mot, parfois à l'aide d'outils tels que les diagrammes de phrases . Elle met généralement l'accent sur l'importance des divisions grammaticales comme le sujet et le prédicat .
En linguistique informatique, le terme désigne l'analyse formelle par ordinateur d'une phrase ou d'une autre chaîne de mots en ses constituants, aboutissant à un arbre d'analyse syntaxique montrant leurs relations syntaxiques et pouvant également contenir des informations sémantiques . Certains algorithmes d'analyse syntaxique génèrent une forêt d'analyse ou une liste d'arbres d'analyse à partir d'une chaîne syntaxiquement ambiguë .
Le terme est également utilisé en psycholinguistique pour décrire la compréhension du langage. Dans ce contexte, l'analyse syntaxique désigne la manière dont les êtres humains analysent une phrase ou un syntagme (à l'oral ou à l'écrit) « en termes de constituants grammaticaux, en identifiant les parties du discours, les relations syntaxiques, etc. » Ce terme est particulièrement courant lorsqu'on aborde les indices linguistiques qui aident les locuteurs à interpréter les phrases ambiguës .
En informatique, ce terme est utilisé dans l'analyse des langages informatiques , désignant l'analyse syntaxique du code source en ses composantes afin de faciliter l'écriture des compilateurs et des interpréteurs . Il peut également servir à décrire une division ou une séparation.
En analyse de données, ce terme est souvent utilisé pour désigner un processus d'extraction d'informations souhaitées à partir de données, par exemple la création d'un signal de série temporelle à partir d'un document XML .
parties du discours, en expliquant la forme, la fonction et la relation syntaxique de chaque partie. Cette décomposition repose en grande partie sur l'étude des conjugaisons et des déclinaisons de la langue , qui peuvent être très complexes pour les langues à flexion riche . Pour analyser une phrase comme « un homme mord un chien », il faut noter que le nom singulier « homme » est le sujet de la phrase, le verbe « mord » est la troisième personne du singulier du présent du verbe « mordre », et le nom singulier « chien » est le complément d'objet direct. Des techniques telles que les diagrammes de phrase sont parfois utilisées pour indiquer les relations entre les éléments de la phrase.L'analyse grammaticale était autrefois au cœur de l'enseignement de la grammaire dans tout le monde anglophone et était largement considérée comme fondamentale pour l'utilisation et la compréhension de la langue écrite.de traduction automatique et de traitement automatique du langage naturel , les textes écrits en langues humaines sont analysés par des programmes informatiques. Les phrases humaines ne sont pas facilement analysables par les programmes, car la structure du langage humain présente une ambiguïté considérable. Son usage consiste à transmettre du sens (ou de la sémantique ) parmi un éventail potentiellement illimité de possibilités, dont seules certaines sont pertinentes dans le cas présent. Ainsi, l'énoncé « Un homme mord un chien » est clair sur un point précis, contrairement à l'énoncé « Un chien mord un homme ». Dans une autre langue, il pourrait apparaître comme « Un homme mord un chien », la distinction entre les deux possibilités s'appuyant alors sur le contexte plus large, si tant est que cette différence soit pertinente. Il est difficile d'établir des règles formelles pour décrire un comportement informel, même s'il est évident que certaines règles sont respectées.grammaire à utiliser. Le choix de la syntaxe est influencé par des considérations à la fois linguistiques et informatiques ; par exemple, certains systèmes d'analyse syntaxique utilisent une grammaire lexicale fonctionnelle , mais en général, l'analyse syntaxique pour ce type de grammaire est connue pour être NP-complète . La grammaire de structure de syntagme pilotée par la tête est un autre formalisme linguistique populaire dans la communauté de l'analyse syntaxique, mais d'autres travaux de recherche se sont concentrés sur des formalismes moins complexes, comme celui utilisé dans le Penn Treebank . L'analyse syntaxique superficielle vise uniquement à identifier les frontières des constituants principaux, tels que les syntagmes nominaux. Une autre stratégie courante pour éviter les controverses linguistiques est l'analyse syntaxique par grammaire de dépendance .
corpus de données d’entraînement préalablement annoté (analysé manuellement). Cette approche permet au système de recueillir des informations sur la fréquence d’apparition de différentes constructions dans des contextes spécifiques (voir apprentissage automatique ) . Parmi les approches utilisées, on peut citer les grammaires hors contexte probabilistes ( PCFG ) classiques , l’entropie maximale et les réseaux de neurones . La plupart des systèmes les plus performants utilisent des statistiques lexicales (c’est-à-dire qu’ils prennent en compte l’identité des mots impliqués, ainsi que leur catégorie grammaticale ). Cependant, ces systèmes sont sensibles au surapprentissage et nécessitent un lissage pour être efficaces.hors contexte , une approximation hors contexte de la grammaire est utilisée pour effectuer une première passe. Les algorithmes utilisant des grammaires hors contexte s'appuient souvent sur une variante de l' algorithme CYK , généralement avec une heuristique pour éliminer les analyses improbables et gagner du temps (voir l'analyse syntaxique par diagrammes ). Cependant, certains systèmes privilégient la précision à la vitesse, en utilisant par exemple des versions linéaires de l' algorithme de décalage-réduction . Une approche relativement récente consiste de compréhension du langage naturel , les analyseurs sémantiques convertissent le texte en une représentation de sa signification.
Psycholinguistique
En psycholinguistique , l'analyse syntaxique ne se limite pas à l'attribution de mots à des catégories (formation d'intuitions ontologiques), mais implique également l'évaluation du sens d'une phrase selon les règles syntaxiques déduites de chaque mot qui la compose (ce que l'on appelle la connotation ). Ce processus se déroule généralement lors de la perception orale ou écrite des mots.
En neurolinguistique, l'analyse syntaxique est généralement considérée comme une fonction de la mémoire de travail. Autrement dit, elle permet de maintenir simultanément en mémoire plusieurs éléments d'une phrase, tous facilement accessibles pour analyse ultérieure. La mémoire de travail humaine ayant ses limites, l'analyse syntaxique des phrases présente également des limitations. Plusieurs types de phrases syntaxiquement complexes illustrent ce phénomène et mettent en évidence les difficultés potentielles de leur analyse mentale.
Le premier type de phrase, et peut-être le plus connu, qui met à l'épreuve les capacités d'analyse syntaxique est la phrase ambiguë. Ces phrases sont conçues de telle sorte que leur interprétation la plus courante semble grammaticalement incorrecte, mais qu'à y regarder de plus près, elles sont en réalité correctes. Les phrases ambiguës sont difficiles à analyser car elles contiennent un groupe de mots ou un mot polysémique, dont le sens le plus courant appartient souvent à une autre catégorie grammaticale. Par exemple, dans la phrase « the horse raced past the barn fell », « raced » est d'abord interprété comme un verbe au passé, mais dans cette phrase, il fait partie d'un groupe adjectival. L'analyse syntaxique servant à identifier les catégories grammaticales, ces phrases représentent un défi pour les capacités d'analyse du lecteur.
Un autre type de phrase difficile à analyser est une ambiguïté d'attachement, qui comprend une phrase qui pourrait potentiellement modifier différentes parties d'une phrase et présente donc un défi pour identifier la relation syntaxique (c'est-à-dire « Le garçon a vu la dame avec le télescope », dans lequel la phrase ambiguë avec le télescope pourrait modifier le garçon a vu ou la dame).
Un troisième type de phrase qui met à l'épreuve la capacité d'analyse syntaxique est l'encastrement central, dans lequel des syntagmes sont placés au centre d'autres syntagmes de forme similaire (ex. : « Le rat le chat l'homme a frappé poursuivi couru dans le piège »). Les phrases comportant 2 ou, dans les cas les plus extrêmes, 3 encastrements centraux sont difficiles à analyser mentalement, là encore en raison de l'ambiguïté des relations syntaxiques.
En neurolinguistique, plusieurs théories visent à décrire le processus d'analyse syntaxique dans le cerveau. L'un de ces modèles, plus traditionnel, est un modèle génératif du traitement des phrases. Ce modèle postule l'existence, au sein du cerveau, d'un module distinct dédié à l'analyse syntaxique. Ce module est précédé par l'accès à la reconnaissance et à la récupération lexicale, puis suivi d'un traitement syntaxique qui considère un résultat syntaxique unique et ne révise cette interprétation qu'en cas de problème potentiel. Le modèle opposé, plus contemporain, postule que le traitement d'une phrase n'est ni modulaire ni strictement séquentiel. Il postule plutôt que plusieurs possibilités syntaxiques peuvent être envisagées simultanément, car l'accès lexical, le traitement syntaxique et la détermination du sens se déroulent en parallèle dans le cerveau. Ces processus sont ainsi intégrés.
Bien que la neurologie de l'analyse syntaxique reste encore largement à explorer, des études ont mis en évidence le rôle potentiel de plusieurs régions cérébrales dans ce processus. Il s'agit notamment du pôle temporal antérieur gauche, du gyrus frontal inférieur gauche, du gyrus temporal supérieur gauche, du gyrus frontal supérieur gauche, du cortex cingulaire postérieur droit et du gyrus angulaire gauche. Bien que cela n'ait pas été formellement démontré, il a été suggéré que ces différentes structures pourraient favoriser soit l'analyse syntaxique par syntagme, soit l'analyse syntaxique par dépendance, ce qui signifie que différents types d'analyse pourraient être traités différemment, selon des mécanismes encore inconnus.
Analyse du discours
L'analyse du discours étudie les méthodes d'analyse de l'usage du langage et des phénomènes sémiotiques. Le langage persuasif peut être qualifié de rhétorique .
Langages informatiques
L'entrée d'un analyseur syntaxique est généralement du texte écrit dans un langage informatique , mais peut également s'agir de texte en langage naturel ou de données textuelles moins structurées. Dans ce cas, seules certaines parties du texte sont généralement extraites, plutôt que de construire un arbre d'analyse syntaxique. Les analyseurs syntaxiques vont de fonctions très simples comme ` scanf` à des programmes complexes tels que l'interface d'un compilateur C++ ou l' analyseur HTML d'un navigateur web . Une catégorie importante d'analyse syntaxique simple repose sur l'utilisation d'expressions régulières . Un ensemble d'expressions régulières définit un langage régulier , et un moteur d'expressions régulières génère automatiquement un analyseur syntaxique pour ce langage, permettant la reconnaissance de motifs et l'extraction de texte. Dans d'autres contextes, les expressions régulières sont utilisées avant l'analyse syntaxique, lors de l'étape d'analyse lexicale dont le résultat est ensuite utilisé par l'analyseur.
L'utilisation des analyseurs syntaxiques varie selon le type de données d'entrée. Dans le cas des langages de données, un analyseur syntaxique est souvent intégré au module de lecture de fichiers d'un programme, comme pour la lecture de texte HTML ou XML ; il s'agit alors de langages de balisage . Dans le cas des langages de programmation , un analyseur syntaxique est un composant d'un compilateur ou d'un interpréteur , qui analyse le code source du langage pour créer une représentation interne ; l'analyseur syntaxique est une étape clé du processus de compilation . Les langages de programmation sont généralement spécifiés à l'aide d'une grammaire déterministe hors contexte, car cela permet d'écrire des analyseurs syntaxiques rapides et efficaces. Pour les compilateurs, l'analyse syntaxique peut être effectuée en une ou plusieurs passes (voir compilateur à une passe et compilateur à plusieurs passes ).
Les inconvénients inhérents à un compilateur à une seule passe peuvent être largement surmontés par l'ajout de correctifs . Ces correctifs permettent la relocalisation du code lors de la passe avant et sont appliqués en sens inverse une fois le segment de programme courant considéré comme terminé. Un exemple d'utilisation d'un tel mécanisme de correctif serait une instruction GOTO avant, dont la cible est inconnue jusqu'à la fin du segment de programme. Dans ce cas, l'application du correctif serait différée jusqu'à ce que la cible soit identifiée. À l'inverse, une instruction GOTO arrière ne nécessite aucun correctif, car son emplacement est déjà connu.
Les grammaires hors contexte sont limitées dans leur capacité à exprimer toutes les exigences d'un langage. En termes simples, cela tient au fait que la mémoire d'un tel langage est limitée. La grammaire ne peut pas se souvenir de la présence d'une construction sur une entrée arbitrairement longue ; or, ceci est nécessaire pour un langage où, par exemple, un nom doit être déclaré avant de pouvoir être référencé. Cependant, les grammaires plus puissantes capables d'exprimer cette contrainte ne peuvent pas être analysées efficacement. C'est pourquoi une stratégie courante consiste à créer un analyseur syntaxique souple pour une grammaire hors contexte, qui accepte un sur-ensemble des constructions du langage souhaité (c'est-à-dire qu'il accepte certaines constructions invalides) ; ces constructions indésirables peuvent ensuite être filtrées lors de l' analyse sémantique (analyse contextuelle).
Par exemple, en Python , le code suivant est syntaxiquement valide :
L’exemple suivant illustre le cas courant de l’analyse syntaxique d’un langage informatique comportant deux niveaux de grammaire : lexicale et syntaxique.
La première étape est la génération de jetons, ou analyse lexicale , qui consiste à diviser le flux de caractères d'entrée en symboles significatifs définis par une grammaire d' expressions régulières . Par exemple, un programme de calculatrice analyserait une entrée telle que «12 * (3 + 4)^2 » et la diviserait en jetons12 : , *, (, 3, +, 4, ), ^, 2, chacun étant un symbole significatif dans le contexte d'une expression arithmétique. L'analyseur lexical contiendrait des règles indiquant que les caractères *, +, ^, (et )marquent le début d'un nouveau jeton, de sorte que des jetons sans signification comme «12* » ou «(3 » ne seraient pas générés.
L'étape suivante est l'analyse syntaxique, qui consiste à vérifier que les jetons forment une expression valide. Cette analyse s'effectue généralement à l'aide d'une grammaire hors contexte qui définit récursivement les composants pouvant constituer une expression et l'ordre dans lequel ils doivent apparaître. Cependant, toutes les règles définissant les langages de programmation ne peuvent être exprimées uniquement par des grammaires hors contexte, comme la validité des types et la déclaration correcte des identificateurs. Ces règles peuvent être exprimées formellement à l'aide de grammaires d'attributs .
La phase finale est l'analyse sémantique , qui consiste à déterminer les implications de l'expression validée et à prendre les mesures appropriées. Dans le cas d'une calculatrice ou d'un interpréteur, cette action consiste à évaluer l'expression ou le programme ; un compilateur, quant à lui, génère du code. Les grammaires d'attributs peuvent également servir à définir ces actions.
Types d'analyseurs syntaxiques
La tâche de l'analyseur syntaxique consiste essentiellement à déterminer si et comment l'entrée peut être déduite du symbole de départ de la grammaire. Cela peut se faire de deux manières principales :
- Analyse descendante
- L'analyse syntaxique descendante peut être vue comme une tentative de trouver les dérivations les plus à gauche d'un flux d'entrée en recherchant des arbres d'analyse syntaxique à l'aide d'une expansion descendante des règles grammaticales formelles données . Les jetons sont traités de gauche à droite. Le choix inclusif est utilisé pour gérer l'ambiguïté en développant toutes les alternatives possibles pour les membres droits des règles grammaticales. Cette approche est connue sous le nom de « soupe primordiale ». Très similaire à la diagrammation de phrases, la « soupe primordiale » décompose les constituants des phrases.
- Analyse ascendante
- Un analyseur syntaxique peut partir de l'entrée et tenter de la réécrire jusqu'au symbole de départ. Intuitivement, l'analyseur cherche à localiser les éléments les plus élémentaires, puis les éléments qui les contiennent, et ainsi de suite. Les analyseurs LR sont des exemples d'analyseurs ascendants. Ce type d'analyseur est également appelé analyse par décalage-réduction .
Les analyseurs LL et l'analyseur à descente récursive sont des exemples d'analyseurs descendants incapables de gérer les règles de production récursives à gauche . Bien qu'il ait été admis que les implémentations simples d'analyse descendante ne pouvaient pas prendre en charge la récursivité gauche directe et indirecte et pouvaient nécessiter une complexité temporelle et spatiale exponentielle lors de l'analyse de grammaires hors contexte ambiguës , des algorithmes plus sophistiqués d'analyse descendante ont été créés par Frost, Hafiz et Callaghan Ces algorithmes prennent en charge l'ambiguïté et la récursivité gauche en temps polynomial et génèrent des représentations de taille polynomiale du nombre potentiellement exponentiel d'arbres d'analyse. Leur algorithme est capable de produire les dérivations les plus à gauche et les plus à droite d'une entrée par rapport à une grammaire hors contexte donnée .
Une distinction importante concernant les analyseurs syntaxiques est de savoir si un analyseur génère une dérivation la plus à gauche ou la plus à droite (voir grammaire hors contexte ). Les analyseurs LL génèrent une dérivation la plus à gauche et les analyseurs LR génèrent une dérivation la plus à droite (généralement dans l'ordre inverse).
QuelquesDes algorithmes d'analyse graphique ont été conçus pourles langages de programmation visuels. Les analyseurs syntaxiques pour les langages visuels sont parfois basés surdes grammaires de graphes.
Des algorithmes d'analyse adaptatifs ont été utilisés pour construire des interfaces utilisateur en langage naturel « auto-extensibles » .
Mise en œuvre
Une implémentation d'analyseur syntaxique simple lit l'intégralité du fichier d'entrée, effectue un calcul ou une traduction intermédiaire, puis écrit l'intégralité du fichier de sortie, comme les compilateurs multi-passes en mémoire .
Approches alternatives d'implémentation de l'analyseur syntaxique :
- Les analyseurs syntaxiques de type « push » appellent les gestionnaires enregistrés ( fonctions de rappel ) dès qu'ils détectent des jetons pertinents dans le flux d'entrée. Un analyseur syntaxique de type « push » peut ignorer les parties de l'entrée qui ne sont pas pertinentes (par exemple, Expat ).
- les analyseurs syntaxiques , tels que les analyseurs syntaxiques généralement utilisés par les interfaces des compilateurs en « extrayant » le texte d'entrée.
- les analyseurs incrémentaux (tels que les analyseurs de graphiques incrémentaux ) qui, lorsque le texte du fichier est modifié par un utilisateur, n'ont pas besoin de réanalyser complètement l'intégralité du fichier.
- Analyseurs syntaxiques actifs versus passifs
Logiciel de développement d'analyseurs syntaxiques
Perspectives
LL , LR et LALR , où elle est souvent explicitement indiquée en l'ajoutant entre parenthèses au nom de l'algorithme, comme dans LALR(1).La plupart des langages de programmation , cibles principales des analyseurs syntaxiques, sont soigneusement définis de manière à ce qu'un analyseur syntaxique à anticipation limitée (généralement une seule) puisse les analyser, car ces analyseurs sont souvent plus efficaces. Un changement important dans cette tendance est survenu en 1990 lorsque Terence Parr a créé ANTLR pour sa thèse de doctorat : un générateur d'analyseurs syntaxiques pour les analyseurs LL( k ) efficaces, où k est une valeur fixe quelconque.
Les analyseurs LR n'effectuent généralement que quelques actions après la rencontre de chaque jeton : décalage (ajouter ce jeton à la pile pour une réduction ultérieure), réduction (dépiler les jetons et former une construction syntaxique), fin, erreur (aucune règle connue ne s'applique) ou conflit (l'analyseur ne sait pas s'il doit effectuer un décalage ou une réduction).
La prévision présente deux avantages.L'ensemble des règles d'analyse syntaxique des expressions (appelé grammaire) est le suivant :
Règle 1 : E → E + E L'expression est la somme de deux expressions. Règle 2 : E → E * E Une expression est le produit de deux expressions. Règle 3 : E → nombre L'expression est un nombre simple Règle 4 : + a moins de priorité que * La plupart des langages de programmation (à l'exception de quelques-uns comme APL et Smalltalk) et des formules algébriques privilégient la multiplication à l'addition ; dans ce cas, l'interprétation correcte de l'exemple ci-dessus est les analyseurs LALR .