Conception du compilateur - Analyseur ascendant

L'analyse ascendante commence à partir des nœuds feuilles d'un arbre et fonctionne vers le haut jusqu'à ce qu'elle atteigne le nœud racine. Ici, on part d'une phrase puis on applique les règles de production de manière inverse pour atteindre le symbole de départ. L'image ci-dessous illustre les analyseurs ascendants disponibles.

Analyse Shift-Réduire

L'analyse de réduction de décalage utilise deux étapes uniques pour l'analyse ascendante. Ces étapes sont appelées étapes de décalage et réduction de pas.

  • Shift step: L'étape de décalage fait référence à l'avancement du pointeur d'entrée vers le symbole d'entrée suivant, appelé symbole décalé. Ce symbole est poussé sur la pile. Le symbole décalé est traité comme un nœud unique de l'arborescence d'analyse.

  • Reduce step: Lorsque l'analyseur trouve une règle de grammaire complète (RHS) et la remplace par (LHS), on parle de réduction de pas. Cela se produit lorsque le haut de la pile contient une poignée. Pour réduire, une fonction POP est effectuée sur la pile qui saute de la poignée et la remplace par le symbole non terminal LHS.

Analyseur LR

L'analyseur LR est un analyseur ascendant non récursif, à réduction de décalage. Il utilise une large classe de grammaire sans contexte, ce qui en fait la technique d'analyse syntaxique la plus efficace. Les analyseurs LR sont également connus sous le nom d'analyseurs LR (k), où L représente le balayage de gauche à droite du flux d'entrée; R représente la construction de la dérivation la plus à droite en sens inverse, et k désigne le nombre de symboles d'anticipation pour prendre des décisions.

Il existe trois algorithmes largement utilisés pour construire un analyseur LR:

  • SLR (1) - Analyseur LR simple:
    • Fonctionne sur la plus petite classe de grammaire
    • Peu d'états, donc très petit tableau
    • Construction simple et rapide
  • LR (1) - Analyseur LR:
    • Fonctionne sur un ensemble complet de grammaire LR (1)
    • Génère une grande table et un grand nombre d'états
    • Construction lente
  • LALR (1) - Analyseur LR Look-Ahead:
    • Fonctionne sur la taille intermédiaire de la grammaire
    • Le nombre d'états est le même que dans SLR (1)

Algorithme d'analyse LR

Nous décrivons ici un algorithme squelette d'un analyseur LR:

token = next_token()

repeat forever
   s = top of stack
   
   if action[s, token] = “shift si” then
      PUSH token
      PUSH si 
      token = next_token()
      
   else if action[s, token] = “reduce A::= β“ then 
      POP 2 * |β| symbols
      s = top of stack
      PUSH A
      PUSH goto[s,A]
      
   else if action[s, token] = “accept” then
      return
      
   else
      error()

LL contre LR

LL G / D
Fait une dérivation la plus à gauche. Fait une dérivation la plus à droite en sens inverse.
Commence par le non-terminal racine de la pile. Se termine par le non-terminal racine de la pile.
Se termine lorsque la pile est vide. Commence avec une pile vide.
Utilise la pile pour désigner ce qui reste à attendre. Utilise la pile pour désigner ce qui est déjà vu.
Construit l'arborescence d'analyse de haut en bas. Construit l'arborescence d'analyse de bas en haut.
Saute en continu un non-terminal hors de la pile et pousse le côté droit correspondant. Tente de reconnaître un côté droit de la pile, le fait apparaître et pousse le non-terminal correspondant.
Développe les non-terminaux. Réduit les non-terminaux.
Lit les terminaux lorsqu'il en sort un de la pile. Lit les terminaux pendant qu'il les pousse sur la pile.
Parcours de pré-commande de l'arbre d'analyse. Parcours post-ordre de l'arbre d'analyse.