Compilation : De l'algorithme à la porte logique (2023-2024)

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 G₁ :

 R1  S → a S a
 R2  S → a a
 R3  S → a

Quelle est la nature de cette grammaire ?
Quel est le langage L₁ 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 L₂={a^m bⁿ c^p | m, n, p > 0}.
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 :

L₁={aⁿ bⁿ | n > 0}.
L₂={aⁿ aⁿ | n > 0}.
L₃={aⁿ b^m | n > 2, m < 4 }.
L₄={aⁿ b^m | n > 2, m > 4 }.
L₅={aⁿ b^m | n < m }.
L₆={aⁿ b^m | n + m < 256 }.
L₇={w∈{a,b}*, tel que w contient autant de a que de b }.
L₈={w∈{a,b}*, tel que w contient au moins 2 a et au plus 2 b }.
L₉={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.

aⁿ bⁿ et lemme de l'étoile

Écrire une grammaire générant le langage L={aⁿ bⁿ | n ≥ 0} .
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}

Quand c'est flou, il y a un loup

Montrer que la grammaire algébrique suivante est ambiguë :

 R1 E → E + E
 R3 E → E * E
 R5 E → ( E )
 R6 E → a | b | c

Écrire une grammaire non ambiguë pour le même langage.

La balade du else (dangling else)

Montrer que la grammaire algébrique suivante est ambiguë :

 Inst ::= Inst_if
 Inst_if ::= IF Expr Inst
 Inst_if ::= IF Expr Inst ELSE Inst
 Expr ::= ...

É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.

C) Tout dépend du contexte : Langages contextuels

aⁿ bⁿ cⁿ

Le langage L={aⁿ bⁿ cⁿ| 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 :

 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 :

 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.

aⁿ bⁿ c^p et aⁿ b^p c^p sont dans un bateau

Considérons les deux langages :

L₁ = {aⁿ bⁿ c^p | n, p > 0},
L₂ = {aⁿ b^p c^p | n, p > 0}.

Quelle est la nature des langages : L₁, L₂, L₁∩L₂ et L₁∪L₂ ?

aⁿ b^p c^q d^r

Les langages suivants sont-ils algébriques ou pas ?

L₁ = {aⁿ b^p cⁿ d^p| p,n > 0}.
L₂ = {aⁿ bⁿ c^p d^p| p,n > 0}.
L₃ = {aⁿ b^p c^p dⁿ| p,n > 0}.

Justifier les réponses en prenant le point de vue des automates à pile.

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 :

 R1  S → S a
 R3  S → a

Même exercice avec la grammaire récursive droite :

 R2  S → a S
 R3  S → a 

Conclusion ?

ligne à ligne

Soit une spécification CUP de la forme :

 terminal NL; /* fin de ligne */
 non terminal Lignes Phrase; 
 Lignes ::=  /* vide */    {: Action1(); :}
        | Lignes Phrase NL {: Action2(); :}

É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.

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 ?

Mêmes questions avec une version récursive droite de la grammaire :

non terminal Liste;
terminal N;
Liste ::= /* vide */ ;
Liste ::= N ;
Liste ::= N Liste;

Retour de balade du else (dangling else)