Théorie des langages : Td langages formels frederic gruau
Télécharger PDFLangages Formels 2019-2020
TDs + devoir + TP
Fr ́ed ́eric GruauPlan Le cours est divis ́e en six p ́eriodes de deux
semaines, avec l’enchainement des six th`emes
suivants : a-Rappels, b-approfondissement au-
tomates, c- Grammaires Hors Contexte, d-
Automates `a piles, e- analyse syntaxique ascen-
dantes, f- Machine de Turing. L’enchaˆınement
est une construction logique, c’est `a dire qu’il
est n ́ecessaire d’assimiler les concepts au fur et
`a mesure, pour pouvoir continuer `a suivre jus-
qu’au bout. En particulier, les ́el ́eves n’ayant
jamais vus d’expressions rationnelles ni d’au-
tomates d’ ́états finis, doivent fournir un effort
consid ́erable les deux premi`eres semaines (rap-
pels), pour se mettre `a niveau avec le reste. Ce
recueil de TD et le support de cours se trouvent
`a l’adresse : https :// ̃gruau/
Il y `a 12 cours(1h30) suivi de 12 TD(2h). Le
cours pr ́epare aux TDs. Le d ́eroulement pour
chacune des 12 semaines est le suivant :
a- Rappel
1. Cours : Panoramique, Langage formels,
Expression rationnelle, lemme d’Arden,
def. automate d’ ́état fini.
TD : Egalit ́e langage, Expression ration-
nelle, Automates simples.
2. Cours : Automate non-d ́eterministe, epsi-
lon transitions, th ́eoreme de kleene
TD : Automates, suite et fin, d ́etermi-
nisation, r ́esolution d’ ́equation (d ́ebut).
b- Approfondissement automates
3. Cours : minimisation d’un automate
TD:r ́esolutiond’ ́equation(autre
exemple),constructiond’automates,
construction directe de l’automate mini-
mal a partir du langage.
4. Cours pompage, clˆoture, d ́ecidabilit ́e.
TD pompage, clˆoture.
c- Grammaires Hors Contexte
5. Cours : grammaires hors contexte, arbre de
d ́erivation, ambiguit ́e, r ́e ́ecriture droite.
TD : grammaire d’un langage, langage
d’une grammaire, d ́esambigu ̈ıser.
6. Cours : nettoyage de grammaire, FN
Chomsky, d ́ecidabilit ́e, cloture, analyse
lexicale.
TD : analyse lexicale, grammaire d’un vrai
langage, est-il-alg ́ebrique (1,4,5).
d- Automates `a piles
7. Cours+TD : automates `a piles TD est-il-
alg ́ebrique (suite)
8. Cours : ́
Equivalence automate `a pile-
grammaire,clˆoture, premier et suivant.
TD : est-il-alg ́ebrique (fin), Analyse ascen-
dente `a la main, premier et suivant.
e- Analyse Ascendente
9. Cours+TD : Analyse ascendente
10. Cours:automateLR(1)g ́en ́eral,
LALR(1), intro machine de Turing.
TD : exo d’analyse ascendante (rappel +
LR, LALR ). machine de Turing simple
f- Machine de Turing
11. Cours d ́ecidabilit ́eTD machinede Turing
compliqu ́ee,
d ́ecidabilit ́e de l’ambigu ̈ıt ́e.
12. Cours : NP compl ́etude,
TP en salle machine : yacc et lex
Les exercices optionnels sont plus difficiles.
Ils sont con ̧cus pour occuper les meilleurs ́etudiants ou vous permettre de travailler chez
vous. Ils ne sont en g ́en ́eral pas trait ́es avec
toute la classe par manque de temps. Certains1 exercices plus importants ou plus difficile sont
r ́epartis sur deux TDs : le premier TD traite
un exemple facile, et le TD de la semaine sui-
vant un deuxi`eme exemple plus difficile. C’est
le cas pour les automates d’ ́état finis (TD 1 et
2), la r ́esolution d’ ́equations de langages (TD 2
et 3), est-il-alg ́ebrique (TD 6,7 et 8, car il y a
plusieurs m ́ethodes), l’analyse ascendante (TD
9 et 10), les machine de Turing (TD 10 et 11).
Examens, Devoir,Rattrapage.
Seules les notes de cours manuscrites, et les
poly de cours et d’exercices sont autoris ́es aux
examens. Chaque TD fait l’objet d’un exercice
au partiel ou `a l’examen. Le partiel et l’examen
comprennent aussi des questions de cours non
trait ́ees en TD. Les notes de partiels mauvaises
pourront ˆetre ”partiellement” rattrap ́ees grˆace
`a un devoir relativement facile, mais sur un co-
efficient de seulement 10 pourcent par rapport
au partiel. Contrˆole continu = (9* partiel + de-
voir)/10. L’ ́enonce du devoir est inclus dans ce
recueil, `a la section 12. L’examen de rattrapage
en juin, porte sur toute l’ann ́ee.1 D ́emonstrationd’ ́egalit ́e
entre deux langages
Les ́egalit ́es suivantes sont elles vraies ? si oui,
le d ́emontrer sinon donner un contre-exemple.1.L ∗=L ∗.L ∗
= (L∗ )∗ 2.L.(M∩N) = (L.M)∩(L.N)
3. Optionnel : (L∗ .M)∗ ={}+ (L+M)∗ .M2 Expression rationnelle2.1 ExprRat d’un langageL 1
={w|wcommence parab}L 2
={w|wtermine parbb}L 3
={w|wcommence parabet termineparbb} L4 ={w|wcontient trois occurrences suc-
cessives de la lettrea}L 5
={w|wne commence pas parba}L 6
={w|wne termine pas parbba}2.2 optionnel : ExprRat compliqu ́e.L 7
={w|wne contient pas deux occur-
rences successives de la lettrea}L 8
={w|wne contient pas trois occurrences
successives de la lettrea}L 9
={w|le nombre deadanswest pair
}={w||w|a = 0 (mod2)}L 10={w||w| a
= 1 (mod3)}2.3 ExprRat pour l’analyse lexicale.
La premi`ere ́etape d’un compilateur et l’ana-
lyse lexicale, qui d ́ecoupe le texte d’un pro-
gramme en unit ́es lexicales appel ́ee ”token”.
Un token peut ˆetre un mot clef, un identifiant,
une constante num ́erique. On utilise des ex-
pression rationnelle pour identifier la nature
des diff ́erent token. On utilisera la notation
” ́etendue”” plus compacte. Par exemple,e? =
e|qui signifie queeest optionnel, [0−9] signifie
un chiffre.
Ecrire l’expression rationnelle d ́ecrivant :
1. un identificateur comme une lettre suivit
d’une suite de lettre ou de chiffre,
2. un entier positif
3. un entier relatif
4. un nombre `a virgule3 Automates reconnaissant un
langage donn ́e.
Donner des automates reconnaissant les lan-
gages suivants : les entiers sont cod ́es en bi-
naire. Pour les entiers comme pour les mots
habituel, on consid`ere que les caract`eres sont
lus de gauche a droite, donc en commen ̧cant
par les bits de poids forts.
— des entiers pairs, des entiers impairs, des
puissances de 2
—A={0,1},L={w|wcode une puis-
sance de 4}
—A={0,1},L={w|wcode la somme
de deux puissances de 4 distinctes : 4k +4k ′,k6=k ′}. —A={a,b},L={w|wcommence parabaaba} —A={a,b},L=
{w|wcontientaabaaab}
—A={a,b},L={w|wcommence par
abbet termine parbba}2 — Les ́ecritures de nombre `a virgule
—A={a,b,c},L={w|wcontient au
moins une fois chacune des trois lettres}
— Optionnel.A={a,b},L={w| |w|a est
pair, ainsi que|w|b }
— OptionnelA={a,b},L={w|w
contient un nombre pair de fois le facteurbab} — Optionnel.A={0,1},L={w|en base
2,wrepr ́esente un nombre valant 1 mo-
dulo 3}4 D ́eterminisation4.1 M ́ethode de d ́eterminisation.
D ́eterminisez :? l lhl ll l14 25 36 �� @@R -- @@R �� ab bb ba � -a,ba,b 4.2
Boum !SoitL n
l’ensemble des mots sur{a,b}de lon-
gueur au moinsndont lani`eme lettre avant la
fin est unb. Donnez un petit automate non-
d ́eterministe pourL3 . puis son d ́eterminis ́e.
Comparez leur nombre d’ ́etats. Au lieu de faire
marcher l’algorithme de d ́eterminisation, on
commencera par r ́efl ́echir quels doivent ˆetre les ́etats, puis on rajoutera les transitions.5 Resolution d’ ́equations
Rappel de cours : `a tout automate on peut
associer un syst`eme d’ ́equations dont les va-
riables repr ́esentent les langages reconnus par
cet automate `a partir de chacun de ses ́etats.5.1 Exemple `a faire` A l’aide du syst`eme d’ ́equations pr ́ec ́edent,
que l’on r ́esoudra par ́elimination et utilisation
du lemme d’Arden, d ́eterminer une expression
rationnelle correspondant aux automates sui-
vants : ( sur l’alphabetA={a,b})12 ab a,b123 ab ab a,b5.2 Exemple optionnel.123 45 ab ab ba a,ba b12 a,ba,b 6
Construction d’automates.6.1 Construction classiquesLest reconnupar l’automateA=
(Σ,Q,δ,q0 ,F). Construire des automates re-
connaissant :
—miroir(L)={a na n−1...a 3a 2a 1|a 1a 2...a n∈L} — l’ensemble des mots obtenus a partir des
mots deLen effa ̧cant tous lesa.
— le compl ́ementaire deL, en supposantA
d ́eterministe.
— Optionnel : l’ensemble des mots obtenus
en effa ̧cant un nombre pair de lettres d’un
mot deL6.2 Construction du produit syn-
chronis ́e pour l ’intersection.L 1etL 2
sont reconnus par les automatesA1 etA2 .
On suppose queA1 etA2 sont d ́eterministes
complets.
— Donner un algorithme lin ́eaire en|u|pour
savoir siu∈L1 ∩L2 .
— En d ́eduire la construction d’un automate
d ́eterministe reconnaissant l’intersection.
il s’appelle le ”produit synchronis ́e”.
— Construire ́egalementunautomate
d ́eterministe reconnaissant l’union3 — Les constructions pr ́ec ́edentes s’adaptent-
elles aux automates non complet ?non-
d ́eterministes ?6.3 Optionnel : Le barman boxeur
Un tr`es bon exercice ludique, de Laurent Ro-
saz : il met en jeu des techniques de construc-
tion d’automate, il permet de bien comprendre
comment le non-d ́etermisme est fondamental
pour mod ́eliser certain probl`emes. Corrig ́e dans
l’appendice.
Un barman et un client jouent au jeu sui-
vant : Le barman met un bandeau sur les yeux
qui le rend aveugle, et il met des gants de
boxe qui l’empˆechent de ”sentir” si un verre
est `a l’endroit ou `a l’envers. Devant le bar-
man, se trouve un plateau tournant sur lequel
sont plac ́es quatre verres en carr ́e. Ces verres
peuvent ˆetre `a l’envers ou `a l’endroit. Le sens
des verres est choisi par le client et est inconnu
du barman. Si les verres sont tous dans le mˆeme
sens, alors le barman gagne (Quand le barman
gagne, un autre client, ”arbitre”, annonce qu’il
a gagn ́e et le jeu s’arrˆete.) Le barman peut
r ́ep ́eter 10 fois l’op ́eration suivante : Il annonce
au client qu’il va retourner certains verres (par
exemple le verre en bas `a gauche et celui en bas
`a droite). Le client fait alors tourner le plateau,
puis le barman retourne les verres comme il l’a
annonc ́e. Si les verres sont alors tous dans le
mˆeme sens, le barman gagne.
1)On se place du point de vue du client.
Donnez un automate dont les ́états sont les
diff ́erentes configurations du plateau, les lettres
les coups annonc ́es par le barman et o`u les
fl`eches d ́ecrivent les ́evolutions possibles des
configurations. Le fait que 1- le client fait tour-
ner le plateau comme il veut, et 2- on ne
se pr ́eoccupe pas que tout les verres soit a
l’endroit, mais seulement qu’ils soient dans le
mˆeme sens, conduit `a beaucoup simplifier : il y
a seulement quatre ́états `a distinguer, et seule-
ment trois coups possibles `a jouer, pour passer
d’un ́état `a un autre.
2) A partir de l’ ́état ou 2 verres a Cote l’un
de l’autre dans un sens et les 2 autres dans
l’autre, donner une s ́equence de coup permet-
tant au barman de gagner. Comme on a utilis ́e
une seule lettre pour nommer les coups, cette
suite corresponds `a un mot d’un langage for-mel. 3) Donnez un automate non d ́eterministe
(avec ́eventuellement plusieurs ́états entr ́ee) qui
donne toutes les s ́equences d’annonces les bonschoix). 4) Donnez un automate qui donne les coups
qui assurent au barman de gagner quel que
soit le comportement du client. On utilisera
le r ́esultat suivant : SoitAun automate
d ́et ́erministe complet qui reconnaˆıt un langage
L, pour obtenir un automate qui reconnaˆıt le
compl ́ementaire, il suffit d’inverser final/non-
final. Attention, cette m ́ethode ne marche pas
siAest non-deterministe ou siAest non-
complet.
5) Jouez-vous de l’argent contre le barman ?7 Minimisation7.1 Construction de l’automate mi-nimal. Minimisez l’automates suivant :- j
j
12345678 ---- aaaaa a,b@ @@R �� � �� � bbb 6?? bbb� ?a 6 b ?a 7.2
Egalit ́e entre automates.
Montrer que les deux automates suivants,
( ́état initial 0), reconnaissent le mˆeme langage.δ0123 a1213
b3133 ́état terminal : 1δ012345 a123225b545345 terminaux : 1,3,47.3 Construction de l’automate mi-
nimal `a partir du langage.7.3.1 Rappel de cours.
L’exercice fait intervenir des concepts un peu
difficile `a dig ́erer en cours, c’est pourquoi on
vous les redonne ici, r ́esum ́e. SiL ́etant un4 langage sur l’alphabetA, la relation de demi
congruence syntaxique surA∗ , not ́ee∼L , est
d ́efinie par la relation suivante :x∼L yssi∀z∈A ∗
,(xz∈L⇔yz∈L) C’est une relation
d’ ́equivalence. Deux mots sont en relation pour
la demi-congruence, si ils ont le mˆeme avenir
avec avenirL (u) qui est{v|uv∈L}. Si un au-
tomateAreconnaitL, `a un ́etatq, on asso-
cie un languageAvenirL (q) qui est les mots
qui m`enent de cet ́état a un final. Ce langage
est pr ́ecis ́ement celui qui se calcule en r ́esolvant
les ́equations associ ́e a chaque nœud avec le
Lemme d’Arden. L’avenir d’un ́état est ́egal
`a l’avenir d’un mot qui y m`ene. Deux ́etats
peuvent ˆetre fusionn ́es, si ils ont le mˆeme ave-
nir. Dans l’automate minimal, il y a donc un
seul ́état par classe d’ ́equivalence, la classe d’un ́etatp, c’est l’ensemble des mots qui vont deq0 `ap, et l’avenir dep, c’est les mots qui vont de
pa un final.
Th ́eoreme :Lreconnaissable ssi siLa un
nombre fini de classes, le nombre de classe etant
en fait le nombre d’ ́états dans le determiste mi-nimal SiLreconnaissable, alors les classes sont en
nombre fini, puisque il y a une classe par ́etat.
Si il y a un nombre fini de classe, alors on fait
l’automate comme suit : un ́état par classe, ou,
ce qui revient au mˆeme et rend la chose plus
compr ́ehensible, un ́état par avenir distinct. On
met une fl`eche depversqavec la lettreasi
Classe(p).aest inclus dans classe deq, L’etat
initial = la classe de epsilon, Un ́état est final
si il a epsilon dans son avenir.7.3.2 Calcul des classe d’ ́equivalence et
construction de l’automate.
SoitA={a,b}. Pour chacun des langages
ci-dessous, d ́eterminer les classes d’ ́equivalences
pour la relation de congruence syntaxique. Dire
s’il est reconnaissable, et si oui, construire l’au-
tomate minimal le reconnaissant, `a partir de
ces classes.
On proc ́edera en choisissant d’abord des pe-
tits motsu, en calculant l’avenir deu, puis la
classe deuqui est l’ensemble des mots qui on le
mˆeme avenir ; On choisisuseulement parmi les
mots qui sont des pr ́efixes d’un mot du langage,
les autres mots ont tous le mˆeme avenir : l’en-
semble vide, et sont donc dans la mˆeme classe
qui corresponds `a un ́état poubelle dans l’au-
tomate minimal.1.A ∗2.{a} 3.a∗ b∗ 4.abba+ababa5.{a nb n,n≥0} 6. Optionnel :{uu|u∈A∗ }8 Le lemme de la pompe8.1 Non pompabilit ́e
Montrez, en utilisant le lemme de la pompe
que les langages suivants ne sont pas reconnais-sables —{an b2n |n≥0}—{(ab) nc n|n≥0} —{an bm |n≥m≥0}—{a nb m|m≥n≥0} —{an bn |n≥0}+{ap bq |p6=q[7]}
— optionnel{an bm |n6=m}8.2 Pompabilit ́e-optionnel
Montrez que le langage suivant est pompable
mais pas reconnaissable :{bm an bn |m >0, n≥
0}∪a(a+b)∗ 9
Clˆoture langages r ́eguliers.
En utilisant les propri ́et ́es de clˆoture des lan-
gages rationnels et le fait que{an bn }n’est pas
rationnel, montrer que les langages suivants ne
sont pas rationnels :
—L1 ={w∈(a+b)∗ ||w|a =|w|b }
—L2 ={an bp |n6=p}
—L3 ={a2n b2n |n≥0}
—L4 ={an bp |n≥p}
Pour le dernier, vous pourrez utiliser deux
m ́ethodes : Une premi`ere qui ́etablit une re-
lation entre{an bp |n≥p}et{an bp |n > p}. Une
deuxi`eme qui utilise la stabilit ́e des reconnais-
sables par miroir.. 10
Grammaires hors contexte10.1 De la grammaire vers le langage
D ́eterminer les langages engendr ́es par les
grammaires dont les r`egles de production sont
les suivantes :5 1.S→|aaaS
2.S→ab|aSb
3.S→XY|Z;X→Xa|a;Y→aY b|;
Z→aZb|W;W→bW|b
4.S→SS||(S)
5.S→SS|()|[]|(S)|[S]6.S→ S→ai Sai pour touti,1≤i≤n 7.S→bS|aT;T→aT|bU;U→aV|bS;
V→aT|bU|
Ces grammaires sont-elles ambigu ̈es ? Si
oui, pouvez-vous donner une grammaire non-
ambigu ̈e ?10.2 Du langage vers la grammaire
Trouver des grammaires pour les langages
suivants.
1. (a+ (a+b)∗ )(ab∗ )∗ 2.{an bp |0< p < n}3.{a nb p
|0≤n≤p+ 1}4.{a nb nc md m|n,m∈N} 5.{an bm cn+m |n,m∈N}6.{a nb mc p
|n=moum=p}
7. optionnel{an bm cp dq |n+q=m+p}
8. optionnel{an bm cp dq |n+p=m+q}10.3 D ́esambiguiser `a la mainSoitF 1
la grammaire
E→E+E|E−E|(E)|idetG 1
la grammaireF1 plus les r`egles :
E→E∗E|E/E|E∧E
1. Donner tous les arbres de d ́erivations du
motid−id−id. Combien y en a-t-
il ? Correpondent-ils `a des interpr ́etations ́equivalentes ?
2. Donner des grammairesF2 etG2 telles queL(F 1
) =L(F2 ), queL(G1 ) =L(G2 ), que
chaque motwposs`ede une seule d ́erivation
`a partir du symbole initial deG2 , et que
la d ́ecomposition en arbre corresponde au
regles usuelles de priorit ́e.11 Grammaire et compilation.
Faut avoir parl ́e d’analyse lexicale en cours.11.1 Analyse lexicale
l’utilisation d’ocamllex n’est pas limit ́ee a
l’analyse lexicale des que l’on souhaite analyser
un texte (chaˆıne, fichier, flux) sur la base d’ex-
pressions r ́eguli`eres, ocamllex est un outil de
choix en particulier pour ́ecrire des filtres, i.e.
des programmes traduisant un langage dans un
autre par des modifications locales et relative-
ment simples. ́
Ecrire un programme occamlex qui imprime
un fichier en ayant pr ́ealablement enlev ́e toutes
les lignes vides, et un autre qui compte les oc-
currences d’un mot dans un texte le mot et le
nom du fichier texte sont pass ́es en param`etres11.2 Grammaire d’un Language de
programmation
Consid ́erons le petit programme suivant ́ecrit
en Pascal :
program calcul;var T : array[1..10] of integer;
S,I : integer;begin S:=0; (* initialisation *)
for I:= 1 to 10 dobegin read(T[I]);
S := S + T[I]end; writeln(S)end. L’analyseur lexical d ́ecoupe ce programme en
une liste des entit ́es lexicales appel ́ees ”token”
dont nous donnons ici le d ́ebut :
programcalcul;
<0><-1,50><11>
varT:array[1
<1><-1,51><12><2><13><3,1>
Chaque token est donn ́e par une classe et sa
valeur, s’il y en a une. Pour les identificateurs,
la valeur sera la chaine de caract ́ere, ou mieux,
l’adresse d’entr ́ee dans une table des symboles.
Lorqu’elle
rencontredes identificateurs,
l’analyse lexicale les ranges dans une table des6 symboles qui permettra de centraliser les infor-
mations rattach ́ees aux identificateurs. Apr ́es
l’analyse lexicale, cette table sera :
adressechaˆıneinformation
0program1var 2array3of 4integer5begin 6for7to 8do9end .. .. .. 50calcul51T 52S53I 54read
55writeln. .. .. .
La table est d ́ecoup ́ee en une zone pour les
mots-cl ́es, occup ́ee ici de 0 `a 9 et une zone pour
les identificateurs `a partir de 50. Cette table est
compos ́ee d’un champ repr ́esentant la chaˆıne
de caract`eres et d’un champ pouvant contenir
diff ́erentes informations utiles `a l’analyse
s ́emantique. On suppose les diff ́erentes entit ́es
rang ́ees dans l’ordre de leur apparition, sauf les
mots-cl ́es qui sont charg ́es pr ́ealablement dans
la table. Les symboles ; : [],.,..sont associ ́es
dans l’ordre `a des tokens de classe 11 `a 17 ;
Comme il n’y a qu’une unit ́e lexicale dans
chacune de ces classes il n’est pas n ́ecessaire
de passer de valeurs.
On souhaite ́ecrire un grammaire permet-
tant de g ́en ́erer des programme Pascal, et en
particuler notre programme. Plus pr ́ecis ́ement,
la grammaire doit g ́en ́erer non pas le texte
du programme mais le ”mot” repr ́esentant la
suite de token de ce programme. On commence
par quelques questions pour d ́ej`a mieux com-
prendre c’est quoi ce ”mot”.
1. A quoi corresponds la classe d’un token
pour cette grammaire ?
2. A quoi corresponds la classe -1, sur cet
exemple ?
3. Que sont les mots clefs pour cette gram-
maire ?
4. Quelle valeur a un token constante enti ́ere,
`a quelle ́etape on la calcule, et comment la
calculer ?
5. Proposer une grammaire permettant d’en-
gendrer le langage auquel ce programme
appartient.
6. Donner l’arbre de d ́erivation syntaxique
associ ́e `a ce programme. Il couvre plusieurs
pages, on pourra le finir chez soi. Indiquez
les valeurs des tokens.
7. Lorsqu’on compile, on construit une ver-
sion r ́esum ́ee de l’arbre d’analyse appel ́ee
”Arbre de Syntaxe Abstraite” (AST). Elle
contient juste les informations utiles. Pro-
poser un AST pour ce programme.12 DM pour mardi 17 mars.
Ce devoir est `a faire individuel. Il est `a rendre
imp ́erativement `a votre prof de TD, sauf le
groupe du mercredi qui peut le rendre ou bien
en cours, ou bien `a Sandrine. Un devoir rendu
apr`es mardi 17 mars aura pour note z ́ero.
Ce DM reprends le TD11.2 qui va trop vite
pour que tout le monde comprenne. Il vous per-
mettra de 1- dissocier le travail fait par l’ana-
lyse lexicale 2- apprendre `a ́ecrire des gram-
maires ”grandeur nature” 3- Aborder la notion
de syntaxe abstraite.
On consid ́ere le programme PASCAL sui-
vant :
program factoriel ;var i,n : integer ;
f : longint ;begin write(’ Donner un entier : ’) ;
readln(n) ; f:=1 ;
for i:=2 to n do
f:= f * i ;
writeln(’Le factoriel est ’, f);End. 12.1
Analyse lexicale : Classe, valeur
L’analyseur lexical d ́ecoupe ce programme en
token (comprenant toujours une classe et par-
fois une valeur) et range les identificateurs dans
une table des symboles.
1. Que code le num ́ero de classe d’un token ?
2. Les identificateurs sont ils tous de la mˆeme
classe ?
3. Les mots clefs sont ils tous de la mˆeme
classe ?7 4. Quelle valeur a un token identificateur ?
5. Quelle valeur a un token mot clef ?
6. Comment peut on reconnaˆıtre les mots
clefs de facon simple, lors de l’analyse lexi-
cale ? (On suppose que les mot clefs sont
pr ́echarg ́es dans cette table.)
7. D ́ecrivez l’ ́état de la table des symboles,
apr ́es l’analyse lexicale.
8. Ecrire la suite de tokens g ́en ́er ́ee par ce
programme, avec les classes et les valeurs
des tokens. pour le bout suivant
for i:=2 to n do
f:= f * i ;12.2 Analyse syntaxique
1. Construction de la grammaire : Propo-
ser une grammaire permettant d’engen-
drer un langage auquel ce programme ap-
partient. On convient qu’un non-terminal
commence par une majuscule et que les
terminaux (correspondant aux classe de
tokens) commencent par une minuscule
2. Analyse syntaxique : Dessiner l’arbre de
d ́erivation syntaxique g ́en ́er ́e pour l’ana-
lyse de ce programme. Comme il est tr`es
grand, utiliser plusieurs pages. On indi-
quera aussi la valeur des tokens, lorqu’il
y en a une.
3. Syntaxe abstraite : Proposer un AST
r ́esumant les informations contenue dans
le programme.13 Optionnel grammaire13.1 Nettoyage de grammaires
On veut nettoyer une grammaire, c’est `a dire
enlever :
(1) Les non-terminaux impasse, c’est `a dire
qui ne produisent pas de mots surA∗ (2) les non-terminaux inaccessibles , c’est `a
dire qui ne figurent dans aucune d ́erivation faite
`a partir deS.
Donner un algorithme permettant de rep ́erer
(et donc d’ ́eliminer) les impasses
Donner un algorithme permettant de rep ́erer
(et donc d’ ́eliminer) les inaccessibles
Quand on veut faire un nettoyage com-
plet, l’ordre dans lequel on effectue ces deux
op ́erations est-il indiff ́erent ? Pourquoi ?
Nettoyer la grammaire :
S→X X→Y Z→W|eS
W→b|fX Y→aT|TK
U→bdX|Y|dZ K→cV|Z
X→abcY W→U
T→aT||ef|aY V→af13.2 D ́esambigu ̈ısation difficile.SoientD 1,D 2etD 3
les langages suivants :D 1
={w∈{a,b}∗ ||w|a =|w|b }D 2
={w∈{a,b}∗ ||w|a =|w|b et
∀vpr ́efix dew|v|a ≥|v|b }D 3={w R∈{a,b} ∗|w∈D 2} On veut donner une grammaire pourD1 non
ambigue. Montrer comment obtenirD1 avec les
op ́erations de concat ́enation et d’ ́etoile `a partir
du langageD2 (Dyck d’ordre 1) et de son miroirD 3
. Utiliser cette description et