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

Ruxor (2014-01-24T00:01:13Z)

@Thierry: Merci pour cette question !, qui me permet de me m'éclaircir les idées.

Telles que je comprends les choses : les grammaires LL et LR sont nécessairement inambiguës et sont définies par le fait que l'algorithme de construction de l'analyseur correspondant ne produit pas de conflit, ce qui peut se réexprimer de façon plus intrinsèque au moyen de propriétés sur les dérivations. Par exemple, une grammaire est dite LL(k) si et seulement si à chaque fois qu'on a une dérivation partielle S ⇒* wAγ (avec A le nonterminal le plus à gauche, w un mot sur les terminaux, et γ un mot sur les terminaux et nonterminaux) et deux façons de terminer cette dérivation wAγ ⇒* wx et wAγ ⇒* wy où x et y ont le même préfixe de longueur k, alors la règle utilisée pour réécrire ce A dans la dérivation est uniquement définie. Une grammaire est dite LR(k) si et seulement si (S ne peut pas se dériver en lui-même en strictement plus que 0 étapes et que) à chaque fois qu'on a des dérivations partielles S ⇒* αAw ⇒ γw (où γ=αβ et A→β) et S ⇒* α′A′w′ ⇒ γ′w′ avec γ′w′=γz où w et z ont le même préfixe de longueur k, alors le nonterminal réécrit est le même (A=A′), la règle appliquée est la même (β=β′) et le contexte est le même (α=α′). Voir par exemple le début de <URL: https://cs.uwaterloo.ca/research/tr/1979/CS-79-36.pdf >.

J'ai tort de laisser penser qu'un analyseur descendant (terme informel et non rigoureusement défini) est forcément un analyseur LL. Il existe des catégories plus générales d'analyseurs descendants, par exemple l'article de 1975 de Jarzabek and Krawczyk, "LL-regular grammars" définit la catégorie éponyme, plus générale que LL (ou peut-être seulement que LL(*)?), et montre comment on peut l'analyser de façon descendante.

D'autre part, un automate à pile déterministe reconnaît toujours un langage qui peut être décrit par une grammaire inambiguë.

L'exemple que tu donnes n'est donc pas un analyseur LL, même si c'est intéressant parce que ça y ressemble beaucoup. D'autre part, il doit exister une grammaire inambiguë associée au langage qu'il reconnaît. Mais j'ai abandonné en essayant de l'écrire parce que les démonstrations à ce sujet changent sans arrêt d'avis entre les différentes conditions d'arrêt sur les automates à pile (arrêt par état final, arrêt par pile vide, ou la conjonction des deux…). En plus il y a des subtilités sur la reconnaissance de la fin de la chaîne (voir la notion de langage déterministe strict), je n'arrive jamais à retenir tout ça.

Ce serait intéressant d'approfondir. Notamment, ceci soulève la question de savoir comment décider si un automate à pile est un vrai automate LL (i.e., vraiment isomorphe à celui produit par l'algorithme pour un langage LL) par opposition à juste y ressembler. (On doit pouvoir faire en retrouvant la grammaire, puis en vérifiant qu'elle est bien LL. Mais il y a peut-être plus direct.)

Thierry (2014-01-23T16:46:33Z)

C’est joli d’avoir de tels exemples pour introduire les grammaires LL et LR, merci ! Quel est le statut des grammaires ambiguës ? Dit-on forcément qu’elles ne peuvent être ni LL ni LR par définition ?

J’ai l’impression d’avoir les idées un peu confuses à ce sujet, et du coup sur la relation entre les automates à pile déterministes, les analyseurs récursifs descendants, les analyseurs LL et les grammaires LL.

L’automate à pile déterministe suivant reconnaît { a^ib^j | j ≤ i } :

S : { a : S → aT ; $ : S → ε }
T : { a : T → aTU ; b : T → b ; $ : T → ε }
U : { b : U → b ; $ : U → ε }

J’aurais envie de dire d’une part qu’il s’agit d’un analyseur déterministe récursif descendant, « donc » (?) d’un analyseur LL, et d’autre part que cet automate « correspond » à la grammaire { S → aT + ε, T → aTU + b + ε, U → b + ε }, mais celle-ci est ambiguë. Que peut-on dire alors ? Que { a^ib^j | j ≤ i } est reconnu par un analyseur LL mais pas par une grammaire LL ? Que { a^ib^j | j ≤ i } est reconnu par une grammaire LL, mais celle-ci est nécessairement ambiguë ? Rien de tout ça ?


You can post a comment using the following fields:
Name or nick (mandatory):
Web site URL (optional):
Email address (optional, will not appear):
Identifier phrase (optional, see below):
Attempt to remember the values above?
The comment itself (mandatory):

Optional message for moderator (hidden to others):

Spam protection: please enter below the following signs in reverse order: 238b4f


Recent comments