La méthode de descente récursive

Les langages réguliers sont soumis à la restriction selon laquelle aucune structure imbriquée ne peut être exprimée. Les structures imbriquées ne peuvent être exprimées qu’à l’aide de la récursivité. Une machine à états finis ne peut donc pas suffire à la reconnaissance des phrases d’un langage sans contexte non régulier. Nous allons néanmoins essayer d’utiliser la technique apprise au chapitre précédent pour dériver un programme d’analyseur syntaxique de l’exemple suivant :

\[\begin{gather*} S = A. \\ A = \mathsf{«a»} A \mathsf{«c»} | \mathsf{«b»}. \end{gather*}\]

Là où la méthode échoue – et elle doit échouer – se trouve l’indice d’une généralisation possible. Il est en effet surprenant de constater à quel point l’effort de programmation supplémentaire nécessaire s’avère faible.

La construction \(A = \mathsf{«a»} A \mathsf{«c»} | \mathsf{«b»}.\)

la construction conduit, après une simplification appropriée et l’utilisation d’une série de if else:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
if sym == "a":
    next_symbol()
    if sym == A:
        next_symbol()
    else:
        error()
    if sym == "c":
        next_symbol()
    else:
        error()
elif sym == "b":
    next_symbol()
else:
    error()

A la ligne 3, nous avons abusivement traité le symbole non terminal A de la même manière qu’un symbole terminal. Ceci n’est évidemment pas acceptable. Le but de la troisième ligne du programme est d’analyser une construction de la forme A (plutôt que de lire un symbole A). Or, c’est précisément l’objectif de notre programme. Par conséquent, la solution simple à notre problème est de donner un nom au programme ci-dessus, c’est-à-dire de lui donner la forme d’une fonction, et de remplacer la troisième ligne du programme par un appel à cette fonction.

Tout comme dans la syntaxe, la construction A est récursive, la fonction A est aussi récursive :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
def A():
    if sym == "a":
        next_symbol()
        A()
        if sym == "c":
            next_symbol()
        else:
            error()
    elif sym == "b":
        next_symbol()
    else:
        error()

L’extension nécessaire de l’ensemble des règles de traduction est extrêmement simple. La seule règle supplémentaire est la suivante :

Règle

Un algorithme d’analyse est dérivé pour chaque symbole non terminal, et il est formulé sous la forme d’une fonction portant le nom du symbole. L’occurrence du symbole dans la syntaxe est traduite en un appel de la fonction correspondante.

Note

Cette règle est valable que la fonction soit récursive ou non.

Il est important de vérifier que les conditions d’un algorithme déterministe soient remplies. Cela implique, entre autres, que dans une expression de la forme term_0 | term_1, les termes ne doivent pas avoir de symboles de départ communs.

Cette condition exclut la récursivité à gauche. En effet, si nous considérons la production suivante :

\[\begin{gather*} A = A \mathsf{«a»} | \mathsf{«b»}. \end{gather*}\]

nous reconnaissons que la condition n’est pas respectée, parce que "b" est un symbole de départ de A, et par conséquent first(A "a") et first("b") ne sont pas disjoints : “b” est l’élément commun.

La conséquence direct est que la récursion à gauche peut et doit être remplacée par la répétition. Dans l’exemple ci-dessus, A = A "a" | "b" est remplacé par A = "b" {"a"}.

Une autre façon d’envisager le passage de la machine d’états à sa généralisation est de considérer cette dernière comme un ensemble de machines d’états qui s’appellent les unes les autres et qui s’appellent elles-mêmes. En principe, la seule nouvelle condition est que l’état de la machine appelante soit repris après l’arrêt de la machine appelée. L’état doit donc être préservé. Comme les machines d’états sont imbriquées, une pile (stack) est la forme de stockage la plus appropriée. Notre extension de la machine à états s’appelle donc un automate pushdown. D’un point de vue théorique, le fait que la pile (le stockage pushdown) doit être arbitrairement profonde est important. C’est la différence essentielle entre l’automate d’états finis et l’automate infini pushdown.

Le principe général suggéré ici est le suivant :

Principe général

l’objectif le plus élevé est la reconnaissance de la construction propositionnelle qui commence par le symbole de début de la syntaxe sous-jacente.

Si, au cours de la poursuite de cet objectif, c’est-à-dire pendant l’analyse de la production, un symbole non terminal est rencontré, la reconnaissance d’une construction correspondant à ce symbole est considérée comme un objectif subordonné à poursuivre en premier, tandis que l’objectif supérieur est temporairement suspendu. Cette stratégie est donc également appelée goal-oriented parsing.

Si nous examinons l’arbre structurel de la phrase analysée, nous constatons que les objectifs (symboles) les plus élevés dans l’arbre sont traités en premier, les objectifs inférieurs (symboles) ensuite. Cette méthode est donc appelée analyse syntaxique descendante (top- down parsing)1. En outre, la mise en œuvre présentée de cette stratégie basée sur des fonctions récursives est connue sous le nom d’analyse syntaxique par descente récursive (recursive descent parsing)

Enfin, nous rappelons que les décisions concernant les chemins à prendre sont toujours prises sur la base du seul symbole d’entrée suivant. L’analyseur syntaxique anticipe d’un symbole. Une anticipation de plusieurs symboles compliquerait considérablement le processus de décision et le ralentirait. C’est pourquoi nous limiterons notre attention aux langues qui peuvent être analysées avec un seul symbole d’anticipation.

L’analyseur syntaxique par descente récursive avec l’anticipation d’un seul symbole est appelé LL(1) parser (pour Left-to-right, Leftmost parser with 1 symbol lookahead).

Le premier travail pratique est consacré à la construction d’un analyseur syntaxique par descente récursive pour l’EBNF.

  1. D.E. Knuth. Top-down syntax analysis. Acta Informatica 1 (1971), 79-110.
    A.V. Aho, J.D. Ullman. Principles of Compiler Design. Reading MA: Addison-Wesley, 1977. ↩