automates/IntroGram.tex

   1
   2
   3 \section{Introduction à la compilation}
   4
   5 \subsection{Le problème posé est...}
   6
   7 Donner à un ordinateur un fichier contenant du texte, le lui faire lire et comprendre de manière à lui faire exécuter un certain nombre de tâches associées à ce fichier
   8
   9 $\Rightarrow$ On fait une compilation.\\
  10
  11 \subsection{Les diverses phases d'une compilation}
  12
  13 Détaillons succintement les différentes phases d'une compilation...
  14
  15 \subsubsection{L'analyse lexicale}
  16
  17 On analyse le flux d'entrée de manière à le découper  en unités lexicales, ou \emph{lexèmes}\index{lexèmes}.
  18
  19 \begin{Ex}
  20 Dans \emph{if (temps == beau ) \{} etc., les unités lexicales sont \og if \fg{}, \og ( \fg{}, \og temps \fg{}, \og == \fg{}, \og beau \fg{}, \og ) \fg{}.
  21 \end{Ex}
  22
  23
  24 \subsubsection{L'analyse syntaxique}
  25
  26 Les contraintes à respecter pour que le texte soit compréhensible sont-elles respectées ? En d'autres termes, le flux de lexèmes est-il conforme à la syntaxe du langage utilisé (par comparaison à la grammaire du langage, \emph{c.f.} ci-dessous) ?
  27
  28 \subsubsection{L'analyse sémantique}
  29
  30 Reconnaître la signification d'un texte syntaxiquement correct : essayer de comprendre ce que cela signifie (le sens).
  31
  32 Cela implique notemment la transformation de la source en une forme utilisable, qui fasse apparaître le sens du texte.
  33
  34 \begin{Ex}[d'analyse sémantique]
  35 \emph{toto = titi + tutu;} est une instruction d'affectation à la variable \og toto \fg{} d'une valeur exprimée par une expression algébrique, constituée de la somme des variables \og titi \fg{} et \og tutu \fg{}.
  36 \end{Ex}
  37
  38
  39 \begin{Rem}
  40 Certains compilateurs utilisent des structures arborescentes :
  41
  42 \begin{center}
  43 \begin{picture}(94,47)(0,-47)
  44 \put(0,-47){\framebox(94,47){}}
  45 \node[NLangle=0.0,Nw=19.29,Nh=8.0,Nmr=2.0](n0)(33.52,-7.88){Affectation}
  46
  47 \node[NLangle=0.0,Nw=13.17,Nh=8.0,Nmr=2.0](n1)(12.02,-24.0){toto}
  48
  49 \node[NLangle=0.0,Nw=21.4,Nmr=2.0](n2)(61.62,-24.34){Addition}
  50
  51 \node[NLangle=0.0,Nw=13.17,Nmr=2.0](n5)(40.02,-40.0){titi}
  52
  53 \node[NLangle=0.0,Nw=13.17,Nmr=2.0](n6)(84.02,-40.0){tutu}
  54
  55 \drawedge(n0,n1){}
  56
  57 \drawedge(n0,n2){}
  58
  59 \drawedge(n2,n5){}
  60
  61 \drawedge(n2,n6){}
  62
  63
  64
  65 \end{picture}
  66 \end{center}
  67
  68 \end{Rem}
  69
  70
  71 \subsubsection{Compilation proprement dite}
  72
  73 Utiliser effectivement le résultat de l'analyse sémantique pour obtenir le résultat escompté, ce qui est demandé : production de code machine, traduction d'un texte dans une autre langue, etc.
  74
  75 \begin{Rem}
  76 En général, ces différentes phases sont menées en parallèle.
  77 \end{Rem}
  78
  79
  80 \section{Les grammaires}
  81
  82 \subsection{Définition de la notion de grammaire}
  83
  84 \begin{Def}[Grammaire]
  85 Une \emph{grammaire}\index{grammaire} est un ensemble de règles de syntaxe qui décrivent quels sont les constructions correctes qui sont possibles dans le langage utilisé, à l'aide de l'alphabet utilisé (alphabet ou vocabulaire).
  86 \end{Def}
  87
  88 Il existe de nombreux types de grammaires, et encore bien plus de formalismes exprimés pour représenter cette grammaire.\\
  89
  90 Nous utiliseront pour commencer un seul symbolisme pour remprésenter les grammaires : la  formalisation BNF (Backus-Naur Form).
  91
  92 \subsection{Le formalisme BNF}
  93
  94 Dans la syntaxe BNF, une grammaire est constituée d'un ensemble de règles.\\
  95
  96 Chaque règle est constituée :
  97
  98 \begin{itemize}
  99  \item d'un premier membre,
 100  \item suivi du symbole de réécriture (::=),
 101  \item suivi d'un second membre, qui peut être vide.
 102 \end{itemize}
 103
 104
 105
 106 On utilise (et on distingue) des symboles terminaux et des symboles non-terminaux (ST et SNT).
 107
 108
 109 \subsection{Les symboles terminaux}
 110
 111 \begin{Def}[Symbole terminal]
 112 Un \emph{symbole terminal}\index{symbole!terminal} est un symbole qui peut effectivement intervenir dans le texte analysé.
 113 \end{Def}
 114
 115
 116 \begin{Ex}
 117  Dans \emph{if (temps == beau)}, \emph{if} est un symbole terminal (on trouve le mot dans le programme).
 118 \end{Ex}
 119
 120 \begin{Notation}
 121 Les symboles terminaux sont entourés par : \og \fg{}.
 122 \end{Notation}
 123
 124
 125 \subsection{Les symboles non terminaux}
 126
 127 \begin{Def}[Symbole non terminal]
 128 Un \emph{symbole non terminal}\index{symbole!non terminal} (SNT) est un symbole introduit (par commodité, ou plutôt par nécessité) par le rédacteur de la grammaire pour décrire les parties du fichier d'entrée qui représentent un tout logique et permettant de simplifier l'écriture de la grammaire.
 129 \end{Def}
 130
 131 \begin{Notation}
 132 Les symboles non-terminaux sont entourés par des chevrons: $<$ $>$.
 133 \end{Notation}
 134
 135 Le premier membre d'une règle de grammaire est un SNT (la règle en constitue la définition), le second membre est une famille ordonnée (éventuellement vide) de symboles, terminaux ou non.\\
 136
 137 Ainsi, chaque règle de la grammaire consiste en la définition d'un symbole non-terminal. Cette dernière est terminée quand tous les SNT ont reçu une définition. Une règle s'écrit finalement sous la forme :
 138
 139 \begin{center}
 140 $<$SNT$>$::= suite (éventuellement vide) de ST et SNT
 141 \end{center}
 142
 143
 144 \begin{Ex}
 145
 146 Voici un bout de grammaire (pour la définition d'une fonction) :\\
 147
 148 \begin{tabular}{lll}
 149 $<fct>$ & $::=$ & $<type> <nom> '' ( '' <parametres> '' ) '' <bloc>$\\
 150
 151 $<type>$ & $::=$ & $'' int ''$\\
 152
 153          & $::=$ & $''char''$
 154 \end{tabular}
 155 \end{Ex}
 156
 157 \begin{Def}[Axiome de la grammaire]
 158 Parmi tous les SNT, l'un d'entre eux doit désigner l'ensemble du texte à analyser, on l'appelle \emph{axiome de la grammaire}\index{grammaire!axiome}.
 159 \end{Def}
 160
 161
 162 \begin{Ex}
 163  $<programme~en~C> ::= <entete> <suite~de~fct>$
 164 \end{Ex}
 165
 166 La grammaire est terminée quand tous les SNT ont reçu au moins une définition.
 167
 168
 169
 170 \subsection{Exercices}
 171
 172 \begin{Exo}
 173 Les mots du langage $\cal L$ sont constitués d'un nombre, éventuellement nul, de $a$, suivi d'un $b$, suivi d'au moins un $c$.
 174
 175 Donner une grammaire BNF de ce langage.
 176 \end{Exo}
 177
 178
 179 \begin{Exo}
 180 Les mots du langage $\cal L$ commencent par un caractère $a$, suivi d'un nombre pair (éventuellement aucun) de caractères $b$, puis de deux caractères $c$.
 181
 182 Donner une grammaire BNF de ce langage.
 183 \end{Exo}
 184
 185
 186 \begin{Exo}
 187 Les mots du langage $\cal L$ sont les noms de variables en C : ils commencent obligatoirement parune lettre (majuscule ou minuscule), et se poursuivent par un nombre quelconque de chiffres, lettres ou underscore.
 188
 189 Donner une grammaire BNF de ce langage.
 190 \end{Exo}
 191
 192
 193 \begin{Exo}
 194 Ecrire la grammaire, en syntaxe BNF, des formes propositionnelles. On rappelle que les opérateurs sont, par ordre de priorité croissante :
 195 \begin{itemize}
 196 \item Implication et équivalence (au même niveau, le moins prioritaire). Qu'ils ne sont pas associatifs (on ne peut ni les répéter, ni les faire coexister, au même niveau (c'est-à-dire, sans parenthèse), dans une expression (par exemple, $a \longrightarrow b \longleftarrow c$, ou $a \longrightarrow b \longrightarrow c$ sont incorrects).
 197 \item Disjonction et conjonction (au même niveau, prioritaires sur implication et équivalence). Ils sont associatifs, mais on ne peut pas les mélanger : on peut écrire $a \ou b \ou c$, sans parenthèse, mais pas $a \ou b \et c$.
 198 \item Négation, prioritaire sur tous les autres. Elle peut être répétée. Il s'agit d'un opérateur unaire préfixé.
 199 \end{itemize}
 200
 201 Les noms de variable commencent par un caractère alphabétique, suivi éventuellement d'un nombre quelconque de caractères alphanumériques ou de soulignements. Il n'y a pas de constantes dans les expressions. Les opérateurs sont réalisés au clavier par les trois caractères consécutifs $<->$ pour l'équivalence, les deux caractères consécutifs $->$ pour l'implication, les lettres consécutives $ou$ pour la disjonction, $et$ pour la conjonction, et $non$ pour la négation. L'expression peut évidemment comporter des parenthèses, et ne peut être vide.
 202 \end{Exo}
 203
 204
 205 \begin{Exo}
 206 Le langage considéré est le prototypage des fonctions en C.
 207
 208 Donner une grammaire BNF de ce langage.
 209 \end{Exo}
 210
 211 \begin{Exo}
 212 On accepte les deux types de phrases suivantes :
 213 \begin{itemize}
 214  \item \og Marie est la mère du frère de Sonia.\fg{}
 215 \item \og Qui est le père de l'oncle de la mère du petit fils de Paul ? \fg{}
 216 \end{itemize}
 217 ...et tous leurs dérivés. \'Ecrire la grammaire correspondante.
 218 \end{Exo}
 219
 220
 221 \section{Un exemple complet}
 222
 223 \og Les expressions correctes sont constituées d'un nombre quelconque, mais non nul, de 0, suivi d'un nombre quelconque, mais non nul, de 1. \fg{}
 224
 225 \subsection{Principes généraux}
 226
 227 On conseille de suivre cette démarche :
 228
 229 \begin{enumerate}
 230 \item Commencer par écrire la grammaire du langage (des expressions correctes).
 231 \item Ecrire l'analyseur syntaxique pur.
 232 \item Passer à l'analyseur syntaxique avec messages d'erreur.
 233 \item Puis à l'analyseur syntaxique avec interprétation sémantique.
 234 \end{enumerate}
 235
 236
 237 \begin{Exo}
 238 Suivez ce cheminement :
 239 \begin{enumerate}
 240 \item Ecrivez cette grammaire.
 241 \item Programmez, en C, l'analyseur syntaxique pur.
 242 \item Ecrire le programme principal associé (le main).
 243 \item Le modifier en analyseur syntaxique avec messages d'erreur, et adaptez le programme principal en conséquence.
 244 \item Améliorez le programme pour qu'il devienne un analyseur syntaxique avec interprétation sémantique : ici, comptez le nombre de 0 et de 1, en cas de réussite.
 245 \end{enumerate}
 246 \end{Exo}
 247
 248
 249 \subsection{La grammaire du langage}
 250
 251 \begin{tabular}{lll}
 252 $<$ expression $>$ & ::= &$<$ groupe0 $>~<$ groupe1 $>$\\
 253
 254 $<$ groupe0 $>$ & ::= & “0" $<$ suite0 $>$\\
 255
 256 $<$ suite0 $>$ & ::= & $<$ groupe0 $>$\\
 257
 258 & ::= &\\
 259
 260 $<$ groupe1 $>$ & ::= & “1" $<$ suite1 $>$\\
 261
 262 $<$ suite1 $>$ & ::= & $<$ groupe1 $>$\\
 263
 264 & ::= &\\
 265 \end{tabular}
 266
 267 Il faut :
 268
 269 \begin{itemize}
 270 \item Subdiviser au maximum les expressions en sous-expressions cohérentes, en n'hésitant pas à multiplier les niveaux.
 271
 272 \item Retarder au maximum les alternatives (en multipliant les niveaux) pour ne les faire intervenir que lorsqu'on ne peut plus faire autrement.
 273 \end{itemize}
 274
 275
 276
 277 \subsection{Analyseur syntaxique pur}
 278
 279
 280
 281 Voici le code de l'analyseur pur : il répond par \og bon \fg{} ou \og mauvais \fg{}.
 282
 283
 284 \begin{lstlisting}
 285 #include <stdio.h>
 286
 287 char s[512];
 288 char **ss;
 289
 290 int expression(){
 291     if (groupe0()==1)
 292         return groupe1();
 293     return 0;
 294 }
 295
 296 int groupe0(){
 297     if (*ss == '0'){
 298         s++;
 299         return suite0();
 300     }
 301     return 0;
 302 }
 303
 304 int suite0(){
 305     if (groupe0() == 0)
 306         return 1;
 307     return 1;
 308 }
 309 \end{lstlisting}
 310
 311 ... même chose pour groupe1() et suite1().
 312
 313
 314 Une fonction prévue pour analyser une sous-expression ne connaît pas ce qui précède et ne s'occupe pas de ce qui suit.
 315
 316
 317 Passons au programme principal :
 318
 319
 320 \begin{lstlisting}
 321 int main(){
 322   printf("Une expression a analyser ? \n");
 323   scanf("%s",s);
 324   ss = s;
 325   if (expression()==1)
 326       if (*ss == '\0')
 327            printf("Bon \n");
 328       else
 329            printf("Mauvais\n");
 330   else
 331       printf("Mauvais\n");
 332 }
 333 \end{lstlisting}
 334
 335 \begin{Rem}
 336 Toujours commencer par l'analyseur syntaxique pur.
 337 \end{Rem}
 338
 339
 340 \subsection{Analyseur syntaxique avec messages d'erreur}
 341
 342 \begin{lstlisting}
 343 int groupe0(){
 344     if (*ss == '0'){
 345         ss++;
 346         return suite0();
 347     }
 348     printf("L'expression doit commencer par 0\n")
 349     return 0;
 350 }
 351
 352 int suite0(){
 353     if (*ss == '0'){
 354         ss++;
 355         return suite0();
 356     }
 357     return 1;
 358 }
 359 \end{lstlisting}
 360
 361
 362 Le programme principal devient alors :
 363
 364 \begin{lstlisting}
 365 int main(){
 366   printf("Une expression a analyser ? \n");
 367   scanf("%s",s);
 368   ss = s;
 369   if (expression()==1)
 370       if (*ss == '\0')
 371            printf("Bon \n");
 372       else if (*ss == '0')
 373                printf("Pas de 0 apres le(s) un(s).\n");
 374            else
 375                printf("Caractere interdit : %c\n",*ss);
 376 }
 377 \end{lstlisting}
 378
 379
 380 \subsection{Analyseur syntaxique avec interprétation sémantique}
 381
 382 \begin{lstlisting}
 383 int groupe0(){
 384     if (*ss == '0'){
 385         ss++;
 386         return 1+suite0();
 387     }
 388     printf("L'expression doit commencer par 0\n")
 389     return 0;
 390 }
 391
 392 int suite0(){
 393     if (*ss == '0'){
 394         ss++;
 395         return 1+suite0();
 396     }
 397     return 0;
 398 }
 399 \end{lstlisting}
 400
 401 Pareil pour groupe1 et suite1. Le programme principal devient alors :
 402
 403 \begin{lstlisting}
 404 int main(){
 405   printf("Une expression a analyser ? \n");
 406   scanf("%s",s);
 407   ss = s;
 408   Expression = expression()
 409
 410   if (*ss == '\0')
 411        printf("Bon \n");
 412   else if (*ss == '0')
 413            printf("Nombre de 0 : %d, nomre de 1 : %d",expression.zero, expression.un);
 414        else
 415            printf("Caractere interdit : %c\n",*ss);
 416 }
 417 \end{lstlisting}
 418
 419
 420 où la structure \emph{Expression} et la fonction \emph{expression()} sont ainsi définis :
 421
 422 \begin{lstlisting}
 423 struct Expression{
 424     int zero;
 425     int un;
 426 }
 427
 428 struct Expression expression(){
 429     struct Expression a;
 430     a.zero = groupe0();
 431     if (a.zero !=0)
 432         a.un = groupe1();
 433     return a;
 434 }
 435 \end{lstlisting}
 436
 437
 438 Cet exemple, et d'autres, seront (re)vus en TP.
 439
 440 %\end{Proof}
 441
 442
 443
 444 % \section{Exemples approfondis}
 445 %
 446 % \og Les expressions correctes sont constituées d'un nombre quelconque, mais non nul, de 0, suivi d'un nombre quelconque, mais non nul, de 1. \fg{}
 447 %
 448 % \subsection{Premier exemple}
 449 %
 450 % \subsubsection{Principes généraux}
 451 %
 452 % On conseille de suivre cette démarche :
 453 %
 454 % \begin{enumerate}
 455 % \item Commencer par écrire la grammaire du langage (des expressions correctes).
 456 % \item Ecrire l'analyseur syntaxique pur.
 457 % \item Passer à l'analyseur syntaxique avec messages d'erreur.
 458 % \item Puis à l'analyseur syntaxique avec interprétation sémantique.
 459 % \end{enumerate}
 460 %
 461 %
 462 % \begin{Exo}
 463 % Suivez ce cheminement :
 464 % \begin{enumerate}
 465 % \item Ecrivez cette grammaire.
 466 % \item Programmez, en C, l'analyseur syntaxique pur.
 467 % \item Ecrire le programme principal associé (le main).
 468 % \item Le modifier en analyseur syntaxique avec messages d'erreur, et adaptez le programme principal en conséquence.
 469 % \item Améliorez le programme pour qu'il devienne un analyseur syntaxique avec interprétation sémantique : ici, comptez le nombre de 0 et de 1, en cas de réussite.
 470 % \end{enumerate}
 471 % \end{Exo}
 472 %
 473 %
 474 % \subsubsection{La grammaire du langage}
 475 %
 476 % \begin{tabular}{lll}
 477 % $<$ expression $>$ & ::= &$<$ groupe0 $>~<$ groupe1 $>$\\
 478 %
 479 % $<$ groupe0 $>$ & ::= & “0" $<$ suite0 $>$\\
 480 %
 481 % $<$ suite0 $>$ & ::= & $<$ groupe0 $>$\\
 482 %
 483 % & ::= &\\
 484 %
 485 % $<$ groupe1 $>$ & ::= & “1" $<$ suite1 $>$\\
 486 %
 487 % $<$ suite1 $>$ & ::= & $<$ groupe1 $>$\\
 488 %
 489 % & ::= &\\
 490 % \end{tabular}
 491 %
 492 % Il faut :
 493 %
 494 % \begin{itemize}
 495 % \item Subdiviser au maximum les expressions en sous-expressions cohérentes, en n'hésitant pas à multiplier les niveaux.
 496 %
 497 % \item Retarder au maximum les alternatives (en multipliant les niveaux) pour ne les faire intervenir que lorsqu'on ne peut plus faire autrement.
 498 % \end{itemize}
 499 %
 500 %
 501 %
 502 % \subsubsection{Analyseur syntaxique pur}
 503 %
 504 %
 505 %
 506 % Voici le code de l'analyseur pur : il répond par \og bon \fg{} ou \og mauvais \fg{}.
 507 %
 508 %
 509 % \begin{lstlisting}
 510 % #include <stdio.h>
 511 %
 512 % char s[512];
 513 % char **ss;
 514 %
 515 % int expression(){
 516 %     if (groupe0()==1)
 517 %       return groupe1();
 518 %     return 0;
 519 % }
 520 %
 521 % int groupe0(){
 522 %     if (*ss == '0'){
 523 %       s++;
 524 %       return suite0();
 525 %     }
 526 %     return 0;
 527 % }
 528 %
 529 % int suite0(){
 530 %     if (groupe0() == 0)
 531 %       return 1;
 532 %     return 1;
 533 % }
 534 % \end{lstlisting}
 535 %
 536 % ... même chose pour groupe1() et suite1().
 537 %
 538 %
 539 % Une fonction prévue pour analyser une sous-expression ne connaît pas ce qui précède et ne s'occupe pas de ce qui suit.
 540 %
 541 %
 542 % Passons au programme principal :
 543 %
 544 %
 545 % \begin{lstlisting}
 546 % int main(){
 547 %   printf("Une expression a analyser ? \n");
 548 %   scanf("%s",s);
 549 %   ss = s;
 550 %   if (expression()==1)
 551 %       if (*ss == '\0')
 552 %            printf("Bon \n");
 553 %       else
 554 %            printf("Mauvais\n");
 555 %   else
 556 %       printf("Mauvais\n");
 557 % }
 558 % \end{lstlisting}
 559 %
 560 % \begin{Rem}
 561 % Toujours commencer par l'analyseur syntaxique pur.
 562 % \end{Rem}
 563 %
 564 %
 565 % \subsubsection{Analyseur syntaxique avec messages d'erreur}
 566 %
 567 % \begin{lstlisting}
 568 % int groupe0(){
 569 %     if (*ss == '0'){
 570 %         ss++;
 571 %         return suite0();
 572 %     }
 573 %     printf("L'expression doit commencer par 0\n")
 574 %     return 0;
 575 % }
 576 %
 577 % int suite0(){
 578 %     if (*ss == '0'){
 579 %         ss++;
 580 %         return suite0();
 581 %     }
 582 %     return 1;
 583 % }
 584 % \end{lstlisting}
 585 %
 586 %
 587 % Le programme principal devient alors :
 588 %
 589 % \begin{lstlisting}
 590 % int main(){
 591 %   printf("Une expression a analyser ? \n");
 592 %   scanf("%s",s);
 593 %   ss = s;
 594 %   if (expression()==1)
 595 %       if (*ss == '\0')
 596 %            printf("Bon \n");
 597 %       else if (*ss == '0')
 598 %                printf("Pas de 0 apres le(s) un(s).\n");
 599 %            else
 600 %                printf("Caractere interdit : %c\n",*ss);
 601 % }
 602 % \end{lstlisting}
 603 %
 604 %
 605 % \subsubsection{Analyseur syntaxique avec interprétation sémantique}
 606 %
 607 % \begin{lstlisting}
 608 % int groupe0(){
 609 %     if (*ss == '0'){
 610 %         ss++;
 611 %         return 1+suite0();
 612 %     }
 613 %     printf("L'expression doit commencer par 0\n")
 614 %     return 0;
 615 % }
 616 %
 617 % int suite0(){
 618 %     if (*ss == '0'){
 619 %         ss++;
 620 %         return 1+suite0();
 621 %     }
 622 %     return 0;
 623 % }
 624 % \end{lstlisting}
 625 %
 626 % Pareil pour groupe1 et suite1. Le programme principal devient alors :
 627 %
 628 % \begin{lstlisting}
 629 % int main(){
 630 %   printf("Une expression a analyser ? \n");
 631 %   scanf("%s",s);
 632 %   ss = s;
 633 %   Expression = expression()
 634 %
 635 %   if (*ss == '\0')
 636 %        printf("Bon \n");
 637 %   else if (*ss == '0')
 638 %            printf("Nombre de 0 : %d, nomre de 1 : %d",expression.zero, expression.un);
 639 %        else
 640 %            printf("Caractere interdit : %c\n",*ss);
 641 % }
 642 % \end{lstlisting}
 643 %
 644 %
 645 % où la structure \emph{Expression} et la fonction \emph{expression()} sont ainsi définis :
 646 %
 647 % \begin{lstlisting}
 648 % struct Expression{
 649 %     int zero;
 650 %     int un;
 651 % }
 652 %
 653 % struct Expression expression(){
 654 %     struct Expression a;
 655 %     a.zero = groupe0();
 656 %     if (a.zero !=0)
 657 %         a.un = groupe1();
 658 %     return a;
 659 % }
 660 % \end{lstlisting}
 661 %
 662 % \subsection{Deuxième Exemple}
 663 %
 664 %
 665 % \og Les expressions correctes sont constituées d'un nombre quelconque mais non nul de 'a', suivi d'un 'b', suivi d'un nombre quelconque éventuellement nul de 'c'.\fg{}
 666 %
 667 %
 668 % \begin{Exo}
 669 % Faire le même travail que précédemment.
 670 % \end{Exo}
 671 %
 672 %
 673 % \subsubsection{La grammaire}
 674 %
 675 %
 676 % \begin{tabular}{lll}
 677 % $<$ expression $>$ & ::= &$<$ groupe a $>~“b"~<$ liste c $>$\\
 678 %
 679 % $<$ groupe a $>$ & ::= & “a" $<$ suite a $>$\\
 680 %
 681 % $<$ suite a $>$ & ::= & $<$ groupe a $>$\\
 682 %
 683 % & ::= &\\
 684 %
 685 % $<$ liste c $>$ & ::= & “c" $<$ liste c $>$\\
 686 %
 687 % & ::= &\\
 688 % \end{tabular}
 689 %
 690 % \subsubsection{Analyseur syntaxique pur}
 691 %
 692 % Cet analyseur syntaxique pur répond par \og Bon \fg{} ou \og Mauvais \fg .
 693 %
 694 %
 695 %
 696 % \begin{lstlisting}
 697 % #include <stdio.h>
 698 %
 699 % char s[512];
 700 % char **ss;
 701 %
 702 % int expression(){
 703 %     if (groupea()==1)
 704 %         if (*ss == 'b'){
 705 %             ss++;
 706 %             return listec();
 707 %         }
 708 %     return 0;
 709 % }
 710 %
 711 % int groupea(){
 712 %     if (*ss == 'a'){
 713 %       s++;
 714 %       return suitea();
 715 %     }
 716 %     return 0;
 717 % }
 718 %
 719 % int suitea(){
 720 %     if (groupea() == 0)
 721 %       return 1;
 722 %     return 1;
 723 % }
 724 %
 725 % int listec(){
 726 %     if (*ss == '\0')
 727 %         return 1;
 728 %     else
 729 %         if (*ss == 'c'){
 730 %             ss++;
 731 %             listec();
 732 %         } else
 733 %             return 0;
 734 % }
 735 %
 736 %
 737 % int main(){
 738 %   printf("Une expression a analyser ? \n");
 739 %   scanf("%s",s);
 740 %   ss = s;
 741 %   if (expression()==1)
 742 %       if (*ss == '\0')
 743 %            printf("Bon \n");
 744 %       else
 745 %            printf("Mauvais\n");
 746 %   else
 747 %       printf("Mauvais\n");
 748 % }
 749 %
 750 % \end{lstlisting}
 751 %
 752 %
 753 % \subsubsection{Analyseur syntaxique avec message d'erreur}
 754 %
 755 %
 756 % \begin{lstlisting}
 757 % int groupea(){
 758 %     if (*ss == 'a'){
 759 %       s++;
 760 %       return suitea();
 761 %     } else {
 762 %         printf("L'expression doit commencer par a \n");
 763 %         return 0;
 764 %     }
 765 % }
 766 %
 767 % int suitea(){
 768 %     if (*ss == 'a'){
 769 %         ss++;
 770 %       return suitea();
 771 %     }
 772 %     return 1;
 773 % }
 774 %
 775 %
 776 % int main(){
 777 %   printf("Une expression a analyser ? \n");
 778 %   scanf("%s",s);
 779 %   ss = s;
 780 %   if (expression()==1)
 781 %       if (*ss == '\0')
 782 %            printf("Bon \n");
 783 %       else
 784 %            printf("Il n'y a que des c apres le b\n");
 785 % }
 786 %
 787 % int expression(){
 788 %     if (groupea()==1)
 789 %         if (*ss=='b'){
 790 %             ss++;
 791 %             return listec();
 792 %         } else {
 793 %             printf("Apres le(s) a il doit y avoir un b");
 794 %         }
 795 %     return 0;
 796 % }
 797 % \end{lstlisting}
 798 %
 799 %
 800 %
 801 % \subsubsection{Analyseur syntaxique avec interprétation sémantique}
 802 %
 803 %
 804 %
 805 % \begin{lstlisting}
 806 % int groupea(){
 807 %     if (*ss == 'a'){
 808 %       s++;
 809 %       return 1+suitea();
 810 %     } else {
 811 %         printf("L'expression doit commencer par a \n");
 812 %         return 0;
 813 %     }
 814 % }
 815 %
 816 % int suitea(){
 817 %     if (*ss == 'a'){
 818 %         ss++;
 819 %       return 1+suitea();
 820 %     }
 821 %     return 0;
 822 % }
 823 %
 824 %
 825 % struct Expression expression(){
 826 %     struct Expression un;
 827 %     un.a = groupea();
 828 %     if (un.a != 0 && *ss == 'b'){
 829 %         ss++;
 830 %         un.c = listec();
 831 %         un.b = 1;
 832 %     } else
 833 %         printf("Apres le(s) a il doit y avoir un b");
 834 %     return un;
 835 % }
 836 %
 837 % struct Expression{
 838 %     int a;
 839 %     int b;
 840 %     int c;
 841 % }
 842 %
 843 %
 844 % int listec(){
 845 %     if (*ss == '\0')
 846 %         return 0;
 847 %     else
 848 %         if (*ss == 'c'){
 849 %             ss++;
 850 %             return 1+listec();
 851 %         } else
 852 %             return 0;
 853 % }
 854 %
 855 % int main(){
 856 %   struct Expression un;
 857 %   printf("Une expression a analyser ? \n");
 858 %   scanf("%s",s);
 859 %   ss = s;
 860 %   un = expression();
 861 %   if (*ss == '\0')
 862 %       printf("Nombre de a : %d, nombre de b : 1, nombre de c : %d \n",un.a, un.c);
 863 %   else
 864 %       if (un.b ==1)
 865 %            printf("Il n'y a que des c apres le b\n");
 866 % }
 867 %
 868 % int expression(){
 869 %     if (groupea()==1)
 870 %         if (*ss=='b'){
 871 %             ss++;
 872 %             return listec();
 873 %         } else {
 874 %             printf("Apres le(s) a il doit y avoir un b");
 875 %         }
 876 %     return 0;
 877 % }
 878 % \end{lstlisting}
 879 %
 880 %
 881 % \subsection{Troisième exemple : les expressions algébriques}
 882 %
 883 %
 884 % \subsubsection{Présentation du problème}
 885 %
 886 % Les expressions algébriques à analyser sont constituées :
 887 % \begin{itemize}
 888 % \item des opérateurs + et *,
 889 % \item des noms de variable : un caractère alphabétique.
 890 % \end{itemize}
 891 %
 892 %
 893 % \begin{Ex}
 894 %  a+b+c*(d+e*(f+g))*((h+i)*j+k*l)+(m+n+o)*(p+q)*r
 895 % \end{Ex}
 896 %
 897 % On souhaite ici faire le même travail que précédemment, tout en sachant que la grammmaire devra tenir compte des deux opérateurs \emph{hiérarchisés}.
 898 %
 899 %
 900 % \subsubsection{Règles générales d'écriture d'une grammaire hiérarchisée}
 901 %
 902 % Les règles sont les suivantes :
 903 %
 904 % \medskip
 905 %
 906 % \begin{enumerate}
 907 % \item L'analyse commence par l'opérateur le moins prioritaire ; cela revient à découper l'expression suivant cet opérateur.
 908 %
 909 % En dehors des parenthèses :
 910 %
 911 % \begin{tabular}{lll}
 912 % $<$ somme $>$ & ::= &$<$ terme $>~<$ finSomme $>$\\
 913 %
 914 % $<$ finSomme $>$ & ::= & “+" $<$ somme $>$\\
 915 %
 916 % & ::= &\\
 917 % \end{tabular}
 918 %
 919 % \medskip
 920 %
 921 % \item Elle continue par le deuxième opérateur, dans l'ordre croissant des priorités.
 922 %
 923 % Les sous-expressions analysées sont dépourvues des opérateurs précédents (en-dehors des parenthèses).
 924 %
 925 % \begin{tabular}{lll}
 926 % $<$ terme $>$ & ::= &$<$ facteur $>~<$ finProduit $>$\\
 927 %
 928 % $<$ finProduit $>$ & ::= & “*" $<$ terme $>$\\
 929 %
 930 % & ::= &\\
 931 % \end{tabular}
 932 %
 933 % \medskip
 934 %
 935 % \item On ne fait intervenir les parenthèses qu'après avoir épuisé tous les opérateurs.
 936 %
 937 % Les sous-expressions analysées ne comptortent alors plus aucun opérateur : plus que des lettres et des parenthèses.
 938 %
 939 %
 940 % \begin{tabular}{lll}
 941 % $<$ facteur $>$ & ::= &$<$ variable $>$\\
 942 %
 943 % & ::= & “(" $<$ somme $>$ “)"\\
 944 %
 945 % $<$ variable $>$ & ::= & “a" ... “z" (notation non BNF)\\
 946 % \end{tabular}
 947 % \end{enumerate}
 948 %
 949 %
 950 % \begin{Exo}
 951 %  \'Ecrire l'analyseur syntaxique pur.
 952 % \end{Exo}
 953 %
 954 %
 955 % \subsubsection{Analyseur syntaxique pur}
 956 %
 957 % On pensera à inclure la bibliothèque \emph{ctype}, permettant la reconnaissance de caractères.
 958 %
 959 % \begin{lstlisting}
 960 % #include <stdio.h>
 961 % #include <ctype.h>
 962 %
 963 % char s[512];
 964 % char *ss;
 965 %
 966 % int somme(){
 967 %     if (terme() == 1)
 968 %         return finSomme();
 969 %     return 0;
 970 % }
 971 %
 972 % int finSomme(){
 973 %     if (*ss == '+'){
 974 %         ss++;
 975 %         return somme();
 976 %     }
 977 %     return 1;
 978 % }
 979 %
 980 % int terme(){
 981 %     if (facteur() == 1;
 982 %         return finProduit();
 983 %     return 0;
 984 % }
 985 %
 986 % int finProduit(){
 987 %     if (*ss == '*'){
 988 %         ss++;
 989 %         return terme();
 990 %     }
 991 %     return 1;
 992 % }
 993 %
 994 % int facteur(){
 995 %     if (variable ==1)
 996 %         return 1;
 997 %     if (*ss == '('){
 998 %         ss++;
 999 %         if (somme() == 1)
1000 %             if (*ss ==')'){
1001 %                 ss++;
1002 %                 return 1;
1003 %             }
1004 %         return 0;
1005 %     }
1006 % }
1007 %
1008 % int variable(){
1009 %     if (isalpha(*ss)){
1010 %         ss++;
1011 %         return 1;
1012 %     }
1013 %     return 0;
1014 % }
1015 %
1016 % int main(){
1017 %     printf("\n Une expression a analyser ? ");
1018 %     scanf("%s",s);
1019 %     ss=s;
1020 %     if (somme() == 1)
1021 %         if (*ss == '\0')
1022 %             printf("Bon\n");
1023 %         else
1024 %             printf("Mauvais\n");
1025 %     else
1026 %         printf("Mauvais\n")
1027 % \end{lstlisting}
1028 %
1029 %
1030 % \begin{Exo}
1031 % Adaptez la grammaire pour qu'elle gère la soustraction et la division.
1032 % \end{Exo}
1033 %
1034 %
1035 %
1036 % \subsubsection{Grammaire enrichie}
1037 %
1038 % \begin{tabular}{lll}
1039 % $<$ somme $>$ & ::= &$<$ terme $>~<$ finSomme $>$\\
1040 %
1041 % $<$ finSomme $>$ & ::= &  $<$ operateurAdditif $>~<$ somme $>$\\
1042 %
1043 % & ::= &\\
1044 %
1045 % $<$ operateurAdditif $>$ & ::= &  “+"\\
1046 %
1047 % & ::= & “-"\\
1048 %
1049 % $<$ terme $>$ & ::= &$<$ facteur $>~<$ finProduit $>$\\
1050 %
1051 % $<$ finProduit $>$ & ::= &  $<$ operateurMultiplicatif $>~<$terme $>$\\
1052 %
1053 % & ::= &\\
1054 %
1055 % $<$ operateurMultiplicatif $>$ & ::= &  “*"\\
1056 %
1057 % & ::= & “/"\\
1058 %
1059 % $<$ facteur $>$ & ::= &$<$ variable $>$\\
1060 %
1061 % & ::= & “(" $<$ somme $>$ “)"\\
1062 %
1063 % $<$ variable $>$ & ::= & “a" ... “z"\\
1064 % \end{tabular}
1065 %
1066 %
1067 % \subsubsection{Version avec messages d'erreur}
1068 %
1069 % \begin{lstlisting}
1070 % #include <stdio.h>
1071 % #include <ctype.h>
1072 %
1073 % char s[512];
1074 % char *ss;
1075 %
1076 % int somme(){
1077 %     if (terme() == 1)
1078 %         return finSomme();
1079 %     return 0;
1080 % }
1081 %
1082 % int finSomme(){
1083 %     if (*ss == '+' || *ss == '-'){
1084 %         ss++;
1085 %         return somme();
1086 %     }
1087 %     return 1;
1088 % }
1089 %
1090 % int terme(){
1091 %     if (facteur() == 1;
1092 %         return finProduit();
1093 %     return 0;
1094 % }
1095 %
1096 % int finProduit(){
1097 %     if (*ss == '*' || *ss == '/'){
1098 %         ss++;
1099 %         return terme();
1100 %     }
1101 %     return 1;
1102 % }
1103 %
1104 % int facteur(){
1105 %     if (*ss == '('){
1106 %         if (*ss == '-' || *ss == '+') ss++;
1107 %         ss++;
1108 %         if (somme() == 1)
1109 %             if (*ss ==')'){
1110 %                 ss++;
1111 %                 return 1;
1112 %             }else{
1113 %                 printf("Il manque une parenthese fermante.\n");
1114 %                 return 0;
1115 %             }
1116 %     }else{
1117 %         if (*ss == '-' || *ss == '+') ss++;
1118 %         if (isalpha(*ss)){
1119 %             ss++;
1120 %             return 1;
1121 %         }else{
1122 %             printf("\n\n ATTENTION :\n");
1123 %             if (*ss == '+' || *ss == '-' || *ss == '/' || *ss == '*')
1124 %                 printf("Deux operateurs ne peuvent pas se suivre");
1125 %             else
1126 %                 if (*ss == '\0')
1127 %                     printf("L'expression ne peut pas se terminer par un operateur");
1128 %                 else
1129 %                     printf("Ce caractere ne fait pas partie de la grammaire : \" %c \" \n.", *ss);
1130 %             return 0;
1131 %         }
1132 %     }
1133 % }
1134 %
1135 % int variable(){
1136 %     if (isalpha(*ss)){
1137 %         ss++;
1138 %         return 1;
1139 %     }
1140 %     return 0;
1141 % }
1142 %
1143 % int main(){
1144 %     printf("\n Une expression a analyser ? ");
1145 %     scanf("%s",s);
1146 %     ss=s;
1147 %     if (*ss == '*' || *ss '/'){
1148 %         printf("Ne peut pas commencer par un operateur binaire")
1149 %         return c;
1150 %     }
1151 %     if (somme() == 1)
1152 %         if (*ss == '\0')
1153 %             printf("Bon\n");
1154 %         else{
1155 %             printf("Attention\n");
1156 %             if (isalpha(*ss))
1157 %                 printf("Deux variables ne peuvent se suivre.\n");
1158 %             else if (*ss == '(' || *ss == ')')
1159 %                 printf("Caractere mal place \" %c "\", *ss)
1160 %             else
1161 %                 printf("Ce caractere ne fait pas parti de la grammaire \" %c \" \n",*ss);
1162 %         }
1163 %     }
1164 %     printf("\n");
1165 %     return 1;
1166 % }
1167 % \end{lstlisting}
1168 %
1169 % \subsubsection{Version avec interprétation sémantique}
1170 %
1171 %
1172 % On utilise les arbres : a+b+c devient
1173 % \begin{lstlisting}
1174 %                                 +
1175 %                                / \
1176 %                               +   c
1177 %                              / \
1178 %                             a   b
1179 % \end{lstlisting}
1180 % et -a+b :
1181 % \begin{lstlisting}
1182 %                                 +
1183 %                                / \
1184 %                               -   b
1185 %                               |
1186 %                               a
1187 % \end{lstlisting}
1188 %
1189 % On est en effet obligé d'associer à gauche pour la soustraction (sinon on change l'expression).
1190 %
1191 % \begin{Exo}
1192 %  Programmez cette structure d'arbre, puis la version sémantique.
1193 % \end{Exo}
1194 %
1195 %
1196 %
1197 % \begin{lstlisting}
1198 % typedef enum {FEUILLE, UNAIRE, BINAIRE} Tnoeud;
1199 %
1200 % typedef struct arbre{
1201 %     Tnoeur selecteur;
1202 %     union{
1203 %         char var;
1204 %         struct{
1205 %             char operateur;
1206 %             struct arbre* fs;
1207 %         } un;
1208 %         struct{
1209 %             char operateur;
1210 %             struct arbre* fd;
1211 %             struct arbre* fg;
1212 %         } bin;
1213 %     } type;
1214 % } arbre;
1215 %
1216 % #include <stdio.h>
1217 % #include <ctype.h>
1218 % #include <stdlib.h>
1219 % #define amalloc (arbre*)malloc (sizeof(arbre))
1220 % #define ANULL (arbre*) NULL
1221 %
1222 % arbre* feuille(char var){
1223 %     arbre* a = ANULL;
1224 %     if ((a = amalloc) != ANULL{
1225 %         a->selecteur = FEUILLE;
1226 %         a->t.var = var;
1227 %     }
1228 %     return a;
1229 % }
1230 %
1231 % arbre* unaire(char op, arbre* fs){
1232 %     arbre* a = ANULL;
1233 %     if (fs != ANULL)
1234 %         if ((a=amalloc) != ANULL){
1235 %             a->sel.UNAIRE;
1236 %             a->t.un.op=op;
1237 %             a->t.un.fs=fs;
1238 %          }
1239 %     return a;
1240 % }
1241 %
1242 % arbre* binaire(char op, arbre* fg, arbre* fd){
1243 %     arbre* a = ANULL;
1244 %     if (fg != ANULL && fd != ANULL)
1245 %         if ((a=amalloc) != ANULL){
1246 %             a->sel.BINAIRE;
1247 %             a->t.un.op=op;
1248 %             a->t.un.fg=fg;
1249 %             a->t.un.fd=fd;
1250 %          }
1251 %     return a;
1252 % }
1253 %
1254 % void printa(arbre* a){
1255 %     switch (a->sel){
1256 %         case FEUILLE : printf("%c",a->t.var);
1257 %                        break;
1258 %         case UNAIRE  : printf("%c(",a->t.un.op);
1259 %                        printa(a->t.un.fs);
1260 %                        printf(")");
1261 %                        break;
1262 %         case BINAIRE : printf("%c(",a->t.bin.op);
1263 %                        printa(a->t.bin.fg);
1264 %                        printf(",");
1265 %                        printa(a->t.bin.fd);
1266 %                        printf(")");
1267 %                        break;
1268 %     }
1269 % }
1270 %
1271 % void print_arbre(arbre* a){
1272 %     if (a != NULL)
1273 %         printa (a);
1274 %     else
1275 %         printf("Arbre vide\n");
1276 %     printf("\n");
1277 % }
1278 %
1279 % #define cmalloc(n) (char*)malloc((n)*sizeof(char))
1280 % #define crealloc(ptr,n) (char*)realloc(ptr,(n)*sizeof(char))
1281 % #define CNULL (char*)NULL
1282 % #define BLOC 16
1283 %
1284 % char* lire_chaine(){
1285 %     char *s, *ss, *ssmax;
1286 %     int taille, c;
1287 %     if ((s = cmalloc(BLOC))==CNULL){
1288 %         fprintf(stderr,"Memoire saturee\n");
1289 %         exit(43);
1290 %     }
1291 %     ss=s;
1292 %     taille = BLOC;
1293 %     smax = s + taille;
1294 %     while ((c=getchar()) != '\n'){
1295 %         *ss++ = (char)c;
1296 %         if (ss == smax){
1297 %             if ((s=crealloc(c,taille+BLOC))==CNULL){
1298 %                 fprintf(stderr,"Memoire saturee\n")
1299 %                 exit(44);
1300 %             }
1301 %             ss=s+taille;
1302 %             taille += BLOC;
1303 %             smax = s+taille;
1304 %         }
1305 %     }
1306 %     *ss++ = '\0';
1307 %     return crealloc(s,ss-s);
1308 % }
1309 % \end{lstlisting}
1310 %
1311 %
1312 %
1313 % \subsubsection{Le cas du moins unaire}
1314 %
1315 % On souhaite rajouter le - unaire ; son analyse intervient au niveau du facteur :
1316 %
1317 \gsaut
1318 \centerline{\x{Fin du Chapitre}}
1319