summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2017-01-23 13:15:12 (GMT)
committerDavid A. Madore <david+git@madore.org>2017-01-23 13:20:51 (GMT)
commitc598a4810da9e79398c5fd97666cd3ba328081a0 (patch)
tree472360049d70b5687ba994f7b02a3ef0adf10164
parent698d956eda9997834e6473034bf2f77926c2a86f (diff)
downloadinf105-c598a4810da9e79398c5fd97666cd3ba328081a0.zip
inf105-c598a4810da9e79398c5fd97666cd3ba328081a0.tar.gz
inf105-c598a4810da9e79398c5fd97666cd3ba328081a0.tar.bz2
Copy practice handout on JavaCC from last year.
-rw-r--r--tp2-files/Calculatrice-final.jj90
-rw-r--r--tp2-files/Calculatrice.jj58
-rw-r--r--tp2.tex194
3 files changed, 342 insertions, 0 deletions
diff --git a/tp2-files/Calculatrice-final.jj b/tp2-files/Calculatrice-final.jj
new file mode 100644
index 0000000..9a03f39
--- /dev/null
+++ b/tp2-files/Calculatrice-final.jj
@@ -0,0 +1,90 @@
+// Options pour JavaCC
+options { LOOKAHEAD=1; FORCE_LA_CHECK=true; }
+
+// Fonction principale
+PARSER_BEGIN(Calculatrice)
+public class Calculatrice
+{
+ public static void main(String args[]) throws ParseException
+ {
+ Calculatrice parser = new Calculatrice(System.in);
+ parser.boucle();
+ }
+}
+PARSER_END(Calculatrice)
+
+// Caractères à ignorer (espaces)
+SKIP: { " " | "\r" | "\t" }
+
+// Définitions pour le lexeur
+TOKEN:
+{
+ < NUMBER: (<DIGIT>)+ ("." (<DIGIT>)*)? > // Un nombre en décimal
+| < DIGIT: ["0"-"9"] > // Un chiffre
+| < EOL: "\n" > // Fin de ligne
+}
+
+// Boucle principale: lire des expressions sur une ligne jusqu'à fin de fichier
+// boucle → (expression <EOL>)* <EOF>
+// (<EOL> est défini ci-dessus, <EOF> est reconnu automatiquement)
+void boucle():
+{ double a; }
+{
+ (
+ a=expression() <EOL> { System.out.println(a); }
+ )*
+ <EOF>
+}
+
+// Expression (axiome de la grammaire de la calculatrice)
+// expression → terme ( "+" terme | "-" terme )*
+double expression():
+{ double a,b; }
+{
+ a=terme()
+ (
+ "+" b=terme() { a += b; }
+ | "-" b=terme() { a -= b; }
+ )* { return a; }
+}
+
+// Terme d'une somme ou différence
+// terme → unaire ( "*" unaire | "/" unaire )*
+double terme():
+{ double a,b; }
+{
+ a=unaire()
+ (
+ "*" b=unaire() { a *= b; }
+ | "/" b=unaire() { a /= b; }
+ )* { return a; }
+}
+
+// Gestion du "+" et "−" unaires
+// unaire → puissance | "+" puissance | "-" puissance
+double unaire():
+{ double a; }
+{
+ a=puissance() { return a; }
+| "+" a=puissance() { return a; }
+| "-" a=puissance() { return -a; }
+}
+
+// Opération puissance (associative à droite)
+// puissance → element ( "^" unaire )?
+double puissance():
+{ double a,b; }
+{
+ a=element()
+ (
+ "^" b=unaire() { a = Math.pow(a,b); }
+ )? { return a; }
+}
+
+// Élément d'un calcul (nombre ou expression parenthésée)
+double element():
+{ Token t; double a; }
+{
+ t=<NUMBER> { return Double.parseDouble(t.toString()); }
+| "(" a=expression() ")" { return a; }
+}
diff --git a/tp2-files/Calculatrice.jj b/tp2-files/Calculatrice.jj
new file mode 100644
index 0000000..965aeb3
--- /dev/null
+++ b/tp2-files/Calculatrice.jj
@@ -0,0 +1,58 @@
+// Options pour JavaCC
+options { LOOKAHEAD=1; FORCE_LA_CHECK=true; }
+
+// Fonction principale
+PARSER_BEGIN(Calculatrice)
+public class Calculatrice
+{
+ public static void main(String args[]) throws ParseException
+ {
+ Calculatrice parser = new Calculatrice(System.in);
+ parser.boucle();
+ }
+}
+PARSER_END(Calculatrice)
+
+// Caractères à ignorer (espaces)
+SKIP: { " " | "\r" | "\t" }
+
+// Définitions pour le lexeur
+TOKEN:
+{
+ < NUMBER: (<DIGIT>)+ ("." (<DIGIT>)*)? > // Un nombre en décimal
+| < DIGIT: ["0"-"9"] > // Un chiffre
+| < EOL: "\n" > // Fin de ligne
+}
+
+// Boucle principale: lire des expressions sur une ligne jusqu'à fin de fichier
+// boucle → (expression <EOL>)* <EOF>
+// (<EOL> est défini ci-dessus, <EOF> est reconnu automatiquement)
+void boucle():
+{ double a; }
+{
+ (
+ a=expression() <EOL> { System.out.println(a); }
+ )*
+ <EOF>
+}
+
+// Expression (axiome de la grammaire de la calculatrice)
+// expression → element ( "+" element | "-" element | "*" element | "/" element )*
+double expression():
+{ double a,b; }
+{
+ a=element()
+ (
+ "+" b=element() { a += b; }
+ | "-" b=element() { a -= b; }
+ | "*" b=element() { a *= b; }
+ | "/" b=element() { a /= b; }
+ )* { return a; }
+}
+
+// Élément d'un calcul
+double element():
+{ Token t; }
+{
+ t=<NUMBER> { return Double.parseDouble(t.toString()); }
+}
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}