\input{transparstyle}

\begin{document}
\LARGE
\titre{Chapitre 2}
\titre{Minicompilateur}
\bigskip
\begin{enumerate}
\item Syntaxe
\item Traduction dirig\'ee par la syntaxe
\item Analyse syntaxique
\item Analyse lexicale
\item Int\'egration des techniques
\end{enumerate}

\pagebreak

\titre{Aper\c{c}u}
Construction d'un traducteur d'expressions arithm\'etiques en
notation postfixe = code interm\'ediaire.

On d\'ecrit la syntaxe par une {\em grammaire}.

On emploie la m\'ethode de {\em traduction di\-ri\-g\'ee par la syntaxe}.

 On aura (dans un deuxi\`eme temps) des identificateurs trait\'es dans
une table des symboles.

\Lafig{minicomp}{173mm}{22mm}{700}{Partie frontale}
\pagebreak

\titre{Syntaxe}
On sp\'ecifie la syntaxe par une {\em grammaire}. Une {\em r\`egle} est
de la forme
\[inst\rightarrow \mbox{\bf if } (exp) \: inst \mbox{ \bf else } inst\]
On aura par exemple une grammaire pour les listes de chiffres s\'epar\'ees par
des $+$ ou $-$ :
\begin{eqnarray*}
list &\rig!
htarrow& list+chiffre\\
list &\rightarrow& list-chiffre\\
list &\rightarrow& chiffre\\
chiffre &\rightarrow& 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
\end{eqnarray*}
ou encore pour les blocs d'instructions:
\begin{eqnarray*}
bloc &\rightarrow& \mbox{\bf begin } opt\verb+_+insts \mbox{ \bf end}\\
opt\verb+_+insts &\rightarrow& inst\verb+_+list\: |\: \epsilon\\
inst\verb+_+list &\rightarrow& inst\verb+_+list;\:inst
\end{eqnarray*}

\pagebreak

\titre{Arbre d'analyse}
On utilise les grammaires pour construire des arbres d'analyse. Par exemple:

\Lafig{arbre1}{101mm}{93mm}{600}{Un arbre d'analyse}
Une notion importante est l'ambiguit\'e des grammaires. Par exemple, la grammaire
\begin{eqnarray*}string&\rightarrow& string+string | string-string\\
&&|0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
\end{eqnarray*}
est ambigu\"e.

\pagebreak
	
\titre{Une grammaire non-ambigu\"e}
On utilise trois niveaux de priorit\'e pour exprimer
\begin{enumerate}
\item L'associativit\'e de gauche \`a droite
\i!
tem La priorit\'e de $*$ et / sur + et $-$. 
\end{enumerate}

On aura d'abord
\[factor\rightarrow \mbox{ \bf chiffre }| (expr)\]
pour les expressions de base. Puis
\begin{eqnarray*}
term&\rightarrow&term*factor\\
&&|term/factor\\
&&|factor
\end{eqnarray*}
pour le deuxi\`eme niveau. Et enfin
\begin{eqnarray*}
expr&\rightarrow&expr+term\\
&&|expr-term\\
&&|term
\end{eqnarray*}
pour le troisi\`eme.
 

\pagebreak

\titre{Traduction dirig\'ee par la syntaxe}

On calcule des {\em attributs} s\'emantiques associ\'es aux constructions
syntaxiques. Par exemple: la valeur d'une expression, l'adresse d'une variable,...
Le calcul se fait sur l'arbre d'analyse.

Les attributs peuvent \^etre :
\begin{enumerate}
\item synth\'etis\'es : calcul\'es en remontant dans l'arbre d'analyse.
\item h\'erit\'es : en descendant (ou en allant horizontalement)
\end{enumerate}

\pagebreak

\titre{Attributs synth\'etis\'es}
Calcul de la valeur d'une expression :

\vspace{5mm}
\begin{tabular}{l|l}
\hline \!
hline
REGLE &  ACTION \\ \hline
$L \rightarrow E$ {\bf n} & $print(E.val)$\\
$E \rightarrow E+T$ & $E.val:=E_1.val+T.val$\\
$E \rightarrow T$ & $E.val:=T.val$\\
$T \rightarrow T*F$ & $T.val:=T_1.val\times F.val$\\
$T \rightarrow F$ & $T.val := F.val$ \\
$F \rightarrow (E)$ & $ F.val:= E.val$\\
$F\rightarrow${\bf chiffre} & $F.val:=${\bf chiffre}$.lexval$\\
\hline 
\end{tabular}


\pagebreak

\titre{Sch\'emas de traduction}
On ajoute aux r\`egles de la grammaire des {\em actions} qui calculent les attributs.
On fixe de plus un ordre de visite de l'arbre d'analyse: l'ordre de l'exploration
en profondeur ({\it `depth-first search'}).

Par exemple, le sch\'ema:
\[\begin{array}{llll}
expr&\rightarrow&expr+term\:\:&\{print('+')\}\\
expr&\rightarrow&expr-term\:\:&\{print('-')\}\\
expr&\rightarrow&term\\
term&\rightarrow&0\:\:&\{print('0')\}\\
term&\rightarrow&1\:\:&\{print('1')\}\\
\ldots\\
term&\rightarrow&9\:\:&\{print('9')\}
\end{array}\]
effectue la traduction en forme suffixe.!


\pagebreak

\titre{Analyse syntaxique}
L'analyse syntaxique est la construction de l'arbre d'analyse \`a partir
de la suite de symboles. Il existe deux grandes classes de m\'ethodes:

\begin{enumerate}
\item descendante : c'est la m\'ethode la plus facile.
\item ascendante : permet de traiter plus de cas.
\end{enumerate}

\noindent Principe de la m\'ethode descendante ({\it 'top-down-parsing'} ou {\it
`recursive descent'}):
\begin{enumerate}
\item Associer une fonction \`a chaque non-terminal de la grammaire.
\item Utiliser une variable globale pour explorer le texte.
\item Ex\'ecuter les productions de la grammaire.
\end{enumerate}


\pagebreak

\titre{Premier programme}

R\'ealise la traduction infixe/suffixe limit\'ee
\`a des \framebox{expressions additives}.

Les lex\`emes sont constitu\'es d'un seul caract\`ere et donn\'es
par la fonction standard \verb+getchar+.

La fonction \verb+match+ v\'erifie les lex\`emes et lit le suivant.
Elle appelle \verb+error+ si la lectu!
re est incorrecte.
\begin{verbatim}
#include <ctype.h> /*charge isdigit */
int lookahead;

main()
{
   lookahead = getchar();
   expr();
   putchar('\n'); /* ajoute newline */
}

\end{verbatim}

\pagebreak
\titre{Les expressions}
On transforme une expression de la forme
\[term_1+term_2+\ldots +term_n\]
en 
\[term_1\:term_2\:+\ldots term_n+\]
d'o\`u le programme:

\begin{verbatim}

expr()
{
   term();
   while(1)
      if (lookahead == '+') {
         match('+'); term(); putchar('+');
      }
      else if (lookahead == '-') {
         match('-'); term(); putchar('-');
      }
      else break;
}
\end{verbatim}

\pagebreak

\titre{Les termes}
La reste est de l'analyse lexicale : 

\begin{verbatim}

term()
{
   if (isdigit(lookahead)) {
      putchar(lookahead);
      match(lookahead);
   }
   else error();
}

match(int t)
{
   if (lookahead == t)
      lookahead = getchar();
   else error();
}
\end{verbatim}
\pagebreak

\titre{Traitement des erreurs}
Il est r\'eduit \`a la pl!
us simple expression :

\begin{verbatim}

error()
{
   printf("syntax error\n");
      /*ecrit un message d'erreur*/
   exit(1); /*arrete l'execution */
} 
\end{verbatim}

\pagebreak

\titre{Analyse lexicale}
On souhaite \'eliminer les blancs, lire des constantes,
des identificateurs.

Paire {\em producteur-consommateur} avec \\ l'analyseur syntaxique. 

\Lafig{analex}{160mm}{25mm}{700}{Insertion de l'analyse lexicale}

L'analyseur lexicale passe le couple du type de lex\`eme
 et de son attribut \`a l'analyseur syntaxique. Ainsi
\[12+45-8\]
est transform\'e en
\[\!\!\!\!<\mbox{\bf num},12><+, ><\mbox{\bf num},45><-, ><\mbox{\bf num},8>\]

\pagebreak

\titre{Impl\'ementation}

\Lafig{lexan}{165mm}{70mm}{600}{Interactions}
Le type du lex\`eme est un entier repr\'esent\'e comme une constante
symbolique :

\begin{verbatim}
#define NUM 256
\end{verbatim}


\pagebreak

\titre{Programme}
Code C pour \'eliminer les blancs et rassembler les nombres.
\begin{verbatim}
#include <stdio.h!
>
#include <ctype.h>

int lineno = 1;
int tokenval = NONE;

int lexan()   /*analyseur lexical*/
{
 int t;
 while(1) {
    t = getchar();
    if (t == ' ' || t == '\t')
        ; /*effacer les blancs*/
    else if (t == '\n')
      lineno = lineno + 1;
    else if (isdigit(t)) 
      {   /* t est un chiffre*/
      tokenval = t - '0';
      t= getchar();
      while (isdigit(t)) {
         tokenval = tokenval*10 + t-'0';
         t = getchar();
      }
      ungetc(t,stdin); 
      return NUM;
    }
    else {
       tokenval = NONE;
       return t;
    }
  }
}
\end{verbatim}
\pagebreak

\titre{Ajout d'une table des symboles}
La table des symboles utilise deux fonctions:

\verb+insert(s,t)+: retourne une nouvelle entr\'ee pour la chaine $s$, correspondant
au lex\`eme $t$.

\verb+lookup(s)+: retoune un indice pour la chaine $s$ ou 0 si $s$
n'apparait pas.

On peut ainsi traiter les {\em mots cl\'e} :

\verb+insert("div", +{\bf div})


L'analyseur utilise un tampon \verb+lexbu!
f+ 
\pagebreak

\Lafig{symtable}{165mm}{119mm}{600}{Structures de donn\'ees}
\titre{Sch\'ema}
\pagebreak

\Lafig{schema}{161mm}{95mm}{700}{Modules du traducteur}

\vspace{2cm}
Listing sur amertume :
\begin{verbatim}
/ens/mpb/Compilation/minicompilateur
\end{verbatim}
\pagebreak

\end{document}