Chapitre Introduction à la compilation
L'analyse syntaxique
Cette leçon fournit les bases pour comprendre ce qu'est l'analyse syntaxique, la notion de grammaire, de règles, d'AST et de terminaux et non terminaux.
L'analyse syntaxique
Un langage (ou code source) accepte plusieurs types de phrases
Que l'on peut voir comme un graphe
L'ensemble des phrases possible s'appelle la syntaxe.
La grammaire est la codification des règles syntaxiques d'un langage
Les expressions régulières sont une forme d'expression d'une grammaire et définit la syntaxe d'une phrase (pattern).
Généralement la grammaire est exprimée avec une syntaxe particulière.
Dans une grammaire, on distingue les tokens appelés aussi symboles : les symboles terminaux et les symboles non terminaux.
Les terminaux sont les mot clés du langage et forment l'alphabet du langage.
Exemple : set, print, let.
Les non-terminaux:
La règle est exprimée formellement par :
nomTerminal = mot
Un mot est un ensemble de nom terminaux et de terminaux.
Les grammaires sont parfois simplifiées en ignorant certains types de tokens (espaces vides, retours à la ligne).
Le principal résultat de l'analyse syntaxique (et l'application et la vérification d'une grammaire) est la construction d'un arbre syntaxique.
Les non terminaux sont les noeuds pères et les terminaux les feuilles de l'arbre.
En reprenant notre exemple précédent, nous pouvons obtenir ce type d'arbre syntaxique (AST).
Et la grammaire pourrait être exprimée ainsi :
Phrase := <Sujet> Séparateur? AdjectifPossessif? <Action> <Complement> Ponctuation
Sujet := Pronom | Prénom
Action := Verbe
Complément := NomCommun | Prénom
Principes de base d'un analyseur syntaxique :
- récupération d'un flux de tokens
- recherche d'une règle qui "matche" le flux de tokens
- cela nécessite de conserver un état (une pile) de tokens consommés et d'éventuellement revenir en arrière si la règle ne matche pas complètement
- appliquer une action sur l'arbre syntaxique construit à partir de la règle
- continuer sur le token suivant.
Les analyseurs syntaxiques existent sous trois types :
- les analyses descendantes (LL) ;
- les analyses montantes (LR) ;
- les "implémentations customs".
Les analyses descendantes consistent à partir de la racine de la grammaire et trouver une règle pour lequel le token en cours de lecture est applicable.
Limites de l’analyse descendante
- On ne peut pas toujours décider de la règle à appliquer (ambiguité)
- Aussi parfois; il faut lire plusieurs tokens en avance pour déterminer la règle à appliquer.
- Uen grammaire descendante est aussi appelée LL(x). x est le nombre de caractères maximum en avance à lire pour résoudre les règles.
- On s’intéresse aux grammaires LL(1) dans lesquelles on peut décider en fonction du premier caractère à lire m.[n].
- Les grammaires récursives gauches (X ::= Xm) ne sont pas LL(1).
- On peut parfois les transformer pour obtenir des grammaires LL(1).
Les analyses montant consistent à partir des feuilles qui sont généralement des terminaux et de remonter afin de trouver les règles qui "matchent" les tokens lus.
