Conception du compilateur - Types d'analyse

Les analyseurs de syntaxe suivent des règles de production définies au moyen d'une grammaire sans contexte. La façon dont les règles de production sont implémentées (dérivation) divise l'analyse en deux types: l'analyse descendante et l'analyse ascendante.

Analyse descendante

Lorsque l'analyseur commence à construire l'arborescence d'analyse à partir du symbole de début, puis essaie de transformer le symbole de début en entrée, il s'agit d'une analyse descendante.

  • Recursive descent parsing: C'est une forme courante d'analyse descendante. Il est appelé récursif car il utilise des procédures récursives pour traiter l'entrée. L'analyse des descentes récursives souffre d'un retour en arrière.

  • Backtracking: Cela signifie que si une dérivation d'une production échoue, l'analyseur de syntaxe redémarre le processus en utilisant différentes règles de la même production. Cette technique peut traiter la chaîne d'entrée plusieurs fois pour déterminer la bonne production.

Analyse ascendante

Comme son nom l'indique, l'analyse ascendante commence par les symboles d'entrée et tente de construire l'arborescence d'analyse jusqu'au symbole de départ.

Example:

Chaîne d'entrée: a + b * c

Règles de production:

S → E
E → E + T
E → E * T
E → T
T → id

Commençons l'analyse ascendante

a + b * c

Lisez l'entrée et vérifiez si une production correspond à l'entrée:

a + b * c
T + b * c
E + b * c
E + T * c
E * c
E * T
E
S