Compiladores 1 Argueta Cortes Jairo I.
Analizador Léxico Mendoza Gaytán José Trinidad
Universidad Nacional Autónoma de
México
Facultad de Ingeniería
Compiladores
Grupo 1
Analizador Sintáctico RECURSIVO
ALUMNOS:
ARGUETA CORTES JAIRO I.
MENDOZA GAYTAN JOSE TRINIDAD
PROFESORA:
ING. LAURA SANDOVAL M.
Lunes 26 de Octubre de 2009
Compiladores 2 Argueta Cortes Jairo I.
Analizador Léxico Mendoza Gaytán José Trinidad
INDICE
Análisis………………………………………………………….. 3
Estudio preliminar
1° PARTE Analizador Léxico……..……………………..3
Planeación………………………………………………….....4
Propuesta de servicios….……………………….……….5
Diseño…………………………………………………………….5
Expresiones regulares ………………………………….. 6
Desarrollo……………………………………………………… 7
Definición de tokens………..…………………………… 7
Técnicas de búsqueda e inserción…………………. 8
2° PARTE Parser Recursivo……..…………………….. 10
Diagramas de tren……..…………………………………. 10
Definición de gramáticas
y Conjuntos de Selección. ……..…..……………….. 12
Diseño………………………………………………………….. 12
Ejecución del PARSER AS-SQLex.c….……..……... 13
Compiladores 3 Argueta Cortes Jairo I.
Analizador Léxico Mendoza Gaytán José Trinidad
OBJETIVO GENERAL
Construir un Parser RECURSIVO que revise la sintaxis de la gramática SQL definida en clase la cual
se presenta al final del documento. Se incluye el analizador léxico escrito en LEX que genera,
además de los tokens, la cadena de átomos que será la entrada al Parser recursivo.
Primera Parte del analizador Sintáctico
El analizador LEXICO
Analizador léxico en LEX
Análisis.
Estudio preliminar.
Objetivo: Elaborar un analizador léxico en Lex o Flex que reconozca los componentes léxicos
pertenecientes a las clases debajo descritas.
Lista de requerimientos:
Las clases de los componentes léxicos validos para el analizador léxico son:
o Clase Descripción
o 0 Palabras reservadas
o 1 Constantes enteras (sin signo)
o 2 Cadenas encerradas entre apostrofes
o 3 Operadores relacionales
o 4 Operadores aritméticos
o 5 Identificadores (Sólo letras)
o 6 Símbolos especiales
o El número de las clases es inamovible.
El analizador léxico tendrá como entrada un archivo con el programa fuente. Que se
deberá dar en la línea de comandos al ejecutar el analizador léxico.
Como delimitador de un componente léxico será uno varios espacios, tabuladores o saltos
de línea, así como el inicio de otro componente léxico.
Cuando detecte un error léxico, deberá seguir el reconocimiento a partir del siguiente
símbolo valido.
El analizador deberá crear la tabla de símbolos con2 campos: nombre y tipo. Y otra tabla
de cadenas con un solo campo.
Los token’s contendrán 2 campos.
o Campo1: la clase (entero de un byte).
o Campo2: el valor (de acuerdo a las sig. Tablas).
o
Compiladores 4 Argueta Cortes Jairo I.
Analizador Léxico Mendoza Gaytán José Trinidad
El valor para el token de cada identificador es la posición dentro de la tabla de símbolos, para las
cadenas su posición en la tabla correspondiente y de las constantes enteras su valor numérico.
El analizador léxico generará una cadena de átomos (de acuerdo a las tablas presentadas más
abajo).
Operadores arieticos
Operador Valor Átomo
Palabras reservadas
+ + +
Palabra Valor Átomo - - -
CONCAT 0 u / / /
CREATE 1 c
DEFAULT 2 d
DROP 3 b
FROM 4 f
INSERT 5 i Operadores relacionales
INTO 6 a
KEY 7 k Operador Valor Átomo
NOT 8 n = 0 =
NULL 9 e <> 1 !
PRIMARY 10 p
< 2 <
SELECT 11 s
TABLE 12 t > 3 >
VALUES 13 v >= 4 g
WHERE 14 w <= 5 l
CHAR 15 h
INTEGER 16 z
Símbolos especiales
Símbolo Valor Átomo
, , ,
; ; ;
* * *
( ( (
) ) )
Valor Átomo
Constantes enteras sin signo Equivalente en decimal #
Cadena de caracteres Posición en la tabla q
Identificador Posición en la tabla y
Como resultados, el analizador léxico deberá mostrar el contenido de la tabla de símbolos, los
tokens y la cadena de átomos
Los errores que vaya encontrando el analizador léxico, los podrá ir mostrando en pantalla o
escribirlos en un archivo.
Compiladores 5 Argueta Cortes Jairo I.
Analizador Léxico Mendoza Gaytán José Trinidad
Planeación.
Se cuenta con un total de 5 días para la entrega del proyecto por lo que la organización quedara
de la siguiente manera:
El programa del analizador léxico se dividirá en tres módulos:
MOD I: Se definirán las expresiones regulares para trabajar en FLEX, así como sus
componentes léxicos y se implementara su código correspondiente.
MOD II: Se implementaran las funciones requeridas para generar los tokens, y cadena de
átomos.
MOD III; Se implementaran las funciones requeridas para la creación de la tabla de
símbolos y de caracteres.
Distribución de tiempos:
Tiempo de análisis y diseño. Tomando en cuenta los requerimientos y alcance del proyecto
se realizara en un total de 2 días.
Tiempo de desarrollo. Será el tiempo restante antes de la entrega del proyecto en este
caso será un total de 3 días naturales.
Asignación de labores:
Tomando en cuenta el tiempo con el que se cuenta, así como los recursos y alcance del proyecto
se organizara de la siguiente manera:
Desarrollador1.- Argueta Cortes Jairo I. (D1)
Desarrollador2.- Mendoza Gaytán José T. (D2)
Propuesta de servicios.
La forma en la que se dará solución a los requerimientos presentados será la siguiente:
Se cuenta con un total de 5 días para la entrega del proyecto por lo que las actividades
relacionadas con el desarrollo del proyecto se tendrán que adecuar a este No. De días.
Objetivo.- Que la Ing. Laura Sandoval Montaño obtenga el programa de Analizador léxico en
tiempo y forma establecidos por la misma, cumpliendo con todos y cada uno de los
requerimientos antes establecidos.
Entregables del proyecto.- se realizara la entrega de:
El análisis, diseño y desarrollo así como la forma en la que el programa se puede implementar.
Se entregara además el código fuente del programa así como un archivo ejecutable del mismo,
esto se realizara de manera electrónica mediante el correo electrónico y de forma escrita
mediante un documento.
Compiladores 6 Argueta Cortes Jairo I.
Analizador Léxico Mendoza Gaytán José Trinidad
Diseño.
Para poder cumplir con los requerimientos especificados en el presente programa se tendrá que
partir desde la creación de expresiones regulares hasta su implementación en FLEX.
Expresiones regulares
Identificadores.
<let> = A|B|…|Z|a|b…|z
<ident>= <let>+
Símbolos
<símbolo> = ,| ; | *| ( | )
Operador aritmético
<opArit> = +| - | /
Operador Relacional
<opRel> = <>|<|>|<=|>=
Cadenas
<caracter>= A|B|…|Z|a|b…|z|!|”|#|$|%|&|/|(|)|=|?|¡|/|*|-
|+|¬|>|<|¿|¬|°|@
<comilla>=’
<cadena> =<comilla><caracter>*<comilla>
Constantes enteras
<dig>= 0|1|2|3|4|5|6|7|8|9
<entero>=<dig>+
Palabras reservadas
<palres>
=CONCAT|CREATE|DEFAULT|DROP|FROM|INSERT|INTO|KEY|NOT|NULL|PRIMARY|
SELECT|TABLE|VALUES|WHERE|CHAR|INTEGER
Compiladores 7 Argueta Cortes Jairo I.
Analizador Léxico Mendoza Gaytán José Trinidad
Desarrollo.
Definición de la tabla de símbolos y de caracteres
Para trabajar con la tabla de símbolos (identificadores) la definimos de la siguiente manera:
TABLA DE SIMBOLOS
Clase Nombre Valor
TABLA DE CADENAS
Nombre Valor
Para lo cual trabajamos con una estructura en C. definida de la siguiente manera
typedef struct sim {
int ClaseS; //Clase del Símbolo
int valorS; //Valor del símbolo
char simbolo[20]; //Símbolo
struct sim *siguiente; //Puntero al siguiente símbolo
} tablaSimbolos;
Esta estructura nos permitirá trabajar con listas ligadas, es por eso que trabajamos con
struct sim *siguiente que es un apuntador al siguiente elemento.
Este tipo de utilización de estructuras de datos nos permitirá optimizar memoria, ya que
podríamos haber utilizado una matriz multidimensional de un tamaño fijo, lo que sería difícil de
modificar en su tamaño aunque simplificaría mas el código.
Definición de Token’s
Cada TOKEN tiene dos campos definidos de la siguiente manera (Clase, Valor)
Clase 0
Palabras reservadas
//Estructura para definir Palabras reservadas {palabra,valor,atomo}
27 struct palabraS{
28 char palabra[10]; //Palabra
29 int valor; //Valor
30 char atomo; //atomo
31 } palabraRes[17] = {{"CONCAT",0,'u'},{"CREATE",1,'c'},{"DEFAULT",2,'d'},{"DROP",3,'b'},
32 {"FROM",4,'f'},{"INSERT",5,'i'},{"INTO",6,'a'},{"KEY",7,'k'},
33 {"NOT",8,'n'},{"NULL",9,'e'},{"PRIMARY",10,'p'},{"SELECT",11,'s'},
34 {"TABLE",12,'t'},{"VALUES",13,'v'},{"WHERE",14,'w'},{"CHAR",15,'h'},
35 {"INTEGER",16,'z'}
36 };
Compiladores 8 Argueta Cortes Jairo I.
Analizador Léxico Mendoza Gaytán José Trinidad
Clase 1
Constantes enteras (sin signo)
Atomo = #
Clase 2
Cadenas encerradas entre apostrofes
Atomo = q
Clase 3
Operadores relacionales
45 //Estructura para definir Operadores relacionales {operador,valor,atomo}
46 struct opRelacional {
47 char operador[2]; //Operador
48 int valor; //Valor
49 char atomo; //atomo
50 } operadorRel[6] =
{{"=",0,'='},{"<>",1,'!'},{"<",2,'<'},{">",3,'>'},{">=",4,'g'},{"<=",5,'l'}};
Clase 4
Operadores aritméticos
38 //Estructura para definir Operadores arimeticos {operador,valor,atomo}
39 struct opAritmetico {
40 char operador; //Operador
41 char valor; //Valor
42 char atomo; //atomo
43 } operadorArit[3] = {{'+','+','+'},{'-','-','-'},{'/','/','/'}};
Clase 5
Identificadores (Sólo letras)
Clase 6
Símbolos especiales
52 //Estructura para definir Simbolos especiales {simbolo,valor,atomo}
53 struct simbolos {
54 char simbolo; //Operador
55 char valor; //Valor
56 char atomo; //atomo
57 } simboloEsp[5] = {{',' , ',' , ','},{';', ';' ,';'},{'*', '*' ,'*'},{'(', '(' ,'('},{')', ')' ,')'}};
Técnicas de búsqueda e inserción
La técnica de búsqueda es lineal para nuestras listas ligadas que viene siendo la tabla de símbolos
por lo tanto cuando el autómata reconoce un Identificador, primero lo busca en la tabla de
símbolos y si este se encuentra toma el valor correspondiente en la tabla se símbolos y genera en
Token.
En caso de que el símbolo no se encuentre en la tabla, lo inserta y le asigna un valor para poder
generar el Token correspondiente.
Compiladores 9 Argueta Cortes Jairo I.
Analizador Léxico Mendoza Gaytán José Trinidad
El algoritmo está definido en C de la siguiente manera:
void buscaSimbolo(int ClaseB, char *CadenaB) {
//aux apunta al inicio de la tabla de simbolos
aux = inicioTabla;
//Bandera que indica si encontro el simbolo
int encontro = 0;
//Inicializacion de la tabla por primera vez
if(ContadorS==0)
{
insertaSimbolo(ClaseB, CadenaB);
aux = inicioTabla;
printf("( %d , %d )\n", aux->ClaseS, aux->valorS);
encontro=1;
}
//Loop que busca un simbolo en la tabla
while (encontro==0)
{
//Si encuentra el simbolo en la tabla
//imprime clase y valor correspondiente
if(strcmp(aux->simbolo,CadenaB)==0)
{
printf("( %d , %d )\n", aux->ClaseS, aux->valorS);
encontro=1;
}
//Apunta al siguiente elemento de la tabla
else
aux = aux->siguiente;
//Si no encuetra el simbolo lo inserta en la tabla
if(aux==NULL)
{
insertaSimbolo(ClaseB, CadenaB);
aux = inicioTabla;
printf("( %d , %d )\n", aux->ClaseS, aux->valorS);
encontro=1;
}
}
La implementación de la tabla de caracteres es idéntica que una tabla de símbolos. Solamente
asignamos nuevos nombres a las variables a utilizar.
Compiladores 10 Argueta Cortes Jairo I.
Analizador Léxico Mendoza Gaytán José Trinidad
2da. Parte del analizador Sintáctico
EL PARSER recursivo
Como el PARSER está incluido en el analizador LEXICO, la entrada es un archivo con el
programa fuente a analizar, el cual se indicará desde la línea de comandos.
EL programa realizará tanto el análisis léxico como el sintáctico. Si encuentra errores
léxicos, ya no continuara con el análisis sintáctico.
Al encontrar el primer error sintáctico se podrá detener el análisis.
Como resultados, el analizador léxico-semántico deberá mostrar el contenido de la tabla e
símbolos, la tabla de cadenas, los tokens, la cadena de átomos y si esta sintácticamente
correcto el programa fuente.
Utilizando diagramas de tren para definir las gramáticas
Sentencia CREATE
Bloque: def_Columna
Sentencia DROP
Compiladores 11 Argueta Cortes Jairo I.
Analizador Léxico Mendoza Gaytán José Trinidad
Sentencia INSERT
Sentencia SELECT
Bloque: predicado
Obteniendo las expresiones regúlales mediante los diagramas de tren, y obteniendo el conjunto
de selección.
Compiladores 12 Argueta Cortes Jairo I.
Analizador Léxico Mendoza Gaytán José Trinidad
Una vez obtenida esta tabla procedemos a programar el PARSER recursivo de la siguiente
manera:
PRODUCCION PREDICTIVO RECURSIVO
A -> b Pop avz. getc(), return
A -> bα Rep(α)r avz. getc(), procesa(α), return
A -> Bα Rep(Bα)r ret procesa(Bα), return
A -> ε Pop ret return
Compiladores 13 Argueta Cortes Jairo I.
Analizador Léxico Mendoza Gaytán José Trinidad
Ejemplo:
Para el símbolo inicial
void Z(){
if(car=='s'){
S();
return;
}
else if(car=='b'){
D();
return;
}
else if(car=='c'){
C();
return;
}
else if(car=='i'){
I();
return;
}
else
rechaza();
}
Y así para cada producción de un No Terminal de nuestra tabla
Ejecución de Programa AS-SQL.c
En una terminal de Linux teclear lo siguiente:
boxer@boxer-desktop:~/Escritorio$flex AS-SQLex.l
boxer@boxer-desktop:~/Escritorio$ gcc [Link].c -lfl
boxer@boxer-desktop:~/Escritorio$./[Link] [nombreArchivo].txt
En [nombreArchivo] se sustituye por el nombre del archivo fuente, para nuestro caso de ejemplo
utilizamos [Link]
