(1/9)
Errores de análisis
- Léxicos: suceden cuando un terminal o no terminal es mal escrito, y por ello no detectado por la gramática
- Sintácticos: cuando los terminales y no terminales no coinciden con reglas gramaticales (por ejemplo cerrar paréntesis)
- Semánticos: cuando las reglas gramaticales están bien, pero las reglas del programa no (p. ej. tipos incompatibles)
- Lógicos: cuando la semántica es correcta pero la lógica causará un programa incorrecto; casi nunca es analizada
(2/9)
Manejo de errores de análisis
- Modo de pánico: al primer error salta hasta hallar un token de final
- Recuperación a nivel de frase: reemplaza el token incorrecto por uno correcto, de ser posible
- Producciones de error: la gramática toma en cuenta los errores más comunes y los maneja
- Corrección global: el programa analiza toda la entrada para corregirla completa con el mínimo esfuerzo necesario
(3/9)
Gramáticas libres de contexto
- Se habían visto en detalle aquí
- Pueden ser analizadas mediante árboles de parsing
- Las gramáticas pueden ser ambiguas
- Toda expresión regular puede expresarse como una gramática también:
- El estado inicial i se coloca como el inicial A(i) de la gramática
- Una transición de i a j mediante a se coloca como A(i) → aA(j)
- Una transición de i a j mediante ϵ se coloca como A(i) → A(j)
- Las gramáticas libres de contexto pueden aceptar cualquier cantidad de tokens, ya que un estado puede volver a sí mismo infinitas veces (la famosa "bomba")
(4/9)
Top-down parsing
- Consiste en analizar sintácticamente una entrada empezando de una entrada raíz y siguiendo hasta obtener todos los tokens
- La que usaremos se denomina LL(1), un analizador que revisa la gramática desde la izquierda
- Dependiendo del caso, puede haber un tipo de recursividad que no es izquierda ni derecha, la que fuerza a usar backtracking
- Por ejemplo, tómese una gramática donde S → cAd y A → ab | a
- Si se analizara cabd, no podría saberse de antemano qué rama de A tomar, forzando el uso de backtracking
(5/9)
Parsing predictivo
- Se puede realizar parsing predictivo mediante llamados recursivos
- También se puede realizar el parsing explícitamente, sin recursión, usando:
- Una pila donde se encuentran todos los símbolos
- Una tabla donde se guarda la gramática
- Usualmente un token $ indica el final de la entrada; también es el primer símbolo en insertarse en la pila, antes del símbolo inicial
- El programa para el parsing sigue las siguientes reglas:
- Al sacar el token $ de la pila, detiene el programa
- Al sacar un terminal distinto a $, lo quita de la pila y avanza el puntero de la entrada
- Al sacar un no-terminal, se revisa la tabla, y si aparece una entrada para el elemento de la pila actual y el símbolo de la hilera, lo sustituye en la pila
- Si aparece un error para el elemento de la pila actual y el símbolo de la hilera, se detiene el programa y muestra error
(6/9)
Las funciones "Primero" y "Siguiente"
- Estas funciones ayudan a construir un parser predictivo como el de arriba, en particular la tabla gramatical de parsing predictivo
- Primero(α) indica todas las posibles combinaciones de tokens que podrían estar antes de las hileras generadas por α
- Siguiente(β) indica todas las posibles combinaciones de tokens que podrían estar después de las hileras generadas por β
(7/9)
La función Primero
- Si X es terminal, Primero(X) es ese terminal
- Si hay X → ϵ, a Primero(X) se añade ϵ
- Si X es no terminal, por cada producción X → Y1, Y2... Yn, a Primero(X) agregue Primero(Yi)
- Si todo Yi contiene ϵ, a Primero(X) se añade ϵ
(8/9)
La función Siguiente
- Siguente se calcula sólo para los no terminales
- Primero requiere calcular todos los Primero(X)
- A partir del símbolo inicial S:
- A Siguiente(S) se le agrega $
- Si hay una producción de la forma A→αBβ, a Siguiente(B) se le agrega todo Primero(β), excepto ϵ que no nos interesa
- Si hay una producción de la forma A→αB, o una A→αBβ tal que ϵ pertenezca a Primero(β), a Siguiente(B) se le agrega Siguiente(A)
(9/9)
Creación de tabla de parsing predictivo
- Para cada producción A → α:
- Para cada terminal a en Primero(α), la posición (A, a) será ocupada por A → α
- Si ϵ forma parte de Primero(α), por cada terminal b en Siguiente(A), se agrega A → α a posición (A, b)
- Si ϵ forma parte de Primero(α) y además $ forma parte de Siguiente(A), se agrega A → α a la posición (A, $)
- Los espacios que queden en blanco serán marcados como errores
- Si se requirió más de una entrada para cualquier posición (A, a), entonces la gramática no es LL(1), y viceversa