La récursivité à gauche, et ce que la réécriture coûte

1. Les deux engendrent $\text{n}(-\text{n}{)}^{\ast }$. Vérifié par énumération de tous les mots sur $\{\text{n},-\}$ jusqu'à la longueur $7$ : les deux ensembles coïncident. Les grammaires sont faiblement équivalentes.

2. Chaque mot a un arbre unique dans chacune des deux — aucune n'est ambiguë. Mais les arbres n'ont pas la même forme :

On a omis, sous chaque $T$, la feuille n qu'elle produit ; et le $P$ le plus à droite de l'arbre de droite se dérive en $\epsilon$. Les feuilles lues de gauche à droite donnent n-n-n dans les deux cas — c'est bien le même mot, et ce sont bien deux arbres différents.

3. Un analyseur qui suivrait naïvement la grammaire réécrite construirait $8-(3-2)$ et calculerait 7. La bonne réponse est 3. Les deux valeurs ont été mesurées en exécutant les deux analyseurs.

Ce que la réécriture coûte, exactement. Elle conserve le langage et détruit la structure. Or c'est la structure qui porte le sens : $-$ est associatif à gauche, l'arbre penché à droite dit le contraire.

Comment on s'en sort en pratique — et c'est ce que fait le problème sur les expressions arithmétiques : on écrit la boucle

let rec e () =
  let acc = ref (t ()) in
  while pointe_sur '-' do lire '-'; acc := Moins (!acc, t ()) done;
  !acc

qui consomme comme la grammaire réécrite — donc termine — mais accumule à gauche, donc construit le bon arbre. La boucle règle les deux problèmes d'un coup ; la simple traduction de la grammaire réécrite n'en règle qu'un.