David Madore's WebLog: Exemple d'analyse d'une grammaire hors-contexte facile

[Index of all entries / Index de toutes les entréesLatest entries / Dernières entréesXML (RSS 1.0) • Recent comments / Commentaires récents]

↓Entry #2187 [older| permalink|newer] / ↓Entrée #2187 [précédente| permalien|suivante] ↓

(mardi)

Exemple d'analyse d'une grammaire hors-contexte facile

On trouve sur le Web plein d'explications sur les deux principales méthodes pour analyser les grammaires hors-contexte que sont les analyseurs (descendants) LL et les analyseurs (ascendants) LR : par exemple, ce cours (je pense aux chapitres 8 à 15) n'est pas mauvais pour ce qui est du côté pratique ; l'article de Knuth définissant les analyseurs LR est aussi intéressant ; et ce résumé des différentes inclusions au niveau des grammaires et au niveau des langages est infiniment précieux pour s'y retrouver un peu. Néanmoins, il y a une chose que je n'ai trouvée nulle part, c'est un exemple simple d'une même grammaire simple avec la présentation explicite d'un analyseur LL et d'un analyseur LR pour celle-ci, afin de pouvoir vérifier à la main comment ils travaillent et comprendre par l'exemple comment ils fabriquent un arbre d'analyse.

J'ai donc pris l'exemple de la grammaire simple suivante (d'axiome S) :

  • Sε | aTS
  • Tε | bUT
  • Uε | cU | dSe

(où ε représente le mot vide) ; les mots du langage qu'elle définit sont, par définition, tous ceux qui s'obtiennent en partant de S et en effectuant une suite quelconque des substitutions indiquées (n'importe quel S peut être remplacé soit par le mot vide soit par aTS, n'importe quel T soit par le mot vide soit par bUT, et U soit par le mot vide soit par cU soit par dSe) jusqu'à tomber sur un mot qui n'a que des symboles (« terminaux ») a, b, c, d et e : par exemple, abcde (par SaTSabUTSabcUTSabcdSeTSabcdeTSabcdeSabcde, dite « dérivation gauche » parce qu'on remplace toujours le nonterminal le plus à gauche, ou SaTSaTabUTabUabcUabcdSeabcde, dite « dérivation droite »). Cette grammaire est inambiguë, c'est-à-dire qu'il existe un unique arbre d'analyse pour chaque mot du langage qu'elle définit (ou, si on préfère, une unique dérivation gauche, ou encore, une unique dérivation droite).

Si on a du mal à visualiser cette grammaire intuitivement, on pourra se dire que d et e sont des sortes de parenthèses, et que par ailleurs si on omet la règle UdSe, alors la grammaire produit exactement le langage décrit par l'expression régulière (a(bc*)*)*.

J'ai calculé (à la main…) les tables définissant l'analyseur LL(1) et l'analyseur SLR(1) pour cette grammaire, ce qui fournit deux façons d'analyser un mot (la première construit l'arbre de dérivation à partir du haut et produit la dérivation gauche du mot, la seconde construit l'arbre de dérivation à partir du bas et produit la dérivation droite).

Bien sûr, l'intérêt de l'histoire n'est pas seulement de vérifier que les tables ci-dessous marchent, mais aussi s'exercer à les construire, en appliquant pas à pas les algorithmes de construction d'un analyseur LL(1) et SLR(1), qui sur cette grammaire simple ne sont pas trop compliqués.

L'analyseur LL(1) est donné par la table suivante :

abcde$
SSaTSSεSε
TTεTbUTTεTε
UUεUεUcUUdSeUεUε

L'algorithme est le suivant : on part d'une pile qui peut contenir n'importe lequel des neuf symboles S, T, U, a, b, c, d, e et $ ; initialement, elle contient les deux symboles S (sommet de la pile) et $ (base de la pile). Le mot sera lu de gauche à droite. À chaque étape :

  • on retire (« pop ») le symbole situé au sommet au sommet de la pile, appelons-le X ;
  • selon la valeur de X :
    • si X est un terminal (a, b, c, d ou e), on vérifie qu'il coïncide avec le prochain symbole du mot (si ce n'est pas le cas, on soulève une erreur de syntaxe : le mot n'appartient pas au langage décrit par la grammaire), et on consomme le symbole en question (=on avance d'un cran) (opération match) ;
    • si X est le symbole spécial $, on vérifie qu'on est arrivé à la fin du mot (si ce n'est pas le cas, on soulève une erreur de syntaxe ; mais ça ne peut pas se produire pour l'exemple que j'ai choisi), et on termine l'exécution ;
    • si X est un nonterminal (S, T ou U), on regarde sans le consommer (lookahead) le prochain symbole r du mot à lire (ou r=$ si on est en fin de chaîne), on consulte l'entrée (X,r) de la table ci-dessus (si la case est vide on soulève une erreur de syntaxe), on enregistre éventuellement la règle en question dans l'arbre d'analyse (ou la dérivation) qu'on est en train de construire, et on empile le membre de droite de cette règle sur la pile (le début de ce membre de droite constituant le nouveau sommet de la pile) (opération predict).

Intuitivement, la pile de l'analyseur LL sert à enregistrer ce que l'analyseur attend, une prévision de ce qui reste à reconnaître pour finir le mot.

Voici par exemple ce que donne l'exécution de cet analyseur sur le mot abcde : initialement la pile contient (S,$) ;

  1. lookahead de r=a, la table (pour X=S) contient la règle SaTS, on enregistre cette règle (comme sommet de l'arbre de dérivation) et on empile son membre de droite ; la pile contient donc maintenant (a,T,S,$) ;
  2. match de a avec le début de la chaîne, qui est donc consommé (il reste : bcde) ; la pile contient donc maintenant (T,S,$) ;
  3. lookahead de r=b, la table (pour X=T) contient la règle TbUT, on enregistre cette règle (comme descendant de T dans l'arbre de dérivation) et on empile son membre de droite ; la pile contient donc maintenant (b,U,T,S,$) ;
  4. match de b avec le début de la chaîne, qui est donc consommé (il reste : cde) ; la pile contient donc maintenant (U,T,S,$) ;
  5. lookahead de r=c, la table (pour X=U) contient la règle UcU, on enregistre cette règle (comme descendant de U dans l'arbre de dérivation) et on empile son membre de droite ; la pile contient donc maintenant (c,U,T,S,$) ;
  6. match de c avec le début de la chaîne, qui est donc consommé (il reste : de) ; la pile contient donc maintenant (U,T,S,$) ;
  7. lookahead de r=d, la table (pour X=U) contient la règle UdUe, on enregistre cette règle (comme descendant du U non détaillé dans l'arbre de dérivation) et on empile son membre de droite ; la pile contient donc maintenant (d,S,e,T,S,$) ;
  8. match de d avec le début de la chaîne, qui est donc consommé (il reste : e) ; la pile contient donc maintenant (S,e,T,S,$) ;
  9. lookahead de r=e, la table (pour X=S) contient la règle Sε, on enregistre cette règle (comme descendant du S non détaillé dans l'arbre de dérivation) et on empile son membre de droite (i.e., rien du tout) ; la pile contient donc maintenant (e,T,S,$) ;
  10. match de e avec le début de la chaîne, qui est donc consommé (il ne reste rien du tout) ; la pile contient donc maintenant (T,S,$) ;
  11. lookahead de r=$ (fin de chaîne), la table (pour X=T) contient la règle Tε, on enregistre cette règle (comme descendant du T non détaillé dans l'arbre de dérivation) et on empile son membre de droite (i.e., rien du tout) ; la pile contient donc maintenant (S,$) ;
  12. lookahead de r=$ (fin de chaîne), la table (pour X=S) contient la règle Sε, on enregistre cette règle (comme descendant du T non détaillé dans l'arbre de dérivation) et on empile son membre de droite (i.e., rien du tout) ; la pile contient donc maintenant ($) ;
  13. match de $ avec le fait d'être en fin de chaîne : le mot est accepté par l'analyseur, qui termine son exécution.

Ceci correspond, en fait, à la méthode d'analyse qu'on a assez intuitivement pour ce langage : on utilise le premier symbole (le lookahead) pour savoir quelle règle s'applique, et la pile contient la prévision de ce qui reste à reconnaître (par exemple, la première étape de l'exécution ci-dessus signifie je vois un a, je dois donc maintenant rencontrer aST). Si on regarde, au fur et à mesure de cette exécution, les symboles consommés auxquels on concatène le contenu de la pile (lue de du sommet vers la base), on obtient précisément la dérivation gauche du mot.

L'analyseur SLR(1) est donné par les tables suivantes :

ActionGoto
abcde$STU
0s2r[Sε]r[Sε]01
1acc.1
2r[Tε]s4r[Tε]r[Tε]23
3s2r[Sε]r[Sε]35
4r[Uε]r[Uε]s7s8r[Uε]r[Uε]46
5r[SaTS]r[SaTS]5
6r[Tε]s4r[Tε]r[Tε]69
7r[Uε]r[Uε]s7s8r[Uε]r[Uε]710
8s2r[Sε]r[Sε]811
9r[TbUT]r[TbUT]r[TbUT]9
10r[UcU]r[UcU]r[UcU]r[UcU]10
11s1211
12r[UdSe]r[UdSe]r[UdSe]r[UdSe]12

[Signification des états (cf. plus loin) : 0 = initial ({init→•S}) ; 1 = {init→S•} ; 2 = {SaTS} ; 3 = {SaTS} ; 4 = {TbUT} ; 5 = {SaTS•} ; 6 = {TbUT} ; 7 = {UcU} ; 8 = {UdSe} ; 9 = {TbUT•} ; 10 = {UcU•} ; 11 = {UdSe} ; 12 = {UdSe•}.]

L'algorithme est le suivant : on part d'une pile qui peut contenir des nombres de 0 à 12 ; initialement, elle contient le seul nombre 0. Le mot sera lu de gauche à droite. À chaque étape :

  • on appelle n le nombre au sommet de la pile (appelé état courant de l'analyseur) et r le prochain symbole (terminal) à lire (ou le symbole spécial $ si on est en fin de mot) ;
  • on consulte la ligne n, colonne r de la table de gauche (table d'actions) :
    • si la case contient une indication sm (où m est un nombre), on consomme le symbole r du mot, et on empile l'état m (action shift) ;
    • si la case contient une indication r[Xγ] (où X est un nonterminal et γ le membre de droite d'une règle pour ce nonterminal) :
      • on dépile autant de nombres qu'il y a de symboles (terminaux comme nonterminaux) dans γ, et on appelle p le nouveau sommet de la pile (nouvel état de l'analyseur),
      • on enregistre éventuellement la règle Xγ (comme père des arbres de dérivation déjà fabriqués pour les symboles de γ),
      • on consulte la table de droite (table de sauts), ligne p, colonne X, et on empile l'état qu'elle indique
      (action reduce ; le symbole r n'est pas consommé) ;
    • si la case contient l'indication acc., on accepte le mot ;
    • si la case est vide, on soulève une erreur de syntaxe.

Intuitivement, la pile de l'analyseur LR sert à enregistrer ce que l'analyseur a analysé, ce qui a été reconnu.

Voici par exemple ce que donne l'exécution de cet analyseur sur le mot abcde : initialement la pile contient (0) ;

  1. le symbole suivant est r=a, la table d'actions pour m=0 contient l'action shift 2, on consomme donc le symbole (il reste : bcde) et on empile l'état 2 ; la pile contient donc maintenant (2,0) ;
  2. le symbole suivant est r=b, la table d'actions pour m=2 contient l'action shift 4, on consomme donc le symbole (il reste : cde) et on empile l'état 4 ; la pile contient donc maintenant (4,2,0) ;
  3. le symbole suivant est r=c, la table d'actions pour m=4 contient l'action shift 7, on consomme donc le symbole (il reste : de) et on empile l'état 7 ; la pile contient donc maintenant (7,4,2,0) ;
  4. le symbole suivant est r=d, la table d'actions pour m=7 contient l'action shift 8, on consomme donc le symbole (il reste : e) et on empile l'état 8 ; la pile contient donc maintenant (8,7,4,2,0) ;
  5. le symbole suivant est r=e, la table d'actions pour m=8 contient l'action reduce Sε, on enregistre donc cette règle (sans consommer de symbole), on ne dépile rien, le nouvel état reste l'état 8, on consulte maintenant la table des sauts pour la colonne X=S, qui demande d'empiler l'état 11 ; la pile contient donc maintenant (11,8,7,4,2,0) ;
  6. le symbole suivant est r=e, la table d'actions pour m=11 contient l'action shift 12, on consomme donc le symbole (il ne reste rien) et on empile l'état 12 ; la pile contient donc maintenant (12,11,8,7,4,2,0) ;
  7. il n'y a plus de symbole (r=$), la table d'actions pour m=12 contient l'action reduce UdSe, on enregistre donc cette règle comme ancêtre de l'arbre de dérivation (sans consommer de symbole), on dépile trois états, le nouvel état est donc l'état 7, on consulte maintenant la table des sauts pour la colonne X=U, qui demande d'empiler l'état 10 ; la pile contient donc maintenant (10,7,4,2,0) ;
  8. il n'y a plus de symbole (r=$), la table d'actions pour m=10 contient l'action reduce UcU, on enregistre donc cette règle comme ancêtre de l'arbre de dérivation (sans consommer de symbole), on dépile deux états, le nouvel état est donc l'état 4, on consulte maintenant la table des sauts pour la colonne X=U, qui demande d'empiler l'état 6 ; la pile contient donc maintenant (6,4,2,0) ;
  9. il n'y a plus de symbole (r=$), la table d'actions pour m=6 contient l'action reduce Tε, on enregistre donc cette règle (sans consommer de symbole), on ne dépile rien, le nouvel état reste l'état 6, on consulte maintenant la table des sauts pour la colonne X=T, qui demande d'empiler l'état 9 ; la pile contient donc maintenant (9,6,4,2,0) ;
  10. il n'y a plus de symbole (r=$), la table d'actions pour m=9 contient l'action reduce TbUT, on enregistre donc cette règle comme ancêtre de l'arbre de dérivation (sans consommer de symbole), on dépile trois états, le nouvel état est donc l'état 2, on consulte maintenant la table des sauts pour la colonne X=T, qui demande d'empiler l'état 3 ; la pile contient donc maintenant (3,2,0) ;
  11. il n'y a plus de symbole (r=$), la table d'actions pour m=3 contient l'action reduce Sε, on enregistre donc cette règle (sans consommer de symbole), on ne dépile rien, le nouvel état reste l'état 3, on consulte maintenant la table des sauts pour la colonne X=S, qui demande d'empiler l'état 9 ; la pile contient donc maintenant (5,3,2,0) ;
  12. il n'y a plus de symbole (r=$), la table d'actions pour m=5 contient l'action reduce SaTS, on enregistre donc cette règle comme ancêtre de l'arbre de dérivation (sans consommer de symbole), on dépile trois états, le nouvel état est donc l'état 0, on consulte maintenant la table des sauts pour la colonne X=S, qui demande d'empiler l'état 1 ; la pile contient donc maintenant (1,0) ;
  13. il n'y a plus de symbole (r=$), la table d'actions pour m=1 contient l'action accept : le mot est donc accepté par l'analyseur, qui termine son exécution.

La différence essentielle avec l'analyseur descendant est que, dans l'analyseur ascendant, la pile sert à enregistrer ce qui a été reconnu et non pas ce qui reste à reconnaître. Plus exactement, chacun des états correspond à une règle « entamée » (ce qu'on appelle plus précisément un item LR(0)) : par exemple l'état 2 correspond à la situation où l'analyseur a détecté ce qui est peut-être le début d'une règle SaTS, il a déjà rencontré le a et il attend la suite (ceci s'écrit donc en abrégé SaTS ; comme c'est un T qui suit, implicitement, l'état 2 comprend donc aussi toutes les règles dérivant un T, c'est-à-dire T→•ε et T→•bUT) ; si depuis cet état on rencontre un b, on pousse (shift) l'état 4={TbUT} ; tandis que quand on aura fini d'analyser le T, on ira (goto) dans l'état 3={SaTS}. Quand à l'issue de la deuxième étape de l'exécution ci-dessus l'analyseur a dans sa pile (4,2,0), ceci signifie qu'il a commencé l'exécution, rencontré un a qui résulte forcément de l'item SaTS, puis un b qui résulte forcément de l'item TbUT. Les actions reduce effecutées sont exactement les règles appliquées dans la dérivation droite, lue à l'envers.

(Si on veut être plus précis dans la construction de la dérivation droite, on peut par exemple, en plus de la pile d'états, garder une pile de symboles qui a toujours exactement la même hauteur que la pile d'états — ou de façon équivalente, une pile de couples (état,symbole). La pile de symboles commence avec le symbole spécial « init » qui restera toujours là ; une opération shift empile le symbole terminal qui est consommé dans cette opération, et une opération reduce, après avoir dépilé les symboles correspondant au membre de droite de la production, empile le symbole correspondant au membre de gauche. L'intérêt de cette construction est que si on regarde, au fur et à mesure de cette exécution, le contenu de la pile de symboles (lue de la base vers le sommet) auquel on concatène les symboles restant à consommer, on obtient précisément la dérivation gauche du mot, lue à l'envers.)

Évidemment, la grammaire très simple que j'ai choisie n'illustre pas vraiment la puissance des analyseurs LR. En voici une différente : cette fois, elle ne peut pas être analysée de façon LL, et même, le langage {aibj:ij} qu'elle engendre n'est pas descriptible par une grammaire qui pourrait être analysée de cette façon :

  • ST | aS
  • Tε | aTb

L'explication intuitive de l'impossibilité à l'analyser de façon LL est que, quel que soit le nombre de a qu'on peut rencontrer au début du mot, il ne permet pas de savoir si ce mot procède de la dérivation de l'axiome S en T ou aS.

Et voici un analyseur SLR(1) de cette nouvelle grammaire :

ActionGoto
ab$ST
0s3r[Tε]r[Tε]012
1acc.1
2r[ST]2
3s3r[Tε]r[Tε]345
4r[SaS]4
5s6r[ST]5
6r[TaTb]r[TaTb]6

[Signification des états : 0 = initial ({init→•S}) ; 1 = {init→S•} ; 2 = {ST•} ; 3 = {SaS, TaTb} ; 4 = {SaS•} ; 5 = {TaTb, ST•} ; 6 = {TaTb•}.]

Cette fois, quand on est dans l'état 3, on ne sait pas au juste quelle règle est entamée : si on compare l'évolution de la pile lors de l'analyse du mot a (à savoir : (0), (3,0), (5,3,0), (4,3,0) puis (1,0)) et ab (à savoir : (0), (3,0), (5,3,0), (6,5,3,0), (2,0) puis (1,0)), on se rend compte que les deux interprétations sont réellement possibles (et idem pour l'état 5). C'est bien cette possibilité qui rend les analyseurs ascendants possiblement plus puissants que les analyseurs descendants.

↑Entry #2187 [older| permalink|newer] / ↑Entrée #2187 [précédente| permalien|suivante] ↑

[Index of all entries / Index de toutes les entréesLatest entries / Dernières entréesXML (RSS 1.0) • Recent comments / Commentaires récents]