Analizadores Sintacticos

ANALIZADOR SINTACTICO LL(K)
Un analizador LL es llamado un analizador LL (k) si usa k tokens cuando el analizador ve hacia delante de la sentencia. Si existe tal analizador para cierta gramática y puede analizar sentencias de ésta gramática sin marcha atrás, entonces es llamada una gramática LL (k). De ésta gramáticas, la gramática LL(1), aunque es bastante restrictiva, éstas son muy popularesporque 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.

Tipo de analizador sintáctico predictivo
Se considera como un intento por encontrar una derivación por la izquierda para una cadena deentrada
Intento de construir un árbol desde la raíz, y creando los nodos del árbol en orden previo

LAS GRAMATICAS Y EL ANALIZADOR LL

Un analizador sintáctico LL(1) no puede resolver gramáticas recursivas por la izquierda
Estas pueden hacer que inicie un proceso recursivo infinito
Estos analizadores resultan ser los más simples pero los menos potentes

COMO FUNCIONA UN ANALIZADOR SINTACTICOLLT

Las funciones primero y siguiente permiten rellenar, siempre que sea posible, las entradas de una tabla de análisis sintáctico predictivo para una gramática
También se usan los componentes devueltos por la función Siguiente para sincronizar la recuperación de errores en modo de pánico

Primero:

Si x es una cadena de símbolos gramaticales, se considera PRIMERO(x) como el conjunto determinales que inician las cadenas derivadas de x.
Si x->e entonces e también está en Primero(x)

Siguiente:
Se define Siguiente(A) como el conjunto de terminales a que pueden aparecer inmediatamente a la derecha de A en alguna forma de frace
El conjunto de terminales de a tal que haya una derivación de la forma S->xaAaB para algún x y B.

En algún momento de la derivaciónpudieron haber existido símbolos entre A y a, pero si así fue, se derivaron a e(épsilon)
Si A puede ser el símbolo situado más a la derecha en una forma de frase, entonces $ esta en SIGUIENTE(A).




ANALIZADOR SINTACTICO LR(K)
Los analizadores sintácticos LR, también conocidos como Parser LR, son un tipo de analizadores para algunas gramáticas libres de contexto. Pertenece a la familia de losanalizadores ascendentes, ya que construyen el árbol sintáctico de las hojas hacia la raíz. Utilizan la técnica de análisis por desplazamiento reducción. Existen tres tipos de parsers LR: SLR (K), LALR (K) y LR (K) canónico.
Un analizador LR consta de:
Un programa conductor
Una entrada
Una salida
Una tabla de análisis sintáctico, compuesta de 2 partes (ACCIÓN Y GOTO)
Cabe acotar que elprograma conductor es siempre igual, solo variando para cada lenguaje la tabla de análisis sintáctico.
El algoritmo para reconocer cadenas es el siguiente: dado el primer carácter de la cadena y el estado inicial de la tabla, buscar qué acción corresponde en la tabla de acción.
Si el estado es shift n (n ∈ N), se coloca el carácter y el número de estado n en la pila, se lee el siguiente carácter yrepite el procedimiento, solo que esta vez buscamos en el estado correspondiente.
SI ACCIÓN = REDUCE n (n ∈ N), se sacan de la pila tantas tuplas (estado, símbolo) como el largo de la cola de la producción en el n-ésimo lugar, y se reemplaza por la cabeza de esta producción. El nuevo estado sale de buscar en la tabla GOTO usando para ubicarlo el número de estado que quedo en el tope de la pila, y elno terminal en la cabeza.
En la tabla acción también encontraremos ACEPTAR que se toma la cadena como valida y se termina el análisis o ERROR que se rechaza la cadena.

COMO FUNCIONA UN ANALIZADOR SINTACTICO ASCENDENTE LR
Para generar un autómata LR(0) en base a una gramática G, primero se debe definir:
Gramática ampliada: Dado una gramática G, se define la gramática ampliada G'a:
1. Se...