Algoritmo de análisis LL(1)

Requisito previo: construcción de la tabla de análisis sintáctico LL(1) .
El análisis LL(1) es un método de análisis de arriba hacia abajo en la fase de análisis de sintaxis del diseño del compilador. Los componentes necesarios para el análisis LL(1) son una string de entrada, una pila, una tabla de análisis para una gramática determinada y un analizador. Aquí, discutimos un analizador que determina que la string dada puede generarse a partir de una gramática determinada (o tabla de análisis) o no.
 Supongamos que la gramática dada es G = (V, T, S, P)
donde V-conjunto de símbolos de variable, T-conjunto de símbolos de terminal, S-símbolo de inicio, P-conjunto de producción. 

LL(1) Algoritmo del analizador:
Entrada- 1. pila = S //la pila contiene inicialmente solo S.
            2. string de entrada = w$
                donde S es el símbolo inicial de la gramática, w es una string dada y $se usa para el final de hilo
            3. PT es una tabla de análisis de gramática dada en forma de array o arreglo 2D.

Salida: determina que la string dada puede ser producida por la gramática dada (tabla de análisis) o no, si no, entonces produce un error.

Pasos:

1. while(stack is not empty) {

       // initially it is S
2.     A = top symbol of stack;  

       //initially it is first symbol in string, it can be $ also
3.     r = next input symbol of given string; 
4.     if (A∈T or A==$) {
5.         if(A==r){
6.             pop A from stack;
7.             remove r from input;
8.         }
9.         else
10.             ERROR();
11.     }
12.     else if (A∈V) {
13.         if(PT[A,r]= A⇢B1B2....Bk) {
14.             pop A from stack;
             
                // B1 on top of stack at final of this step
15.             push Bk,Bk-1......B1 on stack  
16.         }
17.         else if (PT[A,r] = error())
18.             error();
19.     }
20. } 
// if parser terminate without error() 
// then given string can generated by given parsing table.

Complejidad temporal
Como sabemos, el tamaño de una gramática para una lengua es finito. Como, un número finito de variables, terminales y producciones. Si la gramática es finita, entonces su tabla de análisis LL(1) también es finita de tamaño O(V*T). Dejar

• p es el máximo de longitudes de strings en RHS de todas las producciones y
• l   es la longitud de la string dada y

l es mucho mayor que p . si el bloque en la línea 4 del algoritmo siempre se ejecuta durante O (1) tiempo. de lo contrario, si el bloque en la línea 12 del algoritmo toma O(|P|*p) como límite superior para un solo símbolo de entrada siguiente. Y el ciclo while puede ejecutarse más de l veces, pero hemos considerado el ciclo while repetido para un solo símbolo de entrada siguiente en O(|P|*p) . Entonces, la complejidad temporal total es

       T(l) = O(l)*O(|P|*p)
              = O(l*|P|*p)
              = O(l)           { as l >>>|P|*p }

La complejidad temporal de este algoritmo es el orden de longitud de la string de entrada.

Comparación con el lenguaje libre de contexto (CFL): los
idiomas en la gramática LL (1) son un subconjunto adecuado de CFL. Usando el algoritmo CYK podemos encontrar la pertenencia a una string para una gramática libre de contexto dada (CFG). CYK toma O(l ³ ) tiempo para la prueba de membresía para CFG. Pero para la gramática LL(1) podemos hacer una prueba de membresía en tiempo O(l) que es lineal usando el algoritmo anterior. Si sabemos que CFG dado es gramática LL(1), entonces use el analizador LL(1) para analizar en lugar del algoritmo CYK.

Ejemplo –
Sea la gramática G = (V, T, S’, P ) 

S' → S$
S → xYzS | a
Y → xYz | y

Tabla de análisis ( PT ) para esta gramática

	a	X	y	z	ps
S’	S’ → S$	S’ → S$	error	error	error
S	S → un	S → xYzS	error	error	error
Y	error	Y → xYz	Y → y	error	error

Let string1 = xxyzza,

Tenemos que agregar $ con esta string. 
Usaremos el algoritmo de análisis anterior, diagrama para el proceso:

Para string1 obtuvimos una pila vacía, y el ciclo while o el algoritmo terminaron sin error. Entonces, string1 pertenece al lenguaje para la gramática G dada .

Let string2 = xxyzzz,

De la misma manera que arriba, usaremos el algoritmo para analizar la string2, aquí está el diagrama

Para string2 , en la última etapa como en el diagrama anterior cuando la parte superior de la pila es S y el siguiente símbolo de entrada de la string es z , pero en PT[S,z] = error . El algoritmo terminó con un error. Entonces, string2 no está en el lenguaje de la gramática  G.