%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%  Compilation
%  Cours 2  Minicompilateur
%  version du 10 fevrier 2003
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%% en tete %%%%%%%%%%%%%%%%%%%%%%%%%%%%
\documentclass{article}
\pagestyle{headings}
\markright{Cours 2 : Minicompilateur}
\usepackage{color}
\usepackage{graphics}

\newcommand{\titre}[1]{\begin{center}{\huge \bf\textcolor{red} {#1}}\end{center}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{document}
\LARGE


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

\begin{figure}[hbt]

\scalebox{.8}{\includegraphics{minicomp.eps}}
\caption{Partie frontale}
\end{figure}
\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 &\rightarrow& 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:

\begin{figure}[hbt]

\includegraphics{arbre1.eps}
\caption{Un arbre d'analyse}
\end{figure}

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

\pagebreak
        
\titre{Une grammaire non-ambigue}
On utilise trois niveaux de priorit\'e pour exprimer
\begin{enumerate}
\item L'associativit\'e de gauche \`a droite
\item 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 Executer les productions de la grammaire.
\end{enumerate}


\pagebreak

\titre{Premier programme}

R\'ealise la traduction infixe/suffixe limit\'ee
 \`a des 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 lecture 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+term+\ldots +term\]
en 
\[term\:term\:+\ldots term+\]
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(t)
   int t;
{
   if (lookahead == t)
      lookahead = getchar();
   else error();
}
\end{verbatim}
\pagebreak

\titre{Traitement des erreurs}
Il est r\'eduit \`a la plus 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. 

\begin{figure}[hbt]

\scalebox{.8}{\includegraphics{analex.eps}}
\caption{Insertion de l'analyse lexicale}
\end{figure}

L'analyseur lexical 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}

\begin{figure}[hbt]
\scalebox{.8}{\includegraphics{lexan.eps}}
\caption{Interactions}
\end{figure}
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+lexbuf+ 
\begin{figure}[hbt]

\scalebox{.6}{\includegraphics{symtable.eps}}
\caption{Structure de donn\'ees}
\end{figure}

\pagebreak

\titre{Schema}
\begin{figure}[hbt]

\scalebox{.8}{\includegraphics{schemaSym.eps}}
\caption{Modules du traducteur}
\end{figure}

\pagebreak
\titre{Le programme}
\begin{verbatim}
/******* global.h ************/

#include <stdio.h>    /*charge des routines i/o*/
#include <ctype.h>    /*charge les routines de */
                      /*test de caract\`eres*/
#include <string.h>

#define BSIZE  128  /*taille du tampon*/
#define NONE    -1
#define  EOS   '\0'

#define NUM    256
#define DIV    257
#define MOD    258
#define ID     259
#define DONE   260

int  tokenval;  /*valeur de l'attribut du lexeme*/
int  lineno;

struct entry {  /*structure des elements de la */ 
  char *lexptr;    /*table des symboles*/
  int token;
};

extern struct entry symtable[];  /*table des symboles*/

void init(void);

void error(char *m);

void emit(int t, int tval);

int insert(char s[], int tok);

void parse(void);

void expr(void);

void term(void);

void factor(void);

void match(int t);

int lexan(void);

int lookup(char s[]);

/************** init.c *********/

#include "global.h"

struct entry keywords[] = {
     "div", DIV,
      "mod", MOD,
      0,   0
};

init()   /* charge les mots-cle dans la table */
{
     struct entry *p;
     for (p = keywords; p->token; p++)
        insert(p->lexptr, p->token);
}
/************ main.c **************/

#include "global.h"

main()
{
     init();
     parse();
     exit(0);    /*terminaison normale*/
}


/********** lexer.c *************/

#include "global.h"

char lexbuf[BSIZE];
int  lineno=1;
int tokenval = NONE;
extern char lexemes[];
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*/
      ungetc(t, stdin);
      scanf("%d", &tokenval);
      return NUM;
    }
    else if (isalpha(t)) { /*t est une lettre*/
      int i,p, b =0;
      while (isalnum(t)){ /*t est alphanum. */
        lexbuf[b] = t;
         t = getchar();
          b = b+1;
         if (b >= BSIZE)
            error("erreur de compilation");
       }
       lexbuf[b] = EOS;
       if (t!= EOF)
           ungetc(t, stdin);
       p = lookup(lexbuf);
        if (p == 0)
            p=insert(lexbuf, ID);
        tokenval = p;
        return symtable[p].token;
    }
    else if (t == EOF)
      return DONE;
    else {
       tokenval = NONE;
       return t;
    }
  }
}


/********** parser.c *************************/

#include "global.h"
int lookahead;

parse()    /* analyse et traduit la liste */ 
{           /* d'expressions*/
  lookahead = lexan();
   while (lookahead != DONE ) {
     expr(); match(';');
   }
}

expr()
{
   int t;
   term();
   while(1)
     switch (lookahead) {
     case '+': case '-':
       t = lookahead;
       match(lookahead); term(); emit(t, NONE);
       continue;
     default:
       return;
     }
}

term()
{
     int t;
     factor();
     while(1)
       switch(lookahead) {
       case '*': case '/': case DIV: case MOD:
         t = lookahead;
         match(lookahead); factor(); emit(t, NONE);
         continue;
       default:
         return;
       }
}

factor()
{
     switch(lookahead) {
         case '(':
            match('(');expr();match(')');break;
         case NUM:
            emit(NUM, tokenval); match(NUM); break;
         case ID:
            emit(ID, tokenval); match(ID); break;
         default:
            error("syntax error");
     }
}

match(int t)
{
     if (lookahead == t)
       lookahead = lexan();
     else error("syntax error");
}
/******** symbol.c ************/

#include "global.h"

#define STRMAX 999  /*taille de la table lexemes*/
#define SYMMAX 100   /* taille de symtable*/
char lexemes[STRMAX];
int lastchar = -1; /*derniere position */
                  /* utilisee dans lexemes*/
struct entry symtable[SYMMAX];
int lastentry= 0; /*derniere position */
                  /* utilisee dans symtable*/

int lookup(char s[])   /*retourne la position */
               /* d'une entree pour s */

{
   int p;
   for (p= lastentry; p > 0; p = p-1)
      if (strcmp(symtable[p].lexptr, s) == 0)
          return p;
   return 0;
}

int insert(char s[], int tok)   /*retourne la position */
                    /* d'une entree pour s */
 
{
    int len;
    len = strlen(s);   /* strlen calcule la */
                      /*  longueur de s */
    if (lastentry + 1 >= SYMMAX)
        error( "table pleine");
    if (lastchar + len + 1 >= STRMAX)
      error("tableau des lexemes plein");
    lastentry = lastentry + 1;
    symtable[lastentry].token = tok;
    symtable[lastentry].lexptr
                = &lexemes[lastchar + 1];
    lastchar = lastchar + len + 1;
    strcpy(symtable[lastentry].lexptr, s);
    return lastentry;
}
/************* error.c *************/

#include "global.h"

error(char *m)    /* engendre les messages d'erreur */
{
     fprintf(stderr, "line %d: %s\n", lineno, m);
     exit(1);   /*terminaison anormale*/
}
/*************** emitter.c ****************/

#include "global.h"

emit(int t,int tval)   /*engendre l'output*/
{
     switch(t) {
      case '+': case '-': case '*': case '/':
        printf("%c\n",t); break;
      case DIV:
        printf("DIV\n"); break;
      case MOD:
        printf("MOD\n"); break;
      case NUM:
        printf("%d\n", tval); break;
      case ID:
        printf("%s\n", symtable[tval].lexptr);
        break;
      default:
        printf("token %d, tokenval %d\n", t, tval);
     }
}
\end{verbatim}


\end{document}