\documentclass{amsart}
\usepackage{fullpage}
 
\usepackage{epsf}

\setlength{\textwidth}{16cm}
\setlength{\textheight}{24.4cm}
\setlength{\topmargin}{-2cm}
\setlength{\evensidemargin}{0cm}
\setlength{\oddsidemargin}{0cm}

\title{Projet de Th\'eorie des langages\\
 Structures combinatoires et fractales}

\author{Annexe 1\\
Premier temps : reconnaissance des fractales de type L-system}

\begin{document}
\maketitle

\section{Introduction}

Avant de dire que $4+2*(1+2)^2$ vaut 22, il faut avoir {\em lu} 
l'expression en question, non seulement lu comme le ferait un enfant 
de 7 ans, mais bien plus que cela : il faut avoir {\em d\'ecoup\'e} 
cette expression pour en isoler les \'el\'ements significatifs 
et, alors, reconstruire l'expression en calculant la valeur 
au fur et \`a mesure.

En clair, avant de pouvoir {\em \'evaluer}, il faut faire 
une {\em analyse lexicale} et {\em analyse syntaxique}. Il en est 
de m\^eme pour le projet, avant de pouvoir dessiner une fractale 
(donn\'ee sous la forme d'une certain jeu de r\`egles de r\'e\'ecriture),  
il va falloir apprendre \`a lire ce jeu de r\`egles, 
c'est-\`a-dire le d\'ecomposer et voir son architecture. 

\section{Fractales et Fractint}
Il y a deux grandes classes de fractales :
les fractales ``g\'eom\'etriques''  (flocon de neige, feuilles de
chou fleur, formes d'arbres...) et les fractales ``analytiques'' 
(comme le ``bonhomme en pain d'\'epices'' de  Mandelbrot 
ou encore l'ensemble de Julia...).
Les fractales de type analytique 
n\'ecessitent la manipulation de suite de nombres complexes, 
comme ce type n'est pas impl\'emant\'e en Pascal et que pour dessiner 
une telle fractale, il faut manipuler en permanence des nombres
complexes de fa\c con efficace, nous laissons de c\^ot\'e cette classe
de fractales pour l'instant (les \'el\`eves les plus avanc\'es
pourront toujours traiter cette classe par la suite s'ils le d\'esirent).
En revanche, les fractales de
type g\'eom\'etrique
(introduites par Lindenmayer, d'o\`u leur nom de L-systems)
sont d\'ecrites 
par une certaine ``grammaire'', ce qui nous fait d'ores et d\'ej\`a
pr\'esentir l'utilit\'e du couple Lex/Yacc. 


\begin{center}
\leavevmode\epsfxsize=7truecm\epsfysize=10truecm\epsfbox{Flocon.ps}
\leavevmode\epsfxsize=7truecm\epsfysize=10truecm\epsfbox{Over1b.ps}
\title{\\ Fractale de type g\'eom\'etrique \qquad et \qquad fractale de type analytique}
\end{center}

Nous allons dans ce projet employer une fa\c{c}on de d\'ecrire les L-systems
qui est compatible avec le plus grand logiciel d\'edi\'e aux 
fractales : Fractint. Ce logiciel est une interface qui permet de
dessiner des fractales, il a par ailleurs une grande quantit\'e de
formules pr\'eenregistr\'ees et il est possible de cr\'eer ses propres
formules et de voir \`a quel dessin elles vont aboutir.
La derni\`ere version du logiciel (la version 20.0) se trouve sous 
``voisinage r\'eseau, Bdc, Logiciels, Fractint'' ; comme c'est un {\em
freeware} (= un logiciel libre), vous avez le droit de le recopier et de
l'installer chez vous.
% (copier simplement sur disquette le fichier {\bf fract.exe}). 


QUESTION 0.
Allez dans le sous-r\'epertoire de Fractint, puis sur la ligne de
commande de DOS, tapez {\tt fractint}.
Choisissez alors le mode d'affichage 640.480 256 couleurs.
Puis appuyez sur ``t'', choisissez ``lsystems'' puis Koch1.
Validez par entr\'ee. Vous voyez alors appara\^{\i}tre
le flocon de neige ou ``courbe de Von Koch''.
Faites varier le nombre d'it\'erations (0, puis 1, puis 2, puis 3, puis
4...) pour comprendre 
comment la construction se fait. Recommencez la m\^eme op\'eration
avec d'autres fractales dans {\tt lsystem}.


\setlength{\topmargin}{0cm}
\section{L-systems}

Lorsque l'on observe certains arbres, il n'est pas difficile d'imaginer
qu'une branche est relativement semblable \`a l'arbre entier. Les L-systems
utilisent cette id\'ee. Dans le logiciel {\tt Fractint}, un L-system est une description, sur plusieurs 
lignes, donnant : 
le nom choisi pour la fractale, un certain angle $\alpha$, un axiome,
la liste des r\`egles de r\'e\'ecriture.  Voici un exemple (il y en a
d'autres \`a la fin de cette annexe) :\\
{\tt Koch1 \{  \qquad \qquad \qquad ; apr\`es le point-virgule, ce sont des commentaires\\
$\text{ } $\qquad \qquad Angle 6 \qquad \qquad ; l'angle est fix\'e \`a $2\pi/6$\\
$\text{ } $\qquad \qquad Axiom F- -F- -F \qquad ; ici on d\'eclare
qu'on part de la figure F- -F- -F\\
$\text{ } $\qquad \qquad F=F+F- -F+F \qquad ; puis \`a chaque it\'eration, on fait la substitution ci-contre\\
$\text{ } $\qquad \}\\
}
Chaque ligne de description peut \'eventuellement \^etre suivie d'un
point-virgule, indiquant le d\'ebut d'un commentaire. Dans les membres
droits des r\`egles de r\'e\'ecriture, chaque
non-terminal peut \^etre pr\'ec\'ed\'e de $m$ signes $+$, ce qui
signifie que l'on doit tourner d'un angle de $m \alpha$ 
dans le sens contraire des aiguilles d'une montre.
De m\^eme, si un terminal est pr\'ec\'ed\'e de $m$ signes $-$, cela
signifie que l'on doit tourner d'un angle de $m\alpha$ dans le sens
des aiguilles d'une montre.
Il n'y a pas de distinction majuscule /minuscule, les espaces et les
indentations (= tabulations, touche ``Tab'') multiples sont ignor\'ees.
Plusieurs instrutions peuvent rassembl\'ees en une seule ligne 
si elles sont s\'epar\'ees par une virgule.

Voici un autre L-system :\qquad \quad
{\tt Weed \{Angle 50,  Axiom +++++++++++++X,\\
  X=f[@.5+++++++++X]-f[@.4- - - - - - - - - - -!X]@.6X\} }

Les symboles ``+'', ``-'', ``f'', ``@'', ``['', ``]'', et ``!'' sont des symboles
r\'eserv\'es. 
Le symbole ``X'' n'a pas de sens graphique, c'est juste  
un \'el\'ement qui se r\'e\'ecrit selon la ligne ``{\tt X=}''.
Le symbole ``+'' signifie ``tourne \`a gauche de $7.2=360/\alpha$
degr\'es'' ($\alpha$ est la valeur donn\'ee \`a {\tt Angle}). 
Le symbole ``-'' signifie ``tourne \`a droite de 7.2 degr\'es''. 
La ligne avec  ``{\tt Angle 50}'' indique quelle est la valeur de
r\'ef\'erence des rotations, ici 360/50 degr\'es. Le symbole ``f''
signifie
 ``trace une ligne dans la direction actuelle''. 
Les symboles ``['' et ``]'' vont de pairs. ``['' signifie
``sauvegarder les donn\'ees actuelles (position, orientation, longueur de
ligne, etc.)'' ``]'' signifie ``r\'eactiver les valeurs sauvegard\'ees''. 
Le symbole ``@'' signifie ``multiplie la longueur
actuelle du segment par tel taux''. Par exemple ``@.5'' signifie que
cette longueur est multipli\'e par $0,5$ Le symbole ``!''
signifie ``inverser la signification du + et du -''. 


%Le symbole ``X'' repr\'esente le point le segment initial. La ligne Axiom
%indique de tourner ce segment vers la gauche de  13*7.2=93.6
%degr\'es (sachant que la convention est de toujours commencer avec une orientation
%vers la droite). 

%The replacement string for the weed x says draw a line (f), the stem
%of the weed. 
%Raccourcir alors weed de moiti\'e, tourner \`a gauche de 9*7.2=64.8
%degr\'es, 
%tracer la shrunken weed, and return to the stem ([@.5+++++++++x]). 
%This draws the lowest branch of the weed. Next, turn right slightly (7.2 degrees) and draw
%another portion of the stem (-f). Continuing, shrink the weed by .4, turn right 11*7.2=79.2 degrees, reverse the meaning of right and left, draw the
%shrunken weed, and return to the stem ([@.4- - - - - - - - - -
%-!x]). Finalement, 
%tracer la draw the weed at .6 size (@.6x). Here is how the Weed L-system looks. 



%\newpage
\section{La grammaire}

QUESTION 1. En fonction des indications ci-dessus 
et des exemples (ci-apr\`es), proposez 
une grammaire $G_{L-System}$
(celle que vous utiliserez pour le couple Lex/Yacc) 
qui reconnaisse les L-systems. Vous devez aboutir (au nom pr\`es) \`a quelques choses du genre 
\begin{center}
Lsystem $\rightarrow$  Name \{ Declarations \} \\
Declarations  $\rightarrow$ Declaration {\bf ,} Declarations $|$ Declaration
 retourchariot Declarations $|$ Declaration\\
Declaration   $\rightarrow$  DecAngle $|$ DecAxiom $|$ DecRegle \\
DecAngle $\rightarrow$  Angle Entier\\
DecAxiom  $\rightarrow$  Axiom Expr\\
DecRegle  $\rightarrow$ Lettre {\bf =} MembreDroit\\
MembreDroit  $\rightarrow$  (Expression, Environnement [MembreDroit] $)^*$\\
Expression  $\rightarrow$ Environnement Lettre \\
Environnement$\rightarrow$ (Rotation , Longueur , Inverse$)^*$\\
Rotation $\rightarrow$  $\epsilon | -^+ | +^+$\\
Longueur $\rightarrow$ $\epsilon |$ @ Decimal\\
%Couleur  $\rightarrow$ $<$ Entier $| >$ Entier 
%$\vdots$
\end{center}
(Faites attention \`a ne pas confondre ci-dessus
le vocabulaire terminal de  $G_{L-System}$ et diff\'erents caract\`eres
utilis\'es par Lex-Yacc.) Sous Lex, vous utiliserez entre autres les
lex\`emes (tokens) suivants :
Name, Entier, Decimal, Lettre, Inverse. Vous devez donc avoir des
d\'eclarations du type :\\
Lettre  = [a-z,A-Z], \qquad  Name = Lettre $[a-z,A-Z,0-9]^*$, \qquad
Entier = $[1-9][0-9]^*$,\\
 Decimal =  Entier$.[0-9]^*$, \qquad Inverse = [!], \qquad \qquad \dots


Quand vous pensez avoir trouv\'e la bonne grammaire, montrez-l\`a \`a votre enseignant.

\vskip 3mm
QUESTION 2. Impl\'ementez votre grammaire en Lex-Yacc. 
Vous pouvez tester votre programme sur le fichier {\bf fractint.l},
qui contient nombre de L-systems. V\'erifiez que votre programme ne
d\'eclare une ``syntax error'' uniquement pour des formules qui ne
correpondent pas \`a des L-systems comme d\'efinis ci-dessus. 
Quand vous avez fini, montrez votre programme \`a votre enseignant.

Vous \^etes alors pr\^ets \`a passer au deuxi\`eme temps : le dessin de la fractale que vous venez de reconna\^{\i}tre.

\newpage
\section{Exemples}

{Koch1 \{ ; Adrian Mariano\\
; from The Fractal Geometry of Nature by Mandelbrot\\
  Angle 6\\
  Axiom F- -F- -F\\
  F=F+F- -F+F\\
  \}\\

Koch2 \{ 
  Angle 12 ; blablabla ignor\'e @;\#\&?! \\
  Axiom F- - -F- - -F- - -F\\
  F=-F+++F- - -F+\\
  \}\\

Koch3 \{
  Angle 4\\
  Axiom F-F-F-F\\
  F=F-F+F+FF-F-F+F\\
  \}\\

Koch6 \{ 
   axiom f+f+f+f\\
   f=f-ff+ff+f+f-f-ff+f+f-f-ff-ff+f\\
   angle 4\\
    \}\\

Dragon \{
  Angle 8\\
  Axiom FX\\
  F=\\
  y=+FX- -FY+\\
  x=-FX++FY-\\
  \}\\

Peano1 \{ 
  Angle 4\\
  Axiom F-F-F-F\\
  F=F-F+F+F+F-F-F-F+F\\
  \}\\

Cesaro \{ 
  Angle 34\\
  Axiom FX\\
  F=\\
  X=- - - -F!X!++++++++F!X!- - - -\\
  \}\\

FlowSnake \{ 
  angle=6\\
  axiom FL\\
  L=FL-FR- -FR+FL++FLFL+FR-,\\
  R=+FL-FRFR- -FR-FL++FL+FR,\\
  F=\\
  \}
\vskip 4cm

\vskip -23cm\hskip 9cm
\vbox{
CantorDust \{ 
  Angle 6\\
  Axiom F\\
  F=FGF\\
  G=GGG\\
  \}\\

 Plant09 \{ 
   axiom y\\
   x=X[-FFF][+FFF]FX\\
   y=YFX[+Y][-Y]\\
   angle 14\\
\}\\


Bush \{ 
  Angle 16\\
  Axiom ++++F\\
  F=FF-[-F+F+F]+[+F-F-F]\\
  \}\\


DragonCurve \{ 
  Angle 4\\
  Axiom X\\
  X=X-YF-\\
  Y=+FX+Y\\
  \}\\

KochCurve \{ 
  Angle 6\\
  Axiom F\\
  F=F+F- -F+F\\
  \}\\

%Lars2Color\{ ; By Jonathan Osuch\\
%       ; Based on a suggestion by Lars Vangsgaard\\
%  Angle 8  ; angle increment/decrement is 45\\
%  axiom C1+[F]++[F]++[F]++F\\
%  F=F$<$1[+F][-F]$>$1 ; $>1$ fait passer \`a la couleur suivante\\
%   ; et $<1$ fait passer \`a la couleur pr\'ec\'edente\\
%  \}\\

Man \{ ; From Ivan Daunis daunis@teleline.es\\
   ; looks like man with an odd number of iterations\\
  Angle 8\\
  Axiom F++F++F++F\\
  F=-F-FF+++F+FF-F\\
\}\\

Lace \{ ; From Ivan Daunis daunis@teleline.es\\
  Angle 8\\
  Axiom F++F++F++F\\
  F=F+++F---F+F---F++F--F++F\\
\}\\

}

\end{document}

