Analyse syntaxique : types d'analyse du compilateur de haut en bas et de bas en haut
Qu’est-ce que l’analyse syntaxique ?
Analyse syntaxique est une deuxième phase du processus de conception du compilateur dans laquelle la chaîne d'entrée donnée est vérifiée pour la confirmation des règles et de la structure de la grammaire formelle. Il analyse la structure syntaxique et vérifie si l'entrée donnée est ou non dans la syntaxe correcte du langage de programmation.
Le processus d'analyse syntaxique dans la conception du compilateur intervient après la phase d'analyse lexicale. Il est également connu sous le nom d’arbre d’analyse ou d’arbre de syntaxe. Le Parse Tree est développé à l’aide d’une grammaire prédéfinie du langage. L'analyseur syntaxique vérifie également si un programme donné remplit les règles impliquées par une grammaire hors contexte. Si cela satisfait, l’analyseur crée alors l’arbre d’analyse de ce programme source. Sinon, il affichera des messages d'erreur.
Pourquoi avez-vous besoin d'un analyseur de syntaxe ?
- Vérifiez si le code est valide grammaticalement
- L'analyseur syntaxique vous aide à appliquer des règles au code
- Vous aide à vous assurer que chaque accolade d'ouverture a un solde de clôture correspondant
- Chaque déclaration a un type et ce type doit exister
Terminologie importante de l’analyseur de syntaxe
Terminologies importantes utilisées dans le processus d'analyse syntaxique :
- Phrase: Une phrase est un groupe de caractères sur un alphabet.
- Lexème : Un lexème est l'unité syntaxique de niveau le plus bas d'une langue (par exemple, total, début).
- Token: Un jeton n'est qu'une catégorie de lexèmes.
- Mots-clés et mots réservés – Il s’agit d’un identifiant qui est utilisé comme partie fixe de la syntaxe d’une instruction. C'est un mot réservé que vous ne pouvez pas utiliser comme nom de variable ou identifiant.
- Mots bruyants – Les mots parasites sont facultatifs et sont insérés dans une déclaration pour améliorer la lisibilité de la phrase.
- Commentaires – C’est une partie très importante de la documentation. Il s'affiche principalement par, /* */, ou//Blank (espaces)
- Delimiters – C'est un élément syntaxique qui marque le début ou la fin d'une unité syntaxique. Comme une déclaration ou une expression, « commencer »… » fin », ou {}.
- Jeu de caractères – ASCII, Unicode
- Identifiants – Il s’agit d’une restriction sur la longueur qui permet de réduire la lisibilité de la phrase.
- Operasymboles de tor – + et – effectue deux opérations arithmétiques de base.
- Éléments syntaxiques de la langue
Pourquoi avons-nous besoin d'une analyse syntaxique ?
Une analyse vérifie également que la chaîne d’entrée est bien formée et, si ce n’est pas le cas, la rejette.
Voici les tâches importantes effectuées par l'analyseur dans la conception du compilateur :
- Vous aide à détecter tous les types d'erreurs de syntaxe
- Trouver la position à laquelle l'erreur s'est produite
- Description claire et précise de l'erreur.
- Récupération d'une erreur pour continuer et trouver d'autres erreurs dans le code.
- Ne devrait pas affecter la compilation des programmes « corrects ».
- L'analyse doit rejeter les textes invalides en signalant les erreurs de syntaxe
Techniques d'analyse
Les techniques d'analyse sont divisées en deux groupes différents :
- Analyse descendante,
- Analyse ascendante
Analyse descendante
Dans l'analyse descendante, la construction de l'arbre d'analyse commence à la racine puis se dirige vers les feuilles.
Il existe deux types d'analyse descendante :
- Analyse prédictive :
L'analyse prédictive peut prédire quelle production doit être utilisée pour remplacer la chaîne d'entrée spécifique. L'analyseur prédictif utilise un point d'anticipation, qui pointe vers les symboles d'entrée suivants. Le retour en arrière n'est pas un problème avec cette technique d'analyse. Il est connu sous le nom d’analyseur LL(1)
- Analyse de descente récursive :
Cette technique d'analyse analyse de manière récursive l'entrée pour créer un arbre de prase. Il se compose de plusieurs petites fonctions, une pour chaque non-terminal de la grammaire.
Analyse ascendante
Dans l'analyse ascendante dans la conception du compilateur, la construction de l'arbre d'analyse commence par la feuille, puis se poursuit vers sa racine. On l'appelle également analyse par réduction de décalage. Ce type d'analyse dans la conception du compilateur est créé à l'aide de certains des outils logiciels.
Erreur – Méthodes de récupération
Erreurs courantes qui se produisent lors de l'analyse dans le logiciel système
- Lexical: Nom d'un identifiant mal saisi
- syntaxique: parenthèse déséquilibrée ou point-virgule manquant
- Sémantique: affectation de valeur incompatible
- logique: Boucle infinie et code inaccessible
Un analyseur doit être capable de détecter et de signaler toute erreur trouvée dans le programme. Ainsi, chaque fois qu'une erreur se produisait, l'analyseur. Il devrait être capable de le gérer et de continuer à analyser l'entrée restante. Un programme peut présenter les types d’erreurs suivants à différentes étapes du processus de compilation. Il existe cinq méthodes courantes de récupération d'erreur qui peuvent être implémentées dans l'analyseur.
Récupération en mode instruction
- Dans le cas où l'analyseur rencontre une erreur, il vous aide à prendre des mesures correctives. Cela permet au reste des entrées et des états d’être analysés à l’avance.
- Par exemple, l’ajout d’un point-virgule manquant intervient dans la méthode de récupération en mode instruction. Cependant, le concepteur d'analyse doit être prudent lorsqu'il effectue ces modifications, car une mauvaise correction peut conduire à une boucle infinie.
Récupération en mode panique
- Dans le cas où l'analyseur rencontre une erreur, ce mode ignore le reste de l'instruction et ne traite pas l'entrée erronée vers un délimiteur, comme un point-virgule. Il s'agit d'une méthode simple de récupération d'erreur.
- Dans ce type de méthode de récupération, l'analyseur rejette les symboles d'entrée un par un jusqu'à ce qu'un seul groupe désigné de jetons de synchronisation soit trouvé. Les jetons de synchronisation utilisent généralement des délimiteurs comme ou.
Récupération au niveau de la phrase
- Le compilateur corrige le programme en insérant ou en supprimant des jetons. Cela lui permet de procéder à l'analyse à partir de là où il se trouvait. Il effectue une correction sur l'entrée restante. Il peut remplacer un préfixe de l'entrée restante par une chaîne, ce qui aide l'analyseur à poursuivre le processus.
Productions d'erreurs
- La récupération de la production d'erreurs élargit la grammaire du langage qui génère les constructions erronées. L'analyseur effectue ensuite un diagnostic d'erreur sur cette construction.
Correction globale
- Le compilateur doit apporter le moins de modifications possible lors du traitement d'une chaîne d'entrée incorrecte. Étant donné la chaîne d'entrée a et la grammaire c incorrectes, les algorithmes rechercheront un arbre d'analyse pour une chaîne associée b. Comme certaines insertions, suppressions et modifications apportées aux jetons nécessaires pour transformer an en b, elles sont aussi minimes que possible.
Grammaire
Une grammaire est un ensemble de règles structurelles qui décrivent une langue. Les grammaires attribuent une structure à n'importe quelle phrase. Ce terme désigne également l'étude de ces règles, et ce dossier inclut la morphologie, la phonologie et la syntaxe. Il est capable de décrire de nombreuses syntaxes de langages de programmation.
Règles de grammaire des formes
- Le symbole non terminal doit apparaître à gauche d'au moins une production
- Le symbole du but ne doit jamais être affiché à droite du ::= d'une production.
- Une règle est récursive si LHS apparaît dans son RHS
Conventions de notation
Le symbole des conventions de notation peut être indiqué en plaçant l'élément entre crochets. Il s'agit d'une séquence arbitraire d'instances de l'élément qui peut être indiquée en plaçant l'élément entre accolades suivi d'un astérisque, { … }*.
Il s'agit d'un choix de l'alternative qui peut utiliser le symbole au sein de la règle unique. Il peut être placé entre parenthèses ([,] ) si nécessaire.
Deux types de zones de conventions de notation Terminal et Non-terminaux
1.Bornes :
- Lettres minuscules de l'alphabet telles que a, b, c,
- Operasymboles tels que +, -, *, etc.
- Symboles de ponctuation tels que parenthèses, dièse, virgule
- 0, 1, …, 9 chiffres
- Chaînes en gras comme id ou if, tout ce qui représente un seul symbole de terminal
2.Non-terminaux :
- Lettres majuscules telles que A, B, C
- Noms en italique minuscule : l'expression ou certains
Grammaire sans contexte
Une CFG est une grammaire récursive à gauche qui possède au moins une production du type. Les règles d'une grammaire hors contexte sont principalement récursives. Un analyseur de syntaxe vérifie si un programme spécifique satisfait ou non à toutes les règles de la grammaire sans contexte. Si tel est le cas, ces analyseurs de syntaxe de règles peuvent créer un arbre d'analyse pour ce programme.
expression -> expression -+ term expression -> expression – term expression-> term term -> term * factor term -> expression/ factor term -> factor factor factor -> ( expression ) factor -> id
Dérivation de la grammaire
La dérivation grammaticale est une séquence de règles de grammaire qui transforme le symbole de début en chaîne. Une dérivation prouve que la chaîne appartient au langage de la grammaire.
Dérivation la plus à gauche
Lorsque la forme phrasenelle d’entrée est analysée et remplacée dans l’ordre de gauche à droite, on parle de dérivation la plus à gauche. La forme phrase qui est dérivée de la dérivation la plus à gauche est appelée forme phrase à gauche.
Dérivation la plus à droite
La dérivation la plus à droite analyse et remplace l'entrée par les règles de production, de droite à gauche, séquence. C'est ce qu'on appelle la dérivation la plus à droite. La forme phrase qui dérive de la dérivation la plus à droite est connue sous le nom de forme phrase à droite.
Syntaxe vs analyseur lexical
Analyseur de syntaxe | Analyseur lexical |
---|---|
L'analyseur syntaxique traite principalement les constructions récursives du langage. | L'analyseur lexical facilite la tâche de l'analyseur syntaxique. |
L'analyseur de syntaxe fonctionne sur les jetons d'un programme source pour reconnaître les structures significatives dans le langage de programmation. | L'analyseur lexical reconnaît le jeton dans un programme source. |
Il reçoit des entrées, sous forme de jetons, provenant d'analyseurs lexicaux. | Il est responsable de la validité d'un token fourni par
l'analyseur de syntaxe |
Inconvénients de l’utilisation des analyseurs de syntaxe
- Il ne déterminera jamais si un jeton est valide ou non
- Ne vous aide pas à déterminer si une opération effectuée sur un type de jeton est valide ou non
- Vous ne pouvez pas décider que ce jeton est déclaré et initialisé avant d'être utilisé
Résumé
- L'analyse syntaxique est une deuxième phase du processus de conception du compilateur qui suit l'analyse lexicale.
- L'analyseur syntaxique vous aide à appliquer des règles au code
- Phrase, lexème, jeton, mots clés et mots réservés, mots parasites, commentaires, délimiteurs, jeu de caractères, identifiants sont quelques termes importants utilisés dans l'analyse syntaxique dans la construction du compilateur.
- Parse vérifie que la chaîne d'entrée est bien formée, et sinon, la rejette
- Les techniques d'analyse sont divisées en deux groupes différents : analyse descendante et analyse ascendante.
- Lexicale, syntaxique, sémantique et logique sont des erreurs courantes qui se produisent lors de la méthode d'analyse.
- Une grammaire est un ensemble de règles structurelles qui décrivent une langue
- Le symbole des conventions de notation peut être indiqué en plaçant l'élément entre crochets
- Une CFG est une grammaire récursive à gauche qui possède au moins une production du type
- La dérivation grammaticale est une séquence de règles de grammaire qui transforme le symbole de début en chaîne
- L'analyseur syntaxique traite principalement des constructions récursives du langage tandis que l'analyseur lexical facilite la tâche de l'analyseur syntaxique dans SGBD
- L'inconvénient de la méthode de l'analyseur de syntaxe est qu'elle ne déterminera jamais si un jeton est valide ou non.