\input mias

\hsize=16cm \vsize=24.5cm
\voffset=-3mm


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\ptr{\^{ }}
% les dollars de Yacc
\def\doldol{\$\$\ }
\def\dol#1{\$\kern -.05em #1}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\ttt#1{\hbox{\tt #1}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%% D\'efinition d'une instruction
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\font\ttp = cmtt10 at 8pt
\def\ind#1{\modemath{{}_{\hbox{\ttp #1}}}}

\long\def\instr#1#2{\goodbreak\smallskip{
{{\tt #1}}\hfill
{\vtop{\hsize 9cm #2\par}\goodbreak\smallskip}
}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\baspagedroite={{\eightit Projet de compilation
\hfill Institut Galil\'ee\kern 1em M.M. \annee}}
\font\BT = Times at 29pt
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\line{
\vtop{\hsize = 4cm  DEUG MIAS2\par Langages formels.\par}
\vtop{\hsize = 6cm \null \vskip -2.3mm\hfil\BT PROJET\par}
\vtop{\hsize = 4cm \hfill  M.M.  Institut Galil\'ee
\par 
\hfill \annee
\par}
}
\vskip 5cm
Le but de ce projet est de construire, \`a l'aide de Lex et Yacc, un traducteur
du langage {\sl Galileo} en un P--code.
La grammaire de {\sl Galileo} et l'ensemble des P--instructions qui sont utiles \`a sa traduction sont pr\'esent\'es dans ce qui suit.
\parb
\puce Le projet doit \^etre fait par groupes  de 2 ou 3 \'etudiants.
\puce Un programme capable d'\'editer un $P$--code de fa\c con lisible vous sera fourni.
\puce Un programme capable d'ex\'ecuter un $P$--code vous sera fourni.
Afin que nous soyons d'accord, vous devez imp\'erativement respecter certaines d\'eclarations,
qui seront encore signal\'ees dans le sch\'ema du fichier {\tt GAL.Y} ci--joint.\parm
\puce Il vous revient d'\'ecrire les programmes suivants :\pars
{\parindent 1cm
\item{--} Un programme Lex, dans un fichier appel\'e {\tt GALLEX.L}, qui
doit  produire un analyseur lexical  
du langage {\sl Galileo} (une fonction {\tt yylex}).\par
\item{--} Un programme Yacc, dans un fichier appel\'e {\tt GAL.Y}, qui
doit  produire un analyseur syntaxique 
de la grammaire de {\sl Galileo} (une fonction {\tt yyparse}).\par
}
\parm
Le programme {\tt GAL.EXE} que vous obtiendrez devra \^etre capable de traduire un programme
\'ecrit en langage {\sl Galileo} (dans un fichier qui doit avoir le suffixe {\tt .GAL})
en un programme \'ecrit en $P$--code (dans un fichier ayant le m\^eme nom que le pr\'ec\'edent, mais
avec le suffixe {\tt .PCO}).
\vfill
Les pages qui suivent vous proposent des sch\'emas de ces fichiers. Ils ne sont pas contractuels :
soyez donc vigilants \dots
\puce Il vous revient de les compl\'eter et de les mettre au point 
(des points de suspension ({\tt\dots}) signalent les endroits o\`u il reste du travail \`a faire) :
\pars
{\parindent 1cm
\item{--} en d\'efinissant les proc\'edures et les fonctions qui ont \'et\'e signal\'ees dans le sujet,\par
\item{--} en compl\'etant les actions de l'analyseur lexical et de l'analyseur syntaxique.\par
}
\puce Vous testerez votre traducteur sur des programmes de votre choix, pas trop simples (ils devront
en particulier, comporter des tableaux).
\puce Le traitement des erreurs lexicales est assez facile ; pr\'evoyez des messages
d'erreur qui soient utilisables : chacun d'entre eux devra comporter le texte erron\'e
(utilisez {\tt yytext}) et la ligne o\`u il se trouve (utilisez {\tt yylineno}).
\puce Le traitement des erreurs syntaxiques est difficile ! Yacc poss\`ede un {\tt token}
appel\'e {\tt error} qui est pr\'evu \`a cet effet (ne consid\'erez ce probl\`eme qu'\`a l'extr\^eme
fin de votre travail).
\vfill
{\bf Vous devrez pr\'esenter, sous forme de listings, vos programmes {\tt GALLEX.L}, {\tt GAL.Y} et
les fichiers {\tt .GAL} et {\tt .PCO} issus de vos meilleurs tests.
Une <<soutenance>> aura lieu en salle machines.}
\page
\page
\remm
Pr\'esentation de la grammaire.
\endrem
Comme son nom l'indique, {\sl Galileo} est un langage <<maison>> : c'est, en fran\c cais, un
langage imp\'eratif tr\`es simple inspir\'e de Pascal, dont la s\'emantique est par cons\'equent
connue de tous.
\parb
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\vskip .5cm
\propr{\bf La grammaire de Galileo}{
\vskip .3cm
\b Programmes.
\parm
\ \kern .5cm\r{P \donne \b{programme}\k Dv\k Li\k \b{fin}}
\smallskip\goodbreak
\b D\'eclarations de \b variables.
\smallskip\nobreak
\hbox{\ \kern .5cm\vtop{\hsize = 70mm
\r{Dv \donne \varepsilon }
}
\hfill
\vtop{\hsize = 70mm
\r{Dv \donne \b{variables}\k Lid\k \b{fin} }
}
}
\smallskip\goodbreak
\b Listes d'\b{id}entificateurs.
\smallskip\nobreak                        
\hbox{\ \kern .5cm\vbox{\hsize = 70mm
\r{Lid\donne \b{id} : Ty}                                                                    
}
\hfill
\vbox{\hsize = 70mm
\r{Lid\donne Lid  \k \b{id} : Ty}
}
}
\smallskip\goodbreak
\b{Ty}pes.
\smallskip\nobreak
\hbox{\ \kern .5cm\vtop{\hsize = 70mm
\r{Ty \donne \b{entier}}
}
\hfill
\vtop{\hsize = 70mm
\r{Ty \donne \b{tableau}\k [\k \b{nb}\k ]}
}
}
\smallskip\goodbreak
\b Listes d'\b instructions.
\smallskip\nobreak
\hbox{\ \kern .5cm\vtop{\hsize = 70mm
\r{Li \donne I}
}
\hfill
\vtop{\hsize = 70mm
\r{Li \donne Li \k ; \k I}
}
}
\smallskip\goodbreak
\b Instructions.
\smallskip\nobreak
\hbox{\ \kern .5cm\vtop{\hsize = 70mm
\r{I \donne V\k  := \k E}
\r{I \donne \b{si}\k E\k \b{alors} \k Li\k \b{fin}}
\r{I \donne \b{si}\k E\k \b{alors} \k Li\k \b{sinon} \k Li\k \b{fin}}
}
\hfill
\vtop{\hsize = 70mm
\r{I \donne \b{tantque} \k E\k \b{faire} \k Li\k \b{fin}}
\r{I \donne \b{ecrire} \k (\k E\k )}
\r{I \donne \b{retourne}}
}
}
\smallskip\goodbreak
\b Variables.
\smallskip\nobreak
\hbox{\ \kern .5cm\vtop{\hsize = 70mm
\r{V \donne \b{id}}
}
\hfill
\vtop{\hsize = 70mm
\r{V \donne \b{id}\k [ \k ES \k ]}
}
}
\smallskip\goodbreak
\b Expressions.
\smallskip\nobreak
\hbox{\ \kern .5cm\vtop{\hsize = 70mm
\r{E \donne ES}
\r{E \donne ES\k \b{oprel}\k ES}
\r{ES \donne T}
\r{ES \donne ES\k \b{opadd} \k T}
\r{ES \donne ES\k - \k T}
\r{T \donne F}
\r{T \donne T\k \b{opmult} \k F}
}
\hfill
\vtop{\hsize = 70mm
\r{F \donne (\k E\k )}
\r{F \donne -\k F}
\r{F \donne \b{non} \k F}
\r{F \donne \b{id}\k [\k ES\k ]}
\r{F\donne \b{lire}}
\r{F \donne \b{id}}
\r{F \donne \b{nb}} 
}
}
\vskip .5cm
}
\puce Les types autoris\'es sont les entiers et les tableaux d'entiers 
(on n'a donc pas jug\'e utile de mentionner \b{entier} dans la r\`egle 7).
L'introduction d'une expression de type tableau 
se produisant par application de la r\`egle 30 est \`a prohiber :
il n'est pas question de faire des calculs sur un tel objet (les calculs
sur un tableau se font sur ses composantes !)
\puce Pour en finir avec les tableaux : le domaine d'un tableau  de type 
{\tt \b{tableau} [ n ]} est l'ensemble des entiers {\tt 0, \dots , n - 1}.
\puce Les entiers sont interpr\'et\'es comme des bool\'eens lorsque c'est n\'ecessaire : $0$
pour faux et $\not = 0$ pour vrai.\par
\puce Une liste d'instructions ne peut pas \^etre vide  :
 le retour (c'est--\`a--dire la sortie) d'un programme se fait n\'ecessairement par une instruction 
$\b{retourne}$.
\puce Il peut arriver,
pour certaines valeurs des donn\'ees, que l'ex\'ecution n'aboutisse \`a aucune instruction de retour :
ceci est le fruit d'une erreur grave dans le programme mais qui n'est pas
d\'ecelable pendant la traduction. La $P$--instruction {\tt ERREUR} qui doit figurer \`a la fin
de toute traduction permet d'interrompre l'ex\'ecution dans ce cas.
\page
%%%%%%%%%%%%%%%%%%%
\remm
Unit\'es lexicales de Galileo.
\endrem
\puce Chaque mot--clef forme une unit\'e lexicale \`a soi seul. 
\puce Il en est de m\^eme pour les symboles de ponctuation, les parenth\`eses, \dots (le symbole
d'affectation  comportant deux caract\`eres.
\puce \b{nb} : {\tt [-+]\kern -6pt ?[0-9]+}
\puce \b{id} :  {\tt [A-Za-z][A-Za-z0-9]*}
\puce \b{opadd} : les op\'erateurs additifs {\tt +}, {\tt ou}
\puce \b{opmult} : les op\'erateurs multiplicatifs {\tt *},  {\tt et}
\puce \b{oprel} : les op\'erateurs relationnels {\tt =}, {\tt >=}, \dots
\parm
La grammaire et cette description des unit\'es lexicales constituent proprement la d\'efinition 
du langage Galileo. 
\bigskip
\remm
Modifications en vue de la traduction.
\endrem
\puce Il est commode d'introduire une unit\'e lexicale \b{affect} ne comportant que le symbole d'affectation {\tt :=} comme \'el\'ement.
\puce Des nouvelles variables, que nous noterons $M$, $Malors$, $Msinon$, $Mtantque$ et $Mfaire$, sont n\'ecessaires lors de la traduction, pour 
appliquer la <<m\'ethode de reprise>>. 
\parb
Voici les modifications qu'il faut apporter \`a la grammaire pour son utilisation par Yacc :
\propr{ Modifications de la grammaire pour Yacc}{
\smallskip\goodbreak
\b{R\`egles modifi\'ees}.
\smallskip\nobreak
\hbox{\ \kern .5cm\vtop{\hsize = 70mm
\count150 = 8
\r{Li \donne Li\k M \k I}
\r{I\donne V \k \b{affect} \k E}
\r{I \donne \b{si}\k E\k Malors \k Li\k \b{fin}}
}
\hfill
\vtop{\hsize = 70mm
\r{I \donne \b{si}\k E\k Malors \k Li\k Msinon \k Li\k \b{fin}}
\r{I \donne Mtantque \k E\k Mfaire \k Li\k \b{fin}}
}
}
\smallskip\goodbreak
\b{Marqueurs}.
\smallskip\nobreak
\hbox{\ \kern .5cm\vtop{\hsize = 70mm
\count150 = 31
\r{M \donne\kern 1em ; }
\r{Malors \donne \b{alors}}
\r{Msinon \donne \b{sinon}}
}
\hfill
\vtop{\hsize = 70mm
\r{Mtantque \donne \b{tantque}}
\r{Mfaire \donne \b{faire}}
}
}
\vskip .5cm
}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\page
\remm
Pr\'esentation du P--code.
\endrem
Un P--code se pr\'esente sous la forme d'un fichier typ\'e : c'est une liste de P--instructions, dont la plupart agit directement  sur
\b{la pile d'ex\'ecution}. 
\puce Une P--instruction comporte un 
op\'erateur (repr\'esent\'e par un mn\'emonique de quelques lettres, 
qui devra \^etre cod\'e par un entier) et \'eventuellement un 
argument.
\par
\puce On dispose de <<registres>> :
\pars
{\parindent 4cm
\item{} {\tt CP} (Pointeur de Code)\par
\item{} {\tt SP} (Sommet de la Pile)\par 
}

\puce Le registre {\tt CP} est l'adresse, dans le P--code, de l'instruction \`a ex\'ecuter.
\pars
Les instructions d'un $P$--code s'ex\'ecutent s\'equentiellement, \`a partir de la premi\`ere.
\remm
La pile d'ex\'ecution.
\endrem
La pile d'ex\'ecution est d\'esign\'ee comme une partie initiale d'un tableau {\tt PILE} :
l'indice de son sommet est la valeur du registre {\tt SP}.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\puce Le  principe d'ex\'ecution d'une op\'eration sur une pile est bien connu  : 
\pars
{\parindent 1cm
\item{--} les arguments de l'op\'eration sont empil\'es au sommet,
dans l'ordre correspondant \`a la d\'eclaration de cette op\'eration,\par
\item{--} l'ex\'ecution de l'op\'eration a pour effet global de d\'epiler les arguments et d'empiler
le r\'esultat, si l'op\'eration en produit un.\par
}
\puce CONSEIL. Il faut que vous compreniez parfaitement le mode d'action de chaque P--instruction
avant de d\'efinir vos r\`egles s\'emantiques ! 
\parb
\centerline{\bf Les P--instructions.}
\parb
%%%%%%%%%%%%%%%%%%%%%%%%%%% 
\remm
Op\'erations arithm\'etiques.
\endrem
\instr{ADD : $(\ttt E, \ttt E)\donne \ttt E$}{
\item{} \ttt{PILE[SP - 1] := PILE[SP - 1] + PILE[SP]  }
\par
\item{} \ttt{SP := SP - 1  CP := CP + 1  }
}
\instr{SUB  : $(\ttt E, \ttt E)\donne \ttt E$}{
\item{} \ttt{PILE[SP - 1] := PILE[SP - 1] - PILE[SP]  }
\par
\item{} \ttt{SP := SP - 1  CP := CP + 1  }
}
\instr{MUL  : $(\ttt E, \ttt E)\donne \ttt E$}{
\item{} \ttt{PILE[SP - 1] := PILE[SP - 1] * PILE[SP]  }
\par
\item{} \ttt{SP := SP - 1  CP := CP + 1  }
}
\instr{NEG : $\ttt E \donne \ttt E$}{
\item{} \ttt{PILE[SP] := - PILE[SP]  }
\par
\item{} \ttt{CP := CP + 1  }
}
\remm
Op\'erations bool\'eennes.
\endrem
\instr{ET : $(\ttt E, \ttt E)\donne \ttt E$}{
\item{} \ttt{PILE[SP - 1] := PILE[SP - 1] et PILE[SP]  }
\par
\item{} \ttt{SP := SP - 1  CP := CP + 1  }
}
\instr{OU : $(\ttt E, \ttt E)\donne \ttt E$}{
\item{} \ttt{PILE[SP - 1] := PILE[SP - 1] ou PILE[SP]  }
\par
\item{} \ttt{SP := SP - 1  CP := CP + 1  }
}
\instr{LNEG : $\ttt  E\donne \ttt E$}{
\item{} \ttt{PILE[SP] := non PILE[SP]  }
\par
\item{} \ttt{CP := CP + 1  }
}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\remm
Expressions bool\'eennes.
\endrem
\instr{EQU  : $(\ttt E, \ttt E)\donne \ttt E$}{
\item{} \ttt{PILE[SP - 1] := PILE[SP - 1] = PILE[SP]  }
\par
\item{} \ttt{SP := SP - 1  CP := CP + 1  }
}
\instr{GEQ  : $(\ttt E, \ttt E)\donne \ttt E$}{
\item{} \ttt{PILE[SP - 1] := PILE[SP - 1] >= PILE[SP]  }
\par
\item{} \ttt{SP := SP - 1  CP := CP + 1  }
}
\instr{LEQ  : $(\ttt E, \ttt E)\donne \ttt E$}{
\item{} \ttt{PILE[SP - 1] := PILE[SP - 1] <= PILE[SP]  }
\par
\item{} \ttt{SP := SP - 1  CP := CP + 1  }
}
\instr{LES  : $(\ttt E, \ttt E)\donne \ttt E$}{
\item{} \ttt{PILE[SP - 1] := PILE[SP - 1] < PILE[SP]  }
\par
\item{} \ttt{SP := SP - 1  CP := CP + 1  }
}
\instr{GRT  : $(\ttt E, \ttt E)\donne \ttt E$}{
\item{} \ttt{PILE[SP - 1] := PILE[SP - 1] > PILE[SP]  }
\par
\item{} \ttt{SP := SP - 1  CP := CP + 1  }
}
\instr{NEQ  : $(\ttt E, \ttt E)\donne \ttt E$}{
\item{} \ttt{PILE[SP - 1] := PILE[SP - 1] <> PILE[SP]  }
\par
\item{} \ttt{SP := SP - 1  CP := CP + 1  }
}
%%%%%%%%%%%%%%%%%%%%%%%%
\remm
Adressage et transfert de donn\'ees.
\endrem
\instr{LDC  p : $\ttt{vide} \donne \ttt E$}{
\item{} \ttt{SP := SP + 1  PILE[SP] := p  }
\par
\item{} \ttt{CP := CP + 1  }
}
\instr{LDO  p : $\ttt{vide} \donne \ttt E$}{
\item{} \ttt{SP := SP + 1  PILE[SP] := PILE[p]  }
\par
\item{} \ttt{CP := CP + 1  }
}
\instr{STO  : $(\ttt E , \ttt E) \donne \ttt{vide}$}{
\item{} \ttt{PILE[PILE[SP - 1]] := PILE[SP]  }
\par
\item{} \ttt{SP := SP - 2  CP := CP + 1  }
}
\instr{MOV  : $\ttt E \donne \ttt E$}{
\item{} \ttt{PILE[SP] := PILE[PILE[SP]]  }
\par
\item{} \ttt{CP := CP + 1  }
}
\remm
Test de domaine.
\endrem
\instr{CHK p : $\ttt E \donne \ttt E$}{
\item{} \ttt{si ( PILE[SP] < 0 ou  PILE[SP] $\geq$ p ) alors}\par 
\item{} \ttt{erreur(`hors du domaine')}\par
\item{} \ttt{sinon CP := CP + 1 fin  }
}
%%%%%%%%%%%%%%%%%%%%%%%%
\remm
Entr\'ees et sorties.
\endrem
\instr{PECRIRE : $\ttt{E} \donne \ttt{vide}$}{
\item{} {\tt \'ecrire l'entier PILE[SP] \`a l'\'ecran  }\par
\item{} \ttt{SP := SP - 1  CP := CP + 1  }
}
\instr{PLIRE : $\ttt{vide} \donne \ttt E$}{
\item{} \ttt{SP := SP + 1  } \par
\item{} \ttt{PILE[SP] := entier lu \`a l'\'ecran  }
\par
\item{} \ttt{CP := CP + 1  }
}
%%%%%%%%%%%%%%%%%%%%%
\remm
Branchement.
\endrem
\instr{UJP p}{
\item{} \ttt{CP := p  }
}
\instr{FJP p : $\ttt E \donne \ttt{vide}$}{
\item{} \ttt{si PILE[SP] $=$ 0 alors CP := p }
\par
\item{} \ttt{sinon CP := CP + 1 fin  }
\par
\item{} \ttt{SP := SP - 1  }
}
%%%%%%%%%%%%%%%%%%%%%%%%%
\remm
Initialisation.
\endrem
\instr{INIT}{
\item{} \ttt{SP := -1  CP := CP + 1  }
}
%%%%%%%%%%%%%%%%%%%%%%%%%
\remm
R\'eservation de place.
\endrem
\instr{RES p : $\ttt{vide} \donne (\ttt U, \ldots , \ttt U )$}{
\item{} \ttt{SP := SP + p  CP := CP + 1  }
}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\remm
Fin de programme.
\endrem
\instr{RET}{
\item{} {\tt retourne (en TP : halt(0))}
}
\instr{ERREUR}{
\item{} {\tt erreur('sortie impr\'evue') (en TP : halt(1))  }
}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\page
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\remm
Quelques indications.
\endrem
Voici quelques indications utiles pour \'ecrire vos programmes Lex et Yacc :
la s\'eparation des t‰ches attribu\'ees \`a l'analyse lexicale de celles qui
sont attribu\'ees \`a l'analyse syntaxique est importante.
%%%%%%%%
\remm
La table des symboles.
\endrem
\parb
La table des symboles est d\'efinie par les d\'eclarations suivantes :
\parm
{\parindent 3cm
\tt 
\item{\hbox to 2.9cm{type\hfil symbole = }} record\par
\itemitem{nom : } string ;\par
\itemitem{dim : } integer ;\par
\itemitem{depl : } integer \par
\item{} end ;\par
}
\parm
{\parindent 3cm
\tt 
\item{\hbox to 2.9cm{var\hfil table : }} array[1..TMax] of symbole ;\par
\item{longueur : } integer ;\par
}
\parm
\bib{\tt function ranger ( s : string ) : boolean ;}
{\parindent 1cm
\item{} Cette fonction tente de ranger la cha”ne de carct\`eres {\tt s} dans la {\tt table} :
\par
\itemitem{--} si {\tt s} est d\'ej\`a pr\'esente dans la {\tt table} alors
elle renvoie {\tt false} et ne la modifie pas,\par
\itemitem{--} sinon, elle renvoie {\tt true} et range effectivement {\tt s} 
dans la {\tt table} : \par
\itemitem{}\kern 1cm {\tt longueur := longueur + 1 ;}\par
\itemitem{}\kern 1cm {\tt table[longueur].namestr := s ;}\par
}
\parm
\bib{\tt function rechercher ( s : string ; var place : integer ) : boolean ;}
{\parindent 1cm
\item{} Cette fonction recherche la cha”ne de caract\`eres {\tt s} dans la {\tt table} :
\par
\itemitem{--} si {\tt s} en est absente alors elle renvoie {\tt false},\par
\itemitem{--} sinon, elle donne \`a {\tt place} la valeur correspondant \`a la position de {\tt s}
dans la {\tt table} et renvoie la valeur {\tt true}.\par
}
\parm
\bib{\tt var recherche : boolean ; }
{\item{} Cette variable a la valeur {\tt false} pendant toute la partie <<d\'eclaration>> 
du programme : la fonction {\tt ranger}  est utilis\'ee.
Elle devient {\tt true} pendant la partie <<ex\'ecution>> du programme : c'est alors
la fonction {\tt rechercher} qui est utilis\'ee.\par
}
\parb
Pendant la partie <<d\'eclaration>> du programme, on doit r\'eserver la place, au d\'ebut de la 
{\tt PILE} pour chacune des variables (une case pour une variable de type entier, n cases
pour une variable de type tableau [ n ], comme le montre l'exemple suivant)
\midinsert
\parm
\line{\hfil
\vtop{\hsize 4cm
\prog
\p variables
 \a x1 : entier
 \p x2 : tableau[4]
 \p x3 : entier
 \p x4 : entier
 \p \dots
\r fin
\endprog
}
\hfil
\vtop{\hsize 4cm
\def\trait{&\omit\hrulefill&\cr}
\offinterlineskip
\halign{\hfil#\kern .3em&\tv\kern 1em {\tt #} \kern 5em\hfil\tv &\kern 1em{\tt #}&#\cr
\trait
$0 $ : &x1&depl( x1 ) = 0&\cr\trait
$1 $ : &x2[0]&depl( x2 ) = 1&\cr\trait
$2 $ : &x2[1]&&\cr\trait
$3 $ : &x2[2]&&\cr\trait
$4 $ : &x2[3]&&\cr\trait
$5 $ : &x3&depl( x3 ) = 5&\cr\trait
$6 $ : &x4&depl( x4 ) = 6&\cr\trait
etc.\  &\hfil\dots&\cr
}}
\hfil
}%fin de \line
\parb
\endinsert
Le nombre de cases (composante {\tt dim}) et la valeur  (calcul\'ee)
du d\'eplacement (composante {\tt depl}) doivent \^etre enregistr\'es dans la {\tt table} :
cette op\'eration est ex\'ecut\'ee par l'appel de
\pars
{\tt procedure Completertable ( place , dimension : integer ) ; }
\parm


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\remm
Le $P$--code.
\endrem
\pars
{\bf Un $P$--code est une liste de $P$--instructions qui doit imp\'erativement se pr\'esenter 
sous la forme  d'un fichier typ\'e de la fa\c con suivante :}
\pars 
{\parindent 4cm
\tt 
\item{\hbox to 3.9cm{type\hfil pinstruction = }} record\par
\itemitem{operation : } integer ;\par
\itemitem{argument : } longint \par
\item{} end ;\parm
\item{ liste = } \^{ }cliste ;\par
\item{ cliste = } record \par
\itemitem{ adresse : } longint ;\par
\itemitem{ suivant : } liste \par
\item{} end ;\parm
}
\parb
%%%%%%%%%%%%%%%%%

{\parindent 3cm
\tt 
\item{\hbox to 2.9cm{var\hfil pcode :}} file of pinstruction ;\par
}
\parb
{\bf Les $P$--op\'erations doivent imp\'erativement \^etre consid\'er\'ees comme \'etant les constantes :}
\pars
{\tt ADD = 1 ;  SUB = 2 ; MUL = 3 ; \dots ; RET = 25 ; ERREUR = 26 ;}
\parm

Le $P$--code, c'est--\`a--dire le fichier assign\'e \`a variable {\tt pcode}, est obtenu
en utilisant les fonctions et les proc\'edures d\'ecrites ci--dessous :
\pars
\bib{\tt procedure em ( voperation : integer ; vargument : longint ) ;}{
\item{} Ecrit la $P$--instruction {\tt voperation \ argument } \`a la position courante du fichier
assign\'e \`a la variable {\tt pcode}.\par
}
\pars
\bib{\tt procedure em1( voperation : integer ) ; }{
\item{} Ecrit la $P$--instruction{\tt voperation}, sans argument,  \`a la position courante du fichier
assign\'e \`a la variable {\tt pcode}.\par
}
\parm
Au moment o\`u l'on \'ecrit une $P$--instruction de saut, l'adresse de destination 
n'est en g\'en\'eral pas encore connue : ceci explique les variables de <<marquage>> (
{\sl M, Malors, \dots}) qui ont \'et\'e introduites dans la grammaire Yacc de {\sl Galileo}.
Les fonctions et la proc\'edure suivantes permettent de faire les adressages corrects 
par des petits retours en arri\`ere appel\'es <<reprises>>.
\parm
\prog
\p function position : longint ; 
 \a begin
  \a position := filepos ( pcode )
 \r end ;
\endprog
\pars
{\parindent 1cm
\item{} Renvoie la position courante.\par
}
\pars
\bib{\tt function liste0 : liste ; } {
\item{} 
Renvoie une liste vide.}
\pars
\bib{\tt function liste1 ( p : longint ) : liste ; } {
\item{}  
Renvoie une liste dont le seul \'el\'ement est {\tt p}.}
\pars
\bib{\tt function concatener ( l1 , l2 : liste ) : liste ; }  {
\item{} Renvoie la concat\'en\'ee de {\tt l1} et {\tt l2}.}
\pars
\bib{\tt procedure reprendre ( var l : liste ; vadresse : longint ) ;}{
\item{} Ecrit l'adresse {\tt vadresse } comme argument des $P$--instructions de saut dont la
position est dans la liste {\tt l}.\par
}

\parb
\remm
Extensions possibles : pour les rapides et les courageux.
\endrem
\puce Les majuscules et les minuscules.
Tel qu'il vous est propos\'e, le programme Lex produira un analyseur lexical
qui fait la distinction entre les majuscules et les minuscules. Plus pr\'ecis\'ement :\pars
{\parindent 1cm
\item{--} les mot--clefs devront \^etre \'ecrits en minuscules : si vous en
\'ecrivez un avec une seule majuscule, il sera reconnu comme un identificateur ordinaire,\par
\item{--} deux identificateurs qui ne diff\`erent que
par la hauteur de certains de leurs caract\`eres, seront consid\'er\'es comme \'etant
distincts.\par
}
\par
Vous pouvez accepter ces principes (tr\`es contraignants lorsque l'on \'ecrit
un programme), ou les refuser : dans ce dernier
cas, il vous faudra modifier votre analyseur lexical en cons\'equence. Si vous d\'esirez traiter votre table de symboles
 de fa\c con efficace,  vous pouvez vous inspirer du fichier PASLEX.L qui figure dans les environs de TPlex.
\puce Les entr\'ees et les sorties. 
La d\'efinition du langage {\sl Galileo } qui vous a \'et\'e donn\'ee ne permet que la lecture
et l'\'ecriture d'entiers. Or, il est souvent utile d'afficher des messages \`a l'\'ecran
pour <<dialoguer>> avec l'utilisateur. Je vous propose l'extension suivante de notre langage :
\pars
{\parindent 1cm
\item{--} introduire un nouveau mot--clef {\bf ecrirec} et une nouvelle r\`egle syntaxique
$I\donne \b{ecrirec} \k (\k \b{car}\k )$ 
o\`u $\b{car}$ est l'unit\'e lexicale de tous les caract\`eres,
\'ecrits  sous l'une des formes classiques  {\tt 'c', \echap nnn, etc \dots} (attention : on veut
que {\tt c} puisse, par exemple, \^etre un passage \`a la ligne).
\par
\item{} Une instruction {\tt ecrirec( 'c' )} signifiera 
<<\'ecrire {\bf le } caract\`ere {\tt c} \`a l'\'ecran>>.\par
\item{--} introduire une nouvelle $P$--instruction {\tt PECRIREC p} o\`u {\tt p < 256}
est un entier, et qui aura comme effet d'\'ecrire {\bf le } caract\`ere de code ASCII {\tt p} \`a l'\'ecran.
\par
}
Si vous faites cette extension, vous devrez imp\'erativement :\pars
{\parindent 1cm 
\item{--} coder {\tt PECRIREC} comme \'etant la constante {\tt 27},
\item{--} commencer vos $P$-- codes par {\tt INIT 1} (au lieu de {\tt INIT} tout court),
\pars
}
et g\'erer enti\`erement vos affichages \`a l'\'ecran par vous--m\^eme.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\page

\remm 
LE FICHIER LEX : {\tt GALLEX.L}
\endrem
{\tt
\%\accg
\pars
{\parindent 1cm
\item{(*} METTEZ VOS NOMS ET VOS GROUPES DE TD ICI, EN COMMENTAIRE \dots *)
\parb
\item{} var code : integer ; 
\hfill (* pour la proc\'edure standard Val *)
\pars
function ranger ( s : string ) : boolean ; \dots
\pars
function rechercher ( s : string ; var place : integer ) : boolean ; \dots
\parb
\item{(*} Les variables table et longueur sont d\'eclar\'ees dans GAL.Y\par
\item{} On pourrait \'ecrire une seule fonction jouant \`a la fois 
le r™le de ranger\par
 et celui de rechercher \dots \par
\item{} Les autres d\'eclarations sont faites dans GAL.Y :\par
\item{} l'analyseur lexical que Lex va produire \`a partir du pr\'esent programme\par
\item{} c'est-\`a-dire la fonction yylex
\item{} n'est qu'un sous programme de celui que va produire Yacc \dots *)\pars
}
\%\accd
\pars
{\tt \%\%}
\pars
{\def\ligne#1#2{\line{\vbox{\hsize 4cm #1\hfil}\hfill
\vbox{\hsize 10cm #2\hfil}}}
\def\lignes#1{\line{\hfill\vbox{\hsize 10cm #1\hfil}}}
\def\K{\ \kern 5mm}
\tt
\ligne{[ \echap t\echap n]}{;}\par
\ligne{programme}{return( programme ) ;}\par
\ligne{variables}{return( variables ) ;}\par
\ligne{\dots}{\dots etc \dots}\pars
\ligne{ou}{begin yylval.yyinteger := OU ; return( opadd ) end ;}\par
\ligne{\dots}{\dots etc \dots}\pars
\ligne{'='}{begin yylval.yyinteger := EQU ; return( oprel ) end ;}\par
\ligne{\dots}{\dots etc \dots}\pars
\ligne{[-+]\kern -5pt ?[0-9]+}{begin}\par
\lignes{\K Val(yytext, yylval.yyinteger, code) ;}\par
\lignes{\K if code = 0 then return( nb ) }\par
\lignes{\K else begin}\par
\lignes{\K\K (* message d'erreur *) ; halt }\par
\lignes{\K end}\par
\lignes{end ;}\pars
\ligne{[A-Za-z][A-Za-z0-9]*}{(* voir NOTE ci-dessous *)}\pars
\ligne{'\kern -7pt :='}{ return( affect ) ;}\pars
\ligne{'-'$\mid$'('$\mid$')'$\mid$}{}
\ligne{'['$\mid$']'$\mid$'\kern -7pt :'$\mid$'\kern -7pt ;'}{ returnc( yytext[1] ) ;}\pars
\ligne{.}{begin}\par
\lignes{\K (* message d'erreur *) ; halt }\par
\lignes{end ;}\pars
{\parindent 1cm
\item{/*} NOTE : ranger ou rechercher yytext, suivant la circonstance. \par
\item{} En cas de succ\`es : return( id ) et yylval.yyinteger := la place o\`u se trouve\par 
\item{} yytext dans la table, sinon : (* message d'erreur *) et halt ! */\par
}
\pars
{\tt \%\%} 
\pars {\tt (* Ainsi se termine GALLEX.L *)}



\page
%%%%%%%%
\remm
LE FICHIER YACC : {\tt GAL.Y}
\endrem
{\def\bb#1{\vbox{\hsize 3cm #1\hfil}}
\tt 
\%\accg
{\parindent 1cm
\pars
\item{(*} METTEZ VOS NOMS ET VOS GROUPES DE TD, EN COMMENTAIRE \dots *)
\pars
uses crt , dos , yacclib , lexlib ;
\pars
\item{(*}
 IL FAUT IMPERATIVEMENT CODER LES 26 P-OPERATIONS DE CETTE FACON : *)
\par
Const
\par
\line{\bb{ADD = 1 ;}\bb{SUB = 2 ;}\bb{MUL = 3 ;}%
\bb{NEG = 4 ;}\bb{ET = 5 ;}\hfil}\par
\line{\bb{OU = 6 ;}\bb{LNEG = 7 ;}\bb{\dots}\hfil}\par
\line{\bb{RET = 25 ;}\bb{ERREUR = 26 ;\kern -1cm} \hfil (* et \'eventuellement PECRIREC = 27 *)}
\pars
\item{(*}
 D\'eclarations relatives \`a la table des symboles. *)
\par
Const
\par
TMax = \dots \hfill (* la longueur maximale de la table *)
\pars
Type 
\par
{\parindent 4cm
\tt 
\item{symbole = } record\par
\itemitem{nom : } string ;\par
\itemitem{dim : } integer ;\par
\itemitem{depl : } integer \par
\item{} end ;\par
}
\pars
Var
\par
{\parindent 4cm
\tt 
\item{table : } array[1..TMax] of symbole ;\par
\item{longueur : } integer ;\par
\item{recherche : } boolean ;\par
}
\pars
 procedure completertable ( place , dimension : integer ) ; \dots 
\pars
\item{(*}
Les fonctions ranger et rechercher sont d\'eclar\'ees dans GALLEX.L *)
\pars
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\item{(*} 
D\'eclarations relatives au fichier de P-code :\par
IL FAUT IMPERATIVEMENT RESPECTER LA DEFINITION DU TYPE pinstruction,\par
IL FAUT IMPERATIVEMENT RESPECTER LA DEFINITION DE LA VARIABLE pcode. *)
\par
Type
\par
{\parindent 4cm
\tt 
\item{pinstruction = } record\par
\itemitem{operation : } integer ;\par
\itemitem{argument : } longint \par
\item{} end ;\pars
\item{ liste = } \ptr cliste ;\par
\item{ cliste = } record \par
\itemitem{ adresse : } longint ;\par
\itemitem{ suivant : } liste \par
\item{} end ;\par
}
\pars
%%%%%%%%%%%%%%%%%
Var
\par
{\parindent 4cm
\tt 
\item{pcode :} file of pinstruction ;\par
}
\prog 
\p procedure em ( voperation : integer ; vargument : longint ) ;
\p (* \'emettre une P-instruction \`a la fin du fichier assign\'e \`a pcode *) 
\p var v : pinstruction ;
\p  begin  
 \a v.operation := voperation ;
 \p v.argument := vargument ;
 \p write( pcode , v ) 
\r end ;
\endprog
\prog
\p procedure em1 ( voperation : integer ) :
\p begin   em( voperation , 0 )  end ;
\endprog
\prog
\p function position : longint ; 
\p begin  position := filepos ( pcode )  end ;
\endprog
function liste0 : liste ; \dots
\par
 function liste1 ( p : longint ) : liste ;  \dots
\par
function concatener ( l1 , l2 : liste ) : liste ; \dots
\par
 procedure reprendre ( var l : liste ; vadresse : longint ) ; \dots
\par

}
\%\accd
}
\pars
{\def\bb#1{\vbox{\hsize 3cm #1\hfil}}
\tt
\line{\bb{\%token}\bb{<integer>}\bb{programme}\bb{retourne}\bb{variables}\hfill}\par
\line{\bb{ }\bb{ }\bb{id}\bb{entier}\bb{tableau}\hfill}\par
\line{\bb{ }\bb{ }\bb{nb}\bb{si}\bb{alors}\hfill}\par
\line{\bb{ }\bb{ }\bb{sinon}\bb{tantque}\bb{faire}\hfill}\par
\line{\bb{ }\bb{ }\bb{ecrire}\bb{lire}\bb{fin}\hfill}\par
\line{\bb{ }\bb{ }\bb{oprel}\bb{opadd}\bb{opmult}\hfill}\par
\line{\bb{ }\bb{ }\bb{non}\bb{affect}\hfill}\parb
\line{\bb{\%type}\bb{<integer>}\bb{Lid}\bb{Ty}\bb{V}\hfill}\par
\line{\bb{ }\bb{ }\bb{E}\bb{ES}\hfill}\par
\line{\bb{ }\bb{ }\bb{T}\bb{F}\hfill}\parb
\line{\bb{\%type}\bb{<longint>}\bb{M}\bb{Malors}\bb{Msinon}\hfill}\par
\line{\bb{ }\bb{ }\bb{Mtantque}\bb{Mfaire}\hfill}\parb
\line{\bb{\%type}\bb{<liste>}\bb{I}\bb{Li}\hfill}\parb
}
\parb
{\tt \%\%}
\pars
{\parindent 2cm
\def\K {\ \kern 5mm}
\def\R#1{\item{\hbox to 1.99cm{#1\hfil :}}\kern 5mm}
\def\S{\item{$\mid$}\kern 5mm}
\def\F{\item{ ;}}
\def\P#1{\hfill\vbox{\hsize 8.5cm #1\hfil}\par}
\def\PQ#1{\hfill\vbox{\hsize 9.5cm #1\hfil}\par}
\tt
\R{P}programme Dv Li fin
\P{\accg begin }
\PQ{reprendre( \dol 3, position ) ;}
\PQ{em1(ERREUR)}
\P{end ; \accd}
%
\F\par
\R{Dv}/* vide*/ \P{\accg recherche := true ; \accd}
\S variables Lid fin \P{\accg \dots \accd}
\F 
\par
\R{Lid} id '\kern -6pt :' Ty
\P{\accg begin}
\PQ{completertable( \dol 1 , \dol 3 ) ;}
\PQ{em( RES , \dol 3 ) }
\P{end ; \accd}
%
\S Lid id '\kern -6pt :' Ty\P{\accg \dots \accd}
%
\F\par
\R{Ty} entier\P{\accg  \doldol := 1  ; \accd}
\S tableau '[' nb ']' \P{\accg begin}
\PQ{if \dol 3 < 1 then begin}
\PQ{\K (* message d'erreur *) ; halt}
\PQ{end ;}
\PQ{\doldol := \dol 3 }
\P{end ; \accd}
\F\par
\R{Li} I\P{\accg  ; \accd}
\S Li M I
\P{\accg begin}
\PQ{reprendre( \dol 1 , \dol 2 ) ; \doldol := \dol 3}
\P{end ; \accd}
%
\F\par
\R{I} V affect E
\P{\accg begin}
\PQ{em1( STO ) ; \doldol := liste0}
\P{end ; \accd }
%
\S si E Malors Li fin
\P{\accg }
\PQ{\doldol := concatener( liste1( \dol 3 ) , \dol 4 )}
\P{; \accd }
%
\S si E Malors Li Msinon Li fin\kern -2cm
\P{\accg \dots  \accd }
%
\S Mtantque E Mfaire Li fin\kern -2cm
\P{\accg \dots  \accd }
%
\S ecrire '(' E ')'
\P{\accg begin}
\PQ{em1( PECRIRE ) ; \doldol := liste0}
\P{end ; \accd }
%
\S retourne 
\P{\accg \dots \accd }
%
\F\par
\R{V} id
\PQ{\accg  if table[\dol 1].dim = 1 then}
\PQ{\K em( LDC , table[\dol 1].depl ) ;}
\PQ{else begin}
\PQ{\K (* message d'erreur *) ;  halt }
\P{end ; \accd}
%
\S id '[' ES ']' 
\P{\accg begin}
\PQ{em( CHK , table[\dol 1].dim ) ;}
\PQ{em( LDC , table[\dol 1].depl ) ;}
\PQ{em1( ADD ) }
\P{end ; \accd }
%
\F\par
%
\R{E} ES\P{\accg \dots \accd }
\S ES oprel ES\P{\accg  em1( \dol 2 )  ; \accd }
\F\par
%
\R{ES} T\P{\accg \dots \accd }
\S ES opadd T\P{\accg  em1( \dol 2 ) ; \accd }
\S ES '-' T\P{\accg \dots \accd }
\F\par
\R{T} F\P{\accg \dots \accd }
\S T opmult F\P{\accg \dots \accd }
\F\par
\R{F} '(' E ')'\P{\accg \dots \accd }
\S '-' F\P{\accg  em1( NEG )  ; \accd }
\S non F\P{\accg  em1( LNEG )  ; \accd }
\S id '[' ES ']'\P{\accg begin}
\PQ{em( CHK , table[\dol 1].dim ) ;}
\PQ{em( LDC , table[\dol 1].depl ) ; }
\PQ{em1( ADD ) ; em1( MOV )}
\P{end ; \accd }
%
\S lire\P{\accg  em1( PLIRE )  ; \accd}
\S id \PQ{\accg if table[\dol 1].dim = 1 then}
\PQ{\K em( LDO , table[\dol 1].depl )}
\PQ{else begin}
\PQ{\K (* message d'erreur *) ;  halt}
\P{end ; \accd}
%
\S nb\P{\accg  em( LDC , \dol 1)  ; \accd}
\F\par
\R{M} '\kern -7pt ;'\P{\accg  \doldol := position  ; \accd }
\F\par
\R{Malors}  alors\P{\accg begin}
\PQ{\doldol := position ; em1( FJP )  }
\P{end ; \accd}
%
\F\par
\R{Msinon}  sinon\P{\accg \dots \accd}
%
\F\par
\R{Mtantque}  tantque\P{\accg \dots \accd }
\F\par
\R{Mfaire}  faire\P{\accg \dots \accd}
%
\F\pars
}
\pars
{\tt \%\%}
\page
%%%%%%%%%%%%%%%%%%%%
{\tt \accg\$I GALLEX \accd \hfill (* inclut l'analyseur lexical *)}\par
{\parindent 1cm
\item{(*}
D\'eclarations utiles pour r\'ecolter le nom du fichier \`a traduire\par
et pour construire le nom du fichier qui contiendra la traduction. *)
\pars
Var\hfill (* types d\'efinis dans l'unit\'e Dos *)
\par
\parindent 4cm
\tt 
\item{fichier :}  pathstr ; \par
\item{repertoire :}  dirstr ; \par
\item{nom :}  namestr ; \par
\item{extension :}  extstr ; \par
}
\pars
\prog
\p begin
 \a clrscr ;
 \p if paramcount = 0 then begin
   \a writeln( 'Commande : GAL nomDufichier[.GAL]' ) ;  
   \p halt( 1 )
 \r end
  \p else begin 
  \a fichier := fexpand( paramstr( 1 ) ) ;
  \p fsplit( fichier , repertoire , nom , extension ) ;
  \p if nom + extension = '' then begin
   \a writeln( 'Commande : GAL nomDufichier[.GAL]' ) ;  
   \p halt( 1 )
  \r end ;
  \p if extension = '' then extension := '.GAL' ;
  \p  \accg\$I-\accd
  \p assign( yyinput , repertoire + nom + extension ) ;
  \p reset( yyinput ) ;
  \p \accg\$I+\accd
  \p if IOresult <> 0 then begin 
   \a write( 'Impossible d''ouvrir le fichier : ' ) ;
   \p writeln( repertoire + nom + extension ) ; 
   \p halt( 1 )
  \r end 
 \r end ;
 \p \accg\$I-\accd
 \p assign( pcode , repertoire + nom + '.PCO' ) ;
 \p rewrite( pcode ) ;
 \p \accg\$I+\accd
 \p if IOresult <> 0 then begin 
  \a writeln( 'Impossible d''ouvrir un fichier pour la traduction.' ) ;
  \p halt( 1 )
 \r end ;  \hfill (* si l'on est arriv\'e ici : les fichiers sont bien ouverts \dots *)
 \p longueur := 0 ;
 \p recherche := false ;
 \p em1( INIT ) ; \hfill (* d\'ebut oblig\'e d'un P-code *)
 \p if yyparse = 0 then writeln( 'Traduction termin\'ee.' ) ;
\r end. \pars
 (* ainsi se termine GAL.Y \dots *)
\par
\endprog 
}
}
\bye