1. Bibliografía
1.1. Gonzales, U. E. (2014). Análisis léxico y sintáctico. Obtenido de https://www.analisadoreslexsin.com
1.2. Arteaga Caballero Jorge Julián, E. H. (2010). Contenido de compiladores. Obtenido de unidad VII.-Implementación analizador léxico
1.3. Alfred V. Aho, R. S. (1990). Compiladores: principios, técnicas y herramientas.
1.4. Traductores y Compiladores con Lex/Yacc, Jflex/Cup y JavaCC – Sergi Gálvez Rojas
1.5. Aho, A.V., Sethi, R., Ullman, J.D. (1990), Compiladores: principios, técnicas y herramientas, Tema 3, páginas: 85-158.
1.6. Louden, K.C. (1997), Compiler Construction: Principles and Practice, Tema 2, páginas: 31-93.
1.7. Compiladores, A. y. (s.f.). Universidad Autónoma del Estado de Hidalgo. Obtenido de 3.2 Gramáticas Independientes del Contexto
2. Análisis Léxico - Sintáctico
2.1. Lee la secuencia de caracteres del programa fuente, caracter a caracter, y los agrupa para formar unidades con significado propio, los componentes léxicos
2.1.1. Para reconocer los identificadores se realiza mediante:
2.1.1.1. Bucles Anidados
2.1.1.1.1. Usamos una variable para almacenar el estado actual y una estructura tipo case doble anidada.
2.1.1.2. Tabla de Transiciones
2.1.1.2.1. Se asume que los campos en blancos son errores. Los estados de aceptación se marcan con una columna adicional.
2.2. Aspectos prácticos en la implementación de un analizador léxico
2.2.1. Gestión del buffer de entrada
2.2.1.1. El proceso de lectura de los caracteres de la entrada y formar los componentes léxicos es lo más costoso en tiempo en el proceso de traducción
2.2.2. Principio de máxima longitud
2.2.2.1. Se da prioridad al componente léxico de máxima longitud
2.2.3. Palabras reservadas versus identificadores
2.2.3.1. Para evitar tener un AFD demasiado grande las palabras reservadas se reconocen como identificadores
2.2.4. Entrada de los identificadores en la Tabla de Símbolos
2.2.4.1. En lenguajes sencillos con solo variables globales y declaraciones, es normal implementar el scanner para que introduzca los identificadores en la Tabla de Símbolos conforme los va reconociendo, si es que no han sido ya introducidos
2.3. ¿Cómo se relacionan?
2.3.1. El análisis léxico es una subrutina del análisis sintáctico que devuelve el tipo de componente léxico y el lexema cada vez que es llamada.
2.3.1.1. Identificadores
2.3.1.1.1. Las palabras reservadas se reconocen como identificadores y antes de devolver un identificador se comprueba si es una palabra reservada o un identificador consultando en una tabla previamente inicializada con las palabras reservadas.
2.4. Pasos para la implementación
2.4.1. Diseñar una gramática determinista
2.4.1.1. La estructura sintáctica del lenguaje debe interpretarse de forma jerárquica. La cabeza de la regla pone nombre a la estructura sintáctica y el cuerpo define dicha estructura.
2.4.2. Diseñar los lexemas definidos en la gramática
2.4.2.1. Los lexemas con formas iterativas de caracteres pueden expresarse con expresiones regulares de tipo cierre. Por ejemplo, NUMERO : (DIGITO)+;.
2.4.3. Implementar una primera versión del analizador léxico-sintáctico en ANTLR
2.4.3.1. constituir el núcleo principal del parser ANTLR
2.4.4. Testar dicha versión
2.4.4.1. Construida la primera versión del analizador léxico-sintáctico, se procede a testarlo.
2.4.5. Anotar la gramática para construir árboles de sintaxis abstracta
2.4.5.1. Una vez testada la primera versión del analizador, se anota la gramática para que sea capaz de construir árboles de sintaxis abstracta.
2.4.6. Implementar la segunda versión del analizador léxico-sintáctico en ANTLR
2.4.6.1. Se construye la segunda versión del analizador sintáctico
2.4.7. Testar el analizador con distintas clases de sentencias del lenguaje
2.4.7.1. Construida la segunda versión del analizador léxico-sintáctico, se procede a testarlo.
2.5. Estructura del Analizador Sintáctico
2.5.1. sección de definiciones %{ /* delimitadores de código C */ %}
2.5.2. %% sección de reglas
2.5.3. %% sección de funciones de usuario
2.5.4. Similar a léxico pero en la sección de reglas se diferencia es que en el sintáctico se define la estructura o BNF gramatical para su jerarquización, y en la sección de definiciones el sintáctico define los Tokens.
3. Manejo de Errores
3.1. Manejo de Errores
3.1.1. Un error de sintaxis se detecta cuando el analizador sintáctico espera un símbolo que no corresponde al que se acaba de leer.
3.1.2. Los errores encontrados en las distintas fases de análisis se envían a un módulo denominado manejo de errores.
3.1.2.1. En el caso más sencillo puede ser un subprograma al que se le invoca enviándole el código de error, y que se encarga de escribir un mensaje con el error correspondiente, y el número de línea donde se ha producido, así como de cortar el proceso de traducción.
3.2. Funcionalidad
3.2.1. Debe informar de la presencia de errores con claridad y exactitud.
3.2.2. Se debe recuperar de cada error con la suficiente rapidez como para detectar errores posteriores.
3.2.3. No debe retrasar de manera significativa el procesamiento de programas correctos.
3.3. Sintaxis
3.3.1. void yyerror ( ) { //procesos a realizar }
4. Diseño de Gramática
4.1. Gramática N,T,P,S, es una gramática de contexto libre aceptada por el analizador sintáctico donde:
4.1.1. T= Terminales. Conjunto de tokens T, también llamados símbolos terminales, que son los símbolos básicos con los que se construyen cadenas.
4.1.2. N= No Terminales: Un conjunto de símbolos no terminales N también llamadas variables sintácticas, que denotan cadenas de tokens.
4.1.2.1. Cada símbolo no terminal representa un conjunto de cadenas, lo cual simplifica la definición del lenguaje generado por la gramática.
4.1.3. S= Axioma Inicial: En toda gramática existe un símbolo no terminal destacado, S pertenece a N, al que se lo conoce como el axioma o símbolo inicial.
4.1.4. P= Reglas de Producción: Estas producciones describen la forma en que se pueden combinar los símbolos terminales y no terminales para formar cadenas
5. Tabla de símbolos
5.1. Ejemplo
5.1.1. Supongamos que se desea hacer las siguiente operaciones matemáticas:
5.1.1.1. a = 2 * 2 --- b = 3 * a
5.1.1.1.1. En la segunda instrucción se necesita saber cuanto vale la variable "a", es decir, el valor de "a" debe estar guardado en algún sitio.
5.1.1.1.2. Aquí es donde entra en acción la tabla de símbolos y para guardar el valor de "a" se utiliza una lista de pares.
5.2. La tabla de símbolos es una estructura de datos que nos permite realizar operaciones de inserción, búsqueda y eliminación de información en varias construcciones de lenguaje fuente, la cual es analizada por el compilador originándose un código objeto.
5.2.1. ¿Cuándo se los utiliza?
5.2.1.1. Cuando se necesita saber sobre las variables del programa, información tal como: nombre, tipo, dirección de localización, tamaño, entre otras.
5.2.1.1.1. Se componen por:
5.3. Algunos analizadores lexicográficos no reconocen directamente las palabras reservadas, sino que sólo reconocen identificadores de usuario.
5.3.1. El analizador semántico efectúa las comprobaciones sensibles al contexto gracias a la tabla de símbolos
5.3.1.1. En la etapa de síntesis, el generador de código intermedio usa las direcciones de memoria asociadas a cada identificador para generar un programa equivalente al de entrada.
5.3.1.1.1. Cuando un lenguaje posee área de declaraciones y área de sentencias, la aparición de un identificador tiene una semántica bien diferente según el área en que se encuentre:
5.3.1.1.2. El analizador lexicográfico, cuando se encuentra un identificador desconoce en qué área lo ha encontrado, por lo que no resulta fácil incluir una acción léxica que discrimine entre realizar una inserción o una búsqueda; así, deberá ser el analizador sintáctico quien haga estas operaciones.
5.4. ¿Qué operaciones se pueden realizar?
5.4.1. crear ()
5.4.1.1. Crea una tabal vacía.
5.4.2. insertar (símbolo)
5.4.2.1. Añade a la tabla el símbolo dado.
5.4.3. buscar (nombre)
5.4.3.1. Devuelve el símbolo cuyo nombre coincide con el parámetro, en caso de que este símbolo no exista devuelve NULL.
5.4.4. imprimir ()
5.4.4.1. Visualiza por la salida estándar la salida de variables almacenadas en la tabla de símbolos junto con sus valores asociados.
5.5. ¿Cómo se inicializa?
5.5.1. Se puede inicializar con cierta información útil que puede almacenarse en una única estructura o en varias.
5.5.1.1. Ejemplo
5.5.1.1.1. Constantes: EXPRS, SUMA, A, EXPRESIONCALCULAR, entre otros.
5.5.1.1.2. Funciones de libreria: EXP, LOG, SQRT, entre otras.
5.5.1.1.3. Palabras Reservadas: Esto facilita el trabajo al lexicográfico, que tras reconocer un identificador lo busca en la tabla de símbolos, y si es palabra reservada devuelve un token asociado. Bien estructurado puede ser una alternativa más eficiente al lex tal y como lo hemos visto (hash perfecto).
5.5.1.2. Conforme van apareciendo nuevas declaraciones de identificadores, el analizador léxico, o el analizador sintáctico según la estrategia que sigamos, insertará nuevas entradas en la tabla de símbolos, evitando siempre la existencia de entradas repetidas.
6. Ejemplos
6.1. For (i>2 ; i>=5; i++)
6.1.1. Sample.l
6.1.1.1. %{ #include"y.tab.h" extern int yylval; %}
6.1.1.2. %% /* RULES SECTION */ "for" {return FOR;} "=" {return EQU;} "++" {return INC;} "--" {return DEC;}
6.1.1.3. /* RELATIONAL OPERATIONS: */ "<=" {return LE;} ">=" {return GE;} ">" {return GT;} "<" {return LT;} "!=" {return NE;} "==" {return EQ;} "(" {return OPBR;} ")" {return CLBR;} ";" {return SEMIC;} [0-9]+ {yylval=atoi(yytext);return NUM;} [a-zA-Z]+ {yylval=yytext[0];return ID;}
6.1.1.4. Sección de funciones c. %%
6.1.2. Sample.y
6.1.2.1. %{ #include<stdio.h> #include<stdlib.h> int yylex(); void yyerror(const char *s); %}
6.1.2.2. /* Definimos los token que serán retornados del analizador léxico*/ %token FOR NUM OPBR CLBR INC DEC ID SEMIC GE NE LT GT LE EQ EQU // Operadores y asociativos: %right '=' %left GE NE LT GT LE EQ %left '+' '-' %left '*' '/' %right '^'
6.1.2.3. %% S : ST { printf("\nACCEPTED\n"); system("pause");exit(0); } ST : FOR OPBR Expr1 SEMIC Expr2 SEMIC Expr3 CLBR | FOR OPBR SEMIC SEMIC CLBR // for( ; ; ) Expr1 : ID GT ID | ID GT NUM Expr2 : ID RELOP ID | ID RELOP NUM Expr3 : ID INC | ID DEC RELOP : GE | GT | EQ | LE | LT | NE ;
6.1.2.4. %% #include"lex.yy.c" int main() { yyparse(); return 0; }
6.1.3. Comandos Usados
6.1.3.1. yacc -d sample.y (# create y.tab.h, y.tab.c) flex sample.l (# create lex.yy.c) gcc -o ejer2 y.tab.c ejer2
6.2. While (i<5)
6.2.1. Sample.l
6.2.1.1. %{ #include"y.tab.h" extern int yylval; %}
6.2.1.2. %% /* RULES SECTION */ "WHILE" {return WHILE;} "=" {return EQU;}
6.2.1.3. /* RELATIONAL OPERATIONS: */ "<=" {return MEI;} ">=" {return MAI;} ">" {return MA;} "<" {return ME;} "!=" {return DI;} "==" {return EQ;} "(" {return OPBR;} ")" {return CLBR;} ";" {return SEMIC;} [0-9]+ {yylval=atoi(yytext);return NUM;} [a-zA-Z]+ {yylval=yytext[0];return ID;}
6.2.1.4. Sección de funciones c. %%
6.2.2. Sample.y
6.2.2.1. %{ #include<stdio.h> #include<stdlib.h> int yylex(); void yyerror(const char *s); %}
6.2.2.2. /* Definimos los token que serán retornados del analizador léxico*/ %token WHILE NUM OPBR CLBR ID SEMIC MA ME MAI MEI DI EQ EQU // Operadores y asociativos: %right '=' %left MA ME MAI MEI DI EQ %left '+' '-' %left '*' '/' %right '^'
6.2.2.3. %% S : ST { printf("\nACCEPTED\n"); system("pause");exit(0); } ST : WHILE OPBR Expr1 CLBR | WHILE OPBR CLBR // while ( ) Expr1 : ID RELOP ID | ID RELOP NUM RELOP : ME | MA | EQ | MAI | MEI | DI ;
6.2.2.4. %% #include"lex.yy.c" int main() { yyparse(); return 0; }
6.2.3. Comandos Usados
6.2.3.1. yacc -d sample.y (# create y.tab.h, y.tab.c) flex sample.l (# create lex.yy.c) gcc -o ejer2 y.tab.c ejer2