Notas sobre el artículo L.R. Parsing

El artíuclo al cual se hace referencia aquí, “LR Parsing” de A. V. Aho y J. S. Johnson, ya había sido mencionado en entradas anteriores.

En la notación que usa dicho artículo, se escriben en mayúsculas los símbolos no terminales, en minúsculas los terminales, y entre comillas simples los literales.

La derivación* siguiente sirve de un ejemplo:

SALUDO ‘!’ => hola ‘!’

En donde SALUDO es el símbolo no terminal, hola es el terminal, y ‘!’ el literal.

Las letras griegas (por ejemplo α, β, γ) por su parte, representan cadenas de símbolos de cualesquiera de las 3 categorías (terminales, no terminales y literales) generadas durante el proceso de derivación.

Por ejemplo, de la siguiente derivación:

SALUDO SEÑOR_PÉREZ ‘.’ ‘¡Bienvenido!’ => SALUDO NOMBRE pérez ‘.’ ‘¡Bienvenido!’

La parte que está a la derecha del ‘=>’ se podría expresar con la ayuda de letras griegas de las siguientes formas:

• SALUDO α ‘.’ ‘¡Bienvenido!’ 
• SALUDO β 
• SALUDO β pérez ‘.’ ‘¡Bienvenido!’ 
• α β pérez ‘.’ ‘¡Bienvenido!’ 
• α ‘.’ ‘¡Bienvenido!’ 
• α 
• α SALUDO NOMBRE pérez ‘.’ ‘¡Bienvenido!’ 

(En el último ejemplo, a parte de α, la cadena de símbolos es exactamente como la original, lo que significa que α es la cadena vacía, mientras que en el anteúltimo caso, no habiendo más que una α, esta representa a la frase completa.)

Y una sola letra en minúscula, itálica y de forma redondeada (normalmente w) ocupa el lugar de cadenas de símbolos literales, en general la parte de más a la derecha de una frase. Ejemplo:

• SALUDO NOMBRE pérez ‘.’ ‘¡Bienvenido!’ w
• α NOMBRE pérez ‘.’ ‘¡Bienvenido’ w
• α β ‘.’ ‘¡’ w
• α β ‘.’ w
• α β w

(En el primer ejemplo, w es la cadena vacía, de acuerdo a un razonamiento similar al explicado arriba).


Por medio de la simbología introducida, se mostrará una posible definición de algo llamado "viable prefix", sin ocuparnos realmente de definir qué es esto.
Si la parte a la derecha del '=>' tiene la forma α β w, y β representa lo que es diferente con respecto al lado izquierdo, se dice que γ es viable prefix si: γ δ = α β, donde δ puede ser la cadena vacía. 

En otras palabras, el víable prefix siempre empieza bien a la izquierda de la cadena derivada, y se extiende a lo sumo hasta la parte que fue cambiada por la derivación.

*El significado del término derivación queda fuera del alcance de estas notas. Informalmente hablando, se puede reconocer una derivación porque contiene el símbolo '=>'. Una mejor definición se encuentra en “LR Parsing” de A. V. Aho y J. S. Johnson.