Transformation grammaticale des expressions arithmétiques

Dans l'article Parsing Expressions by Recursive Descent de Theodore Norvell (1999), l'auteur commence par la grammaire suivante pour les expressions arithmétiques:

E --> E "+" E | E "-" E | "-" E | E "*" E | E "/" E | E "^" E | "(" E ")" | v

ce qui est assez mauvais, car il est ambigu et récursif à gauche. Il commence donc par en supprimer la récursion gauche, et son résultat est comme tel:

E --> P {B P}
P --> v | "(" E ")" | U P
B --> "+" | "-" | "*" | "/" | "^"
U --> "-"

Mais je n'arrive pas à comprendre comment il est arrivé à ce résultat. Lorsque j'essaie de supprimer moi-même la récursion gauche, je le fais de la manière suivante:

1. Premièrement, je regroupe les productions qui n'ont pas laissé de récursivité dans un groupe, et d'autres (gauche-récursive) dans un autre groupe:

   E --> E "+" E | E "-" E | E "*" E | E "/" E | E "^" E     // L-recursive
   E --> v | "(" E ")" | "-" E

2. Ensuite, je les nomme et facteur pour des manipulations plus faciles:

   E --> E B E  // L-recursive; B stands for "Binary operator"
   E --> P  // not L-recursive; P stands for "Primary Expression"
   P --> v | "(" E ")" | U E   // U stands for "Unary operator"
   B --> "+" | "-" | "*" | "/" | "^"
   P --> "-"

   Maintenant, je n'ai plus besoin que des deux premières productions, qui sont désormais plus faciles à gérer.

3. Je réécris ces deux premières productions en partant de la production non récursive (qui est simplement Pl'expression primaire) et en la suivant par la queue facultative T, que je définis comme le reste de la production originale moins la première non récursive gauche non terminale (c'est-à-dire, juste B E) suivi de la queue T, ou qui pourrait être vide:

   E --> P T
   T --> B E T |

   (notez l'alternative vide pour la queue).

4. Ces deux productions que je peux maintenant réécrire en EBNF comme ceci:

   E --> P {B E}

   ce qui est presque ce que l'auteur obtient, mais j'ai Eau lieu de Plà à l'intérieur du modèle de répétition zéro ou plus (la queue). Les autres productions que je reçois sont presque les mêmes que lui:

   P --> v | "(" E ")" | U E
   B -> "+" | "-" | "*" | "/" | "^"
   U -> "-"

   mais là aussi j'ai Eau lieu de Pdans la première production pour P.

Alors, ma question est: qu'est-ce que je manque? De quelle transformation algébrique de la syntaxe dois-je procéder maintenant pour obtenir la même forme exacte que celle obtenue par l'auteur? J'ai essayé des substitutions pour E, mais cela ne me mène qu'à des boucles. Je pense que je dois en quelque sorte de remplacer Ppour E, mais je ne sais pas toute transformation juridique pour le justifier. Peut-être savez-vous quelle est la dernière étape manquante?

L'étape manquante:

E --> P T
T --> B E T |

réécrire E en T:

E --> P T
T --> B P T T | 

Simplifiez T:

E --> P T
T --> B P T | 

Équivalent à:

E --> P T
T --> {B P}

Et voilà.