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 ")" | "-" E
A 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
E
lugar deP
allí 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
E
lugar deP
en 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 P
de 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
T
s 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?