Exercices de travaux dirigés sur les grammaires
Théorie des langages, Hiérarchie de Chomsky-Schützenberger, Analyse syntaxique LR.
A) Restons réglo : Langages rationnels
Brille, brille, petite étoile
- Écrire une grammaire générant le langage représenté par l'expression régulière a*b.
- Préciser la nature de cette grammaire.
- Écrire une grammaire linéaire gauche pour ce langage.
C'est pas réglo !
Soit la grammaire G1 :
R1 S → a S a
R2 S → a a
R3 S → a
- Quelle est la nature de cette grammaire ?
- Quel est le langage L1 engendré par cette grammaire ?
- Quel est le type de ce langage ?
- Proposer une grammaire régulière engendrant le même langage ?
Abécédaire
Écrire une grammaire générant le langage L2={am bn cp | m, n, p > 0}.
Quel est le type de ce langage ? Peut-on avoir une grammaire linéaire droite ou gauche ?
Quel est le type de ce langage ? Peut-on avoir une grammaire linéaire droite ou gauche ?
Pot pourri
Sources : Joël Gay, LRI
Les langages suivants sont ils rationnels :
Les langages suivants sont ils rationnels :
- L1={an bn | n > 0}.
- L2={an an | n > 0}.
- L3={an bm | n > 2, m < 4 }.
- L4={an bm | n > 2, m > 4 }.
- L5={an bm | n < m }.
- L6={an bm | n + m < 256 }.
- L7={w∈{a,b}*, tel que w contient autant de a que de b }.
- L8={w∈{a,b}*, tel que w contient au moins 2 a et au plus 2 b }.
- L9={w∈{a,b}*, tel que w est égale à son image miroir }.
B) Al-Khwârismî : Langages algébriques
Le mathématicien اÙØ®ÙارزÙ
Ù (Al-Khwârismî) est l'auteur de 'اÙÙتاب اÙÙ
ختصر ÙÙ Øساب اÙجبر ÙاÙÙ
ÙابÙØ©, "KitÄb al-mukhtaá¹£ar fÄ« ḥisÄb al-jabr wa-l-muqÄbala" (Abrégé du calcul par la restauration et la comparaison) et donc du mot algèbre.
an bn et lemme de l'étoile
Écrire une grammaire générant le langage L={an bn | n ≥ 0} .
Quel est le type de ce langage et de cette grammaire ?
Qu'est ce que le lemme de l'étoile ?
Quel est le type de ce langage et de cette grammaire ?
Qu'est ce que le lemme de l'étoile ?
Palindromes
Soit un alphabet Σ={a, b, c, d}, écrire une grammaire générant le langage
L={W d W, avec W dans {a, b, c}* et W la chaîne miroir de W}
Quel est le type de ce langage et de cette grammaire ?
Même exercice avec L'={W W, avec W dans {a, b, c}* et W la chaîne miroir de W}
Quel est le type de ce langage et de cette grammaire ?
Même exercice avec L'={W W, avec W dans {a, b, c}* et W la chaîne miroir de W}
Quand c'est flou, il y a un loup
Montrer que la grammaire algébrique suivante est ambiguë :
Écrire une grammaire non ambiguë pour le même langage.
R1 E → E + E
R3 E → E * E
R5 E → ( E )
R6 E → a | b | c
La balade du else (dangling else)
Montrer que la grammaire algébrique suivante est ambiguë :
Écrire une grammaire non ambiguë pour le même langage. Cette grammaire réalisera la convention usuelle : le ELSE se rapporte au IF le plus proche.
Inst ::= Inst_if
Inst_if ::= IF Expr Inst
Inst_if ::= IF Expr Inst ELSE Inst
Expr ::= ...
C) Tout dépend du contexte : Langages contextuels
an bn cn
Le langage L={an bn cn| n > 0} n'est pas algébrique. C'est un langage
de type 1 dans la hiérarchie de Chomsky-Schützenberger, ou aussi un langage dépendant du contexte, ou context-sensitive.
Le langage ne peut être engendré par une grammaire algébrique (context-free), mais peut être engendré par la grammaire contextuelle suivante :
Donner les pas de dérivation nécessaires pour reconnaître les chaînes abc, puis aabbcc, puis aaabbbccc.
R1 S → a B S c
R2 S → a B c
R3 Ba → a B
R4 Bc → b c
R5 Bb → b b
Donner les pas de dérivation nécessaires pour reconnaître les chaînes abc, puis aabbcc, puis aaabbbccc.
Papous pas à poux papous pas papas
Le langage L={W W, avec W dans {a, b}+ } n'est pas algébrique. C'est un langage dépendant du contexte engendré par la grammaire contextuelle suivante :
Donner les pas de dérivation nécessaires pour reconnaître la chaîne abbabb.
R1 S → a A S
R2 S → b B S
R3 S → a X
R4 S → b Y
R5 A a → a A
R6 B a → a B
R7 A b → b A
R8 B b → b B
R9 A X → X a
R10 B X → Y a
R11 A Y → X b
R12 B Y → Y b
R13 a X → a a
R14 b X → b a
R15 a Y → a b
R16 b Y → b b
Donner les pas de dérivation nécessaires pour reconnaître la chaîne abbabb.
an bn cp et an bp cp sont dans un bateau
Considérons les deux langages :
- L1 = {an bn cp | n, p > 0},
- L2 = {an bp cp | n, p > 0}.
an bp cq dr
Les langages suivants sont-ils algébriques ou pas ?
- L1 = {an bp cn dp| p,n > 0}.
- L2 = {an bn cp dp| p,n > 0}.
- L3 = {an bp cp dn| p,n > 0}.
D) Analyse LR
Décaler ou Réduire ?
Écrire les décalages/réductions (Shift/Reduce)
nécessaires pour reconnaître le
fragment ababa avec la grammaire suivante :
R1 S → A B
R2 A → a b
R3 B → a b a
Récursivité à gauche ou à droite
Écrire les décalages/réductions nécessaires pour reconnaître le
fragment aaaa avec la grammaire récursive gauche :
Même exercice avec la grammaire récursive droite :
Conclusion ?
R1 S → S a
R3 S → a
R2 S → a S
R3 S → a
ligne à ligne
Soit une spécification CUP de la forme :
Écrire les décalages/réductions nécessaires pour l'analyse LR d'un fichier contenant 0,1,2,... lignes avec une "Phrase" correcte par ligne.
terminal NL; /* fin de ligne */
non terminal Lignes Phrase;
Lignes ::= /* vide */ {: Action1(); :}
| Lignes Phrase NL {: Action2(); :}
Conflits et automate LR
Tester avec CUP la spécification :
non terminal Liste;
terminal N;
Liste ::= /* vide */ ;
Liste ::= N ;
Liste ::= Liste N ;
;
- Expliquer le conflit.
- Utiliser l'option -dump de CUP pour visualiser l'automate (cf. aussi diapositive de cours).
- Comment corriger le problème ?
non terminal Liste;
terminal N;
Liste ::= /* vide */ ;
Liste ::= N ;
Liste ::= N Liste;
Retour de balade du else (dangling else)
Tester avec CUP la spécification :
non terminal Inst;
terminal IF, ELSE, COND ;
Inst ::= IF COND Inst ;
Inst ::= IF COND Inst ELSE Inst ;
- Quel type de conflits est signalé par CUP ?
- Comment résoudre le conflit en utilisant les règles de priorité de CUP.
- Analyser l'automate LR fourni avec l'option -dump de CUP.
Réduire ou Réduire ? Telle est la question
Des exemples de conflits Reduce/Reduce à analyser ou tester avec CUP :
Question subsidiaire : Quel est le style littéraire qui correspond au dernier exemple, c'est à dire où l'information
qui permet de déterminer (rendre déterministe) l'interprétation est renvoyer loin en fin de fichier ?
/* Redondance */
terminal PLUS, ID, NUM;
nonterminal Exp, Term;
Exp ::= Exp PLUS Term | Term | ID ;
Term ::= NUM | ID ;
/* Expressions en caml */
terminal MINUS, ID, NUM;
nonterminal Exp, Term ;
Exp ::= Exp MINUS Term | Term | Exp Term ;
Term ::= NUM | ID | MINUS Term ;
/* Conflit sur lookahead limité */
terminal a, b, c, d;
nonterminal S, T, U;
S ::= T b c | U b d ;
T ::= a ;
U ::= a ;
CSC4251_4252, TELECOM SudParis, P. Hennequin,Last modified: Juillet 2024