MASTER 1ère année 2013/2014

(Mis en ligne le 01/10/2013)

Projet de Compilation

(Compilateur du langage algorithmique

du paquetage algorithm2e de LaTeX)

But du projet

LaTeX prononcé /la.tɛk/, est un langage permettant de composer un document texte. Il est très utilisé notamment pour écrire de jolis documents scientifiques ou des articles de recherche. De tels documents peuvent parfois contenir la description d'un algorithme. Pour cela, il existe un module ou paquetage de LaTeX appelé algorithm2e qui étend LaTeX en fournissant des commandes plus spécifiques pour écrire des algorithmes. L'objectif de ce projet est d'implémenter un compilateur (à écrire en C) qui extrait les algorithmes d'un document LaTeX et produit du code exécutable MIPS qui réalise ces algorithmes, c.-à-d. un code MIPS dont l'exécution suit les algorithmes qui sont décrits.

Votre compilateur doit être capable de compiler les algorithmes qui sont écrits en utilisant les commandes LaTeX listées dans la section 1b) qui suit : si, lors de la démonstration de votre projet, vous arrivez à convaincre l'enseignant chargé d'évaluer votre travail que votre compilateur est fiable et produit toujours un code exécutable correct avec cet ensemble de commandes, alors vous obtiendrez la note maximum. La lisibilité du code de votre compilateur et la fiabilité du code exécutable généré, qui font la qualité d'un compilateur, seront très importantes dans l'élaboration de la note (privilégier la qualité à la quantité).

1 Présentation du langage source

a) Principe des commandes LaTeX

Le "programme source" est donc un document texte écrit en LaTeX (contenu dans un fichier dont l'extension est .tex), mais on ne prendra en compte qu'une partie seulement de ce document : la partie qui décrit les algorithmes, tout le reste sera considéré comme des commentaires. La description suivante de la syntaxe du langage source reste assez informelle : nous laissons au concepteur du compilateur la liberté de choisir les règles de grammaire à condition que ces règles définissent bien un langage qui est un sous-ensemble du langage LaTeX étendu avec les commandes du paquetage algorithm2e.

Les commandes LaTeX commencent toutes par une barre oblique inversée (ou antislash) \ (par exemple \title{Projet de compilation}) et sont éventuellement immédiatement suivies d'arguments entre accolades. Celles qui nous intéressent particulièrement ici sont celles situées entre \begin{algo} et \end{algo}. Voici un exemple d'algorithme écrit en LaTeX :

\begin{algo}{factorielle}
\Input{$n \in \Integer$}
\Output{$accu \in \Integer$}
\Global{$\emptyset$}
\Local{$\emptyset$}
\BlankLine
  $accu \leftarrow 1$ \;
  \While{$n \neq 0$} {
    $accu \leftarrow n \times accu$ \;
    $n \leftarrow n - 1$
  }
\end{algo}

Votre "programme source" doit toujours contenir les lignes suivantes (au début du fichier .tex et avant la commande \begin{document}) :

\usepackage[vlined,ruled]{algorithm2e}
\usepackage{amssymb}
\usepackage{amsmath,alltt}

\newenvironment{algo}[1]{%
\vspace{1cm}
\renewcommand{\algorithmcfname}{Algorithm}
\begin{algorithm}[H]
\label{#1}
\caption{#1}
\SetKwInOut{Constant}{Constant}
\SetKwInOut{Input}{Input}
\SetKwInOut{Output}{Output}
\SetKwInOut{Global}{Global}
\SetKwInOut{Local}{Local}
}{%
\end{algorithm}
\vspace{1cm}
}

% Définition des types scalaires
\newcommand{\true}{\mbox{\it true}}
\newcommand{\false}{\mbox{\it false}}
\newcommand{\Boolean}{\{\true,\false\}}
\newcommand{\Integer}{\mathbb{Z}}
\newcommand{\Complex}{\mathbb{C}}
\newcommand{\Real}{\mathbb{R}}

b) Quelques éléments syntaxiques

La description d'un algorithme commence par \begin{algo}{<nom d'algorithme>} et termine par \end{algo}.

-- Au début de la description se trouve une zone (terminée par \BlankLine) pour déclarer les variables utilisées. Les commandes dans cette zone sont :

\Constant{$<suite de déclarations>$} pour déclarer des constantes,

\Input{$<suite de déclarations>$} pour déclarer les variables en entrée (arguments ou paramètres formels),

\Output{$<suite de déclarations>$} pour déclarer les variables en sortie (résultats),

\Global{$<suite de déclarations>$} pour déclarer les variables globales à l'algorithme,

\Local{$<suite de déclarations>$} pour déclarer les variables locales à l'algorithme.

(les $ font partie de la syntaxe, mais pas les mots entre < et >).

Les éléments d'une suite de déclarations sont séparés par une virgule ",". Lorsqu'il n'y a aucune déclaration, la partie <suite de déclarations> se réduit à "\emptyset".

-- Une déclaration de variable est de la forme <nom de variable> \in <type> où le type peut être scalaire : <type_scalaire> (\Integer, \Real, \Complex) ou bien vectoriel auquel cas le type est de la forme <type_scalaire>^{<dimension>} . 

-- Une déclaration de constante est de la forme <nom de constante> = <valeur> \in <type_scalaire> (par exemple, "N = 2 \in \Integer"). 

-- La suite de la description contient des commandes correspondantes à l'écriture d'une instruction ou d'une structure de contrôle par exemple on note :  

• $<nom de variable> \leftarrow <expression>$ pour l'affectation de la valeur d'une expression à une variable, 

• <instruction> \;

...          \;

<instruction>

pour une séquence de plusieurs instructions (les instructions sont séparées par \; et un retour à la ligne),

• \While{$<condition>$}{<instruction>} pour une boucle while,
  

c) Exemple de programme (ou texte) source

Cet exemple est un document LaTeX contenant des algorithmes pour :

1. Factorielle (version itérative)
   
2. Addition de 2 vecteurs

d) Une autre manière de compiler un programme source

2 Génération de code

Le code généré devra être en assembleur MIPS R2000. L’assembleur est décrit dans les documents mips.pdf et mips.ps. Voici des exemples de codes MIPS :

• factiter.s
• sum.s
  

Le code assembleur devra être exécuté à l’aide du simulateur de processeur R2000 SPIM. Celui-ci est installé sur la machine turing. Pour exécuter un code assembleur, il suffit de faire : spim <nom_du_code>.s. Si vous désirez installer SPIM sur votre propre machine :

• télécharger le package spim.tar.gz
• tar xvfz spim.tar.gz
  
• cd spim-8.0/spim
  
• ./Configure // Vérifier qu’il n’y a pas de messages d’erreur (librairie ou logiciel manquant)
  
• Modifier dans le fichier Makefile la ligne EXCEPTION_DIR = en y saisissant le chemin d’accès au répertoire contenant le fichier exceptions.s. Il s’agit du répertoire : /chemin_vers_votre_racine/spim-8.0/CPU
  
• make

3 Autres précisions et recommandations

Une partie du travail demandé consiste à élaborer des exemples qui fonctionnent et qui serviront lors de votre démonstration pour l'évaluation de votre projet.