6 Análisis Sintáctico
6.1 Funciones del analizador sintáctico.
En el modelo del compilador, el analizador sintáctico obtiene una cadena de componentes léxicos del analizador léxico, y comprueba si la cadena puede ser generada por la gramática del programa fuente.
En nuestro modelo de compilador, el analizador sintáctico obtiene una cadena de tokens del analizador léxico, como se muestra en la figura, y verifica que la cadena de nombres de los tokens pueda generarse mediante la gramática para el lenguaje fuente. Esperamos que el analizador sintáctico reporte cualquier error sintáctico en forma inteligible y que se recupere de los errores que ocurren con frecuencia para seguir procesando el resto del programa. De manera conceptual, para los programas bien formados, el analizador sintáctico construye un árbol de análisis sintáctico y lo pasa al resto del compilador para que lo siga procesando. De hecho, el árbol de análisis sintáctico no necesita construirse en forma explícita, y a que las acciones de comprobación y traducción pueden intercalarse con el análisis sintáctico, como veremos más adelante. Por ende, el analizador sintáctico y el resto de la interfaz de usuario podrían implementarse sin problemas mediante un solo módulo.
 |
6.2 Árbol de derivación.
Es una representación gráfica (en forma de árbol invertido) de un proceso de derivación en una gramática. Se define el árbol de derivación como sigue:
- la raíz del árbol será el símbolo inicial de la gramática
- los nodo interiores del árbol están etiquetados por los símbolos no terminales
- las hojas están etiquetadas por símbolos terminales
- si un nodo interior etiquetado por A, posee como hijos los nodos etiquetados por X1,X2, …Xn , entonces A→ X1,X2, …Xn es una producción de la gramática, en donde Xi , representa símbolo terminal o no terminal.
Características del árbol de Derivación:
6.3 Formas normales de Chomsky.
Una gramática formal está en Forma normal de Chomsky si todas sus reglas de producción son de alguna de las siguientes formas:
A → BC o
A → a o
donde A, B y C son símbolos no terminales (o variables) y α es un símbolo terminal.
Todo lenguaje independiente del contexto que no posee a la cadena vacía, es expresable por medio de una gramática en forma normal de Chomsky (GFNCH) y recíprocamente. Además, dada una gramática independiente del contexto, es posible algorítmicamente producir una GFNCH equivalente, es decir, que genera el mismo lenguaje.
Sea G = (∑ N, ∑T, P, $) una gramática con P ⊂ ∑N X (∑N U ∑T)* y X Є ∑N un símbolo no-terminal (o una variable). Podemos clasificar tales símbolos X en tres clases:
Una gramática formal está en Forma normal de Chomsky si todas sus reglas de producción son de alguna de las siguientes formas:
A → BC o
A → a o
donde A, B y C son símbolos no terminales (o variables) y α es un símbolo terminal.
Todo lenguaje independiente del contexto que no posee a la cadena vacía, es expresable por medio de una gramática en forma normal de Chomsky (GFNCH) y recíprocamente. Además, dada una gramática independiente del contexto, es posible algorítmicamente producir una GFNCH equivalente, es decir, que genera el mismo lenguaje.
Sea G = (∑ N, ∑T, P, $) una gramática con P ⊂ ∑N X (∑N U ∑T)* y X Є ∑N un símbolo no-terminal (o una variable). Podemos clasificar tales símbolos X en tres clases:
Variables accesibles.
Variables generativas.
Variables útiles.
6.4 Diagramas de sintaxis
Los diagramas sintácticos, de sintaxis o diagramas del ferrocarril son una forma de representar una gramática libre de contexto. Representan una alternativa gráfica para la Forma de Backus-Naur (BNF, por sus siglas en inglés) o la Forma Extendida de Backus-Naur (EBNF, por sus siglas en ingles).
Los diagramas de ferrocarril son más comprensibles para la mayoría de la gente. Alguna parte de la popularidad del formato de intercambio de datos JSON se debe a su representación en los diagramas de ferrocarril.
Un segundo método alternativo para desplegar las producciones de ciertas gramáticas de tipo 2 es el diagrama de sintaxis. Ésta es una imagen de las producciones que permite al usuario ver las sustituciones en forma dinámica, es decir, verlas como un movimiento a través del diagrama. En la figura 10.5 se ilustrará los diagramas que resultan de la traducción de conjuntos de producciones típicos, que son, por lo general, todas las producciones que aparecen en el lado derecho de algún enunciado BNF.
Los diagramas sintácticos, de sintaxis o diagramas del ferrocarril son una forma de representar una gramática libre de contexto. Representan una alternativa gráfica para la Forma de Backus-Naur (BNF, por sus siglas en inglés) o la Forma Extendida de Backus-Naur (EBNF, por sus siglas en ingles).
Los diagramas de ferrocarril son más comprensibles para la mayoría de la gente. Alguna parte de la popularidad del formato de intercambio de datos JSON se debe a su representación en los diagramas de ferrocarril.
Un segundo método alternativo para desplegar las producciones de ciertas gramáticas de tipo 2 es el diagrama de sintaxis. Ésta es una imagen de las producciones que permite al usuario ver las sustituciones en forma dinámica, es decir, verlas como un movimiento a través del diagrama. En la figura 10.5 se ilustrará los diagramas que resultan de la traducción de conjuntos de producciones típicos, que son, por lo general, todas las producciones que aparecen en el lado derecho de algún enunciado BNF.
6.5 Eliminación de la ambigüedad
Una GLC es ambigua si existe una cadena w Є L(G) que tiene más de una derivación por la izquierda o más de una derivación por la derecha o si tiene dos o más arboles de derivación .
En casi de y que toda cadena w Є L (G) tenga un único árbol de derivación no es ambigua.
Ejemplo: La gramática S → aS| Sa | a es ambigua porque aa tiene dos derivaciones por la izquierda S Þ aS Þ aa S Þ Sa Þ aa.
Una GLC es ambigua si existe una cadena w Є L(G) que tiene más de una derivación por la izquierda o más de una derivación por la derecha o si tiene dos o más arboles de derivación .
En casi de y que toda cadena w Є L (G) tenga un único árbol de derivación no es ambigua.
Ejemplo: La gramática S → aS| Sa | a es ambigua porque aa tiene dos derivaciones por la izquierda S Þ aS Þ aa S Þ Sa Þ aa.
6.7 Tipos de analizadores sintácticos
Analizador Descendente:
Se construye el árbol de análisis sintético partiendo del símbolo inicial y aplicando las producciones mediante derivaciones por la izquierda, el símbolo a expandir es el que esta mas a la izquierda.
Analizador Ascendente:
Se construye el árbol de análisis sintético partiendo de la frase a reconocer y aplicando las producciones mediante reducciones hasta llegar al símbolo inicial de la gramática.
Analizador Descendente:
Se construye el árbol de análisis sintético partiendo del símbolo inicial y aplicando las producciones mediante derivaciones por la izquierda, el símbolo a expandir es el que esta mas a la izquierda.
Analizador Ascendente:
Se construye el árbol de análisis sintético partiendo de la frase a reconocer y aplicando las producciones mediante reducciones hasta llegar al símbolo inicial de la gramática.
6.8 Manejo de errores.
Un compilador es un sistema que en la mayoría de los casos tiene que manejar una entrada incorrecta. Sobre todo en las primeras etapas de la creación de un programa, es probable que el compilador se utiliza para efectuar las características que debería proporcionar un buen sistema de edición dirigido por la sintaxis, es decir, para determinar si las variables han sido declaradas antes de usarla, o si faltan corchetes o algo así.
Por lo tanto, el manejo de errores es parte importante de un compilador y el escritor del compilador siempre debe tener esto presente durante su diseño.
Errores Sintácticos.
Muchos errores de naturaleza sintáctica Recuperación: Al producirse un error el compilador debe ser capaz de informar del error y seguir compilando. (Ideal).
El manejo de errores de sintaxis es el más complicado desde el punto de vista de la creación de compiladores. Nos interesa que cuando el compilador encuentre un error, se recupere y siga buscando errores. Por lo tanto el manejador de errores de un analizador sintáctico debe tener como objetivos:
Muchos errores de naturaleza sintáctica Recuperación: Al producirse un error el compilador debe ser capaz de informar del error y seguir compilando. (Ideal).
El manejo de errores de sintaxis es el más complicado desde el punto de vista de la creación de compiladores. Nos interesa que cuando el compilador encuentre un error, se recupere y siga buscando errores. Por lo tanto el manejador de errores de un analizador sintáctico debe tener como objetivos:
- Indicar los errores de forma clara y precisa. Aclarar el tipo de error y su localización.
- Recuperarse del error, para poder seguir examinando la entrada.
- No ralentizar significativamente la compilación.
Errores semánticos.
Un lenguaje con comprobación fuerte de tipos es capaz de garantizar que los programas se pueden ejecutar sin errores de tipo, por lo que los errores de tipo se detectarán siempre en tiempo de compilación.
Como mínimo, ante un error, un comprobador de tipos debe informar de la naturaleza y posición del error y recuperarse para continuar con la comprobación del resto del programa a analizar.
Como mínimo, ante un error, un comprobador de tipos debe informar de la naturaleza y posición del error y recuperarse para continuar con la comprobación del resto del programa a analizar.
6.9 Generadores de analizadores sintácticos
ANTLR:
ANTLR:
(ANother Tool for Language Recognition; en español "otra herramienta para reconocimiento de lenguajes") es una herramienta creada principalmente por Terence Parr, que opera sobre lenguajes, proporcionando un marco para construir reconocedores (parsers), intérpretes, compiladores y traductores de lenguajes a partir de las descripciones gramaticales de los mismos (conteniendo acciones semánticas a realizarse en varios lenguajes de programación).
GNU bison:
GNU bison:
Es un programa generador de analizadores sintácticos de propósito general perteneciente al proyecto GNU disponible para prácticamente todos los sistemas operativos, se usa normalmente acompañado de flex aunque los analizadores léxicos se pueden también obtener de otras formas.
Grammatica:
Grammatica:
Es un generador de analizadores sintácticos de C# y Java libre. Es similar a otras herramientas como Yacc o ANTLR. Grammatica soporta el algoritmo LL(k) para gramáticas con un número ilimitado de tokens de anticipación. Está bastante bien probado, y ha sido auto compilado desde la versión 0.1. La documentación contiene una lista completa de características, así como una comparación con otros generadores de analizadores.
JavaCC:
JavaCC:
(Java Compiler Compiler) es un generador de analizadores sintácticos de código abierto para el lenguaje de programación Java. JavaCC es similar a Yacc en que genera un parser para una gramática presentada en notación BNF, con la diferencia de que la salida es en código Java. A diferencia de Yacc, JavaCC genera analizadores descendentes (top-down), lo que lo limita a la clase de gramáticas LL (K) (en particular, la recursión desde izquierda no se puede usar). El constructor de árboles que lo acompaña, JJTree, construye árboles de abajo hacia arriba (bottom-up).
Yacc:
Yacc:
Es un programa para generar analizadores sintácticos. Las siglas del nombre significan Yet Another Compiler-Compiler, es decir, "Otro generador de compiladores más". Genera un analizador sintáctico (la parte de un compilador que comprueba que la estructura del código fuente se ajusta a la especificación sintáctica del lenguaje) basado en una gramática analíticaescrita en una notación similar a la BNF. Yacc genera el código para el analizador sintáctico en el Lenguaje de programación C.
Comentarios
Publicar un comentario