m1ilc:compil

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

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)

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

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

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.

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

Dans l'analyse par descente récursive,

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

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

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