Analizador sintáctico LL

El analizador sintático LL es un analizador sintáctico descendente, por un conjunto de gramática libre de contexto. En este analizador las entradas son de izquierda a derecha, y construcciones de derivaciones por la izquierda de una sentencia o enunciado. La clase de gramática que es analizable por este método es conocido como gramática LL.

El resto de este artículo se describe en el cuadro de base del tipo de analizador sintáctico, la alternativa comienza con ser un intérprete de ascendencia recursiva que normalmente son codificados a mano (aunque no siempre; por ejemplo, ANTLR para un LL(*) - (generador de analizador ascendencia recursiva).

Introducción

Un analizador LL es llamado un analizador LL (k) si usa un número k de tokens cuando el analizador va hacia delante de la sentencia. Si existe tal analizador para cierta gramática y puede analizar sentencias de esta gramática sin marcha atrás, entonces es llamada una gramática LL (k). De estas gramáticas, la gramática LL(1), aunque es bastante restrictiva, éstas son muy populares porque los analizadores LL correspondientes sólo necesita ver el siguiente token para hacer el análisis de sus decisiones. Lenguajes mal diseñados usualmente suelen tener gramáticas con un alto nivel de k, y requieren un esfuerzo considerable a analizar.

Existe controversia entre la escuela europea del diseño del lenguaje, quien prefiere gramática basada en LL, y los otros países prefieren predominantemente gramática basada en LR. Esto se debe en gran parte a la influencia de Niklaus Wirth en la ETH Zürich en Suiza, cuya investigación ha descrito una serie de maneras de optimizar lenguajes y compiladores LL(1).

Arquitectura de un analizador LL

Lo siguiente describe un derivaciones por la izquierda por un analizador basado en una tabla descendente (analiza de arriba hacia abajo).

Caso general

El trabajo del analizador sobre una cadena de gramática particular. El análisis consiste en:

un búfer de entrada, una cadena de gramática
una pila sobre la cual se almacenan los símbolos terminales y no-terminales de la gramática aún sin analizar
una tabla de análisis

El analizador aplica la regla encontrada en la tabla por encontrar el símbolo más alto en la pila (fila) con el presente símbolo en el flujo de entrada (columna).

Cuando el analizador empieza, la pila desde el principio contiene dos símbolos:

[ S, $ ]

Donde '$' es un símbolo terminal especial para indicar el final de la pila y el final del flujo de entrada, y 'S' es el símbolo de comienzo de la gramática. El analizador va a intentar modificar el contenido de esta pila para que vea el flujo de entrada. Sin embargo, este solo mantiene en la pila lo que todavía necesita ser reescrito.

Ejemplo Concreto

Preparación

Para explicar un analizador LL(1) tenemos que considerar la siguiente pequeña gramática LL(1):

S → F
S → (S F)
F → a

Y analizar la siguiente entrada: (a a)

Construimos una tabla de análisis para esta gramática expandiendo todos los símbolos terminales por columnas y los no terminales por fila. Después, las expresiones son numeradas por la posición donde las columnas y filas cruzan. Por ejemplo, el símbolo terminal '(' y no terminal 'S' combinan para la expresión número 2. La tabla es como la siguiente:

	(	)	a		$
S	2	-	1	-	-
F	-	-	3	-	-

(Note que también hay una columna para el terminal especial, representado aquí como $, ese es usado para indicar el final del flujo de entrada.)

Procedimiento de análisis

En cada paso, el analizador lee el siguiente símbolo disponible en el flujo de entrada, y el símbolo más alto de la pila. Si el símbolo de entrada y la pila son iguales, el analizador descarta a los dos, dejando solo símbolos sin encontrar en el flujo de entrada y en la pila.

Así, en este primer paso, el analizador lee el símbolo de entrada '(' y el símbolo más alto de la pila 'S'. La instrucción de la tabla de análisis viene desde la columna encabezado por el símbolo de entrada '(' y la fila encabezada por el símbolo más alto en la pila 'S'; esta celda contiene '2', que instruye al analizador aplicar la regla (2). El analizador tiene que reescribir 'S' a '( S F )' en la pila removiendo 'S' y empujando '(', 'S', ' ', 'F', ')' en la pila y este escribe la regla 2 en la salida. La pila entonces se convierte en:

[ (, S,  , F, ), $ ]

Mientras el '(' del flujo de entrada no igualo el símbolo más alto, 'S', de la pila, este no fue removido, y se mantiene como el siguiente símbolo disponible en el siguiente paso.

En el segundo paso, el analizador remueve el '(' de su flujo de entrada y de su pila, desde que ellos son iguales. La pila ahora se convierte en:

[ S,  , F, ), $ ]

Ahora el analizador tiene una 'a' en su flujo de entrada y una 'S' como su símbolo más alto de la pila. La tabla de análisis instruye al analizador que aplique la regla (1) de la gramática y escribir la regla 1 al flujo de salida. La pila se convierte en:

[ F,  , F, ), $ ]

Ahora el analizador tiene una 'a' en su flujo de entrada y una 'F' como su símbolo más alto de la pila. La tabla de análisis instruye al analizador que aplique la regla (3) de la gramática y escribir la regla 3 al flujo de salida. La pila se convierte en:

[ a,  , F, ), $ ]

En los siguientes dos pasos el analizador lee 'a' y ' ' del flujo de entrada y ellos igualan los siguientes dos símbolos en la pila, también los remueve de la pila. Esto resulta en:

[ F, ), $ ]

En los siguientes tres pasos el analizador reemplazara 'F' en la pila por 'a', escribe la regla número 3 al flujo de salida y remueve el 'a' y ')' de la pila y el flujo de entrada. El analizador termina con '$' en su pila y flujo de entrada.

En este caso el analizador reportara que este ha aceptado la cadena de entrada y escribir la siguiente lista de números de regla al flujo de salida:

[ 2, 1, 3, 3 ]

Véase también

Datos: Q932615