Compilation : De l'algorithme à la porte logique

Exercices de travaux dirigés sur les grammaires

Théorie des langages, Hiérarchie de Chomsky-Schützenberger, Analyse syntaxique LR.

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.

 R1  S → a S
 R2  S → b

Cette grammaire est algébrique (context-free), car un unique symbole non-terminal par membre gauche.
Cette grammaire est linéaire, car au plus un symbole non-terminal en membre droit.
Cette grammaire est linéaire droite, car les non-terminaux en membre droit sont toujours complètement à droite.
C'est donc une grammaire régulière pour un langage rationnel.

Une version gauche pour le même langage :

 R1  S → T b
 R2  T → T a
 R3  T → ε

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 ?

La grammaire est algébrique, linéaire, mais non régulière car ni linéaire droite, ni linéaire gauche.
Le langage est L₁={aⁿ | n > 0}
L₁ est un langage régulier reconnaissable par l'expression régulière aa* ou a+.
Ce langage est reconnaissable par une grammaire régulière (linéaire droite) :
R1 S → S a R2 S → a
ou linéaire gauche :
R1 S → a S R2 S → a

Conclusion :

Le type de la grammaire ne détermine pas nécessairement le type du langage.
Pour qu'un langage ne soit pas régulier, il faut qu'il n'existe aucune grammaire régulière engendrant le langage.
L'outil théorique principal pour ce type de preuve s'appelle les lemmes de pompage : lemme de l'étoile pour les langages rationnels (ou pas), lemme de Ogden pour les langages algébriques (ou pas).

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 ?

Le langage est régulier, reconnu par l'expression régulière a+b+c+. Il est reconnu par la grammaire linéaire droite :

 R1  S → aS
 R2  S → aT
 R3  T → bT
 R4  T → bU
 R5  U → cU
 R6  U → c

ou linéaire gauche :

 R1  S → S c
 R2  S → T c
 R3  T → T b
 R4  T → U b
 R5  U → U a
 R6  U → a

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

Non, cf. exercices suivants.
Oui, (aa)+.
Oui, aaa+(ε|b|bb|bbb).
Oui, aaa+bbbbb+.
Non, raisons similaires à L₁.
Oui, langage fini donc rationnel.
Non, L₇ ∩ a*b* = L₁. Si L₇ est rationnel, L₁ doit l'être par fermeture pour l'intersection.
Oui, automate facile à construire (12 états).
Non, cf. Palindromes plus loin.

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 ?

 R1  S → aSb
 R2  S → ε

La grammaire est linéaire non régulière (ni droite, ni gauche). Le Langage est algébrique non rationnel, ce qui se démontre avec le lemme de l'étoile (cf. Wikipédia).

Le lemme de l'étoile (ou ses variantes) est une condition nécessaire pour qu'un langage soit rationnel. Si un langage ne vérifie pas cette condition, il n'est pas rationnel. L'idée du lemme de l'étoile est que la seule manière de faire des mots aussi grands que l'on veut dans un langage rationnel est de répéter un motif un nombre quelconque de fois.

Lemme de l'étoile : Soit L un langage rationnel. Il existe un entier N(L) tel que tout mot w de L de longueur supérieure à N(L) possède une factorisation w = x y z telle que y n'est pas vide et xyⁿz ∈ L pour tout n> 0.
Principe de la preuve : on peut prendre pour N(L), la taille d'un automate fini qui reconnaît le langage L. La reconnaissance d'un mot de taille > N(L) par l'automate fera obligatoirement une boucle dans l'automate (taille du chemin > taille du graphe) d'où la factorisation...

Pour notre langage, supposons que L soit rationnel et appliquons le lemme de l'étoile au mot w=a^N(L)b^N(L) avec la factorisation w=xyz.
Si y ne contient que des a (ou que des b), le mot xy²z n'a plus le même nombre de a et de b !
Si y contient au moins un a et un b, le mot xy²z aura un a (début du deuxième y) après un b (fin du premier y).
Dans tous les cas xy²z n'appartient plus au langage L qui ne peut donc être rationnel.

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}

Le langage L est généré par la grammaire algébrique :

 R1  S → a S a
 R2  S → b S b
 R3  S → c S c
 R4  S → d 

La grammaire est linéaire mais non régulière. La théorie des langages montre que ce langage est algébrique non rationnel (utilisation rapide du lemme de l'étoile sur le mot w=a^N(L)d a^N(L)).
Il est de plus algébrique déterministe : on imagine facilement comment le reconnaitre avec une pile de façon déterministe, ou bien on demande à CUP qui donne la preuve puisqu'il analyse cette grammaire sans conflits.

Pour le langage L', il suffit de remplacer la règle R4 par :

R'4 S → ε

Le langage L' est toujours algébrique mais non-déterministe ! Dans une reconnaissance avec un automate à pile, on ne sait plus quand on est au milieu du mot et que l'on doit passer de j'empile à je dépile. Si on demande à CUP, il indiquera des conflits ce qui n'est pas une preuve mais un indice. Si on demande à Bison avec l'option %glr-parser, on a alors une preuve qu'il n'existe pas d'automate déterministe pour ce langage.

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 grammaire est ambiguë, si il existe 2 arbres de dérivation possibles pour une même expression. Par exemple, pour la chaîne a + b * c, on a les 2 arbres de syntaxe corrects :

     R1                R3
    /  \              / \
  R6   R3            R1  R6
  |    / \          / \   |
  a   R6  R6       R6 R6  c
      |   |        |   |
      b   c        a   b 

On peut trouver une grammaire non ambiguë pour le même langage, en rajoutant des symboles non-terminaux. Une Expression est une somme de Termes qui sont des produits de Facteur. La grammaire fournira alors un unique arbre de syntaxe par énoncé, qui est l'arbre correspondant aux règles usuelles de priorité.

 E → E + T | T
 T → T * F | F
 F → ( E ) | a | b | c 

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.

L'énonce IF exp1 IF exp2 inst1 ELSE inst2 a deux dérivations :

IF exp1 { IF exp2 inst1 } ELSE inst2,
IF exp1 { IF exp2 inst1 ELSE inst2 }.

Une grammaire non ambiguë pour avoir la deuxième interprétation :

 Inst : Inst_open | Inst_close ;
 Inst_open  : IF Expr Inst ;
 Inst_open  : IF Expr Inst_close ELSE Inst_open ;
 Inst_close : IF Expr Inst_close ELSE Inst_close ;
 Inst_close : autres instructions ; 

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.

dérivation de abc : R₂ et R₄,
dérivation de aabbcc : R₁ aBSc, R₂ aBaBcc, R₃ aaBBcc, R₄ aaBbcv et R₅ aabbcc,
dérivation de aaabbbccc : R₁ aBSc, R₁ aBaBScc, R₂ aBaBaBccc, 2 * R₃ aaaBBBccc, R₄ aaaBBbccc et 2 * R₅ 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.

  S → aAS    R1
    → aAbBS  R2
    → aAbBbY  R4
    → abABbY  R7
    → abAbBY  R8
    → abbABY  R7
    → abbAYb  R12
    → abbXbb  R11
    → abbabb  R14

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₂ ?

L₁ et L₂ sont algébriques. Les 2 langages sont aussi non ambigus et déterministes.
La preuve dérive simplement du langage aⁿ bⁿ.
L₁∩L₂ = {aⁿ bⁿ cⁿ| n > 0} n'est pas algébrique (cf. exercice précédent).
Les langages algébriques ne sont pas fermés par intersection, alors que les langages réguliers le sont.
L₁∪L₂ est algébrique.
Les langages algébriques sont fermés par union. L'union des grammaires se fait par union des règles.
De plus, L₁∪L₂ est un langage algébrique intrinsèquement ambigu, c'est-à-dire qu'il ne peut être reconnu que par des grammaires algébriques ambiguës et donc non déterministes. (preuve par lemme de Ogden).

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.

L₂ et L₃ sont algébriques, et facilement reconnaissables avec une Pile.
L₁ n'est pas algébrique.

Conséquence pratique : Vérifier l'égalité du nombre d'arguments entre la déclaration d'une fonction et son utilisation ne peut pas être fait de façon systématique par l'utilisation de grammaires algébriques.

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

	Entrée	Pile	Action
0	•ababa		Décalage
1	a•baba	a	Décalage
2	ab•aba	ab	Réduction R₂
3	ab•aba	A	Décalage
4	aba•ba	Aa	Décalage
5	abab•a	Aab	Décalage
6	ababa•	Aaba	Réduction R₃
7	ababa•	AB	Réduction R₁
8	ababa•	S	Succès

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 ?

Récursivité gauche :

	Entrée	Pile	Action
0	•aaaa		Décalage
1	a•aaa	a	Réduction R₃
3	a•aaa	S	Décalage
4	aa•aa	Sa	Réduction R₁
5	aa•aa	S	Décalage
6	aaa•a	Sa	Réduction R₁
7	aaa•a	S	Décalage
8	aaaa•	S	Succès

Récursivité droite :

pas	Entrée	Pile	Action
0	•aaaa		Décalage
1	&a•aaa	a	Décalage
2	aa•aa	aa	Décalage
3	aaa•a	aaa	Décalage
4	aaaa•	aaaa	Réduction R₃
5	aaaa•	aaaS	Réduction R₂
6	aaaa•	aaS	Réduction R₂
7	aaaa•	aS	Réduction R₂
8	aaaa•	S	Succès

Avec un analyseur LR, la résolution est possible aussi bien avec des règles récursives droites que des règles récursives gauches, mais la récursivité gauche est plus économe sur la pile. Avec des analyseurs LL, comme JavaCC, le récursivité gauche est interdite !

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.

Fichier vide :

Pile d'analyse Action

0 •EOF Réduction Règle 1 et Action 1

1 Lignes • EOF Décalage

2 Lignes EOF • Succès (Règle $START= Lignes EOF)

Ligne unique :

	Pile d'analyse	Action
0	• Phrase NL EOF	Réduction Règle 1 et Action 1
1	Lignes • Phrase NL EOF	"Meta-Décalage"
2	Lignes Phrase • NL EOF	Décalage
3	Lignes Phrase NL • EOF	Réduction Règle 2 et Action 2
4	Lignes • EOF	Décalage
5	Lignes EOF •	Succès

N.B. : "Meta-Décalage" veut dire ici la suite de Shift/Reduce réalisant l'analyse LR du symbole non-terminal "Phrase".

Fichier multi-ligne :
Par récurrence, on voit que pour un fichier avec N lignes • (Phrase NL){N} EOF, il suffit de boucler N fois sur les étapes 1,2 et 3 de l'analyse précédente.
L'action 1 est donc toujours exécutée une seule fois en début de fichier. L'action 2 est exécutée après chaque fin de ligne et dans l'ordre des lignes (merci à la récursivité gauche !).
On notera que l'absence d'un fin de ligne juste avant la fin de fichier est une erreur de syntaxe. Ceci explique une alerte courante missing newline before EOF dans beaucoup d'usage informatique.

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;

L'outil CUP signale un conflit de type Shift/Reduce :

  Warning : *** Shift/Reduce conflict found in state #0
  between Liste ::= (*) 
  and     Liste ::= (*) N 
  under symbol N

A l'état initial avec une pile vide, il y a un conflit entre créer une liste vide (Reduce) pour ajouter les éléments ensuite et décaler pour créer ensuite une liste avec le premier élément. Pour résoudre le problème, il suffit de supprimer la règle Liste::=N qui est redondante.

Avec la version récursive droite de la grammaire, le problème devient un conflit Reduce/Reduce :

  Warning : *** Reduce/Reduce conflict found in state #2
  between Liste ::= N (*) 
  and     Liste ::= (*) 
  under symbols: {EOF}
      

Le problème survient quand on a empilé tous les N de la liste, et que l'on veut créer le symbole Listedans la pile pour dépiler. On a alors le choix de créer Liste comme vide, ou comme une liste avec le dernier élément.

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.

L'outil CUP indique un conflit Shift/Reduce entre les deux règles Inst quand on a en sommet de pile IF COND Inst.

Warning : *** Shift/Reduce conflict found in state #4
  between Inst ::= IF COND Inst (*) 
  and     Inst ::= IF COND Inst (*) ELSE Inst 
  under symbol ELSE
  Resolved in favor of shifting.

N.B. : La résolution par défaut proposée par CUP et de faire le décalage qui correspond de fait à l'interprétation usuelle dans ce cas.
Pour forcer la résolution par décalage, il suffit d'ajouter une directive precedence nonassoc ELSE; avec une priorité sur les autres precedence éventuelles.

...

L'automate :

===== Terminals =====
[0]EOF [1]error [2]IF [3]ELSE [4]COND 
===== Non terminals =====
[0]Inst 
===== Productions =====
[0] Inst ::= IF COND Inst 
[1] $START ::= Inst EOF 
[2] Inst ::= IF COND Inst ELSE Inst 
===== Viable Prefix Recognizer =====
lalr_state [0]: { [Inst ::= (*) IF COND Inst ELSE Inst , {EOF }]
                  [$START ::= (*) Inst EOF , {EOF }]
                  [Inst ::= (*) IF COND Inst , {EOF }] }
transition on IF to state [2]
transition on Inst to state [1]
-------------------
lalr_state [1]: { [$START ::= Inst (*) EOF , {EOF }] }
transition on EOF to state [7]
-------------------
lalr_state [2]: { [Inst ::= IF (*) COND Inst ELSE Inst , {EOF ELSE }]
                  [Inst ::= IF (*) COND Inst , {EOF ELSE }] }
transition on COND to state [3]
-------------------
lalr_state [3]: { [Inst ::= IF COND (*) Inst ELSE Inst , {EOF ELSE }]
                  [Inst ::= (*) IF COND Inst ELSE Inst , {EOF ELSE }]
                  [Inst ::= IF COND (*) Inst , {EOF ELSE }]
                  [Inst ::= (*) IF COND Inst , {EOF ELSE }] }
transition on IF to state [2]
transition on Inst to state [4]
-------------------
lalr_state [4]: { [Inst ::= IF COND Inst (*) , {EOF ELSE }]
                  [Inst ::= IF COND Inst (*) ELSE Inst , {EOF ELSE }] }
transition on ELSE to state [5]
-------------------
lalr_state [5]: { [Inst ::= (*) IF COND Inst ELSE Inst , {EOF ELSE }]
                  [Inst ::= IF COND Inst ELSE (*) Inst , {EOF ELSE }]
                  [Inst ::= (*) IF COND Inst , {EOF ELSE }] }
transition on IF to state [2]
transition on Inst to state [6]
-------------------
lalr_state [6]: { [Inst ::= IF COND Inst ELSE Inst (*) , {EOF ELSE }] }
-------------------
lalr_state [7]: { [$START ::= Inst EOF (*) , {EOF }] }

Avec la table d'actions qui pose problème sur l'état 4 avec le symbole terminal 3 :

-------- ACTION_TABLE --------
From state #0 [term 2:SHIFT(to state 2)]
From state #1 [term 0:SHIFT(to state 7)]
From state #2 [term 4:SHIFT(to state 3)]
From state #3 [term 2:SHIFT(to state 2)]
From state #4 [term 0:REDUCE(with prod 0)] [term 3:SHIFT(to state 5)] [term 3:REDUCE(with prod 0)]
From state #5 [term 2:SHIFT(to state 2)]
From state #6 [term 0:REDUCE(with prod 2)] [term 3:REDUCE(with prod 2)]
From state #7 [term 0:REDUCE(with prod 1)]

Réduire ou Réduire ? Telle est la question

Des exemples de conflits Reduce/Reduce à analyser ou tester avec CUP :

/* 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 ; 

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 ?

...
Le roman policier est un exemple volontaire de langage hautement non déterministe!

CSC4251-52 (CSC 4536), TELECOM SudParis, P. Hennequin,Last modified: Juillet 2022

	Pile d'analyse	Action
0	•EOF	Réduction Règle 1 et Action 1
1	Lignes • EOF	Décalage
2	Lignes EOF •	Succès (Règle $START= Lignes EOF)