\documentclass{article}
\usepackage{syntax}
\usepackage{parskip}
\usepackage{amsmath, amsfonts, amssymb}
\usepackage[french]{babel}
\usepackage[margin=3cm]{geometry}
\usepackage[utf8]{inputenc}
\usepackage{float}
\usepackage{graphicx} % Required for inserting images
\usepackage[svgnames]{xcolor}
\usepackage{listings}
\usepackage{courier}
\lstset{basicstyle=\ttfamily}
\lstdefinelanguage{diff}{
  morecomment=[f][\color{blue}]{@@},     % group identifier
  morecomment=[f][\color{Purple}]{...},     % snippet cuts
  morecomment=[f][\color{red}]-,         % deleted lines 
  morecomment=[f][\color{DarkGreen}]+,       % added lines
  morecomment=[f][\color{Gray}]{//},       % comments
  morecomment=[f][\color{magenta}]{---}, % Diff header lines (must appear after +,-)
  morecomment=[f][\color{magenta}]{+++},
}



\title{
\includegraphics[width=0.2\textwidth]{n7-wordmark.png}
\\[2cm]
Rapport de projet: RAT}
\author{Téo Pisenti et Ewen Le Bihan}
\date{
Traduction des langages et programmation fonctionnelle
\\[0.25cm]
Janvier 2024}

\begin{document}

\maketitle

\tableofcontents

\section{Introduction}

Le but des TPs était la réalisation d'un compilateur pour le langage RAT, compilant vers du code TAM (Triangle Abstract Machine), une machine à pile.

Le langage RAT décrit la définition de variables, de fonctions, de conditions (if/else) et de boucles tant-que (\verb|white|) % todo il en manque sûrement
et les types entier, booléen et rationnels.

Le but du projet a été d'étendre le travail réalisé en TP par la spécification de nouvelles fonctionnalités:

\begin{itemize}
    \item Les pointeurs
    \item Les tableaux
    \item Les boucles \verb|for|
    \item Les goto (saut à un endroit arbitraire du code d'une fonction ou du bloc principal)
\end{itemize}


\section{Implémentation des pointeurs}

\subsection{Syntaxe}

On commence par modifier la grammaire du langage (cf Figure \ref{fig:pointers-ebnf-diff}): l'affectation à et la déclaration de variables ne se fait plus directement sur des identifiants mais peut être effectué sur des pointeurs en les déréférençant avec \verb|*|.

On introduit donc un nouveau type de n\u0153ud dans l'AST, des \emph{cibles d'affectation}, ou \emph{assignment target} en anglais.

Ce type a deux constructeurs, un pour désigner un identifiant direct, (donc une variable), et un autre pour désigner un déréférencement d'une cible d'affectation (la nature récursive permet de déréférencer profondément un pointeur de pointeur de\u2026 à un ordre arbitraire).

On ajoute aussi un nouveau constructeur au type \verb|typ|, définissant les types du langage: il faut pouvoir déclarer que des variables, des paramètres ou le retour d'une fonction sont des pointeurs sur un certain type de donnée. Là encore, le caractère récursif du constructeur permettra de définir de pointeurs d'ordre supérieur.

Enfin, il faut rajouter quelques expressions:

\begin{itemize}
    \item Instanciation de nouveaux pointeurs (avec \verb|new|)
    \item Opérateur pour prendre l'adresse d'une variable (on n'autorise pas de prendre l'adresse d'une variable déréférencée, par exemple \verb|&*a|) (avec \verb|&|)
    \item Utilisation de variables déréférencées (avec \verb|*|)
    \item Une valeur spéciale \verb|null| représentant un pointeur vide (avec \verb|null|)
\end{itemize}

Ceci demande donc l'ajout de trois nouveaux tokens, \verb|new|, \verb|null| (des mots-clés) et \verb|&|. 

\begin{figure}[H]
    \centering
    \begin{lstlisting}[language=diff]
  I ->  TYPE id = E;
-       | id = E;
+       | A = E;
...
// definition des assignment targets
+ A -> id | (* A) 
...
// definition de la syntaxe pour les types pointeurs
  TYPE -> bool 
        | int
        | rat
+       | TYPE * 
...
//definition de new, & et *
  E ->  id ( CP )
        | [ E / E ]
        | num E
        | denom E
-       | id
+       | A
...
+       | null
+       | (new TYPE)
+       | & id
...
    \end{lstlisting}
    \caption{Modification des règles EBNF pour définir la grammaire des relative aux pointeurs}
    \label{fig:pointers-ebnf-diff}
\end{figure}


\subsection{Jugement de types}

On étend les mécanismes déjà existants de vérification de la cohérence des types entre:

\begin{itemize}
    \item  les paramètres formels et effectifs, 
    \item les \verb|return| et le type de retour déclaré de la fonction), et
    \item dans les déclarations de variables.
\end{itemize}

Pour cela, on rend la fonction \verb|estCompatible t1 t2| récursive, et on rajoute le cas des Pointeurs, en comparant simplement si les types intérieurs des pointeurs sont compatibles. 

On a le cas particulier du pointeur null, qui est un autre constructeur de type \verb|typ|, et qui a la particularité d'être compatible avec n'importe quelle type pointeur, peut importe le type intérieur de celui-ci.

\begin{align*}
    \frac{\sigma \vdash v : \operatorname{Pointeur}(\tau)}{
    \sigma \vdash \operatorname{\&}v : \tau
    } \quad\quad 
    \frac{\sigma \vdash e : \tau}{
    \sigma \vdash \operatorname{\ast}e : \operatorname{Pointeur}(\tau)
    } 
\end{align*}

\subsection{Placement mémoire}

On étend la fonction calculant la taille des types avec le cas des pointeurs. Un pointeur prend toujours une place de $1$ (on stocke une adresse, qui est un entier).

\subsection{Génération de code}

On utilise l'instruction \verb|LOADA| de TAM pour charger une valeur dans la pile se trouvant à une adresse déjà chargée dans la pile.

\section{Tableaux}

\subsection{Syntaxe}

Pour la définition des tableaux, il y a plusieurs éléments de langage à définir:

\begin{itemize}
    \item Les types tableau (par ex. \verb|int[]|)
    \item Les littéraux de tableaux (pour décrire un tableau en fournissant explicitement ses éléments, par ex. \verb|{1, 2, 3, 4}|)
    \item L'indexation de tableaux (permettant de récupérer ou de modifier un élément en particulier, par ex. \verb|a[0]|)
    \item L'initialisation de tableaux (pour initialiser un tableau vide en précisant sa capacité en nombre d'éléments, par ex. \verb|new int[10]|)
\end{itemize}

On modifie donc la grammaire, cf Figure \ref{fig:ebnf-rules-diff-arrays}

\begin{figure}[H]
    \centering
    \begin{lstlisting}[language=diff]
  A -> id
    | (* A) 
// indexation
+   | ( A[E] )
...
  TYPE -> bool
        | int
        | rat
        | TYPE*
// types
+       | TYPE[]
...
  E -> id ( CP )
    | [ E / E ]
...
// initialisation
+   | (new TYPE[E])
// litteraux
+   | { CP }
    \end{lstlisting}
    \caption{Ajout des règles EBNF relative aux tableaux}
    \label{fig:ebnf-rules-diff-arrays}
\end{figure}

\subsection{Jugement de types}

\begin{description}
    \item[Types] Extension de la fonction regardant la compatibilité de deux types, en regardant la compatibilité des types des éléments
    \item[Littéraux] Vérification de l'homogénéité des types des éléments déclarés
    \item[Indexation] On vérifie que l'expression servant d'index est bien de type Entier. On pourrait considérer que le nombre d'éléments fait partie du type du tableau pour mettre en place une vérification et éviter les indexations en dehors du tableau (si $\texttt{index} \ge \mathrm{card}(\texttt{tableau})$ ou $\texttt{index} < 0$)
    \item[Initialisation] On vérifie que l'expression donnant la taille du tableau est bien un entier.
\end{description}

Soit $\tau$ un type.

\begin{align*}
\frac{
\sigma \vdash e_1 : \tau \quad\quad
(e_1, \tau)::\sigma \vdash e_2 : \tau \quad\quad
\cdots \quad\quad
(e_1, \tau)::\sigma \vdash e_n : \tau
}{\sigma \vdash \{ e_1, e_2, \ldots, e_n \} : \operatorname{Tableau}(\tau)}
\end{align*}
\begin{align*}
\frac{
\sigma \vdash v : \operatorname{Tableau}(\tau) \quad\quad
\sigma \vdash i : \operatorname{Int}
}{\sigma \vdash (v[i]) : \tau}
\end{align*}

\begin{align*}
    \frac{
    \sigma \vdash e : \operatorname{Entier}
    }{\sigma \vdash \operatorname{new} \tau[e] : \operatorname{Tableau}(\tau)}
\end{align*}

\subsection{Placement mémoire}

On étend la fonction calculant la taille en même d'un type, en ajoutant le cas des tableaux:

$$
|T[n]| = n |T|
$$

\subsection{Génération de code}

Pour les littéraux, on génère le code en chargeant dans l'ordre chacune des expressions. 

Cependant, il faut mettre dans la pile l'adresse vers la base du tableau à la fin, pour que l'on puisse utiliser ce tableau dans des affectations et autres. (En effet, un tableau est un pointeur sur son premier élément)

On utilise \verb|malloc 0| pour charger l'adresse actuelle dans la pile.

\section{Boucle {\texttt{for}}}

\subsection{Syntaxe}

On ajoute ensuite les boucles \verb|for|. Une boucle \verb|for| comporte 4 parties:

\begin{description}
    \item[Initialisation] On initialialise une variable
    \item[Test] On fourni une expression a vérifier pour savoir si l'on continue à effectuer la boucle.
    \item[Incrémentation] On change la valeur de la variable par celle d'une expression calculée à chaque fin de tour de boucle. C'est souvent une incrémentation de la variable (qui agit alors comme un compteur).
    \item[Corps] Les instructions à effectuer à chaque tour de boucle.
\end{description}

La syntaxe ressemble à ceci:

\begin{lstlisting}[language=C]
   for (INITIALISATION; TEST; INCREMENTATION) {
        CORPS
   }
\end{lstlisting}

On rajoute donc une nouvelle variante dans l'union de la règle de production des instructions:

\begin{lstlisting}[language=diff]
  I -> TYPE id = E;
    | A = E;
...
+   | for (int id = E; E; id = E) BLOC
...
\end{lstlisting}

On préfère ceci à utiliser \verb|I| pour \verb|INITIALISATION| (resp. \verb|INCRÉMENTATION|) pour limiter le travail à effectuer dans la passe suivante (il faudrait vérifier que l'instructions est bien une déclaration (resp. affectation)).

\subsection{Gestion des identifiants}

Cependant, les passes suivantes bénéficieront d'un n\u0153ud plus simple, contenant simplement quatres n\u0153uds. On transforme donc, dès la première phase, \verb|int id = E| et \verb|id = E|. On en profite pour vérifier que ces deux identifiants ont bien le même nom.

On crée aussi une TDS fille intermédiaire pour stocker la variable initialisée par la boucle for. L'injecter dans la TDS qui sera créée par le corps de la boucle est possible mais complexe car cela demande de faire attention à ne pas ré-initialiser la variable à chaque tour de boucle. De plus, c'est complexe architecturellement pour le code.

\subsection{Jugement de types}

\begin{description}
    \item[Initialisation] On vérifie que la variable initialisée est bien de type Entier.
    \item[Test] On vérifie que l'expression est bien de type Booléen.
    \item[Incrémentation] Rien de spécial à implémenter (vu que le jugement sera simplement effectué par l'analyse de l'affectation)
    \item[Corps] Rien de spécial non plus.
\end{description}

\begin{align*}
\frac{\sigma \vdash e_1 : \operatorname{Int} \quad\quad (i, \operatorname{Int})::\sigma \vdash e_2 : \operatorname{Bool} \quad\quad (i, \operatorname{Int})::\sigma \vdash e_3 : \operatorname{Int} }{\sigma \vdash \operatorname{for}(\text{int $i$ = $e_1$} ; e_2 ; i = e_3) \  \{ \cdots \} }
\end{align*}

\subsection{Génération de code}

On effectue l'initialisation, on marque le début et la fin de la boucle avec des étiquettes, on effectue l'incrémentation après les instructions, on évalue l'expression du test et on saute au début de la boucle si le test s'évalue à vrai.

\section{Étiquettes et \texttt{goto}}

\subsection{Syntaxe}

L'instruction \verb|goto| permet de sauter à un autre endroit du code. Il faut donc non seulement définir la syntaxe de cette instruction, mais également définir comment marquer cet autre endroit du code, en lui donnant un nom.

On rajoute donc deux productions: l'instruction \verb|goto|, et une instruction spéciale "étiquette" qui comporte le nom de l'étiquette à définir et l'instruction à marquer avec celle-ci. Les modifications sont décrites figure \ref{fig:goto-ebnf-diff}.

\begin{figure}[H]
    \centering
    \begin{lstlisting}[language=diff]
  I -> TYPE id = E;
    | A = E;
...
+   | goto id;
+   | id : I
    \end{lstlisting}
    \caption{Modifications des règles EBNF relatives à \texttt{goto}}
    \label{fig:goto-ebnf-diff}
\end{figure}

\subsection{Gestion des identifiants}

On stocke les étiquettes dans une TDS séparée pour éviter les collisions.

Il y a une difficultée dans le fait qu'une étiquette peut être analysée dans un n\u0153ud Goto avant d'avoir analysé sa déclaration. Il faut donc stocker deux types d'étiquettes dans la TDS: les utilisations d'étiquettes, et les déclarations.

Quand on rencontre une déclaration d'étiquette, on vérifie qu'elle n'existe pas déjà pour éviter les doubles déclarations. Si il existe une utilisation d'étiquette portant le même nom, on remplace celle-ci par une déclaration d'étiquette, afin de marquer que l'étiquette est bien définie.

Enfin, si l'on essaie d'utiliser \verb|goto| avec une étiquette non définie, la passe de génération de code ne trouvera pas l'étiquette car elle ne cherche que dans les \verb|info_ast| de constructeur \verb|InfoLabelDef| (définitions des étiquettes), et non les \verb|InfoLabelUse| (utilisation des étiquettes). Une solution plus propre serait de vérifier que chaque \verb|InfoLabelUse| possède un \verb|InfoLabelDef| correspondant, après analyse des identifiants de chaque fonction (et du programme principal).

\paragraph{Difficultées rencontrées}

Il est impossible d'utiliser les opérateurs standards d'OCaml \verb|ref| et \verb|!| en dehors du fichier \verb|tds.ml|, car celui-ci définit les types \verb|info| et \verb|info_ast| qui opacifie le fait que \verb|info_ast| soit une \verb|ref|. Il faut donc définir une fonction \emph{dans tds.ml} qui modifiera le constructeur de l'étiquette pour passer celle-ci d'une utilisation à une définition, quand on rencontre une instruction avec étiquette \emph{après} avoir recontré son utilisation par un goto.

\subsection{Génération de code}

Il suffit d'utiliser les instructions TAM \verb|JUMP| et les étiquettes, fonctionnalité native à TAM.

Il faut cependant penser à namespacer les noms des étiquettes avec un préfixe pour éviter tout conflit avec des étiquettes internes générées par, par exemple, les boucles.

\subsection{Jugement de typages}

Les étiquettes n'étant pas des valeurs, elles n'ont pas de types. Il n'y a donc rien à juger.
% on juge pas ici ok?

% bon en gros, faut:
% - (Expliquer la structure de l'AST)?


\section{Annexes}


\subsection{Grammaire complète}

\parskip
Le non-terminal servant de point d'entrée au parser est $\langle \text{début} \rangle$.

\subsubsection{Terminaux spéciaux}
\begin{description}
    \item[EOF] fin du fichier
    \item[LT] caractère $<$
    \item[$\Lambda$] chaîne vide
    \item[`*'] caractère * (le * seul servant à dénoter la répétition)
\end{description}


\paragraph{}
\begin{grammar}
    <début> ::= <programme> EOF

    <programme> ::= <fonction>* id <bloc>
    
    <fonction> ::= <type> id ( <paramètres> ) <bloc>

    <bloc> ::= \{ <instruction>* \}

    <instruction> ::= <type> id = <expression> ;
    \alt <cible> = <expression> ;
    \alt const id = <expression> ;
    \alt print <expression> ;
    \alt if <expression> <bloc> else <bloc>
    \alt while <expression> <bloc>
    \alt return <expression> ;
    \alt for ( int id = <expression> ; <expression>  ; id = <expression> ) <bloc> 
    \alt goto id ;
    \alt id : <instruction>

    <cible> ::= id 
    \alt ( `*' <cible> )
    \alt ( <cible> [ <expression> ] )

    <paramètres> ::= <type> id 
    \alt <type> id, <paramètres>
    \alt $\Lambda$

    <type> ::= bool \alt int \alt rat \alt <type> `*' \alt <type> [ ]

    <expression> ::= id ( <liste d'expressions> )
    \alt [ <expression> / <expression> ]
    \alt num <expression> 
    \alt denom <expression>
    \alt <cible>
    \alt \& id
    \alt true \alt false \alt null
    \alt entier
    \alt ( <expression> + <expression> )
    \alt ( <expression> * <expression> )
    \alt ( <expression> = <expression> )
    \alt ( <expression> LT <expression> )
    \alt ( <expression> )
    \alt ( new <type> )
    \alt ( new <type> [ <expression> ] )
    \alt \{ <liste d'expressions> \}

    <liste d'expressions> ::= <expression>
    \alt <expression>, <liste d'expressions>
    \alt $\Lambda$    
\end{grammar}

\end{document}

