

\section{Introduction à la compilation}

\subsection{Le problème posé est...} 

Donner à un ordinateur un fichier contenant du texte, le lui faire lire et comprendre de manière à lui faire exécuter un certain nombre de tâches associées à ce fichier

$\Rightarrow$ On fait une compilation.\\

\subsection{Les diverses phases d'une compilation}

Détaillons succintement les différentes phases d'une compilation...

\subsubsection{L'analyse lexicale}

On analyse le flux d'entrée de manière à le découper  en unités lexicales, ou \emph{lexèmes}\index{lexèmes}.

\begin{Ex}
Dans \emph{if (temps == beau ) \{} etc., les unités lexicales sont \og if \fg{}, \og ( \fg{}, \og temps \fg{}, \og == \fg{}, \og beau \fg{}, \og ) \fg{}.
\end{Ex}


\subsubsection{L'analyse syntaxique}

Les contraintes à respecter pour que le texte soit compréhensible sont-elles respectées ? En d'autres termes, le flux de lexèmes est-il conforme à la syntaxe du langage utilisé (par comparaison à la grammaire du langage, \emph{c.f.} ci-dessous) ?

\subsubsection{L'analyse sémantique}

Reconnaître la signification d'un texte syntaxiquement correct : essayer de comprendre ce que cela signifie (le sens).

Cela implique notemment la transformation de la source en une forme utilisable, qui fasse apparaître le sens du texte.

\begin{Ex}[d'analyse sémantique]
\emph{toto = titi + tutu;} est une instruction d'affectation à la variable \og toto \fg{} d'une valeur exprimée par une expression algébrique, constituée de la somme des variables \og titi \fg{} et \og tutu \fg{}.
\end{Ex}


\begin{Rem}
Certains compilateurs utilisent des structures arborescentes :

\begin{center}
\begin{picture}(94,47)(0,-47)
\put(0,-47){\framebox(94,47){}}
\node[NLangle=0.0,Nw=19.29,Nh=8.0,Nmr=2.0](n0)(33.52,-7.88){Affectation}

\node[NLangle=0.0,Nw=13.17,Nh=8.0,Nmr=2.0](n1)(12.02,-24.0){toto}

\node[NLangle=0.0,Nw=21.4,Nmr=2.0](n2)(61.62,-24.34){Addition}

\node[NLangle=0.0,Nw=13.17,Nmr=2.0](n5)(40.02,-40.0){titi}

\node[NLangle=0.0,Nw=13.17,Nmr=2.0](n6)(84.02,-40.0){tutu}

\drawedge(n0,n1){}

\drawedge(n0,n2){}

\drawedge(n2,n5){}

\drawedge(n2,n6){}



\end{picture}
\end{center}

\end{Rem}


\subsubsection{Compilation proprement dite}

Utiliser effectivement le résultat de l'analyse sémantique pour obtenir le résultat escompté, ce qui est demandé : production de code machine, traduction d'un texte dans une autre langue, etc.

\begin{Rem}
En général, ces différentes phases sont menées en parallèle.
\end{Rem}


\section{Les grammaires}

\subsection{Définition de la notion de grammaire}

\begin{Def}[Grammaire]
Une \emph{grammaire}\index{grammaire} est un ensemble de règles de syntaxe qui décrivent quels sont les constructions correctes qui sont possibles dans le langage utilisé, à l'aide de l'alphabet utilisé (alphabet ou vocabulaire).
\end{Def}

Il existe de nombreux types de grammaires, et encore bien plus de formalismes exprimés pour représenter cette grammaire.\\

Nous utiliseront pour commencer un seul symbolisme pour remprésenter les grammaires : la  formalisation BNF (Backus-Naur Form).

\subsection{Le formalisme BNF}

Dans la syntaxe BNF, une grammaire est constituée d'un ensemble de règles.\\

Chaque règle est constituée :

\begin{itemize}
 \item d'un premier membre,
 \item suivi du symbole de réécriture (::=),
 \item suivi d'un second membre, qui peut être vide.
\end{itemize}



On utilise (et on distingue) des symboles terminaux et des symboles non-terminaux (ST et SNT).


\subsection{Les symboles terminaux}

\begin{Def}[Symbole terminal]
Un \emph{symbole terminal}\index{symbole!terminal} est un symbole qui peut effectivement intervenir dans le texte analysé. 
\end{Def}


\begin{Ex}
 Dans \emph{if (temps == beau)}, \emph{if} est un symbole terminal (on trouve le mot dans le programme).
\end{Ex}

\begin{Notation}
Les symboles terminaux sont entourés par : \og \fg{}.
\end{Notation}


\subsection{Les symboles non terminaux}

\begin{Def}[Symbole non terminal]
Un \emph{symbole non terminal}\index{symbole!non terminal} (SNT) est un symbole introduit (par commodité, ou plutôt par nécessité) par le rédacteur de la grammaire pour décrire les parties du fichier d'entrée qui représentent un tout logique et permettant de simplifier l'écriture de la grammaire.
\end{Def}

\begin{Notation}
Les symboles non-terminaux sont entourés par des chevrons: $<$ $>$.
\end{Notation}

Le premier membre d'une règle de grammaire est un SNT (la règle en constitue la définition), le second membre est une famille ordonnée (éventuellement vide) de symboles, terminaux ou non.\\

Ainsi, chaque règle de la grammaire consiste en la définition d'un symbole non-terminal. Cette dernière est terminée quand tous les SNT ont reçu une définition. Une règle s'écrit finalement sous la forme :

\begin{center}
$<$SNT$>$::= suite (éventuellement vide) de ST et SNT
\end{center}


\begin{Ex}

Voici un bout de grammaire (pour la définition d'une fonction) :\\

\begin{tabular}{lll}
$<fct>$ & $::=$ & $<type> <nom> '' ( '' <parametres> '' ) '' <bloc>$\\

$<type>$ & $::=$ & $'' int ''$\\

         & $::=$ & $''char''$ 
\end{tabular}
\end{Ex}

\begin{Def}[Axiome de la grammaire]
Parmi tous les SNT, l'un d'entre eux doit désigner l'ensemble du texte à analyser, on l'appelle \emph{axiome de la grammaire}\index{grammaire!axiome}.
\end{Def}


\begin{Ex}
 $<programme~en~C> ::= <entete> <suite~de~fct>$
\end{Ex}

La grammaire est terminée quand tous les SNT ont reçu au moins une définition.



\subsection{Exercices}

\begin{Exo}
Les mots du langage $\cal L$ sont constitués d'un nombre, éventuellement nul, de $a$, suivi d'un $b$, suivi d'au moins un $c$.

Donner une grammaire BNF de ce langage.
\end{Exo}


\begin{Exo}
Les mots du langage $\cal L$ commencent par un caractère $a$, suivi d'un nombre pair (éventuellement aucun) de caractères $b$, puis de deux caractères $c$.

Donner une grammaire BNF de ce langage.
\end{Exo}


\begin{Exo}
Les mots du langage $\cal L$ sont les noms de variables en C : ils commencent obligatoirement parune lettre (majuscule ou minuscule), et se poursuivent par un nombre quelconque de chiffres, lettres ou underscore.

Donner une grammaire BNF de ce langage.
\end{Exo}


\begin{Exo}
Ecrire la grammaire, en syntaxe BNF, des formes propositionnelles. On rappelle que les opérateurs sont, par ordre de priorité croissante :
\begin{itemize}
\item Implication et équivalence (au même niveau, le moins prioritaire). Qu'ils ne sont pas associatifs (on ne peut ni les répéter, ni les faire coexister, au même niveau (c'est-à-dire, sans parenthèse), dans une expression (par exemple, $a \longrightarrow b \longleftarrow c$, ou $a \longrightarrow b \longrightarrow c$ sont incorrects).
\item Disjonction et conjonction (au même niveau, prioritaires sur implication et équivalence). Ils sont associatifs, mais on ne peut pas les mélanger : on peut écrire $a \ou b \ou c$, sans parenthèse, mais pas $a \ou b \et c$.
\item Négation, prioritaire sur tous les autres. Elle peut être répétée. Il s'agit d'un opérateur unaire préfixé.
\end{itemize}

Les noms de variable commencent par un caractère alphabétique, suivi éventuellement d'un nombre quelconque de caractères alphanumériques ou de soulignements. Il n'y a pas de constantes dans les expressions. Les opérateurs sont réalisés au clavier par les trois caractères consécutifs $<->$ pour l'équivalence, les deux caractères consécutifs $->$ pour l'implication, les lettres consécutives $ou$ pour la disjonction, $et$ pour la conjonction, et $non$ pour la négation. L'expression peut évidemment comporter des parenthèses, et ne peut être vide.
\end{Exo}


\begin{Exo}
Le langage considéré est le prototypage des fonctions en C.

Donner une grammaire BNF de ce langage.
\end{Exo}

\begin{Exo}
On accepte les deux types de phrases suivantes :
\begin{itemize}
 \item \og Marie est la mère du frère de Sonia.\fg{}
\item \og Qui est le père de l'oncle de la mère du petit fils de Paul ? \fg{}
\end{itemize}
...et tous leurs dérivés. \'Ecrire la grammaire correspondante.
\end{Exo}


\section{Un exemple complet}

\og Les expressions correctes sont constituées d'un nombre quelconque, mais non nul, de 0, suivi d'un nombre quelconque, mais non nul, de 1. \fg{}

\subsection{Principes généraux}

On conseille de suivre cette démarche :

\begin{enumerate}
\item Commencer par écrire la grammaire du langage (des expressions correctes).
\item Ecrire l'analyseur syntaxique pur.
\item Passer à l'analyseur syntaxique avec messages d'erreur.
\item Puis à l'analyseur syntaxique avec interprétation sémantique.
\end{enumerate}


\begin{Exo}
Suivez ce cheminement :
\begin{enumerate}
\item Ecrivez cette grammaire.
\item Programmez, en C, l'analyseur syntaxique pur.
\item Ecrire le programme principal associé (le main).
\item Le modifier en analyseur syntaxique avec messages d'erreur, et adaptez le programme principal en conséquence.
\item Améliorez le programme pour qu'il devienne un analyseur syntaxique avec interprétation sémantique : ici, comptez le nombre de 0 et de 1, en cas de réussite.
\end{enumerate}
\end{Exo}


\subsection{La grammaire du langage}

\begin{tabular}{lll}
$<$ expression $>$ & ::= &$<$ groupe0 $>~<$ groupe1 $>$\\

$<$ groupe0 $>$ & ::= & “0" $<$ suite0 $>$\\

$<$ suite0 $>$ & ::= & $<$ groupe0 $>$\\

& ::= &\\

$<$ groupe1 $>$ & ::= & “1" $<$ suite1 $>$\\

$<$ suite1 $>$ & ::= & $<$ groupe1 $>$\\

& ::= &\\
\end{tabular}

Il faut :

\begin{itemize}
\item Subdiviser au maximum les expressions en sous-expressions cohérentes, en n'hésitant pas à multiplier les niveaux.

\item Retarder au maximum les alternatives (en multipliant les niveaux) pour ne les faire intervenir que lorsqu'on ne peut plus faire autrement.
\end{itemize}



\subsection{Analyseur syntaxique pur}



Voici le code de l'analyseur pur : il répond par \og bon \fg{} ou \og mauvais \fg{}.


\begin{lstlisting}
#include <stdio.h>

char s[512];
char **ss;

int expression(){
    if (groupe0()==1)
	return groupe1();
    return 0;
}

int groupe0(){
    if (*ss == '0'){
	s++;
	return suite0();
    }
    return 0;
}

int suite0(){
    if (groupe0() == 0)
	return 1;
    return 1;
}
\end{lstlisting}

... même chose pour groupe1() et suite1().


Une fonction prévue pour analyser une sous-expression ne connaît pas ce qui précède et ne s'occupe pas de ce qui suit.


Passons au programme principal :


\begin{lstlisting}
int main(){
  printf("Une expression a analyser ? \n");
  scanf("%s",s);
  ss = s;
  if (expression()==1)
      if (*ss == '\0')
           printf("Bon \n");
      else
           printf("Mauvais\n");
  else
      printf("Mauvais\n");
}
\end{lstlisting}

\begin{Rem}
Toujours commencer par l'analyseur syntaxique pur.
\end{Rem}


\subsection{Analyseur syntaxique avec messages d'erreur}

\begin{lstlisting}
int groupe0(){
    if (*ss == '0'){
        ss++;
        return suite0();
    }
    printf("L'expression doit commencer par 0\n")
    return 0;
}

int suite0(){
    if (*ss == '0'){
        ss++;
        return suite0();
    }
    return 1;
}
\end{lstlisting}


Le programme principal devient alors :

\begin{lstlisting}
int main(){
  printf("Une expression a analyser ? \n");
  scanf("%s",s);
  ss = s;
  if (expression()==1)
      if (*ss == '\0')
           printf("Bon \n");
      else if (*ss == '0')
               printf("Pas de 0 apres le(s) un(s).\n");
           else
               printf("Caractere interdit : %c\n",*ss);
}
\end{lstlisting}


\subsection{Analyseur syntaxique avec interprétation sémantique}

\begin{lstlisting}
int groupe0(){
    if (*ss == '0'){
        ss++;
        return 1+suite0();
    }
    printf("L'expression doit commencer par 0\n")
    return 0;
}

int suite0(){
    if (*ss == '0'){
        ss++;
        return 1+suite0();
    }
    return 0;
}
\end{lstlisting}

Pareil pour groupe1 et suite1. Le programme principal devient alors :

\begin{lstlisting}
int main(){
  printf("Une expression a analyser ? \n");
  scanf("%s",s);
  ss = s;
  Expression = expression()

  if (*ss == '\0')
       printf("Bon \n");
  else if (*ss == '0')
           printf("Nombre de 0 : %d, nomre de 1 : %d",expression.zero, expression.un);
       else
           printf("Caractere interdit : %c\n",*ss);
}
\end{lstlisting}


où la structure \emph{Expression} et la fonction \emph{expression()} sont ainsi définis :

\begin{lstlisting}
struct Expression{
    int zero;
    int un;
}

struct Expression expression(){
    struct Expression a;
    a.zero = groupe0();
    if (a.zero !=0)
        a.un = groupe1();
    return a;
}
\end{lstlisting}


Cet exemple, et d'autres, seront (re)vus en TP.

%\end{Proof}



% \section{Exemples approfondis}
% 
% \og Les expressions correctes sont constituées d'un nombre quelconque, mais non nul, de 0, suivi d'un nombre quelconque, mais non nul, de 1. \fg{}
% 
% \subsection{Premier exemple}
% 
% \subsubsection{Principes généraux}
% 
% On conseille de suivre cette démarche :
% 
% \begin{enumerate}
% \item Commencer par écrire la grammaire du langage (des expressions correctes).
% \item Ecrire l'analyseur syntaxique pur.
% \item Passer à l'analyseur syntaxique avec messages d'erreur.
% \item Puis à l'analyseur syntaxique avec interprétation sémantique.
% \end{enumerate}
% 
% 
% \begin{Exo}
% Suivez ce cheminement :
% \begin{enumerate}
% \item Ecrivez cette grammaire.
% \item Programmez, en C, l'analyseur syntaxique pur.
% \item Ecrire le programme principal associé (le main).
% \item Le modifier en analyseur syntaxique avec messages d'erreur, et adaptez le programme principal en conséquence.
% \item Améliorez le programme pour qu'il devienne un analyseur syntaxique avec interprétation sémantique : ici, comptez le nombre de 0 et de 1, en cas de réussite.
% \end{enumerate}
% \end{Exo}
% 
% 
% \subsubsection{La grammaire du langage}
% 
% \begin{tabular}{lll}
% $<$ expression $>$ & ::= &$<$ groupe0 $>~<$ groupe1 $>$\\
% 
% $<$ groupe0 $>$ & ::= & “0" $<$ suite0 $>$\\
% 
% $<$ suite0 $>$ & ::= & $<$ groupe0 $>$\\
% 
% & ::= &\\
% 
% $<$ groupe1 $>$ & ::= & “1" $<$ suite1 $>$\\
% 
% $<$ suite1 $>$ & ::= & $<$ groupe1 $>$\\
% 
% & ::= &\\
% \end{tabular}
% 
% Il faut :
% 
% \begin{itemize}
% \item Subdiviser au maximum les expressions en sous-expressions cohérentes, en n'hésitant pas à multiplier les niveaux.
% 
% \item Retarder au maximum les alternatives (en multipliant les niveaux) pour ne les faire intervenir que lorsqu'on ne peut plus faire autrement.
% \end{itemize}
% 
% 
% 
% \subsubsection{Analyseur syntaxique pur}
% 
% 
% 
% Voici le code de l'analyseur pur : il répond par \og bon \fg{} ou \og mauvais \fg{}.
% 
% 
% \begin{lstlisting}
% #include <stdio.h>
% 
% char s[512];
% char **ss;
% 
% int expression(){
%     if (groupe0()==1)
% 	return groupe1();
%     return 0;
% }
% 
% int groupe0(){
%     if (*ss == '0'){
% 	s++;
% 	return suite0();
%     }
%     return 0;
% }
% 
% int suite0(){
%     if (groupe0() == 0)
% 	return 1;
%     return 1;
% }
% \end{lstlisting}
% 
% ... même chose pour groupe1() et suite1().
% 
% 
% Une fonction prévue pour analyser une sous-expression ne connaît pas ce qui précède et ne s'occupe pas de ce qui suit.
% 
% 
% Passons au programme principal :
% 
% 
% \begin{lstlisting}
% int main(){
%   printf("Une expression a analyser ? \n");
%   scanf("%s",s);
%   ss = s;
%   if (expression()==1)
%       if (*ss == '\0')
%            printf("Bon \n");
%       else
%            printf("Mauvais\n");
%   else
%       printf("Mauvais\n");
% }
% \end{lstlisting}
% 
% \begin{Rem}
% Toujours commencer par l'analyseur syntaxique pur.
% \end{Rem}
% 
% 
% \subsubsection{Analyseur syntaxique avec messages d'erreur}
% 
% \begin{lstlisting}
% int groupe0(){
%     if (*ss == '0'){
%         ss++;
%         return suite0();
%     }
%     printf("L'expression doit commencer par 0\n")
%     return 0;
% }
% 
% int suite0(){
%     if (*ss == '0'){
%         ss++;
%         return suite0();
%     }
%     return 1;
% }
% \end{lstlisting}
% 
% 
% Le programme principal devient alors :
% 
% \begin{lstlisting}
% int main(){
%   printf("Une expression a analyser ? \n");
%   scanf("%s",s);
%   ss = s;
%   if (expression()==1)
%       if (*ss == '\0')
%            printf("Bon \n");
%       else if (*ss == '0')
%                printf("Pas de 0 apres le(s) un(s).\n");
%            else
%                printf("Caractere interdit : %c\n",*ss);
% }
% \end{lstlisting}
% 
% 
% \subsubsection{Analyseur syntaxique avec interprétation sémantique}
% 
% \begin{lstlisting}
% int groupe0(){
%     if (*ss == '0'){
%         ss++;
%         return 1+suite0();
%     }
%     printf("L'expression doit commencer par 0\n")
%     return 0;
% }
% 
% int suite0(){
%     if (*ss == '0'){
%         ss++;
%         return 1+suite0();
%     }
%     return 0;
% }
% \end{lstlisting}
% 
% Pareil pour groupe1 et suite1. Le programme principal devient alors :
% 
% \begin{lstlisting}
% int main(){
%   printf("Une expression a analyser ? \n");
%   scanf("%s",s);
%   ss = s;
%   Expression = expression()
% 
%   if (*ss == '\0')
%        printf("Bon \n");
%   else if (*ss == '0')
%            printf("Nombre de 0 : %d, nomre de 1 : %d",expression.zero, expression.un);
%        else
%            printf("Caractere interdit : %c\n",*ss);
% }
% \end{lstlisting}
% 
% 
% où la structure \emph{Expression} et la fonction \emph{expression()} sont ainsi définis :
% 
% \begin{lstlisting}
% struct Expression{
%     int zero;
%     int un;
% }
% 
% struct Expression expression(){
%     struct Expression a;
%     a.zero = groupe0();
%     if (a.zero !=0)
%         a.un = groupe1();
%     return a;
% }
% \end{lstlisting}
% 
% \subsection{Deuxième Exemple}
% 
% 
% \og Les expressions correctes sont constituées d'un nombre quelconque mais non nul de 'a', suivi d'un 'b', suivi d'un nombre quelconque éventuellement nul de 'c'.\fg{}
% 
% 
% \begin{Exo}
% Faire le même travail que précédemment.
% \end{Exo}
% 
% 
% \subsubsection{La grammaire}
% 
% 
% \begin{tabular}{lll}
% $<$ expression $>$ & ::= &$<$ groupe a $>~“b"~<$ liste c $>$\\
% 
% $<$ groupe a $>$ & ::= & “a" $<$ suite a $>$\\
% 
% $<$ suite a $>$ & ::= & $<$ groupe a $>$\\
% 
% & ::= &\\
% 
% $<$ liste c $>$ & ::= & “c" $<$ liste c $>$\\
% 
% & ::= &\\
% \end{tabular}
% 
% \subsubsection{Analyseur syntaxique pur}
% 
% Cet analyseur syntaxique pur répond par \og Bon \fg{} ou \og Mauvais \fg .
% 
% 
% 
% \begin{lstlisting}
% #include <stdio.h>
% 
% char s[512];
% char **ss;
% 
% int expression(){
%     if (groupea()==1)
%         if (*ss == 'b'){
%             ss++;
%             return listec();
%         }
%     return 0;
% }
% 
% int groupea(){
%     if (*ss == 'a'){
% 	s++;
% 	return suitea();
%     }
%     return 0;
% }
% 
% int suitea(){
%     if (groupea() == 0)
% 	return 1;
%     return 1;
% }
% 
% int listec(){
%     if (*ss == '\0')
%         return 1;
%     else
%         if (*ss == 'c'){
%             ss++;
%             listec();
%         } else
%             return 0;
% }
% 
% 
% int main(){
%   printf("Une expression a analyser ? \n");
%   scanf("%s",s);
%   ss = s;
%   if (expression()==1)
%       if (*ss == '\0')
%            printf("Bon \n");
%       else
%            printf("Mauvais\n");
%   else
%       printf("Mauvais\n");
% }
% 
% \end{lstlisting}
% 
% 
% \subsubsection{Analyseur syntaxique avec message d'erreur}
% 
% 
% \begin{lstlisting}
% int groupea(){
%     if (*ss == 'a'){
% 	s++;
% 	return suitea();
%     } else {
%         printf("L'expression doit commencer par a \n");
%         return 0;
%     }
% }
% 
% int suitea(){
%     if (*ss == 'a'){
%         ss++;
% 	return suitea();
%     }
%     return 1;
% }
% 
% 
% int main(){
%   printf("Une expression a analyser ? \n");
%   scanf("%s",s);
%   ss = s;
%   if (expression()==1)
%       if (*ss == '\0')
%            printf("Bon \n");
%       else
%            printf("Il n'y a que des c apres le b\n");
% }
% 
% int expression(){
%     if (groupea()==1)
%         if (*ss=='b'){
%             ss++;
%             return listec();
%         } else {
%             printf("Apres le(s) a il doit y avoir un b");
%         }
%     return 0;
% }
% \end{lstlisting}
% 
% 
% 
% \subsubsection{Analyseur syntaxique avec interprétation sémantique}
% 
% 
% 
% \begin{lstlisting}
% int groupea(){
%     if (*ss == 'a'){
% 	s++;
% 	return 1+suitea();
%     } else {
%         printf("L'expression doit commencer par a \n");
%         return 0;
%     }
% }
% 
% int suitea(){
%     if (*ss == 'a'){
%         ss++;
% 	return 1+suitea();
%     }
%     return 0;
% }
% 
% 
% struct Expression expression(){
%     struct Expression un;
%     un.a = groupea();
%     if (un.a != 0 && *ss == 'b'){
%         ss++;
%         un.c = listec();
%         un.b = 1;
%     } else
%         printf("Apres le(s) a il doit y avoir un b");
%     return un;
% }
% 
% struct Expression{
%     int a;
%     int b;
%     int c;
% }
% 
% 
% int listec(){
%     if (*ss == '\0')
%         return 0;
%     else
%         if (*ss == 'c'){
%             ss++;
%             return 1+listec();
%         } else
%             return 0;
% }
% 
% int main(){
%   struct Expression un;
%   printf("Une expression a analyser ? \n");
%   scanf("%s",s);
%   ss = s;
%   un = expression();
%   if (*ss == '\0')
%       printf("Nombre de a : %d, nombre de b : 1, nombre de c : %d \n",un.a, un.c);
%   else
%       if (un.b ==1)
%            printf("Il n'y a que des c apres le b\n");
% }
% 
% int expression(){
%     if (groupea()==1)
%         if (*ss=='b'){
%             ss++;
%             return listec();
%         } else {
%             printf("Apres le(s) a il doit y avoir un b");
%         }
%     return 0;
% }
% \end{lstlisting}
% 
% 
% \subsection{Troisième exemple : les expressions algébriques}
% 
% 
% \subsubsection{Présentation du problème}
% 
% Les expressions algébriques à analyser sont constituées :
% \begin{itemize}
% \item des opérateurs + et *,
% \item des noms de variable : un caractère alphabétique.
% \end{itemize}
% 
% 
% \begin{Ex}
%  a+b+c*(d+e*(f+g))*((h+i)*j+k*l)+(m+n+o)*(p+q)*r
% \end{Ex}
% 
% On souhaite ici faire le même travail que précédemment, tout en sachant que la grammmaire devra tenir compte des deux opérateurs \emph{hiérarchisés}.
% 
% 
% \subsubsection{Règles générales d'écriture d'une grammaire hiérarchisée}
% 
% Les règles sont les suivantes :
% 
% \medskip
% 
% \begin{enumerate}
% \item L'analyse commence par l'opérateur le moins prioritaire ; cela revient à découper l'expression suivant cet opérateur.
% 
% En dehors des parenthèses :
% 
% \begin{tabular}{lll}
% $<$ somme $>$ & ::= &$<$ terme $>~<$ finSomme $>$\\
% 
% $<$ finSomme $>$ & ::= & “+" $<$ somme $>$\\
% 
% & ::= &\\
% \end{tabular}
% 
% \medskip
% 
% \item Elle continue par le deuxième opérateur, dans l'ordre croissant des priorités.
% 
% Les sous-expressions analysées sont dépourvues des opérateurs précédents (en-dehors des parenthèses).
% 
% \begin{tabular}{lll}
% $<$ terme $>$ & ::= &$<$ facteur $>~<$ finProduit $>$\\
% 
% $<$ finProduit $>$ & ::= & “*" $<$ terme $>$\\
% 
% & ::= &\\
% \end{tabular}
% 
% \medskip
% 
% \item On ne fait intervenir les parenthèses qu'après avoir épuisé tous les opérateurs. 
% 
% Les sous-expressions analysées ne comptortent alors plus aucun opérateur : plus que des lettres et des parenthèses.
% 
% 
% \begin{tabular}{lll}
% $<$ facteur $>$ & ::= &$<$ variable $>$\\
% 
% & ::= & “(" $<$ somme $>$ “)"\\
% 
% $<$ variable $>$ & ::= & “a" ... “z" (notation non BNF)\\
% \end{tabular}
% \end{enumerate}
% 
% 
% \begin{Exo}
%  \'Ecrire l'analyseur syntaxique pur.
% \end{Exo}
% 
% 
% \subsubsection{Analyseur syntaxique pur}
% 
% On pensera à inclure la bibliothèque \emph{ctype}, permettant la reconnaissance de caractères.
% 
% \begin{lstlisting}
% #include <stdio.h>
% #include <ctype.h>
% 
% char s[512];
% char *ss;
% 
% int somme(){
%     if (terme() == 1)
%         return finSomme();
%     return 0;
% }
% 
% int finSomme(){
%     if (*ss == '+'){
%         ss++;
%         return somme();
%     }
%     return 1;
% }
% 
% int terme(){
%     if (facteur() == 1;
%         return finProduit();
%     return 0;
% }
% 
% int finProduit(){
%     if (*ss == '*'){
%         ss++;
%         return terme();
%     }
%     return 1;
% }
% 
% int facteur(){
%     if (variable ==1)
%         return 1;
%     if (*ss == '('){
%         ss++;
%         if (somme() == 1)
%             if (*ss ==')'){
%                 ss++;
%                 return 1;
%             }
%         return 0;
%     }
% }
% 
% int variable(){
%     if (isalpha(*ss)){
%         ss++;
%         return 1;
%     }
%     return 0;
% }
% 
% int main(){
%     printf("\n Une expression a analyser ? ");
%     scanf("%s",s);
%     ss=s;
%     if (somme() == 1)
%         if (*ss == '\0')
%             printf("Bon\n");
%         else
%             printf("Mauvais\n");
%     else
%         printf("Mauvais\n")
% \end{lstlisting}
% 
% 
% \begin{Exo}
% Adaptez la grammaire pour qu'elle gère la soustraction et la division.
% \end{Exo}
% 
% 
% 
% \subsubsection{Grammaire enrichie}
% 
% \begin{tabular}{lll}
% $<$ somme $>$ & ::= &$<$ terme $>~<$ finSomme $>$\\
% 
% $<$ finSomme $>$ & ::= &  $<$ operateurAdditif $>~<$ somme $>$\\
% 
% & ::= &\\
% 
% $<$ operateurAdditif $>$ & ::= &  “+"\\
% 
% & ::= & “-"\\
% 
% $<$ terme $>$ & ::= &$<$ facteur $>~<$ finProduit $>$\\
% 
% $<$ finProduit $>$ & ::= &  $<$ operateurMultiplicatif $>~<$terme $>$\\
% 
% & ::= &\\
% 
% $<$ operateurMultiplicatif $>$ & ::= &  “*"\\
% 
% & ::= & “/"\\
% 
% $<$ facteur $>$ & ::= &$<$ variable $>$\\
% 
% & ::= & “(" $<$ somme $>$ “)"\\
% 
% $<$ variable $>$ & ::= & “a" ... “z"\\
% \end{tabular}
% 
% 
% \subsubsection{Version avec messages d'erreur}
% 
% \begin{lstlisting}
% #include <stdio.h>
% #include <ctype.h>
% 
% char s[512];
% char *ss;
% 
% int somme(){
%     if (terme() == 1)
%         return finSomme();
%     return 0;
% }
% 
% int finSomme(){
%     if (*ss == '+' || *ss == '-'){
%         ss++;
%         return somme();
%     }
%     return 1;
% }
% 
% int terme(){
%     if (facteur() == 1;
%         return finProduit();
%     return 0;
% }
% 
% int finProduit(){
%     if (*ss == '*' || *ss == '/'){
%         ss++;
%         return terme();
%     }
%     return 1;
% }
% 
% int facteur(){
%     if (*ss == '('){
%         if (*ss == '-' || *ss == '+') ss++;
%         ss++;
%         if (somme() == 1)
%             if (*ss ==')'){
%                 ss++;
%                 return 1;
%             }else{
%                 printf("Il manque une parenthese fermante.\n");
%                 return 0;
%             }
%     }else{
%         if (*ss == '-' || *ss == '+') ss++; 
%         if (isalpha(*ss)){
%             ss++;
%             return 1;
%         }else{
%             printf("\n\n ATTENTION :\n");
%             if (*ss == '+' || *ss == '-' || *ss == '/' || *ss == '*')
%                 printf("Deux operateurs ne peuvent pas se suivre");
%             else
%                 if (*ss == '\0')
%                     printf("L'expression ne peut pas se terminer par un operateur");
%                 else
%                     printf("Ce caractere ne fait pas partie de la grammaire : \" %c \" \n.", *ss);
%             return 0;
%         }
%     }
% }
% 
% int variable(){
%     if (isalpha(*ss)){
%         ss++;
%         return 1;
%     }
%     return 0;
% }
% 
% int main(){
%     printf("\n Une expression a analyser ? ");
%     scanf("%s",s);
%     ss=s;
%     if (*ss == '*' || *ss '/'){
%         printf("Ne peut pas commencer par un operateur binaire")
%         return c;
%     }
%     if (somme() == 1)
%         if (*ss == '\0')
%             printf("Bon\n");
%         else{
%             printf("Attention\n");
%             if (isalpha(*ss))
%                 printf("Deux variables ne peuvent se suivre.\n");
%             else if (*ss == '(' || *ss == ')')
%                 printf("Caractere mal place \" %c "\", *ss)
%             else
%                 printf("Ce caractere ne fait pas parti de la grammaire \" %c \" \n",*ss);
%         }
%     }
%     printf("\n");
%     return 1;
% } 
% \end{lstlisting}
% 
% \subsubsection{Version avec interprétation sémantique}
% 
% 
% On utilise les arbres : a+b+c devient
% \begin{lstlisting}
%                                 +
%                                / \
%                               +   c
%                              / \
%                             a   b
% \end{lstlisting}
% et -a+b :
% \begin{lstlisting}
%                                 +
%                                / \
%                               -   b
%                               |
%                               a
% \end{lstlisting}
% 
% On est en effet obligé d'associer à gauche pour la soustraction (sinon on change l'expression).
% 
% \begin{Exo}
%  Programmez cette structure d'arbre, puis la version sémantique.
% \end{Exo}
% 
% 
% 
% \begin{lstlisting}
% typedef enum {FEUILLE, UNAIRE, BINAIRE} Tnoeud;
% 
% typedef struct arbre{
%     Tnoeur selecteur;
%     union{
%         char var;
%         struct{
%             char operateur;
%             struct arbre* fs;
%         } un;
%         struct{
%             char operateur;
%             struct arbre* fd;
%             struct arbre* fg;
%         } bin;
%     } type;
% } arbre;
% 
% #include <stdio.h>
% #include <ctype.h>
% #include <stdlib.h>
% #define amalloc (arbre*)malloc (sizeof(arbre))
% #define ANULL (arbre*) NULL
% 
% arbre* feuille(char var){
%     arbre* a = ANULL;
%     if ((a = amalloc) != ANULL{
%         a->selecteur = FEUILLE;
%         a->t.var = var;
%     }
%     return a;
% }
% 
% arbre* unaire(char op, arbre* fs){
%     arbre* a = ANULL;
%     if (fs != ANULL)
%         if ((a=amalloc) != ANULL){
%             a->sel.UNAIRE;
%             a->t.un.op=op;
%             a->t.un.fs=fs;
%          }
%     return a;
% }
% 
% arbre* binaire(char op, arbre* fg, arbre* fd){
%     arbre* a = ANULL;
%     if (fg != ANULL && fd != ANULL)
%         if ((a=amalloc) != ANULL){
%             a->sel.BINAIRE;
%             a->t.un.op=op;
%             a->t.un.fg=fg;
%             a->t.un.fd=fd;
%          }
%     return a;
% }
% 
% void printa(arbre* a){
%     switch (a->sel){
%         case FEUILLE : printf("%c",a->t.var);
%                        break;
%         case UNAIRE  : printf("%c(",a->t.un.op);
%                        printa(a->t.un.fs);
%                        printf(")");
%                        break;
%         case BINAIRE : printf("%c(",a->t.bin.op);
%                        printa(a->t.bin.fg);
%                        printf(",");
%                        printa(a->t.bin.fd);
%                        printf(")");
%                        break;
%     }
% }
% 
% void print_arbre(arbre* a){
%     if (a != NULL)
%         printa (a);
%     else
%         printf("Arbre vide\n");
%     printf("\n");
% }
% 
% #define cmalloc(n) (char*)malloc((n)*sizeof(char))
% #define crealloc(ptr,n) (char*)realloc(ptr,(n)*sizeof(char))
% #define CNULL (char*)NULL
% #define BLOC 16
% 
% char* lire_chaine(){
%     char *s, *ss, *ssmax;
%     int taille, c;
%     if ((s = cmalloc(BLOC))==CNULL){
%         fprintf(stderr,"Memoire saturee\n");
%         exit(43);
%     }
%     ss=s;
%     taille = BLOC;
%     smax = s + taille;
%     while ((c=getchar()) != '\n'){
%         *ss++ = (char)c;
%         if (ss == smax){
%             if ((s=crealloc(c,taille+BLOC))==CNULL){
%                 fprintf(stderr,"Memoire saturee\n")
%                 exit(44);
%             }
%             ss=s+taille;
%             taille += BLOC;
%             smax = s+taille;
%         }
%     }
%     *ss++ = '\0';
%     return crealloc(s,ss-s);
% }
% \end{lstlisting}
% 
% 
% 
% \subsubsection{Le cas du moins unaire}
% 
% On souhaite rajouter le - unaire ; son analyse intervient au niveau du facteur :
% 
\gsaut
\centerline{\x{Fin du Chapitre}}

