==== Analyse Descendante ====

=== Exemple (simple) ===

  R1: S -> cAd
  R2: A -> ab | a

Analysons 'cad' et construisons l'arbre de syntaxe abstraite.

^ étape ^  arbre  ^  symboles  ^
^ 0  |  S  |  __c__ad  |
^ 1  |    S \\  /  %%|  \%%  \\ __c__   A   d  | __c__ad  | même symbole, voyons si la suite correspond prenant une première hypothèse pour 'A' |
^ 2  |      S \\  /  %%|  \%%  \\ __c__   A   d\\      %% /   \ %% \\         a    b   | __c__ad  | première hypothèse pour ce qu'a produit 'A'  |
^ 3  |      S \\  /  %%|  \%%  \\ c   A   d\\      %% /   \ %% \\        __ a __   b   | c__a__d  | on avance le pointeur, et ça correspond donc on avance encore un cran |
^ 4  |      S \\  /  %%|  \%%  \\ c   A   d\\      %% /   \ %% \\         a   __b__   | ca__d__  | échec : le choix de la règle pour 'A' n'était pas bon. retour en arrière pour essayeer autre chose. |
^ 3.2  |      S \\  /  %%|  \%%  \\ c   A   d\\      %%    | %% \\        __ a __   | c__a__d  | jusqu'à là c'est bon |
^ 4.2  |      S \\  /  %%|  \%%  \\ c   A   __d__\\      %%    | %% \\         a    | ca__d__  | c'est réussi, on accepte |


=== Algorithme Naïf ===

A chaque étape, on examine le noeud courant dans l'arbre (on parcourt les feuilles de l'arbre de gauche à droite).
  * si ce noeud est un non-terminal A alors on choisit une règle avec A en partie gauche. 
    * Si cette règle est "A produit vide" on passe au noeud suivant.
    * Sinon on développe le noeud de l'arbre en utilisant cette règle.
  * Si le noeud est un terminal "a", on le compare à l'élément courant dans la chaîne.
    * si il y a égalité, on passe au noeud suivant et on avance dans la chaîne
    * sinon on revient à la dernière règles utilisée (retour arrière)

=== Problèmes Rencontrés ===

== a) Les retour arrières sont couteux ==

Ils sont dus à la présence de règles ayant le même début (entrée) telle

  A -> αB1 | αB2 | ... | αBn

On ne peut pas choisir sans risque d'erreur.

Solution : éliminer ces règles en appliquant une factorisation à gauche :

  A -> αA'
  A' -> B1 | B2 | ... | Bn

== b) Bouclages infinis possibles ==

Ils sont dus à la présence de règles récursives à gauche, de la forme :

  * récursivité directe : ''A -> Aα''
  * récursivité indirecte : ''A -> Bα'' et ''B -> Aβ''

Solution : remplacer ces règles par des règles non-récursives à gauche.

> Théorème: tout langage algébrique peut être engendré par une grammaire algébrique non-récursive à gauche.

== c) Opérations utilisées sont couteuses ==

Recherche de règles, parcours et modification de l'arbre sont des opérations couteuses. Deux solutions :

  * analyse par descente récursive
  * analyse itérative : on utilise une pile (pour supprimer la récursivité).

Dans l'analyse par descente récursive, 
  * une procédure est associée à chaque non-terminal
  * la suite d'appels de procédure définit l'arbre de syntaxe
  * les procédures sont mutuellement récursives

  Procedure S
    begin
        match(a)
        A;
        match(d)
    end

  Procedure A
    begin
        match(A)
        if curtoken==b then match(b)
    end

  Procedure match(t:token)
    begin
        if curtoken==t then curtoken=nextoken
        else error
    end

  begin
      curtoken=firstoken
      call S
  end

== c) Deuxième Solution  ==

Analyse itérative: on utilise une pile, pour supprimer la récursivité.

=== Transformation des règles ===

Pour simplifier l'écriture des procédures, on peut utiliser la notation BNF (Backus-Naur Form).


==== Navigation ====

[[compil_2|<= cours précedent]] -\- [[compil_ll_2| cours suivant =>]] Analyseur LL(1)