\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Žs dans les pages ci--jointes mais la vŽritable rŽfŽrence 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Žguli�res de votre programme LEX).
\puce Compiler {\tt ESSAI1.PAS} par TPC puis tester le programme {\tt ESSAI1.EXE} :
celui-- ci est censŽ analyser la cha”ne de caract�res que vous entrerez au clavier.
Faites plusieurs essais !
\exo Enrichir le programme prŽcŽdent en lui ajoutant d'autres ``tribus''
linguistiques. Tester le programme {\tt .EXE} correspondant.
\par\vskip 1cm
Par la suite, le texte ˆ analyser se trouvera dans un fichier ainsi que le rŽsultat de 
l'analyse : LEX met ˆ 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Že'' (ˆ analyser)
et celui d'un ``fichier de sortie'' (rŽsultat 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 ˆ l'Žcran). ExŽcuter le programme  {\tt .EXE} 
correspondant sur un fichier
de votre choix (pas trop prŽcieux !)
\exo Ecrire un programme LEX qui recopie un programme en Turbo Pascal en mettant tous ses mots
rŽservŽs en MAJUSCULES ( par exemple le mot BegIN devra �tre recopiŽ BEGIN).
 ExŽcuter le programme  {\tt .EXE} correspondant sur un fichier
de votre choix (en Turbo Pascal mais pas trop prŽcieux !)
\par\vskip 1cm

\remm{PrŽsentation succinte de LEX.}\endrem
\parb
La version de LEX que nous utilisons est adaptŽe au langage Turbo Pascal.
La lecture de la prŽsentation succinte qui suit n'est pas suffisante 
pour comprendre toutes les possiblilitŽs 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 ˆ 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Žfaut est {\tt FICHIER.PAS}. 
Ce dernier peut ˆ son tour �tre compilŽ pour produire un programme exŽcutable {\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ŽparŽes par {\tt \%\%} :
\parb
{\tt
\%\accg\par
\hskip 1cm DŽclarations en Turbo Pascal\par
\%\accd\par
DŽfinitions LEX\pars
\%\%\pars
r�gles\pars
\%\%\pars
ProcŽdures Turbo Pascal auxiliaires\par
}
\parb
Chacune de ces sections peut �tre vide ! Voyons ce qu'il est cependant 
possible d'y mettre.
\remm{Premi�re section.}\endrem
Les dŽclarations en Turbo Pascal seront recopiŽes, sans modification dans le programme
{\tt .PAS} qui est produit par LEX ; ceci se fait au tout dŽbut dudit programme, 
c'est--ˆ--dire au niveau global : 
on peut y dŽclarer des constantes, des variables, des procŽdures et des fonctions, des commentaires \dots
\pars
{\bf DŽfinitions LEX.} Le premier type de dŽfinition se prŽsente sous la forme 
\pars
{\tt nom \kern 1em  expression}
\pars 
o� {\tt nom} est un identificateur (de type Turbo Pascal) qui pourra �tre utilisŽ, 
dans la suite de la premi�re section et dans la seconde 
pour reprŽsenter l'expression rŽguli�re\footnote{*}{cf. ci--dessous les dŽfinitions
prŽcises en LEX} {\tt expression} ; afin de distinguer cet
identificateur de la cha”ne des caract�res qui sert ˆ le dŽsigner, 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�me section : les r�gles.}\endrem
Cette section donne ˆ LEX les instructions qui lui sont nŽcessaires pour dŽfinir 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� {\tt instruction\_simple} est une instruction simple de Turbo Pascal, qui peut �tre vide.
\pars
La fonction {\tt yylex} parcourt le fichier ˆ analyser : 
lorsque qu'une cha”ne de caract�res {\tt s} de ce fichier rŽpond au mod�le donnŽ par
{\tt expression}, la fonction {\tt yylex} a pour premier effet l'exŽcution de l'action
dŽfinie par l'{\tt instruction\_simple}  et affecte la valeur {\tt s} 
ˆ une variable 
\pars
{\tt yytext : string ; }
\pars
dŽclarŽe  par LEX lui--m�me.
\pars
La forme gŽnerale 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� 
\puce le symbole {\tt \altern} indique que l'instruction 
est la m�me que pour l'expression suivante,
\puce {\tt instruction} peut �tre une instruction simple ou composŽe (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Žbut d'une ligne car LEX tenterait de la prendre 
ˆ son propre compte, comme il est dit un peu plus loin).
\pars
Lorsqu'une instruction comporte plusieurs expressions, il peut se prŽsenter des cas d'ambigu•tŽ :
c'est alors la cha”ne la plus longue qui sera choisie : par exemple, si {\tt 'a'} rŽpond ˆ
 {\tt ri} et {\tt 'avoir'} ˆ {\tt rj}, cette derni�re cha”ne sera reconnue et non pas 
dŽcoupŽe en {\tt 'a'} suivie de {\tt 'voir'}.
\parb
Il faut penser ˆ la fonction {\tt yylex} comme Žtant essentiellement constituŽe d'une instruction
{\tt case expression of} dont les cas sont 
\pars
{\parindent 1cm\tt\par
r1, r2, \dots\ , rn : instruction\par
}
\remm{Derni�re 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 Žcrivez ici, en Turbo Pascal, la fin de programme que vous souhaitez !
\pars
{\bf Attention.} Un programme LEX est traitŽ ligne par ligne, avec la convention suivante, valable dans les deux premi�res sections :\pars
\hfil {\sl une ligne commen�ant par un blanc est simplement recopiŽe dans le fichier {\tt .PAS}}\pars
une instruction LEX ne doit donc jamais �tre prŽcŽdŽe 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 Žcrire des expressions ``bien'' rŽguli�res. 
%
\remm{Caract�res rŽservŽs.}\endrem
Ce sont les caract�res significatifs pour LEX lui--m�me, c'est--ˆ--dire :
{\tt \%}, {\tt \echap}, {\tt \altern}, {\tt \accg} et {\tt \accd}, ainsi que
les caract�res servant ˆ coder les expressions rŽguli�res.
\pars
Lorsqu'on dŽsire utiliser un caract�re rŽservŽ {\tt c} pour sa valeur 
littŽrale, 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�res en gŽnŽral.}\endrem
En dehors des caract�res rŽservŽs, tout caract�re ``imprimable'' prend
toujours sa valeur littŽrale. Le tableau qui suit permet de rŽsoudre des cas plus spŽciaux :
\parb
\centerline{
\boxit{1pt}{\vbox{
\offinterlineskip
\halign{%
\tv#&&\cc{#}&\tv#\cr\trait
&Expression&&Description&\cr\trait
&{\tt \echap n}\hfill&&passage ˆ 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�re\hfill&\cr\trait
&{\tt \echap f}\hfill&&passage ˆ la page\hfill&\cr\trait
&{\tt \echap nnn}\hfill&&caract�re de code ASCII {\tt nnn} en octal\hfill&\cr\trait
}}}
}
\remm{Les expressions rŽguli�res.}\endrem
Une expression rŽguli�re caractŽrise un langage rŽgulier ; en fait, une telle expression
est le mod�le auquel doit correspondre une cha”ne de carat�res 
pour appartenir au langage en question. Les tableaux suivants dŽcrivent la fa�on d'Žcrire
les expressions rŽguli�res qui est comprŽhensible par un programme LEX. 
Cependant, les expressions ainsi dŽfinies ne sont enti�rement dŽfinies que si on applique 
les conventions de ``prŽcŽdence'' suivantes :
\pars
{\parindent 1cm
\item{--} Les opŽrateurs {\tt *}, {\tt +}, {\tt ?} et  {\tt\accg\kern .2em\accd} ont le
plus grand degrŽ de prŽcŽdence,\par
\item{--} vient ensuite la {\tt concatŽnation}, qui est notŽe par simple juxtaposion,
\par
\item{--} l'opŽrateur de mise en alternative {\tt \altern} a le plus bas degrŽ de prŽcŽdence.
\par
}
\pars
Les parenth�ses {\tt (\kern .2em )} permettent de contrevenir volontairement aux conventions
prŽcŽdentes (par exemple {\tt a\altern b*} est le mod�le des cha”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”nes que l'on peut Žcrire
avec les caract�res {\tt a} et {\tt b}). 
\pars
Enfin, {\tt<\kern .2em >} et {\tt /} ne peuvent appara”tre qu'une fois 
dans une expression rŽguli�re.
\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�re {\tt c} non rŽservŽ\hfill&&{\tt a}\hfill&\cr\trait
&{\tt \char`\\ c}\hfill&&le caract�re rŽservŽ 
{\tt c}, littŽralement\hfill&&{\tt \char`\\ *}\hfill&\cr\trait
&{\tt 's'}\hfill&&la cha”ne {\tt s}, littŽralement\hfill&&{\tt '*a*'}\hfill&\cr\trait
&{\tt [s]}\hfill&&tout caract�re 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 Žcrire {\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�re alphanumŽrique.
\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Žnation)\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�me\hfill&&{\tt (a\altern b)}\hfill&\cr\trait
}}}
}
\pars
\centerline{OpŽrations 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Žro ou une occurrence 
de {\tt r}\hfill&&{\tt [abc]\kern -.4em?}\hfill&\cr\trait
&{\tt r\accg m,n\accd}\hfill&&de {\tt m} ˆ {\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�re sauf 
{\tt \char`\\ n}\hfill&&{\tt a.\char`\\ *}\hfill&\cr\trait
&{\tt [\^{ }s]}\hfill&&tout caract�re n'apparaissant pas 
dans {\tt s}\hfill&&{\tt [\^{ }abc]}\hfill&\cr\trait
}}}
}\pars
\centerline{Autres opŽrations.}
\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Žbut 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Žrations ˆ ``contexte''.}
\parm



\bye