Análisis sintáctico: Análisis descendente
Introducción
¡Hola!
Me siento muy feliz al saber que sigues aprovechando este curso, espero que lo sigas disfrutando, por lo tanto te invito a comenzar nuestra octava clase.
En esta sesión aprenderemos sobre
Comencemos con energía y entusiasmo.
¡Sigue adelante!
Desarrollo del tema
Gramática Libre de Contexto (CFG):
- Es una gramática formal que consiste de reglas de producción para describir todas las cadenas posibles de un lenguaje formal
- Terminales
- Símbolos básicos que componen las cadenas.
- Un sinónimo es token.
- No terminales.
- Variables sintácticas que denotan conjuntos de cadenas.
- Símbolo de inicio.
- Es un no terminal.
- Variable sintáctica que denota el código generado por la gramática.
- Reglas de producción.
- Especifican la forma en que los terminales y no terminales se combinan para formar cadenas.
- Constan de: un no terminal, el símbolo →, un cuerpo
Derivación:
- Aplicación de las reglas de la gramática para transformar el símbolo de inicio en una cadena.
- Prueba que una cadena pertenece al lenguaje generado por la gramática.
- Regla de producción:
- Derivación:
Ambigüedad:
- Una derivación puede ser representada como un árbol sintáctico (AST).
- La ambigüedad ocurre cuando hay más de un árbol sintáctico.
- Regla de producción:
- Árboles sintácticos para id + id * id:
Ambigüedad de IF-ELSE:
La instrucción if-else usualmente causa ambigüedad en la gramática.
Los compiladores suelen solucionarla asociando el else al último if
Otra manera es dar una prioridad más alta a la forma if-else
- Gramática ambigua:
- Cadena:
- Cómo Eliminar Ambigüedad:
- Gramática no ambigua para if-then-else
La parte entre then y else no debe terminar o contener un then abierto
- Recursión Izquierda:
- Cuando el símbolo no terminal aparece a la izquierda de su producción:
- Los métodos de análisis descendente no pueden manejar la recursión izquierda.
- Por lo tanto se debe eliminar la recursión izquierda.
- Eliminar Recursión Izquierda:
- Eliminar recursión izquierda directa:
- Si A tiene producciones de la forma:
- Eliminar recursión izquierda directa:
donde ningún βi inicia con A
Entonces las producciones de A pueden ser reemplazadas por:
Ejemplo:
- Eliminación de la recursión izquierda
Se sustituye S en A
Gramática sin recursión izquierda
Análisis Sintáctico:
- Técnicas de Análisis sintáctico.
- Análisis descendente (TD)
Encontrar las derivaciones izquierdas de una cadena de entrada por la búsqueda de árboles sintácticos usando una expansión descendente de las reglas de gramática.
Los tokens son consumidos de izquierda a derecha.
- Análisis descendente con retroceso
- Análisis descendente predictivo (LL(k))
- Análisis ascendente (BU)
- LR es un tipo especial de analizador
Transformar la cadena de entrada aplicando las reglas hasta llegar al símbolo inicial.
Análisis Descendente (TD):
- Construir el árbol de análisis iniciando por el nodo raíz
- Es equivalente a encontrar una derivación izquierda de una cadena de entrada.
- Gramática:
- Análisis de id+id*id
Conclusión
Para recordar:
Has finalizado la clase y tus esfuerzos hasta el momento comenzarán a dar sus frutos en pasos mucho más grandes a partir de aquí, no dejes que la curiosidad por comprender lo que te rodea sea opacada por el conformismo, sigue esforzándote, Revisa el material complementario y realiza las actividades propuestas. Te encuentro en tu siguiente clase, hasta entonces.