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

Index of all entries / Index de toutes les entréesXML (RSS 1.0) • Recent comments / Commentaires récents

Entry #2187 [older|newer] / Entrée #2187 [précédente|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) :

(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 :

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 :

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 :

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|newer] / ↑Entrée #2187 [précédente|suivante]

Recent entries / Entrées récentesIndex of all entries / Index de toutes les entrées