, 
, l'axiome est 
, les
règles sont données par:
Pour un mot 
de 
, il est immédiat de déterminer 
tel que
En effet, si est de longueur 
, ou bien 
et le
résultat de l'analyse syntaxique se limite à 
, ou bien
n'appartient pas au langage engendré par la grammaire.
Si est de longueur supérieure à , il suffit de connaître les
deux premières lettres de pour pouvoir retrouver . Si ces
deux premières lettres sont 
, c'est la règle 
qui a été appliquée, si ces deux lettres sont 
alors c'est
la règle 
. Tout autre début de règle conduit à un
message d'erreur.
Ce qui vient d'être dit pour retrouver en utilisant les deux
premières lettres de se généralise sans difficulté à la
détermination du 
mot 
de
la dérivation à partir de 
. On décompose d'abord et
en:
et on procède en fonction des deux premières lettres de 
.
commence par 
, alors 
commence par , alors 
commence par , alors 
signifie que n'est pas une expression
préfixée correcte, il y a une erreur de syntaxe.
Cet algorithme reprend les grandes lignes de la descente récursive
avec une différence importante: la boucle while qui consistait
à appliquer chacune des règles de la grammaire est remplacée par un
examen de certaines lettres du mot à analyser, examen qui permet de
conclure sans retour arrière. On passe ainsi d'une complexité
exponentielle à un algorithme en 
. En effet, une manière
efficace de procéder consiste à utiliser une pile pour gérer le mot
qui vient de la décomposition 
. La
consultation de la valeur en tête de la pile et sa comparaison avec
la lettre courante de permet de décider de la règle à
appliquer. L'application d'une règle consiste alors à supprimer la
tête de la pile (membre gauche de la règle) et à y ajouter le mot
formant le membre droit en commençant par la dernière lettre.
Nous avons appliqué cette technique pour construire l'arbre de
syntaxe abstraite associé à une expression préfixée. Dans ce qui
suit, le mot à analyser est une variable globale de même que la
variable entière pos qui indique la position à laquelle on se
trouve dans ce mot.
function ArbSyntPref: Arbre;
var a, b, c: Arbre;
x: char;
begin
if f[pos] = 'a' then
begin
a := NouvelArbre('a', nil, nil);
pos := pos + 1;
end
else if (f[pos] = '(') and (f[pos+1] in {'+', '*'}) then
begin
x := f[pos + 1];
pos := pos + 2;
b := ArbSyntPref;
c := ArbSyntPref;
a := NouvelArbre(x, b, c);
if f[pos] = ')' then pos := pos + 1
else Erreur(pos);
end
else
Erreur(pos);
ArbSyntPref := a
end;
L'algorithme d'analyse syntaxique donné ici peut s'étendre
à toute grammaire dans laquelle pour chaque couple de règles 
et 
, les mots qui dérivent de 
et 
n'ont pas des
facteurs gauches égaux de longueur arbitraire. Ou de manière plus
précise, il existe un entier 
tel que tout facteur gauche de
longueur appartenant à d'un mot qui dérive de est
différent de celui de tout mot qui dérive de . On dit alors que
la grammaire est 
et on peut alors démontrer:
En fait, cet algorithme est surtout utile pour 
. Nous donnons ici
ses grandes lignes sous forme d'un programme Pascal qui utilise une
fonction Predicteur
calculée au préalable. Pour un
élément de 
et un mot 
de longueur , cette fonction
indique le numéro de l'unique règle telle que se
dérive en un mot commençant par ou qui indique Omega si
aucune telle règle n'existe. Dans l'algorithme qui suit, on utilise
une pile comme variable globale. Elle contient la partie du mot
qui doit engendrer ce qui reste à lire dans . Nous en donnons ici
une forme abrégée.
function Analyse(f: Mot; pos: integer): boolean;
var i: integer;
begin
pos := 1;
while Pvaleur(p) = f[pos] do
begin
Psupprimer(p);
pos := pos + 1;
end;
if Pvide(p) and f[pos] = '$' then
Analyse := true
else
begin
y := Pvaleur(p);
if not Auxiliaire(y) then
Analyse := false
else
begin
i := Predicteur (y, pos, pos+k-1);
if i <> Omega then
begin
writeln (y, '->', regle[y,i]);
Pinserer(regle[y,i], p);
Analyse := Analyse (f, pos);
end
else
Analyse := false;
end;