From c598a4810da9e79398c5fd97666cd3ba328081a0 Mon Sep 17 00:00:00 2001 From: "David A. Madore" Date: Mon, 23 Jan 2017 14:15:12 +0100 Subject: Copy practice handout on JavaCC from last year. --- tp2.tex | 194 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 194 insertions(+) create mode 100644 tp2.tex (limited to 'tp2.tex') 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} -- cgit v1.2.3