Bon, je vais essayer d'expliquer rapidement le parsing LR, mais il n'y aura pas tous les détails:
* Tu commences avec une "grammaire". Celle-ci contient des "états", et des "tokens" qui correspondent à des mots, ou plus exactement à des catégories de mots. La grammaire décrit à quel état on passe en fonction de l'état de départ et du token lu. Par exemple, pour une phrase simple:
état "départ" + token "sujet" -> état 1
état 1 + token "verbe" -> état 2
état 2 + token "objet" -> état "fin"
Tout token qui n'est pas prévu par la grammaire sera vu comme une erreur de syntaxe ("parse error").
* En plus des passages d'état, la grammaire te dit comment interpréter les tokens. Par exemple:
"sujet": "shift" (le token ne veut rien dire tout seul, il faut en lire un autre)
"sujet"+"verbe": "shift"
"sujet"+"verbe"+"objet": "reduce" -> "phrase" (sujet+verbe+objet=phrase)
* En pratique, ces informations ne sont pas codées comme dans l'exemple ci-dessus, mais associées aux états:
état "départ": shift, "sujet" -> état 1
état 1: shift, "verbe" -> état 2
état 2: shift, "objet" -> état 3
état 3: reduce(3) -> "phrase" -> état "fin" (le 3 de
reduce(3) étant le nombre de tokens à "réduire")
* La phrase "Je parse une phrase." sera donc parsée par cette grammaire comme:
état "départ": shift,
Je = "sujet" -> état 1
état 1: shift,
parse = "verbe" -> état 2
état 2: shift,
une phrase = "objet" -> état 3
état 3: reduce(3): "sujet" + "verbe" + "objet" -> "phrase" -> état "fin"
(En pratique, "une phrase" sera lu comme "préposition" "nom commun" et devra être également réduit en un seul token "objet".)
* Èvidemment, le résultat final intéressant n'est pas juste le token "phrase", mais aussi les étapes de réduction. Ici, on sait que notre phrase est constituée du "sujet"
Je, du "verbe"
parse et de l'"objet"
une phrase. Ici, le "parse tree" a un seul niveau. En général, c'est un arbre qui peut devenir très grand.
* En pratique, un parseur LR ne se limite pas à passer d'état en état, il exécute aussi du code quand il se trouve en certains états. Ce code fait en quelque sorte partie de la grammaire.
* Le parsing LR parse toujours de gauche à droite, d'où le nom "LR" (left-right). Cela présuppose une rangée limitée de grammaires possibles. Dans une grammaire générale, il peut y avoir des conflits entre un "shift" et un "reduce" (par exemple: "I saw the man" a un sens tout seul, mais "I saw [a man with a telescope]" a un sens différent que "[I saw a man] with a telescope". Donc il y a conflit entre un reduce de "I saw a man" ou un shift, suivi d'un reduce de "[a man with a telescope]") ou entre 2 "reduce" (situation semblable: 2 simplifications possibles, et on ne sait à priori pas laquelle choisir). Il existe une généralisation, le "generalized LR" qui consiste à résoudre ces conflits en essayant les 2 solutions jusqu'à trouver une erreur, et cela d'une manière astucieuse en temps et en vitesse (évidemment, ça ne marche bien que si la phrase n'est pas ambigüe. Si elle est ambigüe, il y a plusieurs solutions dont aucune ne porte à une erreur). (Mais ce n'est pas toujours fait de cette manière optimale.
GCC fait par exemple à certains endroits du parseur C++ actuel du "generalized LR" naïf: on essaye une solution; si elle passe, on accepte, sinon on essaye la prochaine solution. Et on recalcule tout même s'il y a des calculs en commun entre les 2 solutions, ce qui n'est pas optimal.) Mais je ne rentrerai pas dans les détails du "generalized LR" parce que c'est très long à expliquer clairement. Déjà le LR simple est assez compliqué.
(J'ai travaillé sur les parseurs LR en partie pour l'université (exposé sur le "generalized LR parsing") et en partie en travaillant sur
GCC (
GNU Bison). Mais je ne connais quand-même pas tout jusqu'au dernier détail.
)
