1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
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}
|
