Sommaire Définition du langage d’expérimentation Compilateur pour le langage Z minimal Extensions du langage Z minimal
Chapitre précédent Chapitre 4 : L’analyse syntaxique Chapitre suivant
4.2 Grammaire du langage Z minimal
4.3 Vérification de la propriété LL(1)
4.5 Forme d’une procédure récursive
4.6 Forme de l’analyseur syntaxique
4.1 Objectifs
Le but principal de la phase syntaxique est de reconnaître les phrases du langage conformément à une grammaire. L’analyseur syntaxique (parser) récupère les unités lexicales produites par le scanner et vérifie que leurs agencements forment des phrases correctes.
Le scanner devient ainsi un sous programme de l’analyseur syntaxique.
Si la grammaire est LL(1), on peut alors appliquer un type particulier d’analyse syntaxique. C’est ce qu’on appelle la descente récursive.
Dans ce qui suit, nous rappelons la grammaire du langage Z minimal afin de vérifier qu’elle possède bien les propriétés LL(1). Ces dernières sont données par la suite.
Rappelons ci-après la grammaire du langage Z minimal et vérifions qu’elle est bien LL(1).
4.2 Grammaire du langage Z minimal
Structure du programme
<Algo Z> → [ ~Soit|Soient~ <Ps> ] Debut <Lis> Fin [;]
<Ps> → <S>;{ [~Soit|Soient~] <S>;}*
<S> → <Li> Sep <Typ>
<Li> → Idf {, Idf}*
< Lis > → < Inst > { ; < Inst > }*
<Typ> → Entier
Instructions
<Inst> → Idf := <Exp> | Lire ( Idf {, Idf }* ) | Ecrire (<Exp> {,<Exp>}* )
Expressions
<Exp> → <Exps>[ Opr <Exps>]
<Exps> → [Sign] <Terme> { Opa <Terme> }*
<Terme> → <Facteur>{Opm <Facteur>}*
<Facteur> → Idf | Cste | ( <Exp>)
4.3 Vérification de la propriété LL(1)
Rappelons d’abord qu’une grammaire est formée d’un ensemble de règles et que chaque règle peut avoir plusieurs productions.
Comme exemple, pour la règle <Inst>, il existe trois productions (alternatives).
Sachant qu’aucune production ne dérive la chaîne vide, il suffit de déterminer pour chaque non terminal les premiers des productions et vérifier que leur intersection est vide.
Les premiers d’une production sont les symboles terminaux que la production peut dériver.
Exemples
Premiers( Idf := <Exp> ) = { Idf }
Premiers ( Lire ( Idf {, Idf }* ) ) = { Lire }
Premiers( [Sign] <Terme> { Opa <Terme> }* ) = { +, -, Idf, Cste, ( }
4.4 Le module Check
Le parser utilise le module de base Check(Code, n) défini comme suit:
Si Syn = Code // Syn et Sem sont des variables globales pour Check
Scan(Syn, Sem) // Avancer
Sinon
Error(n) // Symbole attendu non trouvé
Fsi
Ce module fait appel à
- Scan( Syn, Sem) qui est l’automate délivrant la prochaine unité lexicale définie par les variables Syn et Sem.
- Error(n) qui affiche le message d’erreur correspondant à n.
4.5 Forme d’une procédure récursive
Nous avons mentionné précédemment que l’analyseur syntaxique peut être écrit sous la forme d’un ensemble de procédures récursives si la grammaire du langage considéré vérifie les propriétés LL(1).
Pour une règle de la forme:
<NT> → α1 | aα2 | ….| aαn
nous associons la procédure suivante ( en Pascal)
Procedure NT ;
CASE
Prem(α1) : Traiter la production α1
Prem(α2) : Traiter la production α2
…
Prem(αn) : Traiter la production αn
ELSE
Retour(Si NT peut produire le vide) ou Erreur (Sinon)
END
Prem désigne les premiers d’une production.
Exemple
A la règle suivante relative aux instructions
<Inst> → Idf := <Exp> | Lire ( Idf {, Idf }* ) |Ecrire(<Exp> {,<Exp>}* )
nous associons la procedure récursive suivante (exprimée en PASCAL):
Procedure INST ;
CASE
Code_idf : Begin Check(Code_idf, n1); Check(Code_aff, n2); EXP End
Code_lire :
Begin
Check(Code_lire, n3); Check(Code_paro, n4); Check(Code_idf, n1);
While (Syn=Code_virgule) Do
Begin Scan(Syn, Sem) ; Check(Code_idf, n1) End;
Check(Code_parf, n6)
End
Code_ecrire:
Begin
Check(Code_ecrire, n5); Check(Code_paro, n4); EXP;
While (Syn=Code_virgule) Do
Begin Scan(Syn, Sem); EXP End;
Check(Code_parf, n6)
End
END // CASE
Code_idf, Code_aff, Code_lire, Code_ecrire, Code_paro, Code_parf et Code_virgule sont les codes associés aux unites lexicales et n1, n2, ..., n6 sont des messages d’erreurs.
4.6 Forme de l’analyseur syntaxique
C’est l’ensemble des procédures récursives, une procédure par non terminal.
La procédure associée à l’axiome <Algo Z> constitue le programme principal. C’est elle qui est appelée la première fois.
En général, s’il y a n non terminaux, il y a n procédures récursives parallèles qui s’entre appellent.
Considérations
Les procédures sont dépourvues de paramètres.
Les variables Syn et Sem sont globales pour l’analyseur syntaxique.
Afin de simplifier l’analyseur, nous optons pour l’arrêt prématuré de la compilation dés qu’une erreur est rencontrée.
4.7 Test du parser
Il s’agit de programmer toutes les procédures pour le langage Z minimal.
Afin de tester le parser, nous devons écrire des programmes conformément au langage Z minimal.