Véase también LL(1)
Un analizador LL ( parser LL ) es un analizador de arriba hacia abajo en informática para un subconjunto de gramáticas libres de contexto conocidas como gramáticas LL . Sin embargo, no todas las gramáticas libres de contexto son gramáticas LL.
Las letras L en la expresión "analizador LL" significan que la cadena de entrada se analiza de izquierda a derecha y, al mismo tiempo , se construye su derivación más a la izquierda.
Un analizador LL se denomina analizador LL(k) si este analizador utiliza una búsqueda anticipada de k tokens (tokens) al analizar el flujo de entrada. Una gramática que puede ser reconocida por un analizador LL(k) sin retroceder se llama gramática LL(k). Un lenguaje que se puede representar como una gramática LL(k) se denomina lenguaje LL(k)o. Hay idiomas LL(k+n) que no son idiomas LL(k).
A continuación se describe el analizador, que se basa en la construcción de tablas; una alternativa es un analizador de descenso recursivo, que generalmente se escribe a mano (aunque hay excepciones, como el generador de analizador ANTLR para gramáticas LL(*)).
Las gramáticas LL(1) son muy comunes porque sus analizadores LL correspondientes miran el flujo solo un carácter por delante cuando deciden qué regla gramatical aplicar. Los lenguajes basados en gramáticas con valores k grandes se han considerado tradicionalmente difíciles de reconocer, aunque con el uso generalizado de generadores de analizadores que admiten gramáticas LL(k) con k arbitrario, esta observación ya no es relevante.
Un analizador LL se llama analizador LL(*) si no hay una restricción estricta en k y el analizador puede reconocer el lenguaje si los tokens pertenecen a algún conjunto regular (por ejemplo, usando autómatas finitos deterministas ).
Existen contradicciones entre la llamada "escuela europea" de construcción del lenguaje, que se basa en las gramáticas LL, y la "escuela americana", que prefiere las gramáticas LR. Tales contradicciones se deben a las tradiciones de enseñanza y los detalles de la descripción de varios métodos y herramientas en libros de texto específicos; también influenciado por N. Wirth de ETHZ , cuya investigación describe varios métodos para optimizar los resolutores y compiladores LL(1).
El analizador está diseñado para resolver el problema de si una cadena pertenece a una gramática dada y para construir un árbol de salida si es así.
El analizador consta de:
En las filas de la tabla hay símbolos del alfabeto de la tienda y en las columnas, símbolos del alfabeto terminal.
Cuando comienza el análisis, la pila ya contiene dos caracteres:
[ S, $ ]Donde '$' es un terminal especial usado para indicar el final de la pila, y 'S' es un axioma de la gramática. El analizador intenta, usando reglas gramaticales, reemplazar el axioma en la pila con una cadena de caracteres similar a la cadena en la cinta de entrada, y luego lee completamente la cinta, vaciando la pila.
Para explicar cómo funciona el analizador LL, considere la siguiente gramática:
Y analicemos el análisis en el ejemplo de una cadena:
(1+1)La tabla de análisis para esta gramática se ve así:
| ( | ) | una | + | ps | |
| S | 2 | — | una | - | - |
| F | — | — | 3 | - | - |
También hay una columna para una terminal especial, denotada por $, que se usa para indicar el final del flujo de entrada. Los números (en negrita) en las celdas indican los números de las reglas indicadas anteriormente.
El analizador mira el primer carácter '(' del flujo de entrada, en ese momento el carácter 'S' está en la parte superior de la pila, en la intersección de estos valores en la tabla de análisis hay una regla de la gramática En este ejemplo, esta es la regla número 2, que indica reemplazar en la pila el carácter 'S' en la cadena '(S + F)' El estado de la pila después de aplicar esta regla es:
[ (, S, +, F, ), $ ]En el siguiente paso, el analizador lee el carácter '(' del flujo de entrada. Dado que hay un carácter similar '(' en la parte superior de la pila, este carácter se lee de la cinta y se elimina de la pila. El estado de la pila después de aplicar esta regla es:
[S, +, F, ), $]El siguiente en la cinta es el símbolo '1', y en la parte superior de la pila 'S', en la intersección de estos símbolos en la tabla, está la regla 1. Después de aplicar esta regla, según la tabla, el analizador aplica regla 3. El estado de la pila después de aplicar las reglas:
[ F, +, F, ), $ ] [ 1, +, F, ), $ ]A continuación, el analizador lee '1' y '+' del flujo de entrada y, dado que corresponden a los siguientes dos elementos de la pila, también los elimina de la pila. Como resultado, la pila se ve así:
[ F, ), $ ]En los tres pasos siguientes, el carácter 'F' de la pila se cambiará a '1', después de lo cual los caracteres '1' y ')' se leerán de la cinta y se eliminarán de la pila. Como resultado, el símbolo '$' estará en la parte superior de la pila y en la cinta, según la definición, esto significa un análisis sintáctico exitoso de la cadena.
En este caso, el analizador informará el éxito y devolverá una lista de las reglas que se aplicaron durante el proceso de inferencia:
[2, 1, 3, 3]Estas reglas son de hecho la inferencia más a la izquierda:
S → (S + F) → (F + F) → (1 + F) → (1 + 1)Como puede ver en el ejemplo, el analizador hace tres cosas diferentes dependiendo de si la parte superior de la pila es una no terminal, una terminal o el carácter especial $:
Estos pasos se repiten hasta que se produce una parada. Después de la parada, recibiremos un mensaje de error o un mensaje de que la cadena se reconoció con éxito.
Para llenar la tabla de análisis, es necesario establecer qué regla gramatical debe elegir el analizador si el no terminal A está en la parte superior de su pila y el carácter a está en el flujo de entrada. Es fácil ver que tal regla debe ser de la forma A → w y que el idioma correspondiente a w debe tener al menos una línea que comience con a . Para ello, definimos el Primer conjunto de w , escrito aquí como Fi(w) , como el conjunto de terminales que se pueden encontrar al principio de cualquier línea en w , y ε si la línea vacía también pertenece a w . Dada una gramática con reglas A 1 → w 1 , …, A n → w n , se puede calcular Fi(w i ) y Fi(A i ) para cada regla de la siguiente manera:
Desafortunadamente, los primeros conjuntos no son suficientes para construir una tabla de análisis. Esto se debe a que el lado derecho w de la regla eventualmente podría convertirse en la cadena vacía. Por lo tanto, el analizador también debe usar la regla A → w si ε está en Fi(w) y en el flujo de entrada hay un carácter que puede seguir a A. Por lo tanto, también es necesario construir un conjunto siguiente A (aquí escrito como Fo(A) ) que se define como un conjunto de terminales a tal que hay una cadena de caracteres αAaβ que se puede obtener del carácter de inicio. El cálculo de los siguientes conjuntos para no terminales en una gramática se puede hacer de la siguiente manera:
Ahora puede definir exactamente qué reglas estarán contenidas en la tabla de análisis. Si T[A, a] denota una entrada en la tabla para un no terminal A y un terminal a , entonces
T[A,a] contiene la regla A → w si y solo si:
Si la tabla no contiene más de una regla en cada celda, el analizador podrá determinar sin ambigüedades qué regla se debe aplicar en cada paso de análisis. En este caso, la gramática se llama gramática LL(1) .
El tamaño de la tabla de análisis tiene una complejidad exponencial en función de k en el peor de los casos . Sin embargo, después del lanzamiento de Compiler Construction Toolkit (PCCTS, ahora conocido como ANTLR ) alrededor de 1992, se demostró que el tamaño de la tabla de análisis para la mayoría de los lenguajes de programación no tiende a aumentar exponencialmente, ya que no es el peor. caso. Además, en ciertos casos incluso fue posible crear analizadores LL( * ). Sin embargo, a pesar de esto, los generadores de analizadores tradicionales como yacc / GNU bison usan tablas de análisis LALR( 1 ) para crear un analizador LR limitado .
Los generadores de analizadores modernos , para gramáticas LL con anticipación de múltiples relés, incluyen:
| Lenguajes formales y gramáticas formales | |
|---|---|
| Conceptos generales | |
| tipo 0 | |
| Tipo 1 |
|
| Tipo 2 | |
| Tipo 3 |
|
| analizando | |