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 cad
1 S
/ | \
c A d
cad même symbole, voyons si la suite correspond prenant une première hypothèse pour 'A'
2 S
/ | \
c A d
/ \
a b
cad première hypothèse pour ce qu'a produit 'A'
3 S
/ | \
c A d
/ \
a b
cad on avance le pointeur, et ça correspond donc on avance encore un cran
4 S
/ | \
c A d
/ \
a b
cad é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
cad jusqu'à là c'est bon
4.2 S
/ | \
c A d
|
a
cad 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


 
m1ilc/compil_ll.txt · Dernière modification: 2010/01/04 18:10 par suitable