En el artículo Parsing Expressions by Recursive Descent de Theodore Norvell (1999), el autor comienza con la siguiente gramática para expresiones aritméticas:
E --> E "+" E | E "-" E | "-" E | E "*" E | E "/" E | E "^" E | "(" E ")" | v
lo cual es bastante malo, porque es ambiguo y recursivo a la izquierda. Entonces comienza a eliminar la recursión izquierda de él, y su resultado es como tal:
E --> P {B P}
P --> v | "(" E ")" | U P
B --> "+" | "-" | "*" | "/" | "^"
U --> "-"
Pero no puedo entender cómo llegó a este resultado. Cuando trato de eliminar la recursividad izquierda, lo hago de la siguiente manera:
Primero, agrupé las producciones que no han dejado recursividad en un grupo, y otras (recursivas a la izquierda) en otro grupo:
E --> E "+" E | E "-" E | E "*" E | E "/" E | E "^" E // L-recursive E --> v | "(" E ")" | "-" EA continuación, los nombro y factor para manipulaciones más fáciles:
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 --> "-"Ahora solo necesito lidiar con las dos primeras producciones, que ahora son más fáciles de manejar.
Reescribo esas dos primeras producciones comenzando desde la producción no L-recursiva (que es simplemente
P, la expresión primaria) y siguiendo por la cola opcionalT, que defino como el resto de la producción original menos el primer no terminal recursivo izquierdo (es decir, soloB E) seguido de la colaT, o que podría estar vacío:E --> P T T --> B E T |(tenga en cuenta la alternativa vacía para la cola).
Estas dos producciones ahora las puedo reescribir en EBNF así:
E --> P {B E}que es casi lo que obtiene el autor, pero tengo en
Elugar dePallí dentro del patrón de repetición cero o más (la Cola). Las otras producciones me dan lo mismo que él tiene:P --> v | "(" E ")" | U E B -> "+" | "-" | "*" | "/" | "^" U -> "-"pero aquí también tengo en
Elugar dePen la primera producción paraP.
Entonces, mi pregunta es: ¿qué me estoy perdiendo? ¿Qué transformación algebraica en la sintaxis necesito proceder ahora para obtener la misma forma exacta que obtiene el autor? Intenté sustituciones por E, pero solo me lleva a bucles. Sospecho que necesito sustituirlo Pde alguna manera E, pero no conozco ninguna transformación legal que lo justifique. ¿Quizás sabes cuál es el último paso que falta?

Respuestas:
El paso que falta:
reescribe E en T:
Simplifica T:
Equivalente a:
Y ahi estas.
fuente
Ts juntos en unoT? ¿Hay alguna regla para eso? (Sospecho que podría ser de alguna manera similar a la regla en la lógica algebraica booleana que dice "aa = a".)*? Vi en "Dragon Book" (3.3, p.91) esox** = x*. ¿Es esa la misma regla que usaste?