
\documentclass{article}

\usepackage[latin1]{inputenc}
\usepackage[T1]{fontenc}
\usepackage[francais]{babel}

\newcommand\esp{\hspace{1cm}}
\newcommand\chap{\^{ }}
\begin{document}

\noindent \Large {\bf Universit\'e d'Orl\'eans} \hfill {\bf Ma\^{\i}trise d'Informatique}

\normalsize
%\hfill {\bf Ann\'ee 2001-02}

\Large
\begin{center}
{\it Feuille de Travaux Dirig\'es 0}\\
Prise en main de {\bf Lex} et {\bf Yacc}
\end{center}
\hrule

\normalsize

\section{Petit manuel de lex et yacc}


Copiez chez vous les fichiers {\tt lexgram.l} et {\tt gram.y}
se trouvant dans le répertoire

\esp
\begin{tabular}{l}
{\tt /home/info/ens/todinca/Compilation/lex-yacc/V0}\\
\end{tabular}


Pour compiler, il suffit de faire:

\esp
\begin{tabular}{l}
{\tt lex lexgram.l}\\
{\tt yacc gram.y}\\
{\tt gcc y.tab.c}\\
\end{tabular}


ce qui aura comme effet de créer un fichier exécutable {\tt a.out}.

\subsection{Structure des fichiers {\bf lex}}


{\bf Lex} est un outil standard d'analyse lexicale. Un fichier lex est
de la forme~:

\esp
\begin{tabular}{l}
{\tt déclarations}\\
{\%\%}\\
{\tt productions}\\
{\%\%}\\
{\tt code additionnel}\\
\end{tabular}

\begin{itemize}
\item La partie {\tt déclarations} contient des expressions régulières 
définissant des notions non terminales, telles que lettre, chiffre et nombre. 
Ces spécifications sont de la forme~: {\tt notion expression\_régulière}
(cf. annexe \ref{app:reg_lex}).

Elle peut contenir aussi du code en langage cible (en occurrence le C)
encadré entre $\%\{$ et $\%\}$, par exemple~:

\begin{tabular}{l}
$\%\{$\\
$\#${\tt include <stdio.h>}\\
$\%\}$\\
\end{tabular}

\item Les {\tt productions} ont la forme~: {\tt 
expression\_régulière action}. Lorsque {\tt action} est absente, {\bf Lex} 
recopiera 
les caractères tels quels sur la sortie standard. Si {\tt  action} est 
présente, elle devra être écrite en langage cible.

Typiquement, une action retourne comme résultat un symbole terminal
de la grammaire (nombre, opérateur, mot clef).
Remarquez l'existence des variables {\tt yytext}, qui contient
le texte correspondant à l'unité lexicale, et {\tt yylval}, 
qui permet d'associer une valeur (un attribut) à cette unité 
lexicale (voir aussi la description de {\bf yacc}). 

\item On peut enfin utiliser la dernière partie pour écrire du code en 
langage cible.
\end{itemize}

\subsection{Structure des fichiers {\bf yacc}}

Les fichiers yacc ont une structure similaire aux fichiers lex~:

\esp
\begin{tabular}{l}
{\tt déclarations}\\
{\%\%}\\
{\tt productions}\\
{\%\%}\\
{\tt code additionnel}\\
\end{tabular}

\begin{itemize}
\item La partie {\tt déclarations} est formée de~:
\begin{itemize}
\item Spécifications écrites dans le langage cible, placées entre $\%\{$ 
	et $\%\}$, ces deux symboles étant obligatoirement en début de ligne. 
\item Les déclarations des terminaux pouvant être rencontrés, à l'aide du
	 mot-clé {\tt $\%$token} 
\item Le type de donnée du terminal courant, avec le mot-clé {\tt $\%$union} 
\item Des informations donnant la priorité et l'associativité des opérateurs. 
\item L'axiome de la grammaire, avec le mot-clé {\tt $\%$start} (si celui-ci 
	n'est pas précisé, l'axiome de la grammaire est la première 
	production de la deuxième partie). 
\end{itemize}

\item La zone des {\tt productions}, qui ne peut pas être vide, contient
des productions de la grammaire du langage choisi et éventuellement
des déclarations et/ou définitions encadrées par $\%\{$ et $\%\}$.

Observez l'utilisation des attributs de la grammaire à l'aide des opérateurs
$\$\$$ et $\$n$.

\item Le {\tt code additionnel} devra obligatoirement comporter une 
déclaration du {\tt main()} (qui devra appeler la fonction {\tt yyparse())}, 
et de la fonction {\tt yyerror(char *message)}, appelée lorsqu'une erreur 
de syntaxe est trouvée.

\end{itemize}

\section{Votre travail}

\subsection{Expressions arithmétiques}

Enrichissez la grammaire pour que l'on puisse utiliser les expressions 
arithmétiques habituelles (opérateurs +,-,*,/ et parenthèses). 
Que pensez vous de l'associativité de l'opérateur ``puissance''?

\subsection{Variables}

L'objectif est de compiler un langage qui accepte en plus 
\begin{itemize}
\item des déclarations de variables, de la forme~:
{\tt decl variable1;}
\item des affectations~:
{\tt variable1 = 2+3;
variable1 = variable1*5;}
\item des instructions d'affichage~:
{\tt print variable1+3;}
\end{itemize}

\subsubsection{Un peu de syntaxe, très peu se sémantique}
Définissez un jeton {\tt VARIABLE} et une production (au niveau de
l'analyse lexicale) qui identifiera les variables.
Cette production devra associer à {\tt yylval} le nom de la
variable, donc {\tt yylval} prendra tantôt des valeurs entières
(lorsqu'il s'agit d'un nombre), tantôt des valeurs chaîne de
caractères (lorsqu'il s'agit d'une variable).

La modification du type {\tt YYSTYPE} de {\tt yylval}
se fait en rajoutant les lignes suivantes dans les déclarations
du fichier yacc~:

\begin{tabular}{l}
{\tt /* YYSTYPE, le type de yylval */}\\
{\tt $\%$union}\\
$\{$\\
{\tt \esp  int nombre;}\\
{\tt \esp  char variable$[$LG\_MAX\_ID$]$;}\\
$\}$\\
\end{tabular}

Pour indiquer qu'au symboles terminaux de type NOMBRE correspond l'attribut
{\tt yylval.nombre} et aux symboles VARIABLE correspond l'attribut
{\tt yylval.variable}, la déclaration des deux jetons prendra la forme~:

\begin{tabular}{l}
{\tt $\%$token <nombre> NOMBRE}\\
{\tt $\%$token <variable> VARIABLE}\\
\end{tabular}

L'attribut des non-terminaux {\tt expr} sera aussi {\tt yylval.nombre}~:

\begin{tabular}{l}
{\tt $\%$type <nombre> expr}\\
\end{tabular}

Pour que l'évaluation des expressions continue de fonctionner,
faites comme si chaque variable valait 0.

\subsubsection{Table des symboles}

Implémentez une table de symboles simple (un tableau dont chaque
élément est formé d'un nom de variable de d'une valeur).
Vous pouvez définir les fonctions suivantes~:

\tt
\begin{tabular}{l}
/* prototypes */\\
typedef int POS;\\
typedef int err;\\
\\
void yyerror(char*); /* traitement des ereurs */\\
\\
err init\_TDS();\\
err creer\_id(char*);\\
POS chercher\_id(char* nom); /* renvoie la position de l'ID \\
\esp			     dans la TDS  ou -1 si l'ID n'existe pas*/\\
int valeur\_id(char*); /* renvoie la valeur de l'ID;\\ 
\esp			 provoque une erreur si l'ID n'existe pas */\\
err maj\_id(char*, int); /* mise a jour de la valeur de l'ID,\\
\esp			 provoque une erreur si l'ID n'existe pas */\\
void affiche\_TDS(void);\\
\end{tabular}

\normalfont

\bigskip
On décide qu'une variable déclarée est initialisée à 0.
Vous pouvez faire fonctionner votre calculette!

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% A N N E X E S
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\appendix
\section{Expressions regulières en {\bf lex}}\label{app:reg_lex}

\begin{tabular}{ll}
Symbole & Signification \\\hline
x 	& le caractère 'x'\\
.	& n'importe quel caractère sauf $\backslash$n\\
$[$xyz$]$	& soit x, soit y, soit z\\
$[$\chap bz$]$ 	& tous les caractères, sauf b et z\\
$[$a-z$]$	& n'importe quel caractère entre a et z\\
$[$\chap a-z$]$	& tous les caractères, sauf ceux compris entre a et z\\
R*	& zéro R ou plus, où R est n'importe quelle expression\\
	&  régulière\\
R+	& un R ou plus\\
R?	& zéro ou un R (c'est-à-dire un R optionnel)\\
R$\{$2,5$\}$	& entre 2 et 5 R\\
R$\{$2,$\}$	& 2 R ou plus\\
R$\{$2$\}$	& exactement 2 R\\
"$[$xyz$\backslash$"foo"& la chaîne "[xyz"foo"\\
$\{$NOTION$\}$ & l'expansion de la notion NOTION définie plus haut\\
$\backslash$X	& si X est un "a", "b", "f", "n", "r", "t", ou "v",\\
 	& représente l'interprétation ANSI-C de $\backslash$X.\\
$\backslash$0	& le caractère ASCII 0\\
$\backslash$123	& le caractère dont le code ASCII est 123, en octal \\
$\backslash$x2A	& le caractère dont le code ASCII est 2A, en hexadécimal\\
RS	& R suivi de S\\
R|S	& R ou S\\
R/S	& R, seulement s'il est suivi par S\\
\chap R	& R, mais seulement en début de ligne\\
R\$	& R, mais seulement en fin de ligne\\
<<EOF>> & fin de fichier\\
\end{tabular}

\bigskip 

\noindent
Ainsi, la définition

\begin{tabular}{l l}
lettre &	$[$a-zA-Z$]$\\
chiffre &	$[$0-9$]$\\
identificateur  & $\{$lettre$\}$(\_|$\{$lettre$\}$|$\{$chiffre$\}$)*\\
\end{tabular}

\noindent
reconnaîtra comme identificateur les mots "intEGER", "une\_variable", "a1", 
mais pas "\_ident" ni "1variable".

\end{document}








