Introducción al análisis sintáctico

Tema 3 Introducci´n al an´lisis o a sint´ctico a
Bibliograf´ ıa: Aho, A.V., Sethi, R., Ullman, J.D. (1990), Compiladores: principios, t´cnicas y herramientas, Tema 4, p´g.: 163-186. e a Louden, K.C. (1997), Compiler Construction: Principles and Practice, Tema 3, p´ginas: 93-140. a Contenidos: 1. El proceso de an´lisis sint´ctico. a a 2. Especificaci´n sint´ctica de los lenguajes de programaci´n:o a o a a) Gram´ticas independientes del contexto versus expresiones regulares. b) Gram´ticas independientes del contexto versus gram´ticas a a dependientes del contexto. 3. Derivaciones y ´rboles sint´cticos. a a 4. Gram´ticas limpias y bien formadas. a u a 5. El problema de la ambig¨edad en las gram´ticas. Eliminaci´n: o a) Mediante reglas de precedencia. b) Mediante transformaci´n. o o e a a 6.Clasificaci´n de los m´todos de an´lisis sint´ctico.
71

72

´ ´ ´ TEMA 3. INTRODUCCION AL ANALISIS SINTACTICO

3.1.

El proceso de an´lisis sint´ctico a a

Funciones del analizador sint´ctico: a Comprobar si la cadena de componentes l´xicos proporcionae da por el analizador l´xico puede ser generada por la gram´tica e a que define el lenguaje fuente (Gram´tica Independiente del aContexto, GIC). Construir el ´rbol de an´lisis sint´ctico que define la estruca a a tura jer´rquica de un programa y obtener la serie de derivaa ciones para generar la cadena de componentes l´xicos. El e ´rbol sint´ctico se utilizar´ como representaci´n intermedia a a a o en la generaci´n de c´digo. o o Informar de los errores sint´cticos de forma precisa y siga nificativa y deber´ estar dotado de unmecanismo de recua peraci´n de errores para continuar con el an´lisis. o a
gram. indep. contexto

programa fuente

analizador léxico

componente léxico

analizador sintáctico

analizador
árbol semántico análisis sintáctico

obtén siguiente componente léxico

gestor errores

tabla de símbolos

El an´lisis sint´ctico se puede considerar como una funci´n que a a o toma como entradala secuencia de componentes l´xicos producie da por el an´lisis l´xico y produce como salida el ´rbol sint´ctico. a e a a En la realidad, el an´lisis sint´ctico hace una petici´n al an´lisis a a o a l´xico del componente l´xico siguiente en la entrada (los s´ e e ımbolos terminales) conforme lo va necesitando en el proceso de an´lisis, a conforme se mueve a lo laro de la gram´tica. a Reconocedorversus analizador sint´ctico a

´ ´ ´ 3.2. ESPECIFICACION SINTACTICA DE LOS LENGUAJES DE PROGRAMACION73

Un reconocedor trata de determinar simplemente si la cadena puede o no ser generada por la gram´tica (salida boolena). Poa dr´ ıamos preguntar algo m´s. Si queremos reconocer las estruca turas propias de los lenguajes de programaci´n en el fichero de o entrada para guiar la traducci´n, esnecesario conocer su estruco tura jer´rquica, el ´rbol de an´lisis sint´ctico. a a a a

3.2.

Especificaci´n sint´ctica de los lenguajes o a de programaci´n o

La mayor´ de las construcciones de los lenguajes de programaci´n ıa o se pueden representar con una gram´tica independiente del cona texto (GIC). La mayor´ de las construcciones de los lenguajes de ıa programaci´n implican recursividad yanidamientos. o G = {S, VT , VN T , P }, S: el axioma o s´ ımbolo de inicio VT : conjunto de terminales, los componentes l´xicos e VN T : conjunto de no-terminales P: conjunto de reglas de producci´n de la forma o VN T → X1 , . . . , Xn , con Xi ∈ (VT ∪ VN T ) Pregunta: Si las expresiones regulares son un caso particular de GIC, por qu´ no se incluye la especificaci´n l´xica como e o e parte de lasintaxis? Los AFD son muy sencillos de implementar y son muy eficientes frente a los aut´matas a pila necesarios para reconocer las o GIC, la eficiencia del traductor se ver´ comprometida. ıa ¿Expresiones regulares o gram´ticas independientes del a contexto? Las expresiones regulares no permiten construcciones anidadas tan comunes en los lenguajes de programaci´n: par´ntesis equilio e brados,...