\documentclass{article}
%\usepackage{french}
\newtheorem{theo}{Th\'eor\`eme}%[section]
\newtheorem{prop}[theo]{Proposition}
\newtheorem{coro}{Corollaire}
\newtheorem{conj}[theo]{Conjecture}
\newtheorem{lemm}[theo]{Lemme}
\newtheorem{exem}[theo]{Exemple}
\newtheorem{rema}[theo]{Remarque}
\newtheorem{defi}[theo]{D\'efinition}
\def\sg{s\'e\-rie g\'e\-n\'e\-ra\-tri\-ce }
\title{Th\'eorie des langages et compilation}
\date{Mars 2000}
\author{Cyril Banderier\\Universit\'e de Paris XIII\\
Contact~: Cyril.Banderier@inria.fr}
\begin{document}
\maketitle
 Voici un rapide panorama de choses que vous devez conna\^{\i}tre pour l'examen
et d'autres dont vous n'entendrez peut-\^etre plus jamais parler. 



\section{Th\'eorie des langages}
La structure de base de la TL sont les mots,
on peut en donner une d\'efinition math\'ematique

\begin{defi}[Mono\"{\i}de] 
Un mono\"{\i}de est un ensemble avec une loi interne associative (not\'ee ``$.$'') et
un \'el\'ement neutre not\'e $\epsilon$. 
\end{defi}
\begin{defi}[Libert\'e]
Le mono\"{\i}de est dit libre
s'il poss\`ede une base (un sous-ensemble) dont les \'el\'ements sont ind\'ependants 
(c'est-\`a-dire qu'il n'y a pas de relations entre les \'el\'ements 
de la base~; n\'eanmoins, doter une telle base de relations n'est pas stupide et donne en fait lieu \`a la riche th\'eorie des groupes de repr\'esentation). Moralement, on a donc existence et unicit\'e d'une factorisation sur un
 mono\"{\i}de libre.
\end{defi}
\begin{defi}[Langage, TP1]
En TL, la base est appel\'ee alphabet, les \'el\'ements
de cette base sont appel\'es lettres, la loi du mono\"{\i}de est appel\'ee 
concat\'enation 
(du latin catena=cha\^{\i}ne). Une concat\'enation de lettres forme un mot, 
l'\'el\'ement neutre $\epsilon$ est ainsi logiquement d\'enomm\'e le mot vide. Un ensemble de mots est appel\'e langage.
\end{defi}

\begin{defi}[Rationnel]
On appelle {\bf Rat} la plus petite classe 
des langages stable par union,  produit,
 \'etoile et qui contient les lettres de l'alphabet. 
Un langage de cette classe est appel\'e rationnel.
\end{defi}

Un langage rationnel est associ\'e \`a une expression rationnelle (du
type $b(a+b)^*ab$).
 

\begin{defi}[Reconnaissable]
On appelle  {\bf Rec} la classe des langages reconnus par un automate.
Un langage de cette classe est appel\'e reconnaissaible.
\end{defi}

Il existe par ailleurs une th\'eorie des automates qui reconnaissent 
des mots infinis
(une d\'efinition due \`a B\"uchi dit qu'il suffit, 
pour qu'un mot soit accept\'e, 
qu'il passe une infinit\'e de fois dans des \'etats terminaux).

\begin{theo}[Kleene 1951, RAND reseach memorandum \# 704, p. 80] 
{\bf Rat}={\bf Rec}, 
i.e. on a \'equivalence entre un langage reconnu par un automate et un langage correspondant
\`a une expression rationnelle.
\end{theo}


\begin{defi}[Grammaire alg\'ebrique]
On appelle {\bf Alg} la classe des langages engendr\'es par une grammaire.
Un langage de cette classe est appel\'e alg\'ebrique.
\end{defi}

\begin{theo}[{\bf Alg}={\bf Pile}]
La classe des langages engendr\'es par une grammaire
correspond \`a la classe des langages reconnus par un automate \`a pile.
\end{theo}

La classe des langages rationnels est incluse dans la classe des
langages alg\'ebriques, comme le montre la proposition suivante.
\begin{prop}[Grammaire r\'eguli\`ere, ex.1 TD2]
{\bf Reg}={\bf Rat}, i.e. la classe des langages engendr\'es par une grammaire r\'eguli\`ere (i.e. dont les membres droits sont du type $aB$ ou $b$) correspond aux langages rationnels.
\end{prop}

La TL n'est pas purement ``alg\'ebrique'', il existe un lien avec l'analyse via ce qui suit.
Soit $a_n$ le nombre de mots de $L$ de longueur $n$, on appelle \sg de $L$ la fonction
$F(z)=\sum_{n \geq 0} a_n z^n$

\begin{theo}[Chomsky et Sch\"utzenberger 1963]
Un langage rationnel a une s\'erie g\'en\'eratrice $F$ rationnelle
(i.e. $F$=un quotient de deux polyn\^omes).\\
Un langage alg\'ebrique a une  s\'erie g\'en\'eratrice $F$ alg\'ebrique
(i.e.  $\exists P\in Q[z][F]$,avec $P(F)=0$).
\end{theo}

\begin{exem}[Dyck et \L ukasiewicz]
Le langage de Dyck $S\rightarrow (S)S|\epsilon$, qui correspond aux mots bien parenth\'es\'es, a une \sg $F$ qui v\'erifie $F(z)=zF(z)zF(z)+1$, 
donc $z^2 F(z)-F(z)+1=0$ et ainsi 
$$F(z)=\frac{1-\sqrt{1-4z^2}}{2z^2}=1+z^2+2z^4+5z^6+14z^8+O(z^{10}).$$
Le langage de \L ukasiewicz 
(cf notation polonaise des calculatrices Hewlett Packard) $S\rightarrow aSS|b $ a quant \`a lui la \sg alg\'ebrique
$$F(z)=\frac{1-\sqrt{1-4z^2}}{2z}=z+z^3+2z^5+5z^7+14z^9+O(z^{11}).$$
Dans les deux cas, on reconna\^{\i}t la suite des nombres de Catalan 
$\frac{{2n \choose n}}{n+1}$.\\
Une suite quelconque de tirage \`a pile ou face correspond 
\`a l'expression rationnelle $(P+F)^*$ et donc \`a la \sg rationnelle
$\frac{1}{1-2z}$.
Remarquez que dans tous les cas, il y a un lien entre le rayon de
convergence $\rho$ de $F$ et le nombre de mots de grande longueur ($a_n\sim\rho^{-n}$).
\end{exem}





\begin{theo}[Propri\'et\'es de stabilit\'e]
Les langages rationnels et alg\'ebriques 
sont stables par union, produit, \'etoile,
 miroir, homomorphisme, homomorphisme inverse,
substitution rationnelle, r\'esiduel...
Les langages rationnels sont \'egalement clos par passage au 
compl\'ementaire et intersection.
\end{theo}

On peut toutefois donner l'exemple de stabilit\'es bien moins triviales~:
$L$ \'etant un langage rationnel sur un alphabet $\Sigma$ de cardinalit\'e quelconque, on peut
montrer  avec la notion sophistiqu\'ee de 
transduction rationnelle (hors programme) que les langages suivants sont rationnels
 $\sqrt L=\{w \in \Sigma^* | ww\in L\}$,
et 
$\frac{1}{2}L=\{u \in \Sigma^* | \exists v\in \Sigma^*$ avec $uv\in L$
 et $|u|=|v|\}$.

En dehors des propri\'etes de stabilit\'e (on dit aussi cl\^oture ou fermeture),
un moyen courant et pratique pour montrer qu'un langage (n') est (pas)
rationnel (respectivement alg\'ebrique) sont les lemmes d'it\'erations.

\begin{prop}[Lemme d'it\'eration pour les rationnels, ex.2 TD2]
Si $L$ est ration\-nel alors il existe un certaine longueur $k$ \`a partir de laquelle pour tout mot $w$ de longueur $\geq k$ qui admet une d\'ecomposition $w=\alpha u\beta$ (avec $\alpha$, $u$ et $\beta$ non vides),
on a $\forall n, \alpha u^n \beta \in L$. Connu aussi sous le nom 
de lemme de l'\'etoile (pumping lemma).
Application~: $\{a^nb^n\}$ n'est pas rationnel.
\end{prop}
\begin{prop}[Lemme d'it\'eration pour les alg\'ebriques]
Si $L$ est alg\'e\-bri\-que, alors il existe une certaine longueur $k$ 
\`a partir de laquelle pour tout mot $w$ de longueur $\geq k$ 
qui admet une d\'ecomposition $w=\alpha u\beta v\gamma$ 
(avec soit $u$ soit $v$ non vide et soit $\alpha$ soit $\gamma$ 
non vide), on a  $\forall n, \alpha u^n \beta v^n \gamma \in L$.
Applications~: $\{a^nb^nc^n\}$ n'est pas alg\'ebrique~; 
{\bf Alg} n'est pas stable par intersection et compl\'ementaire.
\end{prop}


\begin{defi}[Ambig\"uit\'e, TD1]
Si dans une grammaire, il existe un mot qui peut \^etre obtenu de deux 
 fa\c{c}ons diff\'erentes \`a partir de l'axiome (c'est-\`a-dire plus
 rigoureusement si ce mot 
poss\`ede plusieurs arbres de d\'erivation), on dit que la grammaire 
est ambig\"ue. Il existe des langages alg\'ebriques dont toutes 
les grammaires qui les engendrent sont ambig\"ues~; un exemple de langage ainsi
inh\'eremment ambigu est donn\'e par $\{a^nb^mc^p$ avec $n=m$ ou $m=p\}$.
\end{defi}

\begin{defi}[Compl\'etude, TD3]
Un automate est dit complet si chacun de ses \'etats poss\'ede une transition
\'etiquet\'ee par chacune des lettres de l'alphabet.
Quitte \`a rajouter un \'etat puits, 
tout automate peut \^etre rendu complet. 
\end{defi}

\begin{defi}[D\'eterminisation, TD3]
Un automate est dit d\'eterministe si on n'a jamais de choix, d'h\'esitation dans 
les transitions. Plus formellement, on a un seul \'etat initial puis, 
pour chaque \'etat, pas plus d'une transition par lettre.
Tout automate peut \^etre rendu d\'eterministe. 
%(En revanche, un
%automate \`a pile ne peut pas forc\'ement \^etre rendu d\'eterministe.)
\end{defi}

\begin{defi}[Minimisation]
Un automate est dit minimal s'il n'y a pas d'automate avec moins d'\'etats
qui engendre le m\^eme langage.
Tout automate peut \^etre minimis\'e. Tout langage rationnel admet un
unique automate minimal.
\end{defi}



\begin{defi}[R\'ecursivement \'enum\'erable]
Les grammaires contextuelles (i.e. dont les membres {\em gauches} des 
productions peuvent contenir des terminaux et des non-terminaux)
engendre une classe de langages, appel\'es r\'ecursivement \'enum\'erables.
Ces derniers correspondent aux machines de Turing. 
\end{defi}

\begin{conj}[Th\`ese de Church]
On conjecture que tout ce que le cerveau humain peut calculer est
effectivement calculable par une machine de Turing. Tout langage
humain est ainsi r\'ecursivement \'enum\'erable.
\end{conj}



\section{Compilation}
La compilation d'un programme est la succession des \'etapes suivantes~:
\begin{center}
programme source
$$\Downarrow$$
\begin{tabular}{|c|c|}
\hline
analyse lexicale (``scanner'') & Lex\\
\hline
analyse syntaxique (``parser'') & Yacc\\
\hline
analyse s\'emantique\\
g\'en\'eration du code interm\'ediaire & \\
optimisation du code & tpc \\
g\'en\'eration de code  &  \\
\hline
\end{tabular}
$$\Downarrow$$
programme ex\'ecutable
\end{center}


L'optimisation de code consiste essentiellement 
\`a compacter l'arbre de d\'eri\-va\-tion
(on le transforme en DAG, directed acyclic graph, graphe orient\'e sans cycle)
 afin de ne pas refaire deux fois un m\^eme calcul.
Notez que le programme ex\'ecutable d\'epend profond\'ement 
de la machine (architecture PC/Mac/Alpha...) et de son
syst\`eme d'exploitation (Dos/Windows/Unix/Linux)
alors que le programme source tend vers une certaine universalit\'e.


L'analyse lexicale lit les lettres du  programme source
une \`a une et reconna\^{\i}t des 
"mots-clefs" ou des "nombres" (lex\`emes ou token en anglais).
On a alors traduit le programme source en un nouveau mot $u$ 
(sur l'alphabet des lex\`emes).

L'analyse syntaxique (qui pr\'esuppose que l'on s'est fix\'e une grammaire non-ambig\"ue)
essaie alors de trouver {\em la} d\'erivation de l'axiome en $u$.
L'id\'ee de base consiste \`a promener une fen\^etre de longueur $k$ 
sur le mot $u$ et d'en d\'eduire quelle suite de r\`egles de r\'ecritures
ont \'et\'e employ\'ees pour produire ce mot.
Il y a deux strat\'egies.
\begin{defi}[analyse montante]
On part de $u$ et on essaie d'atteindre l'axiome.
\end{defi}
Exemple : analyse LR($k$). La suite des r\'eductions, prise \`a
l'envers, donne la suite des r\`egles \`a appliquer pour avoir une
d\'erivation droite de l'axiome en $u$.
\begin{defi}[analyse descendante]
On part de l'axiome et on essaie d'atteindre $u$.
\end{defi}
Exemple : analyse LL($k$). La suite des r\`egles donne
 une d\'erivation gauche de l'axiome en $u$.

\begin{defi}[Tables d'analyse, TD4]
Pour nous aider dans cette t\^ache,  
il existe des tables d'analyse. Elles se construisent en calculant les 
Follow($k$), First($k$)...
\end{defi}

Il existe de nombreuses analyses : LL($k$), LR($k$), SLR... 
Signalons que Yacc (construit) et utilise une table LALR(1).
Voir le TD4 pour une analyse LR(1).

Quand on compile un programme, on est amen\'e \`a sauvegarder les
 diff\'erentes valeurs/types des variables, tout ceci se fait via une
 pile (voir le TD5 pour la gestion de la pile). On peut ainsi
 facilement faire les calculs associ\'es \`a l'arbre d'\'evaluation
li\'e \`a l'arbre de d\'erivation que vient de trouver l'analyse
 syntaxique (les $\$\$:=\$1 +\$3$ de Yacc).


\begin{rema}[Puissance/pile]
Quand on n'a pas de pile, on a la puissance des langages rationnels~;
quand on a une pile ($\sim$ un compteur) on a la puissance des langages
alg\'ebriques~; quand on a plusieurs piles, on a la puissance d'une
machine de Turing.
\end{rema}
\section{Bibliographie}

Puisque vous rechignez \`a lire des livres/articles en anglais,
je puis vous conseiller, en plus du cours en amphi et des TD/TP, 
les ouvrages suivants : 
\begin{itemize}
\item Compilation. Cours de licence de Dominique Perrin. Jussieu, 1986-1987.
\item Th\'eorie des langages et des automates. J.-M. Autebert. Masson,
1994.
\item Le petit manuel sur Lex et Yacc qui vous a \'et\'e distribu\'e. 
\end{itemize}


\section{Examen}
J'esp\`ere que vous aurez un aper\c{c}u plus clair 
de la th\'eorie des langages et de la compilation avec ces quelques
pages.
Apr\`es avoir lu ces quelques pages, assurez-vous que vous ma\^itrisez les techniques de
 bases (manipulation d'expressions rationnelles, 
d\'eterminisation d'un automate, utilisation d'une table LR(1),
trouver une d\'erivation d'un mot pour une grammaire donn\'ee)
 et pouvez interpr\'eter 
ce que fait un .l et un .y (e.g. exprlex.l et expr.y).
Nota bene~: ceci peut ne vous aider en rien a l'examen, 
ce n'est pas moi qui fais le sujet~!\\
Bonnes r\'evisions~! :-)
\end{document}