5.5 Diagramas de sintaxis 5.6 Eliminación de la ambigüedad. 5.7 Tipos de analizadores sintácticos 5.8 Generación de matriz predictiva (cálculo first y follow)
5.5 Diagramas de sintaxis
Los diagramas de sintaxis, también conocidos como diagramas de ferrocarril, son representaciones gráficas de las reglas de una gramática libre de contexto. Ofrecen una alternativa visual a las notaciones textuales como la Forma de Backus-Naur (BNF) o su versión extendida (EBNF). Estos diagramas facilitan la comprensión de la estructura sintáctica de un lenguaje al ilustrar cómo se pueden construir las cadenas válidas mediante rutas en el diagrama. Cada símbolo no terminal se representa por su nombre encerrado en un rectángulo, y los símbolos terminales se muestran en círculos o cajas con bordes redondeados. Las producciones con varias alternativas o repeticiones se representan mediante bifurcaciones o bucles en el diagrama.
5.6 Eliminación de la ambigüedad
Una gramática es ambigua si existe al menos una cadena que puede derivarse de más de una manera, es decir, tiene múltiples árboles de derivación o derivaciones por la izquierda o derecha. La ambigüedad puede causar interpretaciones conflictivas de las cadenas de entrada, complicando el proceso de análisis sintáctico. Para eliminar la ambigüedad, se pueden aplicar técnicas como:
Reescritura de la gramática: Modificar las reglas de producción para asegurar que cada cadena tenga una única derivación.
Factorización: Reestructurar las producciones para eliminar elecciones comunes y simplificar la gramática.
Eliminación de la recursividad por la izquierda: Reformular las reglas que presentan recursividad por la izquierda para evitar bucles infinitos durante el análisis.
Estas técnicas ayudan a transformar una gramática ambigua en una no ambigua, facilitando su análisis y procesamiento.
https://www.youtube.com/live/TI8N_4dvT7s?si=d8D61lmWCEj2K4FB
5.7 Tipos de analizadores sintácticos
Los analizadores sintácticos, o parsers, son herramientas que verifican si una secuencia de tokens cumple con las reglas de una gramática. Se clasifican principalmente en:
Analizadores descendentes (top-down): Construyen el árbol de derivación desde el símbolo inicial hacia las hojas, prediciendo las producciones a aplicar. Ejemplos incluyen:
Analizadores predictivos LL(k): Utilizan una cantidad fija de tokens de anticipación para tomar decisiones.
Descenso recursivo: Implementan funciones recursivas para cada regla de la gramática.
Analizadores ascendentes (bottom-up): Construyen el árbol de derivación desde las hojas hacia la raíz, reconociendo patrones en la entrada y reduciéndolos a no terminales. Ejemplos incluyen:
- Analizadores LR(k): Utilizan tablas de análisis para manejar gramáticas más complejas y pueden reconocer una amplia clase de lenguajes libres de contexto.
La elección del tipo de analizador depende de la complejidad de la gramática y de las necesidades específicas del lenguaje a procesar.
https://youtu.be/1kGX9N-D37c?si=2XRHt-9TwmZzPnBD
5.8 Generación de matriz predictiva (cálculo de conjuntos FIRST y FOLLOW)
En el análisis sintáctico predictivo, la matriz predictiva es una estructura que guía al analizador en la selección de la producción adecuada según el token actual de entrada. Para construir esta matriz, es esencial calcular los conjuntos FIRST y FOLLOW para cada símbolo no terminal de la gramática:
Conjunto FIRST(X): Incluye todos los terminales que pueden aparecer al inicio de alguna cadena derivada del no terminal X.
Conjunto FOLLOW(X): Contiene todos los terminales que pueden aparecer inmediatamente después del no terminal X en alguna derivación.
El cálculo de estos conjuntos se realiza de manera iterativa, analizando las producciones de la gramática y aplicando reglas específicas para determinar los símbolos que pertenecen a cada conjunto. Una vez obtenidos, se construye la matriz predictiva que indica, para cada par de no terminal y terminal, la producción que debe aplicarse, facilitando así el proceso de análisis sintáctico sin necesidad de retroceso.
Comentarios
Publicar un comentario