Majeure 2
Langages et Compilation
Cours 1


Grammaires formelles

jean-jacques.levy@inria.fr

21 janvier 1998

Les supports de cours sont en

http://www.polytechnique.fr/poly/edu/informatique/
http://www.polytechnique.fr/poly/~levy/

Livres:

• Kozen, Automata and Computability, Springer 1997.
• Hopcroft-Ullman, Formal languages and their Relation to Automata, Addison Wesley, 1969
• Aho-Ullman. The Theory of Parsing, Translation, and Compiling, volume 1 et 2: Parsing. Prentice-Hall, 1972.

Introduction

• Langages
• Grammaires
• Classification de Chomsky

Langages

Soit $\Sigma$ un alphabet (fini) donné,
un mot est une chaîne de caractères de $\Sigma$,
le mot vide $\epsilon$ a une longueur nulle,
$\Sigma^*$ est l'ensemble des mots sur $\Sigma$,
$\Sigma^+$ est l'ensemble des mots non vides sur $\Sigma$.

On appelle langage tout sous-ensemble L de $\Sigma^*$.

uv est le mot obtenu en concaténant u et v,
$u\epsilon = \epsilon u = u$   et    (uv)w = u(vw).

Exemples de langages

Prenons $\Sigma=\{a,b\}$ et notons w^R l'image miroir de w:

$L_1 =\{ a^n b^n \mid n \geq 0\}$
$L_2 =\{ w w^R \}$
$L_3 =\{ w \mid w = w^R \}$

Algorithmes et semi-algorithmes

• Un algorithme est un programme qui termine toujours
• Un semi-algorithme peut ne pas terminer
• Un langage L est récursif s'il existe un algorithme qui re'pond a` la question $u \in L$ par oui ou par non.
• Un langage L est récursivement énumérable s'il existe un semi-algorithme qui répond par oui à la question $u \in L$ si $u \in L$, mais qui répond non ou ne termine pas si $u \not\in L$.

Attention: ici récursif est dans le sens de Kleene, donc différent de celui de la programmation. On dit aussi que l'appartenance à un langage récursif est décidable.

Grammaire

On cherche une description finie d'un langage (éventuellement infini). Chomsky a inventé la notion de grammaire formelle.

Une grammaire G est un quadruplet $(\Sigma, V_N, S, \mathcal{P})$où:

$\Sigma$ est l'alphabet des terminaux (ou tokens),
V_N est l'alphabet des non-terminaux, $V_N \cap \Sigma = \emptyset$,
$S \in V_N$ est l'axiome,
$\mathcal{P}$ est un ensemble fini de règles de production de la forme $\alpha \rightarrow\beta$ avec $\alpha\in V^+$, $\beta \in V^*$, $V = \Sigma \cup V_N$

Dérivations

Une grammaire génère les mots d'un langage en dérivant l'axiome.

Si $\alpha \rightarrow\beta$ est une règle de production, on peut dériver le mot $x\alpha y$ en $x\beta y$. On écrit $x\alpha y \Rightarrow x\beta y$.

On pose $\alpha \Rightarrow^* \beta$ si $\alpha=\alpha_0 \Rightarrow\alpha_1 \cdots \Rightarrow\alpha_n=\beta$, où $n \geq 0$ (fermeture transitive de $\Rightarrow$).

Le langage généré par G est défini par $L(G) = \{ w \mid w\in \Sigma^*, \; S \Rightarrow^* w \}$

C'est donc l'ensemble des mots de l'alphabet terminal que l'on peut dériver depuis l'axiome.

Exemples de grammaire

$$\Sigma=\{a,b\} V_N = \{S\}$$

$$S \rightarrow aSb$$

$$S \rightarrow ab$$

$$L(G_1) = \ldots$$

$$S \rightarrow aSb$$

$$S \rightarrow ab$$

$$S \rightarrow SS$$

$$L(G_2) = \ldots$$

$$\Sigma=\{a,b,c\} V_N = \{S,B,C\}$$

$$S \rightarrow aSBC$$

$$S \rightarrow aBC$$

$$CB \rightarrow BC$$

$$aB \rightarrow ab$$

$$bB \rightarrow bb$$

$$bC \rightarrow bc$$

$$cC \rightarrow cc$$

$$L(G_3) = \ldots$$

Classification de Chomsky

4 types de grammaires selon la forme des règles de production.

type 0: quelconque

type 1: $\alpha \rightarrow\beta$ avec $\vert\alpha\vert \leq \vert\beta\vert$(context sensitive)

type 2: $A \rightarrow\alpha$,   $\alpha \neq \epsilon$(context free - algébrique)

type 3:

$$A \rightarrow aB$$

$$A \rightarrow a$$

(régulière - rationnelle)

avec $A,B \in V_N$, $a \in \Sigma$, $\alpha, \beta \in V$

Un langage est de type i s'il existe une grammaire de type i qui le génère: langages réguliers, context-free, ou context-sensitifs.

Autres exemples de grammaires

$$\Sigma=\{a,b\} V_N = \{S,A,B\}$$

$$S \rightarrow aB$$

$$S \rightarrow bA$$

$$A \rightarrow a$$

$$A \rightarrow aS$$

$$A \rightarrow bAA$$

$$B \rightarrow b$$

$$B \rightarrow bS$$

$$B \rightarrow aBB$$

$$L(G_4) = \ldots$$

$$\Sigma=\{a,b\} V_N = \{S,A,B\}$$

$$S \rightarrow aA$$

$$S \rightarrow bB$$

$$A \rightarrow aA$$

$$A \rightarrow aS$$

$$A \rightarrow bB$$

$$B \rightarrow bB$$

$$B \rightarrow b$$

$$B \rightarrow a$$

$$S \rightarrow a$$

$$L(G_5) = \ldots$$

La chaîne vide

Seuls les langages de type 0 contiennent le mot vide $\epsilon$. Pourtant, on voudrait que $L \cup \{\epsilon\}$ soit de type i, si L est de type i.

On change la classification de Chomsky en autorisant la règle $S \rightarrow \epsilon$ à chaque type de grammaire, pourvu que S ne soit pas utilisé dans les parties droites des règles de production. La règle $S \rightarrow \epsilon$ ne peut donc être utilisée que pour ajouter $\epsilon$dans le langage généré.

Lemme 1 Si G est de type i, il existe G₁ de type i telle que L(G) = L(G₁) et G₁ n'utilise pas son axiome dans les parties droites de ses règles.

La démonstration est laissée en exercice.

Théorème 1 Si L est de type i, alors $L \cup \{\epsilon\}$ et $L - \{\epsilon\}$ sont de type i.

Exercices

On note $\char93 _a(x)$ le nombre de a que contient le mot x. Trouver des grammaires générants les langages suivants:

$L_6 = \{ w \mid \char93 _a(w) = \char93 _b(w) = \char93 _c(w) \}$
$L_7 = \{ w \mid \char93 _a(w) = 2 \times \char93 _b(w) \}$
$L_8 = \{ w \mid w \;\mbox{n'a jamais}\; 2b \;\mbox{consécutifs}\; \}$
$L_9 = \{ ww \mid w \in \Sigma^* \}$

Montrer que les langages réguliers sont aussi engendrés par des grammaires dont les productions sont de la forme:
$A \rightarrow x B$
$A \rightarrow x$
où $x \in \Sigma^*$

Montrer qu'il existe un algorithme pour reconnaître tout langage context-sensitif.

Montrer qu'il existe un semi-algorithme pour reconnaître tout langage de type 0.