Analyse descendante des grammaires récursives à gauche
- Le
problème et sa solution
- Principe
- Exemple
: la notation polonaise postfixée
- La
notation traditionnelle à précédences
- Traitons
d'abord le cas simple à un seul niveau de
priorité.
- La
situation usuelle à deux niveaux de priorité
- Mise en œuvre effective
- Factorisation
- Programmation en C++, en application directe de la théorie
-
-
En analyse descendante, toute règle récursive à gauche (directement ou
indirectement) provoque une descente infinie.
Le remède classique est de modifier la grammaire de manière à éliminer
la récursion à gauche,
sur la base du lemme d'Arden :
Une règle récursive à gauche de la forme A --> AX,
A --> Y
engendre un langage de la forme YX*
.
Ce langage est aussi bien engendré par A -->
Y, A --> YB, B --> XB, B --> X.
où la récursion à gauche a été remplacée par une récursion à droite,
que les analyseurs descendants traitent sans difficulté.
Naturellement, les arbres de dérivation sont modifiés, mais sans perte
d'information (notamment, sans introduire d'ambiguïté).
Leur exploitation sera seulement un peu plus compliquée...
-
La grammaire habituelle
E --> E E Op
E --> Var
E --> Cte
entre dans le cadre du "principe" ci-dessus avec A
= E
, X
= E Op
, Y
= Var∪Cte
.
En reportant dans la grammaire, elle se transforme en
E --> Var,
E --> Cte,
E -->
Var B,
E --> Cte B,
B --> E Op B,
B -->
E Op.
-
La règle d'association à gauche de la syntaxe traditionnelle se traduit
par des règles récursives à gauche.
-
La grammaire "naturelle" :
E -> E Op T
E ->
T
T
-> ( E )
T -> Var
T -> Cte
se
transforme en
E -> T S
E -> T
S -> Op T S
S
-> Op T
T -> ( E )
T -> Var
T -> Cte
-
La grammaire habituelle
E -> E Opadd T
E -> T
T
-> T Opmul F
T -> F
F -> ( E )
F -> Var
F -> Cte
se transforme en
E -> T S1
E -> T
S1 -> Opadd
T S1
S1 -> Opadd T
T -> F S2
T -> F
S2 ->
Opmul
F S2
S2 -> Opmul F
F -> ( E )
F -> Var
F -> Cte
-
-
La grammaire ci-dessus ne se prête pas à la programmation,
car
comment choisir entre les deux règles issues de chaque non-terminal
autre que F
?
On doit donc recourir à une seconde transformation (par factorisation)
qui va nous ramener à des choix
qui pourront être effectués sur la base du prochain caractère à lire
(procédé dit du look-ahead).
On pose X = S1 ∪ {ε}, Y = S2 ∪ {ε}, et on écrit :
E -> T X
X -> + T X
X ->
ε ------
interprétation : si le prochain
caractère à lire n'est pas '+
', ôter 'X' de la pile
T -> F Y
Y -> * F Y
Y ->
ε
------
interprétation : si
le prochain caractère à lire n'est pas '*
', ôter 'Y' de la pile
F -> ( E )
F -> Var
F -> Cte
-
Le programme suit exactement le modèle exposé au cours 18.
Sa rédaction est donc quasi-automatique !
Voici une trace d'exécution :
x+y*((z+3+x*y)+z)*2*z
x -- E
x -- T X
x -- F Y X
x -- x Y X
+ -- Y X
+ -- X
+ -- + T X
y -- T X
y -- F Y X
y -- y Y X
* -- Y X
* -- * F Y X
( -- F Y X
( -- ( E ) Y X
( -- E ) Y X
( -- T X ) Y X
( -- F Y X ) Y X
( -- ( E ) Y X ) Y X
z -- E ) Y X ) Y X
z -- T X ) Y X ) Y X
z -- F Y X ) Y X ) Y X
z -- z Y X ) Y X ) Y X
+ -- Y X ) Y X ) Y X
+ -- X ) Y X ) Y X
+ -- + T X ) Y X ) Y X
3 -- T X ) Y X ) Y X
3 -- F Y X ) Y X ) Y X
3 -- 3 Y X ) Y X ) Y X
+ -- Y X ) Y X ) Y X
+ -- X ) Y X ) Y X
+ -- + T X ) Y X ) Y X
x -- T X ) Y X ) Y X
x -- F Y X ) Y X ) Y X
x -- x Y X ) Y X ) Y X
* -- Y X ) Y X ) Y X
* -- * F Y X ) Y X ) Y X
y -- F Y X ) Y X ) Y X
y -- y Y X ) Y X ) Y X
) -- Y X ) Y X ) Y X
) -- X ) Y X ) Y X
) -- ) Y X ) Y X
+ -- Y X ) Y X
+ -- X ) Y X
+ -- + T X ) Y X
z -- T X ) Y X
z -- F Y X ) Y X
z -- z Y X ) Y X
) -- Y X ) Y X
) -- X ) Y X
) -- ) Y X
* -- Y X
* -- * F Y X
2 -- F Y X
2 -- 2 Y X
* -- Y X
* -- * F Y X
z -- F Y X
z -- z Y X
OK
On observe que
- la transformation de la boucle while en une boucle for n'est pas aussi évidente
que pour les grammaires traitées au cours 18.
- l'adaptation du programme en vue de la génération de l'arbre d'expression
est encore moins évidente !