summaryrefslogtreecommitdiffstats
path: root/tp2.tex
diff options
context:
space:
mode:
Diffstat (limited to 'tp2.tex')
-rw-r--r--tp2.tex194
1 files changed, 194 insertions, 0 deletions
diff --git a/tp2.tex b/tp2.tex
new file mode 100644
index 0000000..8fb0917
--- /dev/null
+++ b/tp2.tex
@@ -0,0 +1,194 @@
+%% This is a LaTeX document. Hey, Emacs, -*- latex -*- , get it?
+\documentclass[12pt,a4paper]{article}
+\usepackage[a4paper,margin=2cm]{geometry}
+\usepackage[francais]{babel}
+\usepackage[utf8]{inputenc}
+\usepackage[T1]{fontenc}
+%\usepackage{ucs}
+\usepackage{times}
+% A tribute to the worthy AMS:
+\usepackage{amsmath}
+\usepackage{amsfonts}
+\usepackage{amssymb}
+\usepackage{amsthm}
+%
+\usepackage{mathrsfs}
+\usepackage{wasysym}
+\usepackage{url}
+%
+\usepackage{graphics}
+\usepackage[usenames,dvipsnames]{xcolor}
+%\usepackage{tikz}
+%\usetikzlibrary{arrows,automata,positioning}
+\usepackage[hyperindex=false]{hyperref}
+%
+\theoremstyle{definition}
+\newtheorem{comcnt}{Tout}
+\newcommand\thingy{%
+\refstepcounter{comcnt}\smallbreak\noindent\textbf{\thecomcnt.} }
+\newcommand\exercice{%
+\refstepcounter{comcnt}\bigbreak\noindent\textbf{Exercice~\thecomcnt.}}
+\renewcommand{\qedsymbol}{\smiley}
+%
+\newcommand{\liff}{\mathrel{\Longleftrightarrow}\relax}
+%
+\DeclareUnicodeCharacter{00A0}{~}
+\DeclareUnicodeCharacter{03B5}{$\varepsilon$}
+%
+\DeclareMathSymbol{\tiret}{\mathord}{operators}{"7C}
+\DeclareMathSymbol{\traitdunion}{\mathord}{operators}{"2D}
+\DeclareSymbolFont{roman}{OT1}{cmr}{m}{n}
+\DeclareMathSymbol{\ldquote}{\mathopen}{roman}{"5C}
+\DeclareMathSymbol{\rdquote}{\mathopen}{roman}{"22}
+\DeclareMathSymbol{\endash}{\mathbin}{roman}{"7B}
+%
+%
+\DeclareFontFamily{U}{manual}{}
+\DeclareFontShape{U}{manual}{m}{n}{ <-> manfnt }{}
+\newcommand{\manfntsymbol}[1]{%
+ {\fontencoding{U}\fontfamily{manual}\selectfont\symbol{#1}}}
+\newcommand{\dbend}{\manfntsymbol{127}}% Z-shaped
+\newcommand{\danger}{\noindent\hangindent\parindent\hangafter=-2%
+ \hbox to0pt{\hskip-\hangindent\dbend\hfill}}
+%
+\newcommand{\spaceout}{\hskip1emplus2emminus.5em}
+\newif\ifcorrige
+\corrigetrue
+\newenvironment{corrige}%
+{\ifcorrige\relax\else\setbox0=\vbox\bgroup\fi%
+\smallbreak\noindent{\underbar{\textit{Corrigé.}}\quad}}
+{{\hbox{}\nobreak\hfill\checkmark}%
+\ifcorrige\relax\else\egroup\fi\par}
+%
+%
+%
+\begin{document}
+\ifcorrige
+\title{TP \texttt{JavaCC} — Corrigé}
+\else
+\title{TP \texttt{JavaCC}}
+\fi
+\author{David A. Madore}
+\maketitle
+
+\centerline{\textbf{INF105}}
+
+{\footnotesize
+\immediate\write18{sh ./vc > vcline.tex}
+\begin{center}
+Git: \input{vcline.tex}
+\end{center}
+\immediate\write18{echo ' (stale)' >> vcline.tex}
+\par}
+
+\pretolerance=8000
+\tolerance=50000
+
+
+%
+%
+%
+
+
+JavaCC est un programme permettant de créer automatiquement un
+analyseur syntaxique (=parseur, \textit{parser} en anglais) pour un
+langage décrit sous forme de grammaire hors contexte. Le principe est
+le suivant : on écrit un fichier \texttt{.jj} qui contient un mélange
+de description du langage (sous forme de productions dans une syntaxe
+évoquant les expressions régulières) et de code Java à exécuter
+lorsque ces différentes productions sont rencontrées. Le programme
+\texttt{javacc} convertit ce fichier \texttt{.jj} en un fichier
+\texttt{.java} qui contient le code de l'analyseur (on peut ensuite
+compiler ce fichier avec \texttt{javac} comme n'importe quel code
+Java).
+
+La documentation de JavaCC est accessible en ligne sur
+\url{http://javacc.java.net/doc/docindex.html} mais il est
+probablement plus simple d'apprendre par imitation.
+
+Sur \url{http://perso.enst.fr/~madore/inf105/Calculatrice.jj} (à
+télécharger, ou à recopier depuis
+\texttt{\char`\~madore/Calculatrice.jj} dans les salles de TP) on
+trouvera le code d'une calculatrice très simple écrit en JavaCC. On
+peut compiler et lancer ce code (après l'avoir recopié) en lançant
+successivement :
+
+\noindent
+\indent\texttt{\char`\~madore/bin/javacc Calculatrice.jj}\\
+\indent\texttt{javac Calculatrice.java}\\
+\indent\texttt{java Calculatrice}
+
+On peut alors taper des expressions arithmétiques telles que
+\texttt{3+4} ou \texttt{2*6} (terminer chaque calcul en tapant
+Enter, et terminer le programme en tapant Control-D). Vérifier que
+cela fonctionne correctement.
+
+Initialement, la grammaire de la calculatrice dans
+$\texttt{Calculatrice.jj}$ est donnée par :
+\[
+\begin{array}{rcl}
+\mathit{expression} & \rightarrow & \mathit{element} \;
+( \ldquote\hbox{\texttt{+}}\rdquote \mathit{element}
+\,|\, \ldquote\hbox{\texttt{-}}\rdquote \mathit{element}
+\,|\, \ldquote\hbox{\texttt{*}}\rdquote \mathit{element}
+\,|\, \ldquote\hbox{\texttt{/}}\rdquote \mathit{element}
+){*}\\
+\mathit{element} & \rightarrow & \mathit{Number}\\
+\mathit{Number} & \rightarrow &
+[\ldquote\mathtt{0}\rdquote\endash\ldquote\mathtt{9}\rdquote]{+} \;
+(\ldquote\mathtt{.}\rdquote \;
+[\ldquote\mathtt{0}\rdquote\endash\ldquote\mathtt{9}\rdquote]*)?
+\end{array}
+\]
+
+(1) Que se passe-t-il quand on demande de calculer \texttt{3+4*5} à
+la calculatrice ? Pourquoi ?
+
+Modifier la grammaire pour avoir une priorité correcte des opérations
+(\texttt{*} et \texttt{/} doivent être prioritaires sur
+\texttt{+} et \texttt{-}, et en particulier \texttt{3+4*5} doit
+renvoyer $23$). Pour cela, on peut par exemple introduire un nouveau
+nonterminal $\mathit{terme}$ représentant un terme d'une somme ou
+différence, et qui est lui-même formé de produits ou quotients.
+Tester la calculatrice ainsi modifiée.
+
+(2) La calculatrice ne gère pas les parenthèses : ajouter cette
+fonctionnalité et tester. Par exemple, \texttt{(3+5)/(2*2)} doit
+revoyer $2$. Pour cela, on pourra ajouter une nouvelle production
+pour $\mathit{element}$ correspondant à une $\mathit{expression}$
+entourée de parenthèses.
+
+(3) La calculatrice ne gère pas le $-$ unaire (pour indiquer l'opposé
+d'un nombre) : ajouter cette fonctionnalité et tester. Par exemple,
+\texttt{-3*-6} doit renvoyer $18$, et \texttt{-1-2} doit
+renvoyer $-3$. Vérifier que le moins unaire marche aussi devant les
+parenthèses (\texttt{-(2+3)} doit renvoyer $-5$). On pourra aussi
+ajouter le $+$ unaire (qui ne change pas le nombre). Pour cela, on
+pourra introduire un nouveau nonterminal $\mathit{unaire}$
+représentant un élément éventuellement précédé d'un $-$ (ou d'un $+$)
+unaire.
+
+(4) La calculatrice ne gère pas l'opération puissance : introduire
+celle-ci sous la notation du caractère ``\texttt{\char"5E}''
+(accent circonflexe) : attention, on veut que l'opération
+\texttt{\char"5E} soit prioritaire sur toutes les autres (addition,
+soustraction, multiplication, division, et opérations unaires), et on
+veut qu'elle soit associative \emph{à droite}, c'est-à-dire par
+exemple que \texttt{2\char"5E\relax 3\char"5E\relax 2} doit calculer $2^{3^2}
+= 2^9 = 512$.
+
+La méthode Java permettant de calculer $a^b$ s'écrit \texttt{Math.pow(a,b)}.
+
+Tester notamment les calculs suivants : $\hbox{\texttt{2\char"5E\relax
+ 3\char"5E\relax 2}} \rightsquigarrow 512$ ;
+$\hbox{\texttt{-1\char"5E\relax 2}} \rightsquigarrow -1$ ;
+$\hbox{\texttt{(-1)\char"5E\relax 2}} \rightsquigarrow 1$ ;
+$\hbox{\texttt{2\char"5E\relax -1}} \rightsquigarrow 0.5$ ;
+$\hbox{\texttt{2*3\char"5E\relax 2*3}} \rightsquigarrow 54$.
+
+
+
+%
+%
+%
+\end{document}