Construcción de la tabla de análisis LL(1) – Part 1

Requisito previo: clasificación de los analizadores de arriba hacia abajo, FIRST Set , FOLLOW Set 
Un analizador de arriba hacia abajo construye el árbol de análisis de arriba hacia abajo, comenzando con el no terminal de inicio. Hay dos tipos de analizadores de arriba hacia abajo: 
 

1. Analizador de arriba hacia abajo con retroceso
2. Analizadores de arriba hacia abajo sin retroceso

Los analizadores de arriba hacia abajo sin retroceso se pueden dividir en dos partes: 

En este artículo, vamos a discutir el descenso no recursivo, que también se conoce como analizador LL(1). 

Análisis LL(1): 
aquí la primera L representa que el escaneo de la entrada se realizará de izquierda a derecha y la segunda L muestra que en esta técnica de análisis vamos a utilizar el árbol de derivación más a la izquierda. Y finalmente, el 1 representa el número de anticipación, lo que significa cuántos símbolos verás cuando quieras tomar una decisión.

Algoritmo para construir la tabla de análisis LL(1): 

Paso 1:  primero verifique la recursividad por la izquierda en la gramática, si hay recursión por la izquierda en la gramática, elimínela y vaya al paso 2.

Paso 2: Calcule First() y Follow() para todos los no terminales.

1.  Primero(): si hay una variable, y a partir de esa variable, si tratamos de controlar todas las strings, entonces el Símbolo de terminal inicial se llama Primero. 
2. Seguir(): Que es el Símbolo Terminal que sigue a una variable en el proceso de derivación. 

Paso 3: Para cada producción A –> α. (A tiende a alfa)

1. Encuentre First(α) y para cada terminal en First(α), haga la entrada A –> α en la tabla.
2. Si First(α) contiene ε (épsilon) como terminal que, encuentre el Follow(A) y para cada terminal en Follow(A), haga la entrada A –> α en la tabla.
3. Si First(α) contiene ε y Follow(A) contiene $como terminal, entonces haga la entrada A –> α en la tabla para $.
   Para construir la tabla de análisis, tenemos dos funciones: 
    

En la tabla, las filas contendrán los no terminales y la columna contendrá los símbolos de terminales. Todas las Producciones Nulas de las Gramáticas pasarán a formar parte de los elementos de Seguimiento y el resto de las producciones pasarán a formar parte de los elementos del Primer conjunto. 

Ahora, entendamos con un ejemplo. 

Ejemplo-1: 
Considere la gramática: 
 

E --> TE'
E' --> +TE' | ε                
T --> FT'
T' --> *FT' | ε
F --> id | (E)

*ε denotes epsilon

Encuentre sus conjuntos Primero y Seguir: 

	Primero	Seguir
E –> TE’	{ identificación, ( }	ps
E’ –> +TE’/ ε	{ +, ε }	ps
T –> FT’	{ identificación, ( }	{ +, $, ) }
T’ –> *FT’/ ε	{*, ε}	{ +, $, ) }
F –> identificación/(E)	{ identificación, ( }	{ *, +, $, ) }

Ahora, la tabla de análisis LL(1) es: 

	identificación	+	*	(	)	ps
mi	E –> TE’			E –> TE’
MI’		E’ –> +TE’			E’ –> ε	E’ –> ε
T	T –> FT’			T –> FT’
T’		T’ –> ε	T’ –> *FT’		T’ –> ε	T’ –> ε
F	F –> identificación			F –> (E)

Como puede ver, todas las producciones nulas se colocan debajo del conjunto Seguir de ese símbolo y todas las producciones restantes se encuentran debajo del Primero de ese símbolo. 

Nota: No todas las gramáticas son viables para la tabla de análisis LL(1). Es posible que una celda contenga más de una producción. 

Veamos con un ejemplo. 

Ejemplo-2: 
Considere la gramática 
 

S --> A | a
A --> a 

Encuentre sus conjuntos Primero y Seguir: 

	Primero	Seguir
S –> A/a	{ a }	ps
Un –> un	{ a }	ps

Tabla de análisis: 

	a	ps
S	S –> A, S –> un
A	Un –> un

Aquí, podemos ver que hay dos producciones en la misma celda. Por lo tanto, esta gramática no es factible para LL(1) Parser.