24 septembre 2007Cours de compilation 4 - Intranet1 Cours de compilation Techniques danalyse descendantes

24 septembre 2007 Cours de compilation 4 - Intranet 1

Cours de compilationCours de compilation

Techniques d’analyseTechniques d’analysedescendantesdescendantes


Les grandes lignes du coursLes grandes lignes du cours

•Définitions de baseDéfinitions de base•Composition de compilateursComposition de compilateurs•L’environnement d’un compilateurL’environnement d’un compilateur•Evaluation partielle et compilationEvaluation partielle et compilation•Analyses lexicales et syntaxiquesAnalyses lexicales et syntaxiques•Techniques d’analyse descendantesTechniques d’analyse descendantes•Techniques d’analyse ascendantesTechniques d’analyse ascendantes•YACCYACC•Analyse sémantiqueAnalyse sémantique•Environnement d’exécutionEnvironnement d’exécution•Génération de codeGénération de code•Optimisation de codeOptimisation de code


L’analyse descendanteL’analyse descendante----------------------------------------------------------------------------------------------------------------------------

----• Une dérivation de la forme S Une dérivation de la forme S -->> u peut être faite en >> u peut être faite en

dérivation gauche :dérivation gauche :

S S -->> t >> t A A -->> >> t t a w’a w’

• Le préfixe t est déjà reconnu, il ne comporte plus de Le préfixe t est déjà reconnu, il ne comporte plus de lettres non terminales.lettres non terminales.

• Le mot u doit être de la forme u = t w .Le mot u doit être de la forme u = t w .

• Il suffit donc de considérer A Il suffit donc de considérer A et w ! ! ! et w ! ! !

• Pour cela nous distinguons la première lettre de w = a w’ !Pour cela nous distinguons la première lettre de w = a w’ !

A A -->> >> a w’a w’

gauchegauche gauchegauche

??????????


A A -->> a w’>> a w’ ----------------------------------------------------------------------------------------------------------------------------

----• Il peut y avoir plusieurs règles de la forme A ::= . . .Il peut y avoir plusieurs règles de la forme A ::= . . .• Il peut n’y avoir qu’une seule règle de la forme A ::= . Il peut n’y avoir qu’une seule règle de la forme A ::= .

. .. .

Pour des raisons d’efficacité, il est impossiblePour des raisons d’efficacité, il est impossiblede procéder par essai-échec (back-track) !de procéder par essai-échec (back-track) !

Nous devrons donc faire en sorte qu’il n’y aitNous devrons donc faire en sorte qu’il n’y aitpas plus de deux cas à envisager :pas plus de deux cas à envisager :

- Il y a exactement une règle qui s’applique !- Il y a exactement une règle qui s’applique !

- Aucune règle ne s’applique et c’est un- Aucune règle ne s’applique et c’est un échec définitif !échec définitif !


A A -->> a w’>> a w’ ----------------------------------------------------------------------------------------------------------------------------

----• Il peut y avoir plusieurs règles de la forme A ::= . . .Il peut y avoir plusieurs règles de la forme A ::= . . .• Il peut n’y avoir qu’une seule règle de la forme A ::= . . .Il peut n’y avoir qu’une seule règle de la forme A ::= . . .

• Il y a quatre sous-cas suivant la forme de la règle A :: = . . Il y a quatre sous-cas suivant la forme de la règle A :: = . . ..

( 1 ) A ::= a ( 1 ) A ::= a

( 2 ) A ::= b ( 2 ) A ::= b avec a <> bavec a <> b

( 3 ) A ::= B ( 3 ) A ::= B

( 4 ) A ::= ( 4 ) A ::=


A A -->> a w’>> a w’ ----------------------------------------------------------------------------------------------------------------------------



( 1 ) A ::= a ( 1 ) A ::= a

AA --> > a a -->> a w’>> a w’

• Suite avec Suite avec et w’ ! ! ! et w’ ! ! !

• Remarque : Remarque : peut être de la forme c d e N . . . Dans peut être de la forme c d e N . . . Dans ce cas w’ doit commencer par les mêmes lettres c d e ! Si ce cas w’ doit commencer par les mêmes lettres c d e ! Si c’est le cas, nous continuons avec N . . . et un suffixe de c’est le cas, nous continuons avec N . . . et un suffixe de w’ .w’ .


A A -->> a w’>> a w’ ----------------------------------------------------------------------------------------------------------------------------


• Il y a quatre sous-cas suivant la forme de la règle A :: = . Il y a quatre sous-cas suivant la forme de la règle A :: = . . .. .

( 2 ) A ::= b ( 2 ) A ::= b avec a = b avec a = b

AA --> > b b -->> a w’>> a w’

• Il y a échec ! ! !Il y a échec ! ! !

• Cet échec est définitif parce que nous n’avions jamais la Cet échec est définitif parce que nous n’avions jamais la liberté de choisir ( pas de back-track ) !liberté de choisir ( pas de back-track ) !

N O N !N O N !

//


A A -->> a w’>> a w’ ----------------------------------------------------------------------------------------------------------------------------

----• Il peut y avoir plusieurs règles de la forme A ::= . . .Il peut y avoir plusieurs règles de la forme A ::= . . .• Il peut n’y avoir qu’une seule règle de la forme A ::= . Il peut n’y avoir qu’une seule règle de la forme A ::= .

. .. .

• Il y a quatre sous-cas suivant la forme de la règle A :: Il y a quatre sous-cas suivant la forme de la règle A :: = . . .= . . .

( 3 ) A ::= B ( 3 ) A ::= B

AA --> > B B -->> a w’>> a w’

• Suite avec B Suite avec B et a w’ ! ! ! et a w’ ! ! !


A A -->> a w’>> a w’ ----------------------------------------------------------------------------------------------------------------------------



( 4 ) A ::= ( 4 ) A ::=

AA --> > -->> a w’>> a w’

• Suite avec Suite avec et a w’ ! ! ! et a w’ ! ! !

• Remarque : Remarque : peut être de la forme c d e N . . . Dans ce peut être de la forme c d e N . . . Dans ce cas a w’ doit commencer par les mêmes lettres c d e ! Si cas a w’ doit commencer par les mêmes lettres c d e ! Si c’est le cas, nous continuons avec N . . . et un suffixe de c’est le cas, nous continuons avec N . . . et un suffixe de w’ .w’ .


A A -->> a w’>> a w’ ----------------------------------------------------------------------------------------------------------------------------


• Le problème :Le problème :

– Laquelle choisir ? ? ?Laquelle choisir ? ? ?

– Pour des raisons d’efficacité, nous ne pouvons pas jouer Pour des raisons d’efficacité, nous ne pouvons pas jouer au petit jeu de « essai-échec » ! ! !au petit jeu de « essai-échec » ! ! !

• Donc, une règle au plus doit convenir !Donc, une règle au plus doit convenir !

– Si c’est le cas, nous l’utilisons !Si c’est le cas, nous l’utilisons !

– Dans le cas contraire, nous constatons un échec définitif !Dans le cas contraire, nous constatons un échec définitif !

• Le seul caractère du début doit nous permettre de choisir !Le seul caractère du début doit nous permettre de choisir !

– Nous parlons d’analyse descendante LL ( Nous parlons d’analyse descendante LL ( 11 ) ! ! ! ) ! ! !


A A -->> a w’>> a w’ ----------------------------------------------------------------------------------------------------------------------------


• Différents cas de figure caractéristiques !Différents cas de figure caractéristiques !

A ::= a A ::= a et A ::= b et A ::= b avec a <> b avec a <> b

• Le premier caractère de w permet de trancher !Le premier caractère de w permet de trancher !

AA --> > a a -->> a w’>> a w’

AA --> > b b -->> a w’>> a w’

• Nous savons choisir ! ! !Nous savons choisir ! ! !

peut-être ?peut-être ?


A A -->> a w’>> a w’ ----------------------------------------------------------------------------------------------------------------------------



A ::= a A ::= a et A ::= a et A ::= a

• Le premier caractère de w ne permet pas de trancher !Le premier caractère de w ne permet pas de trancher !

AA --> > a a -->> a w’>> a w’

AA --> > b b -->> a w’>> a w’

• Nous ne savons pas choisir ! ! !Nous ne savons pas choisir ! ! !




A A -->> a w’>> a w’ ----------------------------------------------------------------------------------------------------------------------------



A ::= a A ::= a et A ::= B et A ::= B

• Question :Question :

B B -->> a >> a

• Si c’est NON, seule la première règle convient !Si c’est NON, seule la première règle convient !• Si c’est OUI, nous avons l’embarras du choix ! ! !Si c’est OUI, nous avons l’embarras du choix ! ! !

• Définition : Définition : a a Prem ( Prem ( ) ) -->> a . . .>> a . . .

Prem ( Prem ( ) ) -->> >>

?????????? a a Prem ( B ) Prem ( B )

a a Prem ( B ) Prem ( B )

//


A A -->> a w’>> a w’ ----------------------------------------------------------------------------------------------------------------------------



A ::= a A ::= a et A ::= et A ::=

• Il pourrait y avoir deux possibilités :Il pourrait y avoir deux possibilités :

AA --> > a a -->> a w’>> a w’

AA --> > -->> a w’>> a w’

• Est-ce que Est-ce que aa peut être un successeur de peut être un successeur de AA ? ? ? ? ? ?

• Définition : a Définition : a Suiv ( A ) Suiv ( A ) S S -->> . . . A a . . .>> . . . A a . . .

a a Suiv ( A ) Suiv ( A )????




Définition de LL ( 1 )Définition de LL ( 1 ) ----------------------------------------------------------------------------------------------------------------------------

----• Une grammaire est LL ( 1 ), c’est-à-dire avec un seul Une grammaire est LL ( 1 ), c’est-à-dire avec un seul caractère de LOOK-AHEAD, alias w = a w’ et nous ne caractère de LOOK-AHEAD, alias w = a w’ et nous ne connaissons que le seul caractère a , si et seulement si :connaissons que le seul caractère a , si et seulement si :

• pour tout non-terminal A et ses règlespour tout non-terminal A et ses règles

A ::= A ::= | | | | | |

• nous avons les trois propriétés suivantes :nous avons les trois propriétés suivantes :

( 1 ) Prem ( ( 1 ) Prem ( ) Prem ( ) Prem ( si i = j si i = j

( 2 ) Il existe au plus une règle A ::= ( 2 ) Il existe au plus une règle A ::= telle que telle que

A A --> > -->> >> c’est-à-dire que c’est-à-dire que Prem ( Prem ( ) )

( 3 )( 3 )Si Si L ( A ) , alors pour tout i : L ( A ) , alors pour tout i :

Prem ( Prem ( ) Suiv ( A ) = ) Suiv ( A ) =

11 22 nn

vv

ii jj //

kk

kk kk

vv

ii


Correction de LL ( 1 )Correction de LL ( 1 ) ----------------------------------------------------------------------------------------------------------------------------

----• Montrons que pour tout Montrons que pour tout A A et tout et tout a w’a w’ avec avec les règlesles règles A A ::= ::= | | | | | | qui vérifient toutes la qui vérifient toutes la propriétépropriété

LL ( 1LL ( 1 )), nous pouvons sans ambiguïté déterminer l’unique , nous pouvons sans ambiguïté déterminer l’unique règle à appliquer, si elle existe.règle à appliquer, si elle existe.

• Il suffit de prendre la lettre a et . . .Il suffit de prendre la lettre a et . . .

( A ) si a ( A ) si a Prem ( Prem ( ) , nous utilisons A ::= ) , nous utilisons A ::= car, car,

par construction, a par construction, a Prem ( Prem ( ) , pour tout i <> l . ) , pour tout i <> l .

De même, la règle A ::= De même, la règle A ::= avec avec Prem ( Prem ( ) ) ne ne

convient pas parce que a convient pas parce que a Suiv ( A ) . Suiv ( A ) .

11 22 nn

ll ll

ii//

kk kk

//


Correction de LL ( 1 )Correction de LL ( 1 ) ----------------------------------------------------------------------------------------------------------------------------

----• Montrons que pour tout Montrons que pour tout A A et tout et tout a w’a w’ avec avec les règlesles règles A A ::= ::= | | | | | | qui vérifient toutes la propriétéqui vérifient toutes la propriété

LL ( 1LL ( 1 )), nous pouvons sans ambiguïté déterminer l’unique , nous pouvons sans ambiguïté déterminer l’unique règle à appliquer, si elle existe.règle à appliquer, si elle existe.

• Il suffit de prendre la lettre a et . . .Il suffit de prendre la lettre a et . . .

( B ) si a ( B ) si a Prem ( Prem ( ) , pour aucun i , et que ) , pour aucun i , et que L ( A ), L ( A ),

alors c’est une erreur. alors c’est une erreur.

( C ) si a ( C ) si a Prem ( Prem ( ) , pour aucun i , mais que nous ) , pour aucun i , mais que nous

avons avons L ( A ) , nous utilisons clairement l’unique L ( A ) , nous utilisons clairement l’unique

règle A ::= règle A ::= , telle que , telle que Prem ( Prem ( ) . ) .

11 22 nn

ii// //

// ii

kk kk


Théorèmes sur LLThéorèmes sur LL----------------------------------------------------------------------------------------------------------------------------

----• Théorème :Théorème :

– S’il existe une grammaire G qui est LL ( k ) S’il existe une grammaire G qui est LL ( k ) avec k > 1, alorsavec k > 1, alors

– il existe une grammaire G’ qui est LL ( 1 ) et il existe une grammaire G’ qui est LL ( 1 ) et reconnaît le même langage, c’est-à-dire que reconnaît le même langage, c’est-à-dire que L ( G ) = L ( G’ ) . L ( G ) = L ( G’ ) .

• Théorème :Théorème :

– Il existe des langages L tels qu’aucune Il existe des langages L tels qu’aucune grammaire G qui correspond à L , c’est-à-grammaire G qui correspond à L , c’est-à-dire telle que L ( G ) = L , n’est LL ( k ) , dire telle que L ( G ) = L , n’est LL ( k ) , quelle que soit k .quelle que soit k .


Algorithme récursifAlgorithme récursif----------------------------------------------------------------------------------------------------------------------------

----

• A chaque non-terminal correspond une A chaque non-terminal correspond une fonction.fonction.

– Elle choisit la réécriture en fonction du flux Elle choisit la réécriture en fonction du flux d’entrée et reconnaît tout le membre droit de la d’entrée et reconnaît tout le membre droit de la règle retenue.règle retenue.

– Elle appelle d’autres fonctions pour réaliser la Elle appelle d’autres fonctions pour réaliser la reconnaissance des non-terminaux qui reconnaissance des non-terminaux qui apparaissent au membre droit de la règle retenue.apparaissent au membre droit de la règle retenue.

– Elle se termine soit par un échec ou un succès si Elle se termine soit par un échec ou un succès si tout le membre droit a pu être reconnu. tout le membre droit a pu être reconnu.


Algorithme de reconnaissance LL ( 1 )Algorithme de reconnaissance LL ( 1 )----------------------------------------------------------------------------------------------------------------------------

----

• Nous avons une table T [ N , V ] !Nous avons une table T [ N , V ] !

– Dans T [ A , a ] nous mettonsDans T [ A , a ] nous mettons

• A ::= A ::= si a si a Prem ( Prem ( ) ou ) ou

si si Prem ( Prem ( ) et a ) et a Suiv ( A ) , Suiv ( A ) ,

• ERREUR ERREUR sinon.sinon.

• Notre algorithme est une machine à pile Notre algorithme est une machine à pile définie par les cas de figure suivants.définie par les cas de figure suivants.

ii ii

ii



----

• Transition 1 :Transition 1 :

aa

a w #a w #

devientdevient

w #w #



----


aa

b w #b w #

devientdevient ERREUR car a <> bERREUR car a <> b



----


NN

a w #a w #

devientdevient

Si T [ N , a ] donne N ::= Si T [ N , a ] donne N ::=

a w #a w #



----


NN

a w #a w #

devientdevient

Si T [ N , a ] donne ERREURSi T [ N , a ] donne ERREUR

ERREURERREUR


Définition de Prem ( Définition de Prem ( ) )----------------------------------------------------------------------------------------------------------------------------

----

• Soit Soit ( N v V )* . Pour a ( N v V )* . Pour a V nous V nous aurons :aurons :

a a Prem ( Prem ( ) ) -->> a>> a

Prem ( Prem ( ) ) -->> >>

• La définition des pages suivantes vérifie La définition des pages suivantes vérifie cette propriété (sans preuve).cette propriété (sans preuve).


Définition de Prem ( Définition de Prem ( ) )----------------------------------------------------------------------------------------------------------------------------

----

• Soit Soit ( N v V )* . Suivant la forme de ( N v V )* . Suivant la forme de : :

– = a = a : Prem ( : Prem ( ) = { a } ) = { a }

– = = : Prem ( : Prem ( ) = { ) = { } }

– = B= B : Prem ( : Prem ( ) = Prem ( B ) ) = Prem ( B )

– = B= Bavecavec <> <> : :

Prem ( Prem ( ) = Prem ( B ) si ) = Prem ( B ) si Prem ( B )Prem ( B )

Prem ( Prem ( ) = ( Prem ( B ) \ { ) = ( Prem ( B ) \ { } ) v Prem ( } ) v Prem ( ) ) sinon.sinon.

//


Définition de Suiv ( A )Définition de Suiv ( A )----------------------------------------------------------------------------------------------------------------------------

----• Pour a Pour a V , nous aurons : V , nous aurons :

a a Suiv ( A ) Suiv ( A ) S S -->> . . . A a . . .>> . . . A a . . .

• La définition des pages suivantes vérifie cette La définition des pages suivantes vérifie cette propriété (sans preuve).propriété (sans preuve).

• La première apparition de A est entourée de La première apparition de A est entourée de séquences séquences et et telles qu’il existe une règle B ::= telles qu’il existe une règle B ::= A A qui vient d’être appliquée : qui vient d’être appliquée :

S S -->> . . . >> . . . BB . . . . . . --> . . . > . . . A A . . . . . .

• Pour connaître les suivants de A nous inspectons Pour connaître les suivants de A nous inspectons donc les membres droits des règles qui font apparaître donc les membres droits des règles qui font apparaître A. A.


Définition de Suiv ( A )Définition de Suiv ( A )----------------------------------------------------------------------------------------------------------------------------

----• Suiv ( A ) est le plus petit ensemble qui vérifie :Suiv ( A ) est le plus petit ensemble qui vérifie :

– Si A = S (l’axiome), alors # Si A = S (l’axiome), alors # Suiv ( A ) . Suiv ( A ) .

– S’il y a une règle B ::= S’il y a une règle B ::= A , alors Suiv ( B ) Suiv ( A ) . A , alors Suiv ( B ) Suiv ( A ) .

– S’il y a une règle B ::= S’il y a une règle B ::= A A avec avec Prem ( Prem ( ) , alors ) , alors

Prem ( Prem ( ) Suiv ( A ) ) Suiv ( A )

– S’il y a une règle B ::= S’il y a une règle B ::= A A avec avec Prem ( Prem ( ) , alors ) , alors

( Prem ( ( Prem ( ) \ { ) \ { } ) v Suiv ( B ) Suiv ( A ) } ) v Suiv ( B ) Suiv ( A )

vv

vv

//

vv


Rendre LL ( 1 )Rendre LL ( 1 ) ----------------------------------------------------------------------------------------------------------------------------

----• Une grammaire est LL ( 1 ) si, pour tout non-terminal A , Une grammaire est LL ( 1 ) si, pour tout non-terminal A , et ses règleset ses règles

A ::= A ::= | | | | | |

• nous avons les trois propriétés suivantes :nous avons les trois propriétés suivantes :

( 1 ) Prem ( ( 1 ) Prem ( ) Prem ( ) Prem ( si i = j si i = j

( 2 ) Il existe au plus une règle ( 2 ) Il existe au plus une règle tq. A tq. A --> > -->> >>

( 3 )( 3 )Si Si L ( A ) , alors Prem ( L ( A ) , alors Prem ( ) Suiv ( A ) = ) Suiv ( A ) =

• Nous ne pouvons rien si le point ( 3 ) n’est pas respecté.Nous ne pouvons rien si le point ( 3 ) n’est pas respecté.

• Nous pouvons, par contre, essayer de réécrire la Nous pouvons, par contre, essayer de réécrire la grammaire pour qu’elle respecte les deux premiers points.grammaire pour qu’elle respecte les deux premiers points.

vv

ii jj //

kk

vv

ii

11 22 nn



----• L’idée à la base est la même que celle du calcul de la L’idée à la base est la même que celle du calcul de la fermeture pour les analyses ascendantes :fermeture pour les analyses ascendantes :

– Nous développons le début de l’arbre de dérivation Nous développons le début de l’arbre de dérivation etet

– nous factorisons les terminaux initiaux communs !nous factorisons les terminaux initiaux communs !

• Ceci ne marche pas si nous retombons récursivement Ceci ne marche pas si nous retombons récursivement sur le même problème !sur le même problème !

S ::= A T ::= id | ( A )S ::= A T ::= id | ( A )

A ::= V | E V ::= id | IA ::= V | E V ::= id | I

E ::= T E’ I ::= id++E ::= T E’ I ::= id++

E’ ::= + T E’ | E’ ::= + T E’ |



---- S ::= A T ::= id | ( A )S ::= A T ::= id | ( A )

A ::= V | E A ::= V | E V ::= id RV ::= id R

E ::= T E’ I ::= id++E ::= T E’ I ::= id++

E’ ::= + T E’ | E’ ::= + T E’ | R ::= ++ | R ::= ++ |

• Il y a un problème avec la règle Il y a un problème avec la règle V ::= id | I V ::= id | I , car :, car :

id id Prem ( id ) et id Prem ( id ) et id Prem ( I ) Prem ( I )

VV

idid

II id++id++

Ancien !Ancien !

VV

id++id++

id Rid R

Nouveau !Nouveau !

ididV ::= id RV ::= id RR ::= ++ | R ::= ++ |

Elle n’est plusElle n’est plusatteinte !atteinte !



---- S ::= A T ::= id | ( A )S ::= A T ::= id | ( A )

A ::= V | E V ::= id RA ::= V | E V ::= id R

E ::= T E’ R ::= ++ | E ::= T E’ R ::= ++ | E’ ::= + T E’ | E’ ::= + T E’ |

• Il n’y a pas de problème avec la règle Il n’y a pas de problème avec la règle R ::= ++ | R ::= ++ | ::

( 1 )( 1 ) Prem ( ++ ) Prem ( Prem ( ++ ) Prem ( ) = ) =

( 2 )( 2 ) Une seule dérivation atteintUne seule dérivation atteint ..

( 3 )( 3 ) Prem ( R ) = { Prem ( R ) = { , + } n’intersecte pas , + } n’intersecte pas

Suiv ( R ) = Suiv ( V ) = Suiv ( A )Suiv ( R ) = Suiv ( V ) = Suiv ( A )

= { ) } v Suiv ( S ) = { ) , = { ) } v Suiv ( S ) = { ) , # }# }

vv



---- S ::= A T ::= id | ( A )S ::= A T ::= id | ( A )

A ::= V | E V ::= id RA ::= V | E V ::= id R

E ::= T E’ R ::= ++ | E ::= T E’ R ::= ++ | E’ ::= + T E’ | E’ ::= + T E’ |

• Bien sûr, il n’y a pas de problème avec Bien sûr, il n’y a pas de problème avec T ::= id | ( A ).T ::= id | ( A ).

• Il n’y a pas de problème avec la règle Il n’y a pas de problème avec la règle E’ ::= + T E’ | E’ ::= + T E’ | ::

( 1 )( 1 ) Prem ( + T E’ ) Prem ( Prem ( + T E’ ) Prem ( ) = ) =

( 2 )( 2 ) Une seule dérivation atteintUne seule dérivation atteint ..

( 3 )( 3 ) Prem ( E’ ) = { Prem ( E’ ) = { , + } n’intersecte pas , + } n’intersecte pas

Suiv ( E’ ) = Suiv ( E ) = Suiv ( A ) = { ) , # }Suiv ( E’ ) = Suiv ( E ) = Suiv ( A ) = { ) , # }

vv



---- S ::= A T ::= id | ( A )S ::= A T ::= id | ( A )

A ::= V | E V ::= id RA ::= V | E V ::= id R

E ::= T E’ R ::= ++ | E ::= T E’ R ::= ++ | E’ ::= + T E’ | E’ ::= + T E’ |

• Mais, il y a un problème avec Mais, il y a un problème avec A ::= V | E A ::= V | E , car :, car :

id id Prem ( V ) Prem ( E ) Prem ( V ) Prem ( E )

AA

VV

EE

id Rid R

Ancien !Ancien !

T E’T E’

id E’id E’

( A ) E’( A ) E’

AA

( A ) E’( A ) E’

id Pid P

Nouveau !Nouveau !

id Rid R

id E’id E’

vv



---- S ::= A T ::= id | ( A )S ::= A T ::= id | ( A )

A ::= ( A ) E’ | id PA ::= ( A ) E’ | id P

P ::= R | E’ P ::= R | E’

E’ ::= + T E’ | E’ ::= + T E’ | R ::= ++ | R ::= ++ |

PP

RR

E’E’ Ancien !Ancien !

++++

+ T E’+ T E’

PP

+ N+ N

Nouveau !Nouveau !

++++

+ T E’+ T E’



---- S ::= A T ::= id | ( A )S ::= A T ::= id | ( A )

A ::= ( A ) E’ | id PA ::= ( A ) E’ | id P

P ::= + N | P ::= + N | N ::= + | T E’ N ::= + | T E’

E’ ::= + T E’ | E’ ::= + T E’ |

• Il n’y a clairement pas de problème avec Il n’y a clairement pas de problème avec N ::= + | T E’N ::= + | T E’ ! !

• Il n’a pas non plus de problème avec Il n’a pas non plus de problème avec P ::= + N | P ::= + N | , car : , car :

( 1 ) Prem ( + N) = { + } et Prem ( ( 1 ) Prem ( + N) = { + } et Prem ( ) = { ) = { } }

( 2 ) Nous atteignons ( 2 ) Nous atteignons d’une seule façon ! d’une seule façon !

( 3 ) Prem ( P ) = { + , ( 3 ) Prem ( P ) = { + , } n’intersecte pas } n’intersecte pas

Suiv ( P ) = Suiv ( A ) = { ) , # }Suiv ( P ) = Suiv ( A ) = { ) , # }

Documents

24 septembre 2007Cours de compilation 4 - Intranet1 Cours de compilation Techniques danalyse descendantes