Document (in-progress).
Analyse syntaxique
Anatomie d'un analyseur syntaxique
L'analyse syntaxique (parsing) permet de passer d'un texte (fichier
ou chaîne de caractères) à un arbre de syntaxe abstraite.
On procède généralement en deux étapes
-
Analyse lexicale : reconnaître les mots (lexèmes)
du texte (analyse lexicale).
-
Analyse syntaxique : reconnaître la structure (syntaxe
abstraite) du texte (analyse
syntaxique) en appliquant la grammaire
du langage.
1. Analyse lexicale
La conversion texte => lexèmes doit :
-
Segmenter le texte pour isoler mots, symboles, et marques de ponctuation.
-
Supprimer les blancs et commentaires.
-
Reconnaître les différentes classes de lexèmes (identificateurs,
nombres,...).
-
Reconnaître parmi les identificateurs les mots-clés du langage
En général 1-3 sont réalisés simultanément.
Pour une présentation des problèmes associés à
la segmentation on se reportera au thème n°5.
Analyse lexicale
Partie à développer.
2. Analyse syntaxique
Partie à développer.
Tâches à effectuer
Vérifier que la suite de mots est bien formée.
Chercher à reconstruire la structure du texte pour pouvoir l'utiliser..
-
L'ensemble des phrases correctes est décrite par une grammaire
formelle.
-
Le résultat de l'analyse est un arbre de syntaxe abstraite.
La vérification et surtout la construction de l'arbre ne sont pas
toujours possibles; attention aux grammaires ambigües.
Grammaire
On décrit l'ensemble des phrases par des équations récurrentes.
Syntaxe abstraite
On cherche à construire l'arbre d'analyse d'une suite de mot par
cette grammaire, ou, plus précisément, une version simplifiée
de l'arbre d'analyse (on élimine les parenthèses, par exemple).
Analyse descendante
On calque l'organisation des procédures récursives sur la
grammaire, en utilisant les littéraux de la grammaire pour orienter
les choix.
Analyse ascendante
On peut aussi diriger l'analyse par le texte, plutôt que par la grammaire.
-
On tente alors de réduire, autant que possible, un segment
initial du texte, en utilisant les règles de grammaires inversées
-
Ceci est équivalent à analyser le texte avec un automate
qui peut empiler son état.