Deux principales techniques sont utilisées pour effectuer l'analyse
syntaxique. Il faut en effet, étant donnés une grammaire G et un mot 
, de construire la suite des dérivations de G
ayant conduit de l'axiome au mot ,
La première technique consiste à démarrer de l'axiome et
à tenter de retrouver 
, puis 
jusqu'à obtenir 
,
c'est l'analyse descendante. La seconde, l'analyse
ascendante procède en sens inverse, il s'agit de commencer par
deviner 
à partir de puis de remonter à 
et
successivement jusqu'à l'axiome 
. Nous décrivons ici sur des
exemples les techniques d'analyse descendante, l'analyse ascendante
sera traitée dans un paragraphe suivant.
La première méthode que nous considérons s'applique à des cas très
particuliers. Dans ces cas, l'algorithme d'analyse syntaxique devient une
traduction fidèle de l'écriture de la grammaire. On utilise pour cela
autant de procédures qu'il y a d'éléments dans 
chacune
d'entre elles étant destinée à reconnaître un mot dérivant de
l'élément correspondant de . Examinons comment cela se passe
sur l'exemple de la grammaire des expressions infixes, nous
choisissons ici la deuxième forme de cette grammaire:
Que l'on traduit par les trois procédures récursives
croisées suivantes en Pascal. Celles ci construisent l'arbre de
syntaxe abstraite en utilisant la fonction NouvelArbre donnée
dans le chapitre 4.
function Terme; forward;
function Facteur; forward;
function Expression: Arbre;
var a, b: Arbre;
begin
a := Terme;
if f[i] = '+' then
begin
i := i + 1;
b := Expression;
Expression := NouvelArbre('+', a, b);
end
else
Expression := a;
end;
function Terme: Arbre;
var a, b: Arbre;
begin
a := Facteur;
if f[i] = '*' then
begin
i := i + 1;
b := Terme;
Terme := NouvelArbre('*', a, b);
end
else
Terme := a;
end;
function Facteur: Arbre;
begin
if f[i]= '(' then
begin
i := i + 1;
Facteur := Expression;
if f[i] = ')' then
i := i + 1
else
Erreur(i)
end
else
begin
if f[i] = 'a' then
begin
Facteur := NouvelArbre('a', nil, nil);
i := i + 1;
end
else
Erreur(i);
end;
Dans ce programme, le mot à analyser est une variable
globale. Il en est de même pour la variable entière i qui
désigne la position à partir de laquelle on effectue l'analyse
courante. Lorsqu'on active la procédure Expression, on
recherche une expression commençant en 
. A la fin de
l'exécution de cette procédure, si aucune erreur n'est détectée, la
nouvelle valeur (appelons la 
) de 
est telle que
est une expression. Il en est de même pour
les procédures Terme et Facteur. Chacune de ces
procédures tente de retrouver à l'intérieur du mot à analyser une
partie engendrée par 
, 
ou 
. Ainsi, la procédure
Expression commence par rechercher un Terme. Un nouvel
appel à Expression est effectué si ce terme est suivi par le
symbole +. Son action se termine sinon. La procédure
Terme est construite sur le même modèle et la procédure
Facteur recherche un symbole a ou une expression
entourée de parenthèses.
Cette technique fonctionne bien ici car les membres droits des règles
de grammaire ont une forme particulière. Pour chaque élément 
de
, l'ensemble des membres droits 
de règles,
dont le membre gauche est , satisfait les conditions suivantes: les
premières lettres des 
qui sont dans 
, sont toutes distinctes
et les qui commencent par une lettre de sont tous facteurs
gauches les uns des autres. Plusieurs grammaires de langages de
programmation satisfont ces conditions; ainsi N. Wirth concepteur du
langage Pascal a construit ce langage en s'arrangeant pour que sa
grammaire vérifie une propriété de cette forme.
Une technique plus générale d'analyse consiste à
procéder comme suit. On construit itérativement des mots 
dont on
espère qu'ils vont se dériver en . Au départ on a 
. A chaque étape de l'itération, on cherche la première lettre
de qui n'est pas égale à son homologue dans . On a ainsi
Si 
, alors ne peut dériver de , et il faut
faire repartir l'analyse du mot qui a donné . Sinon 
et
on recherche toutes les règles dont 
est le membre gauche.
On applique à successivement chacune de ces règles, on obtient
ainsi des mots 
. On poursuit l'analyse, chacun
des mots 
jouant le rôle de . L'analyse est
terminée lorsque 
. La technique est celle de l'exploration
arborescente qui sera développée au Chapitre 8. On peut la
représenter par la procédure suivante donnée sous forme informelle.
function Analyse(f, u: Mot): boolean;
begin
if f = u then Analyse := true
else
begin
-
if - then Analyse := false
else
begin
b := false;
-
b := Analyse(f, gwv);
Analyse := b;
end;
end
end
Cet algorithme se traduit en Pascal simplement. On utilise
les procédures et fonctions SupprimerPremLettre(u),
Auxiliaire(y), Concatener(u,v), dont les noms ont été choisis pour
rappeler la fonction réalisée, SupprimerPremLettre(u)
supprime la première lettre du mot u, Auxiliaire(y) est
vrai si , Concatener(u,v) donne pour résultat le
mot uv. On suppose que les mots et se terminent
respectivement par $ et #, il s'agit là de sentinelles
permettant de détecter la fin de ces mots.
On suppose aussi que l'ensemble des règles est contenu dans
un tableau regle[S,i] qui donne la -ème règle dont le
membre gauche est . Le nombre de règles dont le membre gauche est
est fourni par nbregle[S].
function AnalyseDescendante(u: Mot; f: Mot): boolean;
var
i, pos: integer;
y: char;
v: Mot;
b: boolean;
begin
b := false;
pos := 1;
while f[pos] = u[pos] do
pos := pos + 1;
b := (f[pos] = '$') and (u[pos] = '#');
if not b then
begin
y := u[pos];
if Auxiliaire(y) then
begin
i := 1;
while (not b) and (i <= nbregle[y]) do
begin
v := Remplacer(u, pos, regle[y,i]);
b := Analyse(v , f);
if b then
writeln ('regle : ', y, '->', regle[y,i]) ;
i := i + 1;
end;
end;
end;
Analyse := b;
end;