méthodes traditionnelles L'exercice grammatical traditionnel d'analyse syntaxique, parfois appelé analyse de la proposition , consiste à décomposer un texte en ses parties du di...
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.
Méthodes de calcul
Dans certains systèmes 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.
Pour analyser des données en langage naturel, les chercheurs doivent d'abord s'accorder sur la 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 .
Analyseur syntaxique
x : int = 1 print ( x )
Le code suivant, cependant, est syntaxiquement valide au regard de la grammaire hors contexte, produisant un arbre syntaxique ayant la même structure que le précédent, mais il enfreint la règle sémantique exigeant que les variables soient initialisées avant leur utilisation :
x : int = 1 print ( y )
Aperçu du processus
Flux de données dans un analyseur syntaxique typique
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 :
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.
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).
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 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
Programme C impossible à analyser avec moins de deux jetons anticipés. En haut : extrait de la grammaire C. En bas : un analyseur syntaxique a traité les jetons « » et s’apprête à choisir une règle pour dériver Stmt . En se basant uniquement sur le premier jeton anticipé « », il ne peut déterminer laquelle des deux alternatives Stmt choisir ; cette dernière nécessite l’examen du deuxième jeton.intv;main(){v
La règle de prédiction (lookahead) détermine le nombre maximal de jetons entrants qu'un analyseur syntaxique peut utiliser pour choisir la règle à appliquer. Elle est particulièrement importante pour les analyseurs 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.
Cela permet à l'analyseur syntaxique de prendre la décision appropriée en cas de conflit. Par exemple, analyser une instruction « if » en présence d'une clause « else ».
Cela élimine de nombreux états dupliqués et allège la charge d'une pile supplémentaire. Un analyseur syntaxique sans anticipation du langage AC comportera environ 10 000 états. Un analyseur syntaxique avec anticipation en comportera environ 300.
Exemple : Analyse de l'expression . Notez que la règle 4 ci-dessus est une règle sémantique. Il est possible de reformuler la grammaire pour l'intégrer à la syntaxe. Cependant, toutes les règles de ce type ne sont pas traduisibles en syntaxe.
Actions d'analyse syntaxique simples sans anticipation
Entrée initiale = [1, +, 2, *, 3]
Déplacer « 1 » sur la pile à partir de l’entrée (en prévision de la règle 3). Entrée = [+, 2, *, 3] Pile = [1]
Réduit « 1 » à l’expression « E » selon la règle 3. Pile = [E]
Déplacer le caractère « + » de l'entrée sur la pile (en prévision de la règle 1). Entrée = [2, *, 3] Pile = [E, +]
Déplacer « 2 » sur la pile à partir de l’entrée (en prévision de la règle 3). Entrée = [*, 3] Pile = [E, +, 2]
Réduisez l'élément de pile « 2 » à l'expression « E » selon la règle 3. Pile = [E, +, E]
Réduire les éléments de la pile [E, +, E] et la nouvelle entrée « E » à « E » selon la règle 1. Pile = [E]
Déplacer « * » sur la pile à partir de l'entrée (en prévision de la règle 2). Entrée = [3] Pile = [E,*]
Déplacer « 3 » sur la pile à partir de l’entrée (en prévision de la règle 3). Entrée = [] (vide) Pile = [E, *, 3]
Réduisez l'élément de pile « 3 » à l'expression « E » selon la règle 3. Pile = [E, *, E]
Réduire les éléments de la pile [E, *, E] et la nouvelle entrée « E » à « E » selon la règle 2. Pile = [E]
L'arbre d'analyse syntaxique et le code qui en résulte ne sont pas corrects selon la sémantique du langage.
Pour effectuer une analyse syntaxique correcte sans prévisualisation, il existe trois solutions :
L'utilisateur doit encadrer les expressions par des parenthèses. Cette solution est souvent impraticable.
L'analyseur syntaxique doit intégrer une logique plus poussée pour revenir en arrière et réessayer lorsqu'une règle est enfreinte ou incomplète. Une méthode similaire est utilisée dans les analyseurs LL.
Autrement, l'analyseur syntaxique ou la grammaire doit intégrer une logique supplémentaire pour différer la réduction et ne l'effectuer que lorsqu'il est absolument certain de la règle à appliquer en premier. Cette méthode est utilisée dans les analyseurs LR. Elle analyse correctement l'expression, mais avec un nombre d'états beaucoup plus important et une profondeur de pile accrue.
actions du parseur Lookahead
Insérer 1 sur la pile de l'entrée 1 en prévision de la règle 3. La réduction n'est pas immédiate.
Réduisez l'élément 1 de la pile à une expression simple sur l'entrée + selon la règle 3. L'assertion étant +, nous sommes sur le chemin vers E +, et pouvons donc réduire la pile à E.
Décaler + sur la pile lors de l'entrée + en prévision de la règle 1.
Décaler 2 sur la pile de l'entrée 2 en prévision de la règle 3.
Réduisez l'élément 2 de la pile à l'expression sur l'entrée * selon la règle 3. L'assertion anticipée * attend uniquement E avant elle.
La pile contient maintenant E + E et l'entrée est toujours *. Deux options s'offrent à elle : soit un décalage selon la règle 2, soit une réduction selon la règle 1. Comme * est prioritaire sur + selon la règle 4, nous empilons * en prévision de l'application de la règle 2.
Déplacer 3 sur la pile de l'entrée 3 en prévision de la règle 3.
Réduisez l'élément de pile 3 à une expression après avoir constaté la fin de l'entrée selon la règle 3.
Réduisez les éléments de la pile E * E à E en fonction de la règle 2.
Réduire les éléments de la pile E + E à E selon la règle 1.
L'arbre d'analyse syntaxique généré est correct et tout simplement
Worldlex Wiki 
