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 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.

 Tipo de analizador sintáctico predictivo

 Se considera como un intento por encontrar una derivación por la izquierda para una cadena de entrada

 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 SINTACTICO LLT

 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 de terminales 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ón pudieron 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 los analizadores 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 el programa 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

...