| INSTITUTO POLITÉCNICO NACIONAL ESCUELA SUPERIOR DE CÓMPUTO |

Introducción | Contenido | Bibliografía

Introducción
Contenido
UNIDAD I
UNIDAD II Introducción 2.1 Estructura de un Compilador 2.1.1 Función del analizador léxico 2.1.2 Función del analizador sintáctico

2.1.3 Tabla de Símbolos

2.1.4 Función del analizador Semántico

2.1.5 Etapa de análisis

2.1.6 Etapa de Síntesis

UNIDAD III
UNIDAD IV
UNIDAD V
UNIDAD VI
UNIDAD VII
UNIDAD VIII
UNIDAD IX
PROBLEMARIO
Bibliografía

> 2.1.2 Función del Analizador Sintáctico

> > Un analizador léxico reconoce los símbolos dentro del flujo de caracteres del código fuente, estas secuencias de símbolos son después analizadas secuencialmente por el analizador sintáctico, el cual decide si una secuencia de símbolos será aceptada por el lenguaje de programación en cuestión.

> > La función principal de un analizador sintáctico es encontrar un árbol de análisis sintáctico para una cadena de componentes léxicos, que tenga como raíz el axioma de la gramática, en caso de éxito la cadena pertenece al lenguaje, en caso contrario se emite un mensaje de error y/o recuperación.

> > Un árbol de análisis sintáctico indica como a partir del axioma de la gramática se deriva una frase (cadena) del lenguaje. Dada una gramática independiente del contexto, un árbol de análisis sintáctico es un árbol tal que:

> > - La raíz está marcada con el símbolo inicial.

> > - Cada hoja está marcada con un símbolo no terminal.

> > - Cada nodo está marcado con un símbolo terminal.

> > A continuación se muestra la ubicación de un analizador sintáctico en el modelo del compilador.

> > Existen básicamente dos métodos para efectuar el análisis sintáctico: el análisis sintáctico ascendente y el análisis sintáctico descendente.

> > Los analizadores sintácticos descendentes construyen árboles de análisis desde arriba (raíz) hacia abajo (las hojas), mientras que los analizadores sintácticos ascendentes comienzan en las hojas y suben hacia la raíz.

> > El Análisis Descendente comienza desde el axioma, mediante derivaciones de las reglas de la gramática se encuentra el árbol sintáctico para la cadena de componentes léxicos de entrada, éste comienza a definirse por la raíz.

> > El Análisis Ascendentes parte de la cadena de componentes léxicos, mediante reducciones se llega al axioma encontrando también el árbol de análisis sintáctico, el cual comienza a definirse por las hojas.

> > Los analizadores sintácticos descendentes y ascendentes más eficientes se basan en las gramáticas LL y gramáticas LR respectivamente.

> > Definimos una gramática que acepta expresiones aritméticas como .

> > símbolos terminales
> > símbolos no terminales

> > Cada expresión es una secuencia de términos separados por “+” o”-”, considerando la derivación por la izquierda de :

> > Derivación por la derecha:

> Árbol de análisis sintáctico para la expresión

> Como podemos ver ya sea por la derivación a la derecha o a la izquierda, se produce el mismo árbol de análisis sintáctico.

> Es importante mencionar que en este caso la gramática utilizada es una gramática ambigua. Una gramática es ambigua cuando produce más de un árbol de derivación.

> Por ejemplo, la gramática siguiente es ambigua:

> Suponiendo la sentencia .

> Entrada:

> El significado semántico es diferente, cuando no existe una única traducción posible, es decir, se genera código diferente.

> No existe un algoritmo que determine con certeza en un plazo finito de tiempo si una gramática es ambigua o no. A lo sumo se han desarrollado algunas condiciones que de cumplirse determinan la ambigüedad, pero en el caso de no cumplirse no se puede decir que la gramática es no ambigua.

> Una forma de evitar las gramáticas ambiguas es:

> 1. Transformar la gramática.
> ó

> 2. Estableciendo precedencias entre operadores y de asociatividad.

> Se puede eliminar la ambigüedad transformando la gramática agrupando todos los operadores de igual precedencia en grupos y asociando a cada uno una regla, de forma que los que tengan menor precedencia aparezcan más cercanos al símbolo de inicio, precedencia en cascada. Esto conlleva el aumento de la complejidad de la gramática y con ello en la del árbol sintáctico, es decir, la gramática deja de ser intuitiva.

> Si la gramática ambigua:

> La transformamos, esta gramática ya no será ambigua:

> Ejercicios:

> Análisis Sintáctico Descendente.

> La gramática , que define los enteros no negativos :

> La frase a analizar 123 es la raíz del árbol

> En el primer paso se encuentra la producción, con esto se obtiene el inicio del árbol sintáctico.

> En el siguiente paso se encuentra de nuevo la misma producción.

> Después encontramos la producción.

> Ahora se encuentra la producción que establece la conexión con el primer elemento de la frase dada.

> Posteriormente se encuentra la producción que establece la conexión con el segundo elemento de la frase.

> Y por último el árbol sintáctico se completa con la producción.

> Como se aprecia en el ejercicio, el árbol crece de arriba hacia abajo conforme se lee la frase.

> Haciendo el análisis ascendente del mismo ejemplo sería, de nuevo solo conocemos la frase y la raíz del árbol. En el primer paso se encuentra la reducción y se obtiene el inicio del árbol sintáctico.

> El siguiente paso está en la reducción de.

> El tercer paso reduce el segundo elemento.

> Entonces se aplica la reducción .

> Se reduce el último elemento de la frase.

> Para concluir el árbol se completa con la reducción .

> Atrás Siguiente

##### Introducción / Contenido / Unidad I / Unidad II / Unidad III / Unidad IV / Unidad V / Unidad VI / Unidad VII / Unidad VIII / Unidad IX / Problemario / Bibliografía

##### Inicio

##### Créditos

José Sánchez Juárez, Andrés Ortigoza Campos, Fabiola Ocampo Botello