Tarea Nº 2 Compiladores • Relacionar la sintaxis con las gramáticas independientes de contexto. La gramática independiente de contexto sirve para reconocer de una manera especifica la sintaxis de un lenguaje. La gramática independiente de contexto se divide en los siguientes componentes: * Un conjunto de componentes léxicos (símbolos terminales). * Un conjunto de símbolos no terminales. * Un conjunto de producciones. * La notación de uno de los símbolos no terminales como símbolo inicial. • Explicar los problemas de ambigüedad, asociatividad y precedencia en operadores. En la ambigüedad se debe tener cuidado con estructura de una cadena con respecto a la gramática, ya que está puede tener más de un árbol que genere la misma cadena de componentes léxicos. Para saber si existe ambigüedad se necesita encontrar una cadena de componentes léxicos que posea más de un desarrollo en componentes del analizador sintáctico, es decir, que tenga más de un árbol. Para la compilación es necesario que nuestras gramáticas sean no ambiguas y de serlo que posean reglas adicionales para resolver dicha ambigüedad. La asociatividad posee una jerarquía, en el caso de trabajar con paréntesis se usa la asociatividad por la izquierda y se usa la asociatividad por la derecha cuando se trabaja con el operador asignación . • Describir en qué consiste la traducción dirigida por la sintaxis. Aquí se presenta la definición dirigida por la sintaxis para especificar las traducciones para las construcciones de lenguajes de programación. Esta especifica la traducción de una construcción en función de atributos asociados con sus componentes sintácticos. Para especificar la traducción, se introduce también una notación más orientada a procedimientos, denominada esquema de traducción. La definición dirigida por la sintaxis utiliza gramática independiente del contexto para especificar la estructura sintáctica de entrada. A cada símbolo se le asocian un conjunto de atributos y a cada producción, reglas semánticas para calcular valores de los atributos asociados con los símbolos de dichas producciones. La traducción básicamente es una transformación de la entrada en una salida mediante un numero de pasos. La salida de una entrada r cualquiera, se realiza de la forma: 1º− Se construye un árbol de análisis sintáctico para la entrada r. 2º− Luego para un cierto nodo n del árbol de análisis sintáctico que esta etiquetado por X, se escribe X.a para indicar el valor del atributo a de Xen el nodo n. El valor de X.a en n se calcula pro la regla semántica para el atributo a en la prod. X.

1

• Describa el Análisis sintáctico y su relación con los contenidos del curso. El análisis sintáctico determina si una cadena de componentes léxicos, proveniente del analizador léxico, puede ser generada por una gramática. Si el analizador sintáctico pude construir un árbol se podrá garantizar que la traducción es correcta. Para cualquier gramática, se puede construir un analizador sintáctico. La mayoría de estos métodos de análisis son de dos clases los métodos descendente y ascendente,esto hace referencia en la sentido en que construyen los nodos del árbol de análisis sintáctico. En el primero la construcción se inicia en la raíz de árbol y avanza hacia las hojas. En el segundo la construcción se inicia en las hojas y avanza hacia la raíz. La diferencia entre uno y otro es que en el primero se pueden construir manualmente analizadores más eficiente con mayor facilidad mientras que en el segundo se puede manejar una mayor cantidad de gramáticas y esquemas de traducción. En relación con la materia de este y otros cursos vemos la aparición de árboles y también que es posible llevar el método descenderte a forma de autómatas. Puesto que siguiendo los pasos para la búsqueda del algoritmo descendente, nos permite trabajar con grafos puesto que estos también son algoritmos. • Describa el Análisis léxico y su relación con los contenidos del curso. El analizador léxico lee y convierte una cadena de entrada en componentes léxicos los cuales son leídos por analizador sintáctico. Más específicamente el analizador léxico puede reducir el código de entrada, eliminado los espacios en blando como los comentarios, reduciendo así la cadena de componentes léxicos. Con respecto del curso podemos pensarlo como una pila. • Explicar el concepto de Máquinas de pila y su relación con las tablas de símbolos. Las maquinas de pila se encuentran en la parte inicial de un compilador y son una representación intermedia del programa fuente. Estas se usan para almacenar datos temporales y evaluar expresiones tales como adición y sustracción. La tabla de símbolos son estructuras de datos que almacenan toda la información de los identificadores del lenguaje fuente. Esta tabla le proporciona información a la maquina de pila. • Copiar los programas dados en las páginas 74 a la 79 /**************** global.h ****************************** #include #include #define TAMBUFF 128 #define NINGUNO −1 #define FDC '\0' #define NUM 256 #define DIV 257 #define MOD 258 2

#define ID 259 #define FIN 260 int valcomplex; int numlinea; struct entrada{ char *aplex; int complex; }; struct entrada tablasimb[]; /**************** analizlex.c ****************************** #include "global.h" char buflex[TAMBUFF]; int numlinea=1; int valcomplex=NINGUNO; int analex() { int t; while(1){ t=getchar(); if(t==' '||t=='\t') ; else if (t=='\n') numlinea=numlinea+1; else if (isdigit(t)){ ungetc(t,stdin); scanf("%d", &valcomplex);

3

return NUM; } else if(isalpha(t)){ int p,b=0; while (isalnum(t)){ buflex[b]=t; t = getchar(); b=b+1; if(b>=TAMBUFF) erro("error del compilador"); } buflex[b]=FDC; if(t!=EOF) ungetc(t, stdin); p=busca(buflex); if(p==0) p=inserta(buflex,ID); valcomplex=p; return tablasimb[p].complex; } else if (t==EOF) return FIN; else { valcomplex= NINGUNO; return t; }

4

} } /**************** analizsint.c ****************************** #include "global.h" int preanalisis; analsint() { preanalisis=analex(); while(preanalisis!=FIN){ expr();parea(';'); } } expr() {int t; termino(); while(1) switch (preanalisis){ case '+': case '−': t= preanalisis; parea (preanalisis); termino();emite (t, NINGUNO); continue; default: return; } } termino()

5

{ int t; factor(); while(1) switch (preanalisis){ case '*': case '/':case DIV:case MOD: t= preanalisis; parea (preanalisis); factor(); emite(t, NINGUNO); continue; default: return; } } factor() { switch(preanalisis){ case '(': parea('(');expr();parea(')');break; case NUM: emite(NUM,valcomplex);parea(NUM);break; case ID: emite(ID,valcomplex);parea(ID);break; default: error("error de sintaxis"); } }

6

parea(t) int t; { if(preanalisis==t ) preanalisis = analex(); else error("error de sintaxis"); } /**************** emisor.c ****************************** #include "global.h" emite (t, tval) int t, tval; { switch(t){ case '+':case'−':case '*':case '/': printf("%c\n",t); break; case DIV: printf("DIV\n");break; case MOD: printf("MOD\n");break; case NUM: printf("%d\n",tval);break; case ID: printf("%s\n",tablasimb[tval].aplex);break; default: printf("complex %d,valcomplex %d\n", t, tval); }

7

} /**************** simbolos.c ****************************** #include "global.h" #define MAXLEX 999 #define MAXSIMB 100 char lexemas[MAXLEX]; int ultcar =−1; struct entrada tablasimb[MAXSIMB]; int ultent =0; int busca(s) char s[]; { int p; for(p=ultent;p>0;p=p−1) if(strcmp(tablasimb[p].aplex,s)==0) return p; return 0; } int inserta(s,clex) char s[]; int clex; { int lon; lon = strlen(s); if(ultent+1>=MAXSIMB) error("tabla de simbolos llena");

8

if(ultcar + lon + 1>MAXLEX) error("matriz de lexemas llena"); ultent = ultent + 1; tablasimb[ultent].complex=clex; tablasimb[ultent].aplex=&lexemas[ultcar +1]; ultcar = ultcar + lon + 1; strcpy(tablasimb[ultent].aplex,s); return ultent; } /**************** inic.c ****************************** #include "global.h" struct entrada palsclave[]={ "div",DIV, "mod",MOD, 0, 0 }; inic() {struct entrada *p; for(p=palsclave; p−>complex;p++) inserta(p−>aplex,p−>complex); } /**************** error.c ****************************** #include "global.h" error(m) char *m; {

9

fprintf(stderr, "linea %d: %s\n", numlinea,m); exit(1); } /**************** principal.c ****************************** #include "global.h" main() { inic(); analsint(); exit(0); }

10