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

@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.)