\input mias

\TP 2
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\altern{\kern .2em\vrule height 1.5ex depth 0pt width .05em\kern .2em}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\parb
{\sl Des renseignements sur LEX vous sont donn\'es dans les pages ci--jointes mais la v\'eritable r\'ef\'erence reste
le `TP LEX and YACC User Manual'.}
\par\vskip .9cm
\exo
Editer le programme suivant dans un fichier {\tt ESSAI1.L}
\pars
{\tt\par	\def\K{\kern 1em}
\parm
\%\accg\par
\hskip 2cm uses lexlib ;\par
\hskip 2cm (* \par
\hskip 2cm  PRESQUE RIEN DANS LE PREMIER SECTEUR \par
\hskip 2cm  SINON uses lexlib ; ET CE COMMENTAIRE :\par
\hskip 2cm  CE SERA RECOPIE DANS ESSAI1.PAS\par
\hskip 2cm  *)
\par
\%\accd
\parm
\%\%
\parm
[\echap t ]+ \K ; \K (* instruction vide *)\par
Q \K \altern\par
q \K begin writeln('fin du programme ESSAI1') ; halt end ;\parm
suis\K \altern\par
es\K \altern\par
est\K \altern\par
sommes\K \altern\par
etes\K \altern\par
sont\K   writeln(yytext, ' :  present du verbe ETRE') ; \parm
ai\K \altern\par
as\K \altern\par
a\K \altern\par
avons\K \altern\par
avez\K \altern\par
ont\K  writeln(yytext, ' :  present du verbe AVOIR') ; \parm
[A-Za-z]+\K    writeln(yytext, '  n''est pas dans notre liste') ; \parm
.\altern\echap n\K  writeln(yytext) ; \parm
\%\%
\parm
begin\parm
\ \kern 1em yylex \parm
end.
}
\pars
\puce Compiler ce programme en LEX avec l'option {\tt /v}  et consulter
les fichiers {\tt ESSAI1.PAS} (le programme produit par LEX) et {\tt ESSAI1.LST} (une description de l'automate fini
correspondant aux expressions r\'eguli\`eres de votre programme LEX).
\puce Compiler {\tt ESSAI1.PAS} par TPC puis tester le programme {\tt ESSAI1.EXE} :
celui-- ci est cens\'e analyser la cha\^\i ne de caract\`eres que vous entrerez au clavier.
Faites plusieurs essais !
\exo Enrichir le programme pr\'ec\'edent en lui ajoutant d'autres ``tribus''
linguistiques. Tester le programme {\tt .EXE} correspondant.
\par\vskip 1cm
Par la suite, le texte \`a analyser se trouvera dans un fichier ainsi que le r\'esultat de 
l'analyse : LEX met \`a notre disposition deux variables 
\pars
{\parindent 1cm\tt\par
yyinput : text ;\par
yyoutput : text ;\par
}
\pars
auxquelles on peut assigner respectivement le nom d'un ``fichier d'entr\'ee'' (\`a analyser)
et celui d'un ``fichier de sortie'' (r\'esultat de l'analyse).
Les exercices qui suivent supposent donc que vous savez utiliser les primitives Turbo Pascal
relatives aux fichiers.
\parm
\exo Ecrire un programme LEX qui compte le nombre de lettres, de mots et de lignes d'un fichier
(la sortie pourra se faire \`a l'\'ecran). Ex\'ecuter le programme  {\tt .EXE} 
correspondant sur un fichier
de votre choix (pas trop pr\'ecieux !)
\exo Ecrire un programme LEX qui recopie un programme en Turbo Pascal en mettant tous ses mots
r\'eserv\'es en MAJUSCULES ( par exemple le mot BegIN devra \^etre recopi\'e BEGIN).
 Ex\'ecuter le programme  {\tt .EXE} correspondant sur un fichier
de votre choix (en Turbo Pascal mais pas trop pr\'ecieux !)
\par\vskip 1cm

\remm{Pr\'esentation succinte de LEX.}\endrem
\parb
La version de LEX que nous utilisons est adapt\'ee au langage Turbo Pascal.
La lecture de la pr\'esentation succinte qui suit n'est pas suffisante 
pour comprendre toutes les possiblilit\'es qui sont offertes par LEX : 
il faut aussi consulter le {\sl User Manual} et des fichiers comme, par exemple, 
{\tt LEXLIB.PAS}.
\pars
LEX est un programme qui \`a partir d'un fichier source {\tt FICHIER.L}, dont on va voir la syntaxe
par la suite, produit un programme en turbo Pascal, dont le nom par d\'efaut est {\tt FICHIER.PAS}. 
Ce dernier peut \`a son tour \^etre compil\'e pour produire un programme ex\'ecutable {\tt FICHIER.EXE},
qui n'est rien d'autre qu'un analyseur lexical.
\pars
Les deux commandes utiles sont respectivement :
\pars
{\parindent 1cm\par
{\tt LEX [options] fichier[.L] [fichier-sortie[.PAS]]}\par
{\tt TPC fichier-sortie[.PAS]}\par
}
\pars
Lorsqu'on utilise l'option bavarde {\tt /v} (v pour {\sl verbeux}), on obtient un fichier
 dont le nom a le suffixe {\tt .LST} et qui contient la description ``en clair'' de l'instrument
essentiel de l'analyse lexicale : un automate fini ! 
Il faut consulter un tel fichier au moins une fois dans sa vie.
\par\vskip 1cm 
{\bf Un fichier source LEX} se divise en trois sections, s\'epar\'ees par {\tt \%\%} :
\parb
{\tt
\%\accg\par
\hskip 1cm D\'eclarations en Turbo Pascal\par
\%\accd\par
D\'efinitions LEX\pars
\%\%\pars
r\`egles\pars
\%\%\pars
Proc\'edures Turbo Pascal auxiliaires\par
}
\parb
Chacune de ces sections peut \^etre vide ! Voyons ce qu'il est cependant 
possible d'y mettre.
\remm{Premi\`ere section.}\endrem
Les d\'eclarations en Turbo Pascal seront recopi\'ees, sans modification dans le programme
{\tt .PAS} qui est produit par LEX ; ceci se fait au tout d\'ebut dudit programme, 
c'est--\`a--dire au niveau global : 
on peut y d\'eclarer des constantes, des variables, des proc\'edures et des fonctions, des commentaires \dots
\pars
{\bf D\'efinitions LEX.} Le premier type de d\'efinition se pr\'esente sous la forme 
\pars
{\tt nom \kern 1em  expression}
\pars 
o\`u {\tt nom} est un identificateur (de type Turbo Pascal) qui pourra \^etre utilis\'e, 
dans la suite de la premi\`ere section et dans la seconde 
pour repr\'esenter l'expression r\'eguli\`ere\footnote{*}{cf. ci--dessous les d\'efinitions
pr\'ecises en LEX} {\tt expression} ; afin de distinguer cet
identificateur de la cha\^\i ne des caract\`eres qui sert \`a le d\'esigner, on l'utilisera entre
{\tt \accg\kern .2em \accd}, par exemple, on peut avoir successivement : 
\pars
{\tt
alpha [a-zA-Z]\par
alphanum  \accg alpha\accd\altern[0-9]\par
ident \accg alpha\accd\accg alphanum\accd *\par
}
\remm{La deuxi\`eme section : les r\`egles.}\endrem
Cette section donne \`a LEX les instructions qui lui sont n\'ecessaires pour d\'efinir la  fonction 
\pars
{\tt function yylex : integer ; }
\pars
La forme la plus simple d'une instruction LEX est \pars
{\tt
expression \kern 1em instruction\_simple ; \par
}\pars
o\`u {\tt instruction\_simple} est une instruction simple de Turbo Pascal, qui peut \^etre vide.
\pars
La fonction {\tt yylex} parcourt le fichier \`a analyser : 
lorsque qu'une cha\^\i ne de caract\`eres {\tt s} de ce fichier r\'epond au mod\`ele donn\'e par
{\tt expression}, la fonction {\tt yylex} a pour premier effet l'ex\'ecution de l'action
d\'efinie par l'{\tt instruction\_simple}  et affecte la valeur {\tt s} 
\`a une variable 
\pars
{\tt yytext : string ; }
\pars
d\'eclar\'ee  par LEX lui--m\^eme.
\pars
La forme g\'enerale d'une instruction LEX est la suivante : 
\pars
{\tt\def\K{\kern 1em}
r1\K\altern\par
r2\K\altern\par
\dots\par
rn\K instruction \par
}\pars
o\`u 
\puce le symbole {\tt \altern} indique que l'instruction 
est la m\^eme que pour l'expression suivante,
\puce {\tt instruction} peut \^etre une instruction simple ou compos\'ee (dans ce cas,
il faudra utiliser la syntaxe habituelle {\tt begin \dots end}, de plus, 
si l'instruction en question comporte plusieurs lignes, il faut veiller 
ne jamais commencer au d\'ebut d'une ligne car LEX tenterait de la prendre 
\`a son propre compte, comme il est dit un peu plus loin).
\pars
Lorsqu'une instruction comporte plusieurs expressions, il peut se pr\'esenter des cas d'ambigu\"\i t\'e :
c'est alors la cha\^\i ne la plus longue qui sera choisie : par exemple, si {\tt 'a'} r\'epond \`a
 {\tt ri} et {\tt 'avoir'} \`a {\tt rj}, cette derni\`ere cha\^\i ne sera reconnue et non pas 
d\'ecoup\'ee en {\tt 'a'} suivie de {\tt 'voir'}.
\parb
Il faut penser \`a la fonction {\tt yylex} comme \'etant essentiellement constitu\'ee d'une instruction
{\tt case expression of} dont les cas sont 
\pars
{\parindent 1cm\tt\par
r1, r2, \dots\ , rn : instruction\par
}
\remm{Derni\`ere section.}\endrem
Lorsque cette section est vide, le programme {\tt .PAS} se termine simplement par 
\pars
{\parindent 1cm\tt
\item{} begin\par
\itemitem{} yylex \par
\item{} end.\par
}
\pars
Sinon, vous \'ecrivez ici, en Turbo Pascal, la fin de programme que vous souhaitez !
\pars
{\bf Attention.} Un programme LEX est trait\'e ligne par ligne, avec la convention suivante, valable dans les deux premi\`eres sections :\pars
\hfil {\sl une ligne commen\c cant par un blanc est simplement recopi\'ee dans le fichier {\tt .PAS}}\pars
une instruction LEX ne doit donc jamais \^etre pr\'ec\'ed\'ee d'un blanc.
\page
\remm{Ainsi se termine la description d'un fichier Lex {\tt .L}.}\endrem
%
Voici maintenant ce qu'il est utile de savoir pour \'ecrire des expressions ``bien'' r\'eguli\`eres. 
%
\remm{Caract\`eres r\'eserv\'es.}\endrem
Ce sont les caract\`eres significatifs pour LEX lui--m\^eme, c'est--\`a--dire :
{\tt \%}, {\tt \echap}, {\tt \altern}, {\tt \accg} et {\tt \accd}, ainsi que
les caract\`eres servant \`a coder les expressions r\'eguli\`eres.
\pars
Lorsqu'on d\'esire utiliser un caract\`ere r\'eserv\'e {\tt c} pour sa valeur 
litt\'erale, on peut 
utiliser l'une des notations {\tt \echap c} ou {\tt 'c'}, par exemple : {\tt \echap\accg},
{\tt '\accg'}, {\tt '+'}, \dots
\remm{Les caract\`eres en g\'en\'eral.}\endrem
En dehors des caract\`eres r\'eserv\'es, tout caract\`ere ``imprimable'' prend
toujours sa valeur litt\'erale. Le tableau qui suit permet de r\'esoudre des cas plus sp\'eciaux :
\parb
\centerline{
\boxit{1pt}{\vbox{
\offinterlineskip
\halign{%
\tv#&&\cc{#}&\tv#\cr\trait
&Expression&&Description&\cr\trait
&{\tt \echap n}\hfill&&passage \`a la ligne\hfill&\cr\trait
&{\tt \echap r}\hfill&&retour de chariot\hfill&\cr\trait
&{\tt \echap t}\hfill&&tabulation\hfill&\cr\trait
&{\tt \echap b}\hfill&&espace arri\`ere\hfill&\cr\trait
&{\tt \echap f}\hfill&&passage \`a la page\hfill&\cr\trait
&{\tt \echap nnn}\hfill&&caract\`ere de code ASCII {\tt nnn} en octal\hfill&\cr\trait
}}}
}
\remm{Les expressions r\'eguli\`eres.}\endrem
Une expression r\'eguli\`ere caract\'erise un langage r\'egulier ; en fait, une telle expression
est le mod\`ele auquel doit correspondre une cha\^\i ne de carat\`eres 
pour appartenir au langage en question. Les tableaux suivants d\'ecrivent la fa\c con d'\'ecrire
les expressions r\'eguli\`eres qui est compr\'ehensible par un programme LEX. 
Cependant, les expressions ainsi d\'efinies ne sont enti\`erement d\'efinies que si on applique 
les conventions de ``pr\'ec\'edence'' suivantes :
\pars
{\parindent 1cm
\item{--} Les op\'erateurs {\tt *}, {\tt +}, {\tt ?} et  {\tt\accg\kern .2em\accd} ont le
plus grand degr\'e de pr\'ec\'edence,\par
\item{--} vient ensuite la {\tt concat\'enation}, qui est not\'ee par simple juxtaposion,
\par
\item{--} l'op\'erateur de mise en alternative {\tt \altern} a le plus bas degr\'e de pr\'ec\'edence.
\par
}
\pars
Les parenth\`eses {\tt (\kern .2em )} permettent de contrevenir volontairement aux conventions
pr\'ec\'edentes (par exemple {\tt a\altern b*} est le mod\`ele des cha\^\i nes qui 
commencent par une occurrence de {\tt a} et 
se poursuivent par un nombre quelconque d'occurrences de {\tt b}, alors que
{\tt (a\altern b)*} est celui de toutes les cha\^\i nes que l'on peut \'ecrire
avec les caract\`eres {\tt a} et {\tt b}). 
\pars
Enfin, {\tt<\kern .2em >} et {\tt /} ne peuvent appara\^\i tre qu'une fois 
dans une expression r\'eguli\`ere.
\parb
\centerline{
\boxit{1pt}{\vbox{
\offinterlineskip
\halign{%
\tv#&&\cc{#}&\tv#\cr\trait
&Expression&&\kern 2.5cm Description \kern 2.5cm&&Exemple&\cr\trait
&{\tt c}\hfill&&tout caract\`ere {\tt c} non r\'eserv\'e\hfill&&{\tt a}\hfill&\cr\trait
&{\tt \char`\\ c}\hfill&&le caract\`ere r\'eserv\'e 
{\tt c}, litt\'eralement\hfill&&{\tt \char`\\ *}\hfill&\cr\trait
&{\tt 's'}\hfill&&la cha\^\i ne {\tt s}, litt\'eralement\hfill&&{\tt '*a*'}\hfill&\cr\trait
&{\tt [s]}\hfill&&tout caract\`ere apparaissant 
dans {\tt s}\hfill&&{\tt [abc]}\hfill&\cr\trait
}}}
}
\pars
\centerline{Expressions de base.}
\parm
Remarque : Dans une expression du type {\tt [s]}, on peut \'ecrire {\tt s} comme une 
juxtaposition de ``domaines'' (des intervalles de la table ASCII)
par exemple :
\pars
{\parindent 1cm
\item{} {\tt [a-z]} est l'expression de toute lettre minuscule,\par
\item{} {\tt [A-Za-z0-9]} est l'expression de tout caract\`ere alphanum\'erique.
\par
}
\parm
\centerline{
\boxit{1pt}{\vbox{
\offinterlineskip
\halign{%
\tv#&&\cc{#}&\tv#\cr\trait
&Expression&&\kern 2.5cm Description \kern 2.5cm&&Exemple&\cr\trait
&{\tt r1r2}\hfill&&{\tt r1} puis {\tt r2} (concat\'enation)\hfill&&{\tt [abc]ef}\hfill&\cr\trait
&{\tt  r1\altern r2}\hfill&&{\tt r1} ou {\tt r2}\hfill&&{\tt a\altern b}\hfill&\cr\trait
&{\tt r\accg m\accd}\hfill&&{\tt m} occurrences de {\tt r}\hfill&&{\tt r\accg 3\accd}\hfill&\cr\trait
&{\tt r*}\hfill&&un nombre quelconque d'occurrences 
de {\tt r}\hfill&&{\tt [abc]*}\hfill&\cr\trait
&{\tt (r)}\hfill&&{\tt r} elle--m\^eme\hfill&&{\tt (a\altern b)}\hfill&\cr\trait
}}}
}
\pars
\centerline{Op\'erations de base.}
\parb
\centerline{
\boxit{1pt}{\vbox{
\offinterlineskip
\halign{%
\tv#&&\cc{#}&\tv#\cr\trait
&Expression&&\kern 2.5cm Description \kern 2.5cm&&Exemple&\cr\trait
&{\tt r\kern -.4em?}\hfill&&z\'ero ou une occurrence 
de {\tt r}\hfill&&{\tt [abc]\kern -.4em?}\hfill&\cr\trait
&{\tt r\accg m,n\accd}\hfill&&de {\tt m} \`a {\tt n} occurrences 
de {\tt r}\hfill&&{\tt r\accg 1,5\accd}\hfill&\cr\trait
&{\tt r+}\hfill&&un nombre non nul d'occurrences 
de {\tt r}\hfill&&{\tt [abc]+}\hfill&\cr\trait
&{\tt .}\hfill&&tout caract\`ere sauf 
{\tt \char`\\ n}\hfill&&{\tt a.\char`\\ *}\hfill&\cr\trait
&{\tt [\^{ }s]}\hfill&&tout caract\`ere n'apparaissant pas 
dans {\tt s}\hfill&&{\tt [\^{ }abc]}\hfill&\cr\trait
}}}
}\pars
\centerline{Autres op\'erations.}
\parb
\centerline{
\boxit{1pt}{\vbox{
\offinterlineskip
\halign{%
\tv#&&\cc{#}&\tv#\cr\trait
&Expression&&\kern 2.5cm Description \kern 2.5cm&&Exemple&\cr\trait
&{\tt \^{ }}\hfill&&d\'ebut de ligne\hfill&&{\tt \^{ }abc}\hfill&\cr\trait
&{\tt <x>r}\hfill&&{\tt r} sous la condition initiale {\tt x}\hfill&&{\tt <x>abc}\hfill&\cr\trait
&{\tt \$}\hfill&&fin de ligne\hfill&&{\tt abc\$}\hfill&\cr\trait
&{\tt r1\char`\/r2 }\hfill&&{\tt r1} si elle est suivie par {\tt r2}\hfill&&{\tt a\char`\/.*b}\hfill&\cr\trait
}}}
}
\pars
\centerline{Op\'erations \`a ``contexte''.}
\parm



\bye