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
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.
No hay comentarios:
Publicar un comentario