\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}