diff options
| -rw-r--r-- | tp2-files/Calculatrice-final.jj | 90 | ||||
| -rw-r--r-- | tp2-files/Calculatrice.jj | 58 | ||||
| -rw-r--r-- | tp2.tex | 194 |
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()); } +} @@ -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} |