\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 }\\ $\%\}$\\ \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}\\ {\tt $\%$token VARIABLE}\\ \end{tabular} L'attribut des non-terminaux {\tt expr} sera aussi {\tt yylval.nombre}~: \begin{tabular}{l} {\tt $\%$type 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\\ <> & 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}