Fichier PDF

Partage, hébergement, conversion et archivage facile de documents au format PDF

Partager un fichier Mes fichiers Convertir un fichier Boite à outils PDF Recherche PDF Aide Contact



correction td2 .pdf



Nom original: correction_td2.pdf

Ce document au format PDF 1.4 a été généré par Writer / OpenOffice.org 3.4.1, et a été envoyé sur fichier-pdf.fr le 06/10/2016 à 14:38, depuis l'adresse IP 88.187.x.x. La présente page de téléchargement du fichier a été vue 560 fois.
Taille du document: 163 Ko (17 pages).
Confidentialité: fichier public




Télécharger le fichier (PDF)









Aperçu du document


Correction du TD2 Langages algébriques

1/17

Correction du TD 2 : Langages algébriques
Exercice 1
Considérons la grammaire définie par les deux productions suivantes :
S → (L) | a
L → L,S | S
Les quatre symboles terminaux de cette grammaire sont : a , ( ). Les deux symboles non
terminaux sont : L et S. Et S est l'axiome.
Construire, si possible, une suite de dérivations gauches, une suite de dérivations droites
et un arbre d'analyse pour chacune des phrases suivantes :

(a,a)
dérivation gauche :
S ⇒ (L) ⇒ (L,S) ⇒ (S,S) ⇒ (a,S) ⇒ (a,a)
dérivation droite :
S ⇒ (L) ⇒ (L,S) ⇒ (L,a) ⇒ (S,a) ⇒ (a,a)
arbre d'analyse :
S
(

L
L

)

,

S

S

a

a

(a,(a,a))
dérivation gauche :

S ⇒ (L) ⇒ (L,S) ⇒ (S,S) ⇒ (a,S) ⇒ (a,(L)) ⇒ (a,(L,S))
⇒ (a,(S,S)) ⇒ (a,(a,S)) ⇒ (a,(a,a))
S ⇒ (L) ⇒ (L,S) ⇒ (L,(L)) ⇒ (L,(L,S)) ⇒ (L,(L,a)) ⇒ (L,(S,a))
⇒ (L,(a,a)) ⇒ (S,(a,a)) ⇒ (a,(a,a))

dérivation droite :
arbre d'analyse :

S
(

L

)

L

,

S

S

(

L

a

L
S

,

)
S
a

a
L3I MIAGE – AMU - 2016/2017

Langages et automates

L. Torres

Correction du TD2 Langages algébriques

2/17


(a,(a,a),a)
dérivation gauche : S ⇒ (L) ⇒ (L,S) ⇒ (L,S,S) ⇒ (S,S,S) ⇒ (a,S,S) ⇒ (a,(L),S)
⇒ (a,(L,S),S) ⇒ (a,(S,S),S) ⇒ (a,(a,S),S) ⇒ (a,(a,a),S) ⇒ (a,(a,a),a)
dérivation droite : S ⇒ (L) ⇒ (L,S) ⇒ (L,a) ⇒ (L,S,a) ⇒ (L,(L),a) ⇒ (L,(L,S),a)
⇒ (L,(L,a),a) ⇒ (L,(S,a),a) ⇒ (L,(a,a),a) ⇒ (S,(a,a),a) ⇒ (a,(a,a),a)
arbre d'analyse :

S
(

L
L

L

,

,

S

(

a

L

)
S

S
L
,

S

a
)
S
a

a

((a))
dérivation gauche et droite : S ⇒ (L) ⇒ (S) ⇒ ((L)) ⇒ ((S)) ⇒ ((a))
arbre d'analyse :
S

(

L

)

S
(

L

)

S
a
(a,a,a,a)))
Ce n'est pas un mot du langage généré par cette grammaire.


L3I MIAGE – AMU - 2016/2017

Langages et automates

L. Torres

Correction du TD2 Langages algébriques

3/17

Exercice 2
Soit la grammaire donnée par la production suivante : S → aSbS | bSaS | 
S est l'axiome et le seul symbole non terminal. a et b sont les symboles terminaux.
1) Montrer que cette grammaire est ambiguë.
La grammaire est ambiguë puisqu'on peut trouver un mot du langage généré par cette
grammaire pour lequel il existe deux dérivations gauches, ou deux dérivations droites, ou
deux arbres d'analyse. Soit le mot abab :
S
2 arbres d'analyse :
S
a
b

S
S

b
a

S

a

S

S

b
a





S

b

S








S

2 dérivations gauches :

S ⇒ aSbS ⇒ abSaSbS ⇒ abaSbS ⇒ ababS ⇒ abab
S ⇒ aSbS ⇒ abS ⇒ abaSbS ⇒ ababS ⇒ abab

2 dérivations droites :

S ⇒ aSbS ⇒ aSb ⇒ abSaSb ⇒ abSab ⇒ abab
S ⇒ aSbS ⇒ aSbaSbS ⇒ aSbaSb ⇒ aSbab ⇒ abab

2) Quel est le langage engendré par cette grammaire ? Le langage formé du mot vide et
des mots contenant autant de a que de b.
Exercice 3
Soit la grammaire G1 suivante :
EXP → EXP + EXP | EXP – EXP | EXP * EXP | EXP / EXP | (EXP) | entier
Cette grammaire a un symbole non terminal, EXP, qui est l'axiome de la grammaire, et
sept symboles terminaux qui sont +, -, *, /, (, ), entier.
1) Quel est le langage engendré par cette grammaire ?
C'est le langage des expressions artithmétiques formées de nombres entiers (en
supposant que le symbole terminal entier peut prendre différentes valeurs de nombres
entiers), des opérateurs binaires +, -, * et / et des parenthèses.
Exemples de mots du langage : 1+2*3+4 ( exactement : entier 1+entier2*entier3+entier4 ) et
((10+12)*8)/45-54 ( exactement : ((entier 10+entier12)*entier8)/entier45-entier54 )
2) Montrer que la grammaire G1 est ambiguë en identifiant deux arbres d'analyse pour le
mot 1+2+3.
EXP
EXP
EXP
entier(1)

+

EXP

EXP

+

entier(2)

L3I MIAGE – AMU - 2016/2017

EXP
EXP

EXP

entier(3)

entier(1)

Langages et automates

+

+
EXP

EXP
entier(3)

entier(2)
L. Torres

Correction du TD2 Langages algébriques

4/17

3) Soit la grammaire G2 suivante (qui reconnaît le même langage) :
EXP → EXP + OPERANDE | EXP – OPERANDE | EXP * OPERANDE
| EXP / OPERANDE | OPERANDE
OPERANDE → ( EXP ) | entier
Vérifier qu'il n'existe plus qu'un arbre d'analyse pour l'expression 1+2+3.
EXP
EXP
EXP

+

OPERANDE

+ OPERANDE
entier(3)
entier(2)

OPERANDE
entier(1)

Remarquer ainsi qu'en introduisant une simple récursion à gauche du symbole non
terminal EXP (dans EXP → EXP + OPERANDE, au lieu de la récursion à gauche et à
droite incluse dans EXP → EXP + EXP), on obtient un arbre d'analyse qui permet
d'interpréter l'expression, par un parcours en profondeur de l'arbre, comme (1+2)+3.
En fait, toute grammaire qui est récursive à gauche et à droite pour le même symbole non
terminal est ambiguë. En remplaçant la double récursion de EXP dans les 4 premières
productions de G1, par une simple récursion (à gauche ou à droite), on obtient une
grammaire équivalente qui n'est plus ambiguë.
4) Vérifier que si la grammaire G1 avait été modifiée en introduisant une récursion à droite
de EXP plutôt qu'à gauche, l'arbre d'analyse (unique) obtenu pour 1+2+3 permettrait
d'interpréter l'expression comme 1+(2+3).
On considère la grammaire G3 équivalente à G1 suivante :
EXP → OPERANDE + EXP | OPERANDE - EXP | OPERANDE * EXP
| OPERANDE / EXP | OPERANDE
OPERANDE → ( EXP ) | entier
EXP
OPERANDE
entier(1)

+

EXP

OPERANDE +
entier(2)

EXP
OPERANDE
entier(3)

5) Quel est l'arbre d'analyse pour l'expression 1+2*3 avec la grammaire G2 (celle de la
question 3) ? Qu'en est-il pour 2*3+5 ?

L3I MIAGE – AMU - 2016/2017

Langages et automates

L. Torres

Correction du TD2 Langages algébriques

5/17

EXP
EXP
EXP

*

OPERANDE

+ OPERANDE

entier(3)

entier(2)

OPERANDE
entier(1)

On remarque que l'expression 1+2*3 peut être aisément interprétée comme (1+2)*3 à
partir d'un parcours en profondeur de l'arbre d'analyse. Or, la valeur arithmétique correcte
de 1+2*3 est 7 (=1+(2*3)) et pas 9 (=(1+2)*3), parce que l'opérateur * est plus prioritaire
que l'opérateur +.
En revanche, l'expression 2*3+5 pourra être correctement interprétée comme ayant la
valeur 11 : (2*3)+5.
6) Considérons maintenant la grammaire G4 suivante :
EXP → EXP + PROD | EXP - PROD | PROD
PROD → PROD * FACT | PROD / FACT | FACT
FACT → ( EXP ) | entier
Quel est l'unique arbre d'analyse correspondant à 1+2*3 ? Remarquer que 1+2*3 peut
maintenant être interprété comme 1+(2*3) et que 2*3+5 peut toujours être interprété
comme (2*3)+5.
EXP
EXP
EXP
PROD
FACT

+

EXP

PROD *

FACT

+

PROD
PROD

FACT
entier(3)

PROD *

PROD
FACT

FACT
entier(5)

FACT

entier(3)

entier(1) entier(2)
entier(2)
En résumé :

L'association à gauche des opérateurs, qui permet d'interpréter par exemple 1+2+3
(respectivement 1-2-3, 1*2*3 et 1/2/3) comme (1+2)+3 (respectivement (1-2)-3,
(1*2)*3 et (1/2)/3), a été obtenue par la récursion à gauche des symboles non
terminaux EXP et PROD.

Les priorités relatives des opérateurs, qui permettent d'interpréter par exemple
10/(1+2*3-4/5) comme 10/(1+(2*3))-(4/5) ont été obtenues en hiérarchisant la
grammaire de telle sorte qu'une expression arithmétique soit définie comme une
L3I MIAGE – AMU - 2016/2017

Langages et automates

L. Torres

Correction du TD2 Langages algébriques

6/17

simple somme ou différence de produits, alors qu'un produit est défini comme une
multiplication ou une division de facteurs, qui sont eux-mêmes des expressions entre
parenthèses ou des entiers. Ainsi les opérateurs de multiplication et de division
pourront être interprétés comme étant plus prioritaires que les opérateurs d'addition
et de soustraction. De même les parenthèses permettent d'obtenir une sousexpression plus "prioritaire" encore que les opérateurs * et /, et donc que + et -. Vous
pouvez ainsi vérifier que l'arbre d'analyse obtenu pour 10/(1+(2*3))-(4/5) réduit aux
symboles terminaux correspond bien à l'interprétation attendue de l'expression.
/
+

10
1

*

/

2 3

4 5

Exercice 4
On considère la grammaire suivante :
INST → si c alors INST | si c alors INST sinon INST | a | b
1) Trouvez un mot de ce langage qui admet deux arbres d'analyse distincts. Que pouvezvous en conclure ?
Au mot "si c alors si c alors a sinon b" correspond 2 arbres d'analyse. La grammaire est
ambiguë.
INST
si

c

INST

alors INST
si

c

sinon INST

alors INST

si

c

alors INST
si

b

c

alors INST

a

a

sinon INST
b

2) Trouvez une grammaire équivalente non ambiguë.
On enlève l'ambiguïté en décidant que tout sinon est attaché au alors le plus proche :
INST1 → si c alors INST1 | si c alors INST2 sinon INST1 | a | b
INST2 → si c alors INST2 sinon INST2 | a | b
INST1
si

c

alors INST1
si

c

alors INST2 sinon INST1
a

L3I MIAGE – AMU - 2016/2017

Langages et automates

b

L. Torres

Correction du TD2 Langages algébriques

7/17

Exercice 5
1) Décrire une grammaire non contextuelle générant le langage suivant : { anbncp / n,p ∈ ℕ
} et donner un arbre d'analyse pour le mot aabbc.
S
G = (V,Σ,P,S) où
V={S,A,B), Σ={a,b}
et P = {S → AB, A → aAb | , B → cB | }
A
B
a

A

a

b

A

c

B

b



2) Donner un automate à pile décrivant ce langage et vérifier son fonctionnement lors de
la reconnaissance du mot aabbc.
A =(Q,1,F,Σ,Π,) où
Q={1,2,3}, F={2,3}, Π={A} et  = ((1,a,,1,A), (1,b,A,2,), (1,c,,3,), (2,b,A,2,), (2,c,,3,),
(3,c,,3,))
c,/
1

Remarque : Cet automate est déterministe.

a,/A
pile:




1

A


1

AA


1

A


2




3




b,A/

2

c,/

b,A/

3
c,/

3

3) La grammaire est-elle LL(1) ?
Essayons de construire la table d'analyse LL(1) pour cette grammaire.
Premier(A)={a,} Premier(B)={c,} Premier(S)=Premier(A)-{}∪Premier(B)={a,c,}
Suivant(S)={#} Suivant(A)={b,c,#} Suivant(B)={#}
Table d'analyse LL(1) :
S
A
B
a

S → AB A → aAb

erreur

b

erreur

A→

erreur

c

S → AB

A→

B → cB

# S → AB
Cette grammaire est LL(1).

A→

B→

Remarque : Si on modifie la règle B → cB en B → Bc dans la réponse à la question 1, la
grammaire est récursive à gauche pour le symbole non terminal B et elle n'est donc pas
LL(1). Si on construit la table d'analyse LL(1), il y aura deux règles B → Bc et B →  dans
la case (B,c).

L3I MIAGE – AMU - 2016/2017

Langages et automates

L. Torres

Correction du TD2 Langages algébriques

8/17

Exercice 6
1) Décrire une grammaire non contextuelle générant le langage suivant : { uv / u ∈ {a,b}*
et v miroir de u }. Par exemple, le miroir de aabab est babaa, donc aababbabaa est un
mot du langage. Donner un arbre d'analyse pour baab.
S
G = (V,Σ,P,S) où V={S}, Σ={a,b} et P = {S → aSa | bSb | }
b
Remarque : Le langage algébrique généré par cette
grammaire est le langage des palindromes de longueur
paire.

a

S

b

S

a


2) Donner un automate à pile décrivant ce langage et vérifier son fonctionnement lors de
la reconnaissance du mot baab.
,/
1
2
Remarque : Cet automate n'est pas déterministe.

pile:




1

B


1

BA
→ 1

3) La grammaire est-elle LL(1) ?
Premier(S)={a,b,}
Suivant(S)={#,a,b}

BA
→ 2

B


3




a,/A

a,A/

b,/B

b,B/

3
S
a

S → aSa
S→

b

S → bSb
S→

Table d'analyse LL(1) :

#
S→
Donc la grammaire n'est pas LL(1).
Exercice 7
Soit la grammaire non contextuelle G1 suivante :
S → (L) | a
L → L-S | S
1) Pourquoi cette grammaire n'est-elle pas LL(1) ?
La grammaire est récursive à gauche pour le non terminal L, donc elle n'est pas LL(1).
2) Trouver une grammaire G2 équivalente à G1 qui ne soit pas récursive à gauche.
S → (L) | a
L → ST
T → -ST | 
3) G2 est-elle LL(1) ?
L3I MIAGE – AMU - 2016/2017

Langages et automates

L. Torres

Correction du TD2 Langages algébriques

9/17

Premier(T) = Premier(-ST)∪Premier() = Premier(-)∪Premier() = { - }∪{  } = { - , }
Premier(S) = Premier( (L) )∪Premier(a) = Premier( ( )∪{a} = { ( }∪{a} = { ( , a }
Premier(L) = Premier(ST) = Premier(S) = { ( , a }
Suivant(S) ={ #, - , ) }
Suivant(L) = { ) }
Suivant(T) ={ ) }
Table d'analyse LL(1) :
S
L
T
(

S → (L) L → ST

erreur

)

erreur

erreur

T→

-

erreur

erreur

T → -ST

a

S→a

L → ST

erreur

erreur

erreur

#
erreur
La grammaire G2 est LL(1).
Exercice 8

Soit la grammaire non contextuelle suivante :
A → abB | 
B → Aaa | b
Montrer que cette grammaire n'est pas LL(1).
Premier(A)={ a,  }
Premier(B)={ b, a }
Suivant(A)={ #, a }
Suivant(B)={ #, a }

Table d'analyse LL(1) :
A
a

Il y a deux productions pour la case (A,a)
dans la table donc la grammaire n'est pas
LL(1).

B

A → abB
A→

b
#

A→

Exercice 9
Soit la grammaire non contextuelle suivante :
S → AB
A → aAb | 0
B → aBbb | 1
1) Quel est le langage généré par cette grammaire ?
C'est le langage algébrique { a n0bnap1b2p / n,p ∈ ℕ }
2) Montrer que la grammaire est LL(1).
Premier(A)={a,0} Premier(B)={a,1} Premier(S)=Premier(A)={a,0}
Suivant(S)={#} Suivant(A)={b,a,1} Suivant(B)={b,#}
Table d'analyse LL(1) :

L3I MIAGE – AMU - 2016/2017

Langages et automates

L. Torres

Correction du TD2 Langages algébriques

S
a

10/17

A

B

S → AB A → aAb B → aBbb

b

erreur

erreur

erreur

0

S → AB

A→0

erreur

1

erreur

erreur

B→1

erreur

erreur

#
erreur
Cette grammaire est bien LL(1).

3) Donner un automate à pile (déterministe) décrivant ce langage.
A =(Q,1,F,Σ,Π,) où
Q={1,2,3,4}, F={4}, Π={A} et  = ((1,a,,1,A), (1,0,,2,), (2,b,A,2,), (2,a,,3,AA), (2,1,,4,),
(3,1,,4,), (3,a,,3,AA),(4,b,A,4,))
1,/
1

0,/

a,/A

2

a,/AA

b,A/

3
a,/AA

1,/

4
b,A/

Cet automate est déterministe.
4) Donner le programme Java d'un analyseur récursif LL(1) de cette grammaire.
Il faut construire une méthode par symbole non terminal et utiliser la table d'analyse LL(1)
pour écrire le code de ces méthodes :
import java.util.Scanner;
class ExceptionAnalyseur extends Exception {}
/**
* class AnalyseurRecursif
* détermine si un mot est engendré par la grammaire
* S → AB
A → aAb | 0
B → aBbb | 1
* par une analyse récursive LL(1)
* en interprétant la table d'analyse :
*
______________________________
*
____| S
| A
| B
|
*
| a | S → AB | A → aAb | B → aBbb |
*
| b | erreur | erreur | erreur
|
*
| 0 | S → AB | A → 0
| erreur
|
*
| 1 | erreur | erreur | B → 1
|
*
| # | erreur | erreur | erreur
|
*
__________________________________
* @author Lucile Torres
* @version 29/09/2012
*/
public class AnalyseurRecursif {
/**
* Indice du caractère courant dans la chaîne d'entrée
*/
private int courant;
L3I MIAGE – AMU - 2016/2017

Langages et automates

L. Torres

Correction du TD2 Langages algébriques

11/17

/**
* Caractère courant dans la chaîne d'entrée
*/
private char carCourant;
/**
* Chaîne d'entrée obligatoirement terminée par le caractère '#'
*/
private String entree;
/**
* Constructeur lit la chaîne en entrée au clavier, initialise le caractère
* courant et son indice au premier caractère de la chaîne en entrée
*
*/
public AnalyseurRecursif() {
entree = new Scanner(System.in).nextLine();
courant = 0;
carCourant = entree.charAt(0);
}
/** Consomme le symbole donné dans la chaîne d'entrée
* @param c symbole à consommer
* @throws ExceptionAnalyseur
si le symbole courant en entrée n'est pas le symbole donné
*/
private void consommer(char c) throws ExceptionAnalyseur {
if (carCourant == c) {
courant++;
carCourant=entree.charAt(courant);
} else
throw new ExceptionAnalyseur() ;
}
/**
* Méthode associée au symbole non terminal S
* qui interprète la colonne S de la table d'analyse
* A la fin de S(), pour un mot accepté, carCourant vaut nécessairement '#'
* @throws ExceptionAnalyseur
*/
private void S() throws ExceptionAnalyseur {
if ( carCourant == 'a' || carCourant == '0' ) {
A(); B(); // S → AB
} else throw new ExceptionAnalyseur();
if (carCourant != '#') throw new ExceptionAnalyseur();
}
/**
* Méthode associée au symbole non terminal A
* qui interprète la colonne A de la table d'analyse
* @throws ExceptionAnalyseur
*/
private void A() throws ExceptionAnalyseur {
if ( carCourant == 'a' ) {
consommer('a'); A(); consommer('b'); // A → aAb
} else if ( carCourant == '0') {
consommer('0'); // A → 0
} else throw new ExceptionAnalyseur();
}

L3I MIAGE – AMU - 2016/2017

Langages et automates

L. Torres

Correction du TD2 Langages algébriques

12/17

/**
* Méthode associée au symbole non terminal A
* qui interprète la colonne B de la table d'analyse
* @throws ExceptionAnalyseur
*/
private void B() throws ExceptionAnalyseur {
if ( carCourant == 'a') {
consommer('a'); B(); consommer('b'); consommer('b'); // B → aBbb
} else if ( carCourant == '1') {
consommer('1'); // B → 1
} else throw new ExceptionAnalyseur();
}
/**
* Analyse d'une chaîne en entrée
*/
public static void main(String [] args) throws ExceptionAnalyseur {
try {
new AnalyseurRecursif().S();
System.out.println("Mot reconnu");
} catch (ExceptionAnalyseur e) { System.out.println("Mot non reconnu"); }
}
}

5) Donner le programme Java d'un analyseur non récursif LL(1) de cette grammaire
import java.util.Scanner;
class ExceptionPilePleine extends Exception {}
class ExceptionAnalyseur extends Exception {}
class Pile {
private char [] contenu;
private int indiceSommetDePile;
Pile() {
contenu = new char[100];
indiceSommetDePile = -1; // pile vide
}
void empiler(char c) throws ExceptionPilePleine {
if (indiceSommetDePile == 99) throw new ExceptionPilePleine();
indiceSommetDePile++;
contenu[indiceSommetDePile]=c;
}
void depiler() { indiceSommetDePile--; }
char sommet() { return contenu[indiceSommetDePile]; }
boolean pileVide() { return indiceSommetDePile == -1; }
}
/**
* class AnalyseurNonRecursif
* détermine si un mot est engendré par la grammaire
* S → AB
A → aAb | 0
B → aBbb | 1
* par une analyse itérative LL(1)
* en interprétant la table d'analyse :
*
______________________________
*
____| S
| A
| B
|
*
| a | S → AB | A → aAb | B → aBbb |
*
| b | erreur | erreur | erreur
|
*
| 0 | S → AB | A → 0
| erreur
|
*
| 1 | erreur | erreur | B → 1
|
*
| # | erreur | erreur | erreur
|
*
__________________________________
L3I MIAGE – AMU - 2016/2017

Langages et automates

L. Torres

Correction du TD2 Langages algébriques

13/17

* @author Lucile Torres
* @version 29/09/2012
*/public class AnalyseurNonRecursif {
/**
* Caractère courant dans la chaîne d'entrée
*/
private char carCourant;
/**
* Indice du caractère courant dans la chaîne d'entrée
*/
private int courant;
/**
* Chaîne d'entrée obligatoirement terminée par le caractère '#'
*/
private String entree;
/**
* Constructeur lit la chaîne en entrée au clavier, initialise le caractère
* courant et son indice au premier caractère de la chaîne en entrée
*
*/
public AnalyseurNonRecursif() {
entree = new Scanner(System.in).nextLine();
courant = 0;
carCourant = entree.charAt(0);
}
/**
* Lit le caractère suivant dans la chaîne d'entrée
*/
public void avancer() {
courant++; carCourant = entree.charAt(courant);
}
/**
* Analyse la chaîne en entrée
* @throws ExceptionAnalyseur
*/
public void analyse() throws ExceptionPilePleine {
Pile p = new Pile();
p.empiler('S');
try {
while (( ! p.pileVide()) && (carCourant != '#')) {
char sommet = p.sommet();
switch (sommet) {
case 'a':
case 'b':
case '0':
case '1':
if ( carCourant==sommet ) { p.depiler(); avancer(); }
else throw new ExceptionAnalyseur();
break;
case 'S' :
if ((carCourant=='a') || (carCourant=='0')) {
p.depiler();p.empiler('B'); p.empiler('A');
} else throw new ExceptionAnalyseur();
break;

L3I MIAGE – AMU - 2016/2017

Langages et automates

L. Torres

Correction du TD2 Langages algébriques
case 'A' :

case 'B' :

}

14/17
if (carCourant=='a') {
p.depiler();p.empiler('b'); p.empiler('A');p.empiler('a');
} else if (carCourant=='0') {
p.depiler();p.empiler('0');
} else throw new ExceptionAnalyseur();
break;
if (carCourant=='a') {
p.depiler();p.empiler('b'); p.empiler('b');
p.empiler('B');p.empiler('a');
} else if (carCourant=='1') {
p.depiler();p.empiler('1');
} else throw new ExceptionAnalyseur();
break;

}
}
if (p.pileVide()) System.out.println("Mot reconnu");
} catch (ExceptionAnalyseur e) { System.out.println("Mot non reconnu"); }

/**
* Analyse une chaîne en entrée
* @throws ExceptionAnalyseur
*/
public static void main(String [] args) throws ExceptionPilePleine {
new AnalyseurNonRecursif().analyse();
}
}

6) Donner le programme Java d'un traducteur de cette grammaire qui transforme chaque
a en b et chaque b en a.
Il faut compléter le code de l'analyseur avec les instructions suivantes en vert.
Version récursive :

public class AnalyseurRecursif {
private String traduction="";
public String getTraduction() { return traduction; }
private void consommer(char c) throws ExceptionAnalyseur {
if (carCourant == c) {
courant++;
carCourant=entree.charAt(courant);
if (c=='a') traduction+='b';
else if (c=='b') traduction+='a';
else traduction+=c;
} else
throw new ExceptionAnalyseur() ;
}

public static void main(String [] args) throws ExceptionAnalyseur {
AnalyseurRecursif a;
try {
a = new AnalyseurRecursif();
a.S();
System.out.println("Mot reconnu, traduction : "+ a.getTraduction());
} catch (ExceptionAnalyseur e) { System.out.println("Mot non reconnu"); }
}
}

Version itérative :
L3I MIAGE – AMU - 2016/2017

Langages et automates

L. Torres

Correction du TD2 Langages algébriques

15/17

public class AnalyseurNonRecursif {
private String traduction="";
public String getTraduction() { return traduction; }
public void analyse() throws ExceptionPilePleine {
...
case 'a':
case 'b':
case '0':
case '1': if ( carCourant==sommet ) {
if (carCourant=='a') traduction+='b';
else if (carCourant=='b') traduction+='a';
else traduction+=carCourant;
p.depiler(); avancer();
} else throw new ExceptionAnalyseur();
break;
...
if (p.pileVide()) System.out.println("Mot reconnu, traduction :"+ getTraduction());
} catch (ExceptionAnalyseur e) { System.out.println("Mot non reconnu"); }
}

Exercice 10
Soit la grammaire non contextuelle suivante :
A → abB | 
B → Aaa | b
Cette grammaire n'est pas LL(1) (cf. exercice 8).
Est-il possible de construire de manière automatique un analyseur de cette grammaire ?
La grammaire est LL(2).
Premier2(A) = {ab}
Premier2(B) = {ab,aa,b}
Suivant2(A) = {aa,#}
Suivant2(B) = {aa,#}
Sa table d'analyse LL(2) est :
A

B

aa

A→

B → Aaa

ab

A → abB

B → Aaa

b

erreur

B→b

#
A→
erreur
Il est possible de construire un analyseur, récursif ou pas, qui interprète la table d'analyse
LL(2) selon les mêmes principes de construction qu'un analyseur LL(1), mais en regardant
un caractère en avance sur le caractère courant dans la chaîne en entrée.
Version récursive :

public class AnalyseurRecursifLL2 {
private int courant;
private char carCourant, carSuivant;
private String entree;
public AnalyseurRecursifLL2() {
entree = new Scanner(System.in).nextLine();
courant = 0;
carCourant = entree.charAt(0);
L3I MIAGE – AMU - 2016/2017

Langages et automates

L. Torres

Correction du TD2 Langages algébriques

}

16/17

if (carSuivant != '#') carSuivant = entree.charAt(1);
}
private void consommer(char c) throws ExceptionAnalyseur {
if (carCourant == c) {
courant++;
carCourant=entree.charAt(courant);
if (carSuivant != '#') carSuivant = entree.charAt(courant+1);
} else
throw new ExceptionAnalyseur() ;
}
private void A() throws ExceptionAnalyseur {
if ( carCourant == 'a' && carSuivant == 'b') {
consommer('a'); consommer('b'); B() ; // A → abB
} else if (( carCourant != 'a' || carSuivant != 'a' ) && (carCourant != '#'))
throw new ExceptionAnalyseur();
}
private void B() throws ExceptionAnalyseur {
if (( carCourant == 'a' && carSuivant == 'a') || ( carCourant == 'a' && carSuivant == 'b')) {
A(); consommer('a'); consommer('a'); // B → Aaa
} else if (carCourant == 'b')
consommer('b'); // B → b
else throw new ExceptionAnalyseur();
}
public static void main(String [] args) throws ExceptionAnalyseur {
try {
new AnalyseurRecursifLL2().A();
System.out.println("Mot reconnu");
} catch (ExceptionAnalyseur e) { System.out.println("Mot non reconnu"); }
}

Version itérative :
public class AnalyseurNonRecursifLL2 {
private char carCourant, carSuivant;
private int courant;
private String entree;
public AnalyseurNonRecursifLL2() {
entree = new Scanner(System.in).nextLine();
courant = 0;
carCourant = entree.charAt(0);
if (carCourant !='#') carSuivant=entree.charAt(1);
}
public void avancer() {
courant++; carCourant = entree.charAt(courant);
if (carCourant !='#') carSuivant=entree.charAt(courant+1);
}
public void analyse() throws ExceptionPilePleine {
Pile p = new Pile();
p.empiler('A');
try {
while (( ! p.pileVide()) && (carCourant != '#')) {
char sommet = p.sommet();
switch (sommet) {
case 'a':
case 'b':
if ( carCourant==sommet ) {
p.depiler(); avancer();
} else throw new ExceptionAnalyseur();
break;
case 'A' :
if ( carCourant == 'a' && carSuivant == 'b') {
p.depiler();p.empiler('B'); p.empiler('b');
L3I MIAGE – AMU - 2016/2017

Langages et automates

L. Torres

Correction du TD2 Langages algébriques

case 'B' :

17/17
p.empiler('a');
} else if (( carCourant != 'a' || carSuivant != 'a' )
&& (carCourant != '#'))
throw new ExceptionAnalyseur();
break;
if (( carCourant == 'a' && carSuivant == 'a')
|| ( carCourant == 'a' && carSuivant == 'b')) {
p.depiler();p.empiler('a'); p.empiler('a');p.empiler('A');
} else if (carCourant=='b') {
p.depiler();p.empiler('b');
} else throw new ExceptionAnalyseur();
break;

}
}
if (p.pileVide()) System.out.println("Mot reconnu");
} catch (ExceptionAnalyseur e) { System.out.println("Mot non reconnu"); }

}

}
public static void main(String [] args) throws ExceptionPilePleine {
new AnalyseurNonRecursifLL2().analyse();
}

L3I MIAGE – AMU - 2016/2017

Langages et automates

L. Torres


Documents similaires


td2
td5 correction
chap 3 compilation version finale ult
sujet thl 2016 2017
les langages rguliers 1
corrige serie3 thl 2017 2018


Sur le même sujet..