%%
%% $Id$
%%
%% Copyright 1989-2016 MINES ParisTech
%%
%% This file is part of PIPS.
%%
%% PIPS is free software: you can redistribute it and/or modify it
%% under the terms of the GNU General Public License as published by
%% the Free Software Foundation, either version 3 of the License, or
%% any later version.
%%
%% PIPS is distributed in the hope that it will be useful, but WITHOUT ANY
%% WARRANTY; without even the implied warranty of MERCHANTABILITY or
%% FITNESS FOR A PARTICULAR PURPOSE.
%%
%% See the GNU General Public License for more details.
%%
%% You should have received a copy of the GNU General Public License
%% along with PIPS.  If not, see <http://www.gnu.org/licenses/>.
%%
\documentclass[12pt]{article}

\usepackage[latin1]{inputenc}
\input{/usr/share/local/lib/tex/macroslocales/Dimensions.tex}
\newcommand{\titre}{RAPPORT FINAL \\
                    ANALYSE LEXICALE \\
		    ANALYSE SYNTAXIQUE INTRA-PROCÉDURALE}
\newcommand{\auteur}{François IRIGOIN \\
        Pierre JOUVELOT \\
        Rémi TRIOLET}
\newcommand{\docdate}{Mai 1989}
\newcommand{\numero}{E110}

\newcommand{\SEC}[1]{\section{#1}}
\newcommand{\SSE}[1]{\subsection{#1}}
\newcommand{\SSS}[1]{\subsubsection{#1}}
\newcommand{\PAR}[1]{\paragraph{#1}}
\newcommand{\SPA}[1]{\subparagraph{#1}}
\newcommand{\BQU}{\begin{quote}}
\newcommand{\EQU}{\end{quote}}
\newcommand{\BIT}{\begin{itemize}}
\newcommand{\EIT}{\end{itemize}}
\newcommand{\BDE}{\begin{description}}
\newcommand{\EDE}{\end{description}}
\newcommand{\BEQ}{\begin{equation}}
\newcommand{\EEQ}{\end{equation}}
\newcommand{\BAR}{\begin{array}}
\newcommand{\EAR}{\end{array}}
\newcommand{\BDO}{\begin{document}}
\newcommand{\EDO}{\end{document}}
\newcommand{\BCE}{\begin{center}}
\newcommand{\ECE}{\end{center}}
\newcommand{\BTG}{\begin{tabbing}}
\newcommand{\ETG}{\end{tabbing}}
\newcommand{\BTR}{\begin{tabular}}
\newcommand{\ETR}{\end{tabular}}
\newcommand{\BAB}{\begin{abstract}}
\newcommand{\EAB}{\end{abstract}}
\newcommand{\BEN}{\begin{enumerate}}
\newcommand{\EEN}{\end{enumerate}}
\newcommand{\BFI}{\begin{figure}}
\newcommand{\EFI}{\end{figure}}
\newcommand{\VSP}{\vspace*{\baselineskip}}

\setlength{\parindent}{0cm}

\begin{document}
\input{/usr/share/local/lib/tex/macroslocales/PageTitre.tex}
\sloppy

\PAR{Introduction} 
\PAR{}
L'analyse lexicale et l'analyse syntaxique intra-procédurale sont
réalisées par un programme nommé {\em parser}. Ce rapport a pour
objet de décrire les structures de données et les algorithmes mis en
oeuvre pour la réalisation de parser.

\PAR{}
Ce rapport reprend des parties de précédents rapports intermédiaires.
Nous décrivons dans la section 1 l'organisation générale de parser,
ce qu'il prend comme données et ce qu'il produit comme résultats. La
section 2 décrit en détail la structure de la représentation
intermédiaire, et montre comment elle permet de représenter les
différents objets manipulés par un programme Fortran. La section 3
décrit les programmes qui composent parser, et indique quels outils UNIX
qui ont été utilisés. Enfin nous donnons en annexe l'intégralité
des programmes sources de parser.


\SEC{Organisation générale de parser}
\PAR{}
L'objet du programme parser est de construire une représentation
intermédiaire pour chaque module Fortran (subroutine, function ou main
program) qui lui est soumis.

\PAR{}
Parser prend en entrée un fichier contenant des modules
Fortran. Le nom de ce fichier doit avoir une extension ``\verb/.f/''.
Parser effectue le même traitement sur chaque module, à savoir:
\begin{itemize}
\item construction en mémoire d'une représentation intermédiaire;
\item stockage sur fichiers disque de cette représentation intermédiaire.
\end{itemize}
Le résultat de parser est identique si on lui soumet un unique fichier
contenant plusieurs modules, ou plusieurs fichiers contenant chacun un
unique module. Nous supposons donc dans la suite que parser est
exécuté sur un fichier de nom \verb/m.f/ contenant un module de nom
\verb/M/. 

\PAR{}
Sous ces hypothèses, le résultat de parser se compose de deux
fichiers: 
\begin{itemize}
\item un fichier de nom \verb/TOP-LEVEL:M.entities/ qui contient la
définition de toutes les entités apparaissant dans M,
\item un fichier de nom \verb/TOP-LEVEL:M.code/ qui contient le code de M.
\end{itemize}

\PAR{}
Les entités définies dans le fichier \verb/TOP-LEVEL:M.entities/ sont
les entités locales de M, et l'entité M elle-même. Les entités
globales telles que les commons ou les autres modules appelés par M
sont considérées comme locales à M\footnote{La phase ultérieure d'édition
de liens aura pour but de repérer ces entités, de les transformer en
entités globales, et de faire en sorte qu'une entité globale ne soit
définie qu'une seule fois et que tous les modules fassent référence
aux mêmes définitions.}.

\PAR{}
Les entités locales à M ont un nom préfixé par \verb/M:/, où
\verb/M/ est le nom du package de M et \verb/:/ un séparateur. Les
entités qui sont réellement locales sont complètement définies, mais
ceci n'est pas vrai pour les entités globales declarées dans M. Ainsi,
la valeur initiale d'une entité de type \verb/function/ sera inconnue
alors qu'elle devrait avoir pour valeur le code de la fonction. La
valeur est inconnue car le code des modules appelés n'est pas
disponible tant que ceux-ci n'ont pas été soumis à parser.

\PAR{}
L'entité définissant le module M lui-même a pour nom
\verb/TOP-LEVEL:M/, ce qui signifie qu'elle appartient au package de
plus haut niveau: \verb/TOP-LEVEL/. Cette entité est parfaitement
définie puisque son code est disponible dans le fichier \verb/m.f/ qui
est soumis à parser. Ce code n'est cependant pas stocké dans le
fichier \verb/TOP-LEVEL:M.entities/ mais dans le fichier
\verb/TOP-LEVEL:M.code/. Les raisons qui nous ont conduit à séparer
code et entités seront exposées ultérieurement.

\PAR{}
La représentation intermédiaire de parser est une structure de
données Newgen. Cela signifie que sa définition est faite à l'aide du
langage de définition de domaines (DDL) présenté dans le document
E-105. Cela signifie aussi que les programmes qui composent parser
utilisent les macros et fonctions automatiquement générés par Newgen:
fonctions de création d'objets, fonctions d'accès aux champs des objets,
fonctions de lecture et écriture disque, fonctions de libération
mémoire, etc.

\SEC{Description de la représentation intermédiaire}

\SSE{Principe généraux}

\PAR{}
Cette représentation intermédiaire de programmes procéduraux a été
définie pour traiter des programmes Fortran mais nous avons pris soin
de nous appuyer sur les idées générales de la sémantique
dénotationnelle pour obtenir une représentation à la fois concise,
solide, extensible et aussi indépendante de Fortran que possible.

\PAR{}
Cette représentation intermédiaire ne vise pas a rendre compte de tous les
problèmes liés aux traitements interprocéduraux qui seront effectués
dans le cadre du projet PIPS. Elle a pour but de représenter d'une
manière sémantiquement équivalente un module: programme principal,
subroutine ou function.

\PAR{}
Le présent document représente le résultat d'une première phase.  La
représentation intermédiaire sera ensuite augmentée pour prendre en
compte les besoins de l'analyse interprocédurale ou du calcul des
dépendances.

\SSE{Spécification NewGen de la représentation intermédiaire}

\PAR{}
Le fichier de spécifications NewGen de la ri est donnée ci après.  La
liste définitions de domaines n'est pas donnée dans un ordre logique,
mais plus simplement par ordre alphabétique.

\begin{verbatim}
array       = basic x dimensions:dimension* ;
basic       = int:int + float:int + logical:int + overloaded:unit + 
              complex:int + string:value ;
call        = function:entity x arguments:expression* ;
code        = declarations:entity* x statement ;
constant    = int + litteral:unit ;
dimension   = lower:expression x upper:expression ;
entity      = name:string x type x storage x initial:value ;
expression  = syntax ;
formal      = function:entity x offset:int ;
functional  = parameters:parameter* x result:type ;
instruction = block:statement* + test + loop + goto:statement + call ;
loop        = index:entity x range x body:statement x label:entity ;
mode        = value:unit + reference:unit ;
parameter   = type x mode ;
ram         = function:entity x section:entity x offset:int ;
range       = lower:expression x upper:expression x increment:expression ;
reference   = variable:entity x indices:expression* ;
statement   = label:entity x instruction ;
storage     = return:entity + ram + formal + rom:unit ;
symbolic    = expression x constant ;
syntax      = reference + range + call ;
test        = condition:expression x true:statement x false:statement ;
type        = statement:unit + area:int + array + functional + 
              unknown:unit + void:unit ;
value       = code + symbolic + constant + intrinsic:unit + unknown:unit ;
\end{verbatim}

\SSE{Analyse de la représentation intermédiaire}

\PAR{}
Dans cette section, nous allons montrer comment cette représentation
intermédiaire permet de représenter les différents objets manipulés par un
programme Fortran.

\SSS{Domaines}

\PAR{}
Nous allons tout d'abord examiner chaque domaine pour expliquer
brièvement à quoi il sert.

\PAR{Entity = name:string x type x storage x initial:value}
\PAR{}
Tout objet ayant un nom dans un programme Fortran est représenté par
une \verb/entity/. Un tel objet peut être un module, une variable, un
common, un opérateur, une constante, un label, etc. Pour chaque objet,
le sous-domaine \verb/name/ de l'entité donne le nom de l'objet tel
qu'il apparait dans le texte source du programme préfixé par le nom du
package dans lequel l'entité est déclarée, le sous-domaine
\verb/type/ donne le type de l'entité, le sous-domaine \verb/storage/
le genre d'allocation mémoire utilisé pour l'entité, et finalement,
le sous-domaine \verb/initial/ donne la valeur initiale, si elle est
connue, de l'entité. Le terme valeur initiale a ici un sens assez
large, puisqu'il s'agit par exemple du code pour les entités
représentant des modules.

\PAR{Type = statement:unit + area:int + array + functional +
unknown:unit + void:unit} 
\PAR{}
Le domaine \verb/type/ représente le type d'une entité.  Le
sous-domaine \verb/statement/ est utilisé pour les labels
d'instruction.  Le sous-domaine \verb/area/ est utilisé pour les
commons.  Le sous-domaine \verb/array/ est utilisé pour toutes les
variables, y compris les paramètres formels et le résultat d'une
fonction.  Le sous-domaine \verb/functional/ est utilisé pour les
fonctions, pour les subroutines et pour le programme principal.  Le
sous-domaine \verb/void/ est utilisé pour le résultat d'une subroutine
ou d'un programme principal.

\PAR{Array = basic x dimensions:dimension*}
\PAR{}
Le domaine \verb/array/ représente le type d'une variable.  Le
sous-domaine \verb/basic/ donne le type Fortran de la variable.  Le
sous-domaine \verb/dimensions/ donne la liste des dimensions de la variable.
Un scalaire est un tableau de zéro dimension.

\PAR{}
Chaque dimension est une expression, qui n'est pas nécessairement
constante dans le cas des tableaux formels. La constante prédéfinie de
nom '*D*' est utilisée pour les tableaux de taille non définie
(\verb/DIMENSION T(*)/).

\PAR{Basic = int:int + float:int + logical:int + overloaded:unit + 
complex:int + string:value}
\PAR{}
Le domaine \verb/basic/ permet de représenter un type Fortran tel que
INTEGER ou REAL. La valeur de ce domaine donne la longueur en octets de
la zone mémoire occuppée par une variable de ce type.

\PAR{Dimension = lower:expression x upper:expression}
\PAR{}
Le domaine \verb/dimension/ permet de représenter une dimension d'un
tableau, c'est à dire un couple borne inférieure -- sous-domaine
\verb/lower/ -- borne supérieure -- sous-domaine \verb/upper/.

\PAR{Functional = parameters:parameter* x result:type}
\PAR{}
Le domaine \verb/functional/ représente le type d'un module, c'est
à dire une fonction, une subroutine ou un programme principal. Le
sous-domaine \verb/parameters/ donne le type et le mode de passage de chaque
paramètre, et le sous-domaine \verb/result/ donne le type du résultat. Ce
dernier type vaut \verb/void/ pour les subroutines et les programmes
principaux. 

\PAR{Parameter = type x mode}
\PAR{}
Le domaine \verb/parameter/ représente le type et le mode de passage d'un
paramètre formel de module. 

\PAR{Mode = value:unit + reference:unit}
\PAR{}
Le domaine \verb/mode/ représente le mode de passage d'un paramètre
formel de module. Le domaine contient un objet du domaine \verb/value/
pour le mode de passage par valeur et \verb/reference/ pour le passage
par adresse.

\PAR{Storage = return:entity + ram + formal + rom:unit}
\PAR{}
Le domaine \verb/storage/ permet de préciser dans quelle zone de la mémoire
est stockée une entité. Il y a plusieurs zones, qui ne correspondent
pas nécessairement à la réalité, c'est à dire aux zones de mémoire
qui seraient affectées par un compilateur.

\PAR{}
Le sous-domaine \verb/return/ permet de représenter les variables ayant
pour nom le nom d'une fonction et auxquelles on affecte la valeur que la
fonction doit retourner. L'entité pointée par \verb/return/ est la
fonction concernée.

\PAR{}
Le sous-domaine \verb/ram/ est reservé aux variables ayant une adresse
en mémoire. Il permet de préciser dans quelle fonction et
éventuellement dans quelle common ces variables ont été déclarées.

\PAR{}
Le sous-domaine \verb/formal/ est réservé aux paramètres formels des
modules.

\PAR{}
Le sous-domaine \verb/rom/ est utilisé pour toutes les entités dont la
valeur n'est pas modifiable, telles que les fonctions, les labels, les
opérateurs, etc.

\PAR{Ram = function:entity x section:entity x offset:int}
\PAR{}
Le domaine \verb/ram/ permet de préciser la déclaration d'une
variable. Le sous-domaine \verb/function/ indique dans quel module une
entité est déclarée. Le sous-domaine \verb/section/ indique dans
quelle aire une entité est stockée; il y a une aire par common
déclaré et deux aires spéciales nommées \verb/STATIC/ et
\verb/DYNAMIC/ pour les entités locales. Enfin, le sous-domaine
\verb/offset/ donne l'adresse dans l'aire de la variable.

\PAR{Formal = function:entity x offset:int}
\PAR{}
Le domaine \verb/formal/ indique le module dans lequel un paramètre formel
est déclaré grâce le sous-domaine \verb/function/, et le rang de ce
paramètre dans la liste des paramètres grâce au sous-domaine \verb/offset/.

\PAR{Value = code + instruction + symbolic + constant + intrinsic:unit + 
unknown:unit}
\PAR{}
Le domaine \verb/value/ permet de représenter les valeurs initiales des
entités. Le sous-domaine \verb/code/ est utilisé pour les entités
modules. Le sous-domaine \verb/symbolic/ est utilisé
pour les entités constantes symboliques. Le sous-domaine
\verb/constant/ est utilisé pour les entités constantes. Le
sous-domaine \verb/intrinsic/ est utilisé pour toutes les entités qui
ne dépendent que du langage, telles que les intrinsics Fortran, les
opérateurs, les instructions, etc. Enfin le sous-domaine
\verb/unknown/ est utilisé pour les valeurs initiales inconnues.

\PAR{Symbolic = expression x constant}
\PAR{}
Le domaine \verb/symbolic/ est utilisé pour représenter la valeur
initiale d'une entité constante symbolique, c'est à dire les PARAMETER
de Fortran ou les CONST de Pascal. Le sous-domaine \verb/expression/ permet
de stocker l'expression qui a permis d'évaluer la valeur initiale
contenue dans le sous-domaine \verb/constant/. Le sous-domaine \verb/expression/
n'est utile qui si on cherche à reproduire un texte source fidèle.

\PAR{Constant = int + litteral:unit}
\PAR{}
Le domaine \verb/constant/ est utilisé pour représenter la valeur
initiale des entités constantes. Seules les entités de type entier
nous intéressent, ce qui explique qu'une constante puisse être soit un
\verb/int/ soit un \verb/litteral/ dont on ne garde pas la valeur (type unit).

\PAR{Code = declarations:entity* x statement}
\PAR{}
Le domaine \verb/code/ est utilisé pour stocker le corps des modules. Le
sous-domaine \verb/declarations/ contient une liste d'entités qui sont les
variables et commons déclarés dans la fonction. Le sous-domaine
\verb/statement/ contient la séquence d'instructions du module.

\PAR{Statement = label:entity x instruction}
\PAR{}
Le domaine \verb/statement/ permet de repérer les instructions d'un module.
Le sous-domaine \verb/label/ contient une entité qui définit le label. Le
sous-domaine \verb/instruction/ contient le corps de l'instruction.

\PAR{Instruction = block:statement* + test + loop + goto:statement + call}
\PAR{}
Le domaine \verb/instruction/ permet de représenter les instructions
d'un module. Une instruction peut être un sous-domaine \verb/block/,
c'est à dire une liste de \verb/statement/, un sous-domaine \verb/test/
pour les instructions de test, un sous-domaine \verb/loop/ pour les
boucles, un sous-domaine \verb/goto/ pour les goto qui contient le
\verb/statement/ vers lequel le goto se branche, ou un sous-domaine
\verb/call/ pour toutes les autres instructions: affectation, appel de
subroutine, entrées-sorties, return, stop, etc. Toutes ces instructions
sont représentées par des appels à des fonctions prédéfinies dont
nous étudierons la nature plus loin.

\PAR{Test = condition:expression x true:statement x false:statement}
\PAR{}
Le domaine \verb/test/ permet de représenter toutes les instructions à base
de contrôle. Le sous-domaine \verb/condition/ contient l'expression à
tester, et les deux sous-domaines \verb/true/ et \verb/false/ contiennent les
instructions à exécuter selon la valeur du test. 

Il faut noter que chaque instruction de contrôle de Fortran,
à l'exception de l'instruction \verb/DO/, est
transformée en une combinaison sémantiquement équivalente de \verb/test/s
et de \verb/goto/s.

\PAR{Loop = index:entity x range x body:statement x label:entity}
\PAR{}
Le domaine \verb/loop/ permet de représenter les boucles du type DO Fortran
ou FOR Pascal. Le sous-domaine \verb/index/ contient l'entité indice de
boucle, le sous-domaine \verb/range/ contient les bornes de la boucle, le
sous-domaine \verb/body/ contient le corps de la boucle, c'est à dire un
\verb/statement/, le sous-domaine \verb/label/ contient le label de fin de boucle,
c'est à dire une entité.

\PAR{Range = lower:expression x upper:expression x increment:expression}
\PAR{}
Le domaine \verb/range/ permet de représenter les bornes des boucles DO
Fortran. Il y a trois sous-domaines \verb/lower/, \verb/upper/ et \verb/increment/ de
type \verb/expression/ qui sont respectivement la borne inférieure, la borne
supérieure et l'incrément.

\PAR{Call = function:entity x arguments:expression*}
\PAR{}
Le domaine \verb/call/ permet de représenter les appels de fonctions.
Les fonctions jouent un rôle important dans notre représentation
intermédiaire puisque les opérateurs et les instructions Fortran
(READ, WRITE, RETURN, ...) sont représentées par des fonctions
prédéfinies.

Le sous-domaine \verb/function/ est une entité qui définit la fonction
appelée. Le sous-domaine \verb/arguments/ est une liste de sous-domaines
\verb/expression/ qui représente les arguments d'appel de la fonction.

\PAR{Expression = syntax}
\PAR{}
Le domaine \verb/expression/ permet de stocker les expressions.
Pour l'instant, ce domaine ne se compose que d'un unique sous-domaine
\verb/syntax/, mais nous pensons ajouter ultérieurement d'autres
sous-domaines, notamment pour conserver avec chaque expression linéaire
un forme compilée, peut-être sous forme d'un vecteur.

Le sous-domaine \verb/syntax/ contient l'expression avec la même
structure que celle du code source.

\PAR{Syntax = reference + range + call}
\PAR{}
Le domaine \verb/syntax/ permet de représenter les expressions telles
qu'elles apparaissent dans le texte source du programme. Un
\verb/syntax/ est soit une \verb/reference/ à un élément de tableau
(on rappelle que les scalaires sont des tableaux à 0 dimension) , soit
un \verb/call/ à une fonction (les opérateurs sont représentés par
des fonctions pré-définies), soit un \verb/range/, dans le cas des
expressions bornes de boucles.


\PAR{Référence = variable:entity x indices:expression*}
\PAR{}
Le domaine \verb/reference/ est utilisé pour représenter une référence à
un élément de tableau. Le sous-domaine \verb/variable/ contient une entité
définissant la variable référencée. Le sous-domaine \verb/indices/
contient une liste expressions qui sont les indices de la référence.

\SSS{Objets du langage Fortran}

\PAR{}
Nous montrons à présent comment les différents objets manipulés dans
un programme Fortran sont traduits dans notre représentation intermédiaire.

\PAR{Module}
\PAR{}
Un module est un programme principal, une fonction ou une subroutine. 

\PAR{}
Un module est représenté par une \verb/entity/ dont le \verb/name/ est
le nom du module préfixé par le nom du package de plus haut niveau
\verb/TOP-LEVEL/, le \verb/type/ est un \verb/functional/ qui indique le
type des paramètres formels et du résultat, le \verb/storage / vaut
\verb/rom/ et le \verb/initial/ est un \verb/code/ qui contient le corps du module.

Les subroutines et le programme principal n'ont pas d'argument et
retournent un \verb/void/. Le nom du programme principal est prefixé
par un '\_' pour le différencier d'une subroutine.

Tous les autres objets sont considérés au niveau du parser comme des
objets locaux. Leur nom est donc préfixé par le nom du package
associé au module, à savoir le nom du module lui-même.

\PAR{Commons et aires}
\PAR{}
Une aire représente une partie de la mémoire où sont rangées les
variables. Les commons sont des aires (voir plus loin).

\PAR{}
Deux aires spéciales sont créées pour les variables qui
n'appartiennent pas à un common (variables locales). Ces deux aires
sont des entités qui ont pour \verb/name/ \verb/STATIC/ et
\verb/DYNAMIC/, pour \verb/type/ un \verb/area/ qui donne la longueur
de l'aire, pour \verb/storage/ un \verb/rom/ et comme \verb/initial/ une
\verb/value/ de type \verb/unknown/. 

\PAR{}
L'appartenance d'une variable ou d'un common à l'une des ces deux aires
spéciales indique si cette variable ou ce common est statique ou
dynamique.

\PAR{}
Un common est représenté par une \verb/entity/ dont le \verb/name/ est
le nom du common, le \verb/type/ est un \verb/area/ qui donne la
longueur du common en octets, le \verb/storage/ est un \verb/ram/ qui
indique la fonction où le common est declaré (\verb/function/) et
l'aire où le common est rangé (\verb/section/)..

\PAR{Variables -- Généralités}
\PAR{}
Les variables scalaires sont traitées comme des tableaux à 0 dimension.

\PAR{}
Une variable est représentée par une \verb/entity/ dont le \verb/name/ est le
nom de la variable. 

\PAR{Variables -- Types}
\PAR{}
Le \verb/type/ d'une entité ``variable{''} est un \verb/array/ qui donne le type
fortran des éléments (\verb/basic/), le nombre de dimensions (longueur de
la liste \verb/dimensions/) et les bornes de chaque dimension.

\PAR{Variables -- Allocation mémoire}
\PAR{}
Le \verb/storage/ d'une entité ``variable résultat de fonction'' est un
\verb/return/ qui indique la fonction contenant cette variable.

\PAR{}
Le \verb/storage/ d'une entité ``variable paramètre formel'' est un
\verb/formal/ qui indique la fonction contenant ce paramètre et le rang de
ce paramètre dans la liste des paramètres formels.

\PAR{}
Le \verb/storage/ d'une entité ``variable locale ou globale{''} est un \verb/ram/
qui indique dans quelle fonction la variable est déclarée
(\verb/function/), à quelle aire (common ou aire spéciale) elle appartient
(\verb/section/) et quelle est son adresse dans ce common (\verb/offset/).

\PAR{Variable -- Valeur initiale}
\PAR{}
Le \verb/initial/ d'une entité ``variable{''} vaut \verb/unknown/ sauf
si cette variable est de type entier et est initialisée par data. Dans
le cadre de la parallélisation, on ne s'intéresse pas aux autres variables.

\PAR{Constantes numériques et symboliques}
\PAR{}
Les constantes sont considérées comme des fonctions. Elles sont donc
représentées par des entités dont le \verb/name/ est le nom de la
constante (\verb/12/, \verb/13.56E12/, \verb/'*NOMBRE DE FACETTES:*'/, \verb/PI/, \verb/MAXITER/,
etc.), dont le \verb/type/ est un \verb/functional/ à 0 paramètre et 1
résultat qui donne le type de la constante, dont le \verb/storage/ est un
\verb/rom/ et dont le \verb/initial/ est un \verb/constant/ pour les constantes
numériques et un \verb/symbolic/ pour les constantes symboliques.

\PAR{Opérateurs}
\PAR{}
Les opérateurs Fortran sont considérés comme des fonctions. Ils sont
donc représentés par des entités dont le \verb/name/ est le nom de
l'opérateur, et dont le \verb/type/ est un \verb/functional/ qui indique l'arité
de l'opérateur (longueur de la liste \verb/parameters/) mais qui n'indique
pas le type des paramètres ou du résultat car le sous-domaine \verb/basic/
vaut toujours \verb/overloaded/. Le storage d'un opérateur est un \verb/rom/ et
son initial un \verb/intrinsic/.

\PAR{Intrinsics}
\PAR{}
Les intrinsics Fortran (MAX, MIN, ABS, etc.) sont traités comme des
opérateurs. 

\PAR{Labels}
\PAR{}
Les labels sont représentés par des entités dont le \verb/name/ est
le nom du label préfixé par un '\verb/@/', dont le \verb/type/ vaut
\verb/statement/, dont le \verb/storage/ vaut \verb/rom/ et dont le
\verb/initial/ est une constante litterale.

\PAR{Instructions simples}
\PAR{}
Les instructions simples de Fortran telles que RETURN, CONTINUE, STOP,
READ, WRITE, PAUSE, END, ... sont considérées comme des fonctions
intrinsèques.  Elles sont donc représentées par des entités qui ont
les mêmes caractéristiques qu'un opérateur à 0 paramètre. On ne
tient pas a jour le nombre de paramètres car il ne sert à peu près à
rien et que de toute façon, il est variable.

\PAR{}
L'instruction PRINT est transformée en WRITE.

\PAR{Instructions de contrôle}
\PAR{}
Toutes les instructions de contrôle du sous-Fortran que nous acceptons
en entrée, à l'exception de l'instruction \verb/DO/, sont
transformées {\em automatiquement} en séquences équivalentes de tests
à deux branches (une vraie et une fausse), de branchements
inconditionnels et de boucles do.

\PAR{}
\begin{verbatim}
      IF (I) 10, 20, 30
\end{verbatim}
devient
\begin{verbatim}
      IF (I.LT.0) THEN
         GOTO 10
      ELSE
         IF (I.EQ.0) THEN
             GOTO 20
          ELSE
             GOTO 30
          ENDIF
      ENDIF
\end{verbatim}

\PAR{}
\begin{verbatim}
      IF (I.GT.J) I = I-J
\end{verbatim}
devient
\begin{verbatim}
      IF (I.GT.J) THEN
         I=I-J
      ELSE
        CONTINUE
      ENDIF
\end{verbatim}

\PAR{Arguments des instructions d'entrées-sorties}
\PAR{}
Les arguments des instructions d'entrées-sorties sont soit des
informations de contrôle (unité, format, longueur des enregistrements,
etc.), soit des références à lire ou des expressions à écrire. 

\PAR{}
Dans notre représentation, les arguments des instructions
d'entrées-sorties sont des listes de couples d'expressions. La
première expression du couple est une constante chaine de caractères
qui indique la nature de l'argument qui apparaissait dans l'instruction
Fortran (\verb/UNIT=/, \verb/FORMAT=/, \verb/RECL=/, ...). La seconde
expression est la valeur de cet argument.

\PAR{}
Le dernier couple de la liste d'un READ ou d'un WRITE n'est pas un vrai
couple: le premier élément est une expression constante qui vaut
\verb/IOLIST=/, et le second élément est une liste d'expressions qui sont
les références à lire ou les expressions à écrire.

\PAR{Boucles implicites}
\PAR{}
Les boucles do implicites dans les entrées-sorties sont représentées
par des appels à un opérateur prédéfini (en fait une fonction) de
nom \verb/IMPLIED-DO/, qui prend comme arguments une entité qui définit
l'indice de la boucle, une expression \verb/range/ qui définit les bornes de
la boucle, et une liste d'expressions.

\PAR{Formats}
\PAR{}
Les formats sont conservés sous forme d'expressions constantes chaines
de caractères. La constante de nom '*F*' est prédéfinie pour les
formats libres (list-directed).

\PAR{}
Voici un exemple d'instruction d'entrées-sorties.
\begin{verbatim}
      READ(2,'(5E16.6)') (IMD(I),I=1,NDOM), K
\end{verbatim}

devient
\begin{verbatim}
      (READ 'FMT=' '(5E16.6)' 'UNIT=' 2 
            'IOLIST=' (IMPLIED-DO I 1,NDOM,1 IMD(I)) K)
\end{verbatim}

\SEC{Implémentation de parser}
\PAR{}
Le programme parser se compose d'un analyseur lexical et d'un analyseur
syntaxique.

\SSE{Analyse lexicale}

\PAR{}
L'analyse lexicale de Fortran pose quelques problèmes puisque ce
langage ne contient pas de mots clefs réservés comme c'est le cas de
langages plus récents tels que Pascal ou C.

\PAR{}
Par exemple, on détecte que l'instruction suivante est une affectation
car le caractère qui suit la parenthèse fermant la référence au
tableau IF est le caractère '='.
\begin{verbatim}
IF(I, J, K) = 6.66
\end{verbatim}

\PAR{}
En conséquence, l'utilitaire {\em lex}, disponible sous UNIX, ne
permet pas de réaliser un analyseur lexical pour Fortran. Une
première solution consistait donc à écrire complètement un
analyseur lexical pour Fortran, ce qui aurait représenté beaucoup de
travail.

\PAR{}
Nous avons préféré décomposer l'analyse lexicale de Fortran en
deux parties, une première partie ayant pour objet de lever les
ambiguités contenues dans un programme Fortran grâce à une
pré-analyse qui introduit des mots clefs au début de chaque
instruction, et une seconde partie, beaucoup plus simple car basée sur
lex, qui réalise l'analyse syntaxique du Fortran avec mots clefs produit
par la première partie.

\SSS{Pré-analyseur lexical}

\PAR{}
La première partie revient à fournir à l'utilitaire {\em lex} une
fonction ``\verb/getc/''qui permette de lever les difficultés liées à
Fortran.

\PAR{}
La nouvelle fonction \verb/getc/ fonctionne de la façon suivante.  Elle
lit d'un seul coup toutes les lignes d'une instruction Fortran, c'est à
dire la ligne initiale et les 19 éventuelles lignes de continuation, et
les stocke dans le buffer ``\verb/Stmt/''.  Au vol, \verb/getc/ repère
le label, enlève tous les blancs, détecte les caractères entre
simples quotes, transforme les minuscules en majuscules, et met à jour
4 variables externes, qui représentent pour l'instruction courante les
numéros de la première et de la dernière ligne commentaire, et de la
première et de la dernière ligne source.  Ensuite, le contenu du
buffer /verb/Stmt/ est analysé pour y détecter les mot clefs, c'est à
dire traiter les cas des instructions IF, ELSEIF, ASSIGN, DO, des
déclaratives IMPLICIT et FUNCTION, et des operateurs {\em .XX.} (.EQ.,
.NEQV., ...).

\PAR{}
Lorsqu'un mot clef est détecté, il est mis en miniscules dans le
texte source, sauf la première lettre qui reste en majuscule.  Ainsi,
lex peut faire la différence entre le mot clef 'Assign' et
l'identificateur 'ASSIGN'.  Grâce à la première lettre, lex peut
détecter deux mots clef successifs, même sans blanc pour les
séparer, comme dans 'IntegerFunctionASSIGN(X)'.

\PAR{}
Lorsqu'un opérateur .XX. est détecté, il est remplacé dans le
source par \verb+_XX_+.  Ainsi, lex peut faire la difference entre une
constante réelle et un opérateur, comme dans \verb/(X+1._EQ_5)/.

\PAR{}
Les sources du pre-analyseur lexical se trouvent dans les fichiers suivants:
\begin{itemize}
\item f77keywords: les mots clef du sous-Fortran reconnu par PIPS;
\item f77symboles: les symboles (opérateurs, signes de ponctuation,
...) du sous-Fortran reconnu par PIPS;
\item reader.c: code de la nouvelle fonction getc.

\end{itemize}

\SSS{Post-analyseur lexical}

\PAR{}
La seconde partie est tout à fait classique, c'est une spécification
d'analyseur lexical, dans le langage proposé par lex. Cette
spécification se compose d'une liste d'expressions régulières
correspondant aux tokens du langage, ave{c}, pour chacune d'entre elles,
le code du token à renvoyer à yacc lorsqu'un token de ce type est
détecté dans le programme source.

\PAR{}
Les sources du post-analyseur lexical se trouvent dans le fichier
scanner.l. 

\SEC{Analyse syntaxique}

\PAR{}
L'analyse syntaxique de PIPS est réalisée avec l'utilitaire yacc. Cet
utilitaire permet de définir une grammaire par un ensemble de règles
construites sur les tokens du langage et sur d'autres symboles appelés
symboles non terminaux. Voici quelques exemples de règles.
\begin{verbatim}
linstruction: instruction TK_EOS
        | linstruction instruction TK_EOS
        ;

expression: reference
        | call
        | constante
        | signe expression
        | expression TK_PLUS expression
        | expression TK_MINUS expression
        | ...
        ;
\end{verbatim}

La première règle signifie qu'une liste d'instructions est composée
de plusieurs instructions séparées par des tokens \verb+TK_EOS+ (token
end-of-statement). La seconde règle signifie qu'une expression est soit
une référence, soit un call, soit une constante, soit un signe suivie
d'une expression, soit la somme ou la différence de deux expressions.
Les symboles call, constante, reference, ... sont des non-terminaux, et
doivent donc être définis plus loin en fonction des tokens du langage.

\paragraph{}
Yacc permet en plus d'associer à chaque règle une portion de code
écrit en langage C, qui est exécutée chaque fois que la règle en
question est reconnue dans le programme Fortran soumis à l'analyseur.
L'exemple suivant montre une partie de la règle instruction, et la
portion de code associée; il s'agit dans ce cas d'un appel de fonction
pour chainer l'instruction que l'on vient de reconnaitre au bloc
d'instructions courant.
\begin{verbatim}
instruction: return_inst
            { LinkInstToCurrentBlock($1); }
        | ...
        ;
\end{verbatim}

\paragraph{}
L'analyseur syntaxique se compose donc d'un ensemble de règles et d'un
ensemble de fonctions C. Les sources de l'analyseur syntaxique se
composent des fichiers dont la description suit.
\begin{itemize}

\item gram.y: fichier contenant la spécification des règles de la
      grammaire du sous-Fortran PIPS et les actions associées. La
      plupart des ces actions consistent en des appels de fonctions C
      définies dans les fichiers \verb/*.c/.

\item declaration.c: fonctions C appelées par les règles d'analyse des
      déclarations d'un module Fortran.

\item equivalence.c: fonctions C appelées par les règles d'analyse des
      équivalences entre variables.

\item eval.c: fonctions C réalisant un évaluateur d'expressions constantes.
      Cet évaluateur est utilisé principalement pour calculer les bornes des
      tableaux et leur adresse en cas d'équivalence.

\item expression.c: fonctions C appelées par les règles d'analyse des
      expressions contenues dans les déclarations et le code d'un
      module Fortran.

\item hashtable.c: fonctions C permettant de gérer la table des symboles de
      l'analyseur syntaxique.

\item intrinsic.c: fonctions C décrivant les fonctions intrinsèques de
      Fortran.

\item parser.c: le programme principal du parser. Ce programme est
      responsable des initialisations, ouvertures de fichiers, et de
      l'enchainement de l'analyseur lexical et de l'analyseur syntaxique.

\item parser.h: fichier contenant quelques constantes et macros partagées.

\item procedure.c:  fonctions C appelées par les règles d'analyse des
      appels de modules externes.

\item statement.c: fonctions C appelées par les règles d'analyse des
      instructions d'un module Fortran.

\item util.c: diverses fonctions C partagées.
\end{itemize}

\PAR{Conclusion}
\PAR{}
Le programme parser est entièrement réalisé. Son code ne devrait
maintenant subir des transformations que pour effectuer des corrections. 

\PAR{}
La représentation intermédiaire va au contraire évoluer au fur et à
mesure que de nouvelles passes de PIPS vont être développées. En
effet, la plupart des informations qui seront calculées par la suite
(prédicats, effets des procédures, etc.) doivent être directement
raccrochées soit aux instructions d'un module, soit aux entités, ou
bien encore aux expressions. Dans tous les cas, cela signifie qu'il
faudra ajouter de nouveaux champs aux domaines déjà existants.

\newpage
\SEC{ANNEXE}
\PAR{}
Cette annexe contient le listing des programmes sources du parser.

\end{document}
\end
