Instituto Tecnológico de Tuxtla Gutiérrez

Ingeniería en Sistemas Computacionales

Teoría De La Computación

Proyecto COCO-R

Presenta

López Maza Jessica

Molina Velasco Jaime Guadalupe

Morales Ocaña José Francisco

Rodas Borges Mario Alberto

Tuxtla Gutiérrez, Chiapas a 23 de Mayo del 2011

INDICE

Introducción

Descripción del Lenguaje

Conjunto de Instrucciones

Analizador léxico

Introducción

Autómata Finito Determinista

Tabla de Análisis Léxico

Programa

Analizador Sintáctico

Introducción

Gramática Libre De Contexto (Con Recursividad)

Gramática Libre De Contexto (Sin Recursividad)

Notación BNF

Diagrama De Sintaxis

Notación BNF / COCO –R

Programa

Conclusión

INTRODUCCION

El presente proyecto se ha realizado en base a un analizador léxico y sintáctico

haciendo uso de COCO-R, que es un generador de compilador de lenguaje que

proporciona un programa y un escáner para el lenguaje creado.

Aplicando los conocimientos adquiridos previamente acerca de los autómatas y los

lenguajes, hemos creado el lenguaje acerca de un control remoto de televisión

indicando las seis principales funciones del antes mencionado.

DESCRIPCION DEL LENGUAJE

El lenguaje que manejamos en este proyecto es referente a las funciones básicas

de un control remoto de televisión, donde podemos mencionar que las

indicaciones básicas que se necesitan son las necesarias como encender, subir y

bajar volumen así mismo como el cambio de canales y la función de menú y la de

enter para aceptar todos los cambios y modificaciones que se desee realizar en la

configuración de una televisión.

CONJUNTO DE INSTRUCCIONES

A Power (cantidad)

B Chanel (Digito)

C Aumentar Volumen (Cantidad)

D Bajar Volumen (Cantidad)

E Menú (Cantidad)

F Direcciones (Arriba, Abajo, Derecha, Izquierda)

G Enter (Cantidad)

ANALIZADOR LEXICO

INTRODUCCION

Analizador léxico (scanner): lee la secuencia de caracteres del programa fuente,

carácter a carácter, y los agrupa para formar unidades con significado propio,

componentes léxicos (tokens). Estos componentes léxicos representan:

Palabras reservadas

Identificadores

Operadores

Símbolos especiales

Constantes Numéricas

Constantes de Caracteres

AFD

TABLA DE ANALISIS LEXICO

PROGRAMA

#include<stdio.h>#include<ctype.h>

#define ESTADOS 24#define CODIGO 12unsigned char Caracter_Act;

int Verifica();int Analizador_Lexico();

void main(){

int Token;printf("Cadena: ");do{

Caracter_Act=getchar();ungetc(Caracter_Act,stdin);Token=Analizador_Lexico();printf("%d\n");

ungetc(Caracter_Act,stdin);}while(Token != 511);

}int Analizador_Lexico()

{unsigned int Codigo;unsigned int Estado=0;unsigned int Salida=0;

/*******Tabla de Transicion*******/static unsigned int Matriz_de_Transicion[ESTADOS][CODIGO]={/* Caracter/ L ( ) ; D + - A Ab -> <- otro *//* Estados */ /* q0 */ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 511, /* q1 */ 1, 500, 500, 500, 500, 500, 500, 500, 500, 500, 500, 500, /* q2 */ 501, 501, 501, 501, 501, 501, 501, 501, 501, 501, 501, 501, /* q3 */ 502, 502, 502, 502, 502, 502, 502, 502, 502, 502, 502, 502, /* q4 */ 503, 503, 503, 503, 503, 503, 503, 503, 503, 503, 503, 503, /* q5 */ 504, 504, 504, 504, 5, 504, 504, 504, 504, 504, 504, 504, /* q6 */ 505, 505, 505, 505, 505, 505, 505, 505, 505, 505, 505, 505, /* q7 */ 506, 506, 506, 506, 506, 506, 506, 506, 506, 506, 506, 506, /* q8 */ 507, 507, 507, 507, 507, 507, 507, 507, 507, 507, 507, 507, /* q9 */ 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, 508, /* q10*/ 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, 509, /* q11*/ 510, 510, 510, 510, 510, 510, 510, 510, 510, 510, 510, 510,};

/*********Tabla de Salida***********/static unsigned int Matriz_de_Salida[ESTADOS][CODIGO]={/* Caracter/ L ( ) ; D + - A Ab -> <- otro *//* Estado */ /* q0 */ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, /* q1 */ 500, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, /* q2 */ 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, /* q3 */ 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, /* q4 */ 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, /* q5 */ 5, 5, 5, 5, 504, 5, 5, 5, 5, 5, 5, 5, /* q6 */ 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, /* q7 */ 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, /* q8 */ 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, /* q9 */ 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, /* q10*/ 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, /* q11*/ 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11,

};while (Salida==0){

Codigo=Verifica();Salida= Matriz_de_Salida[Estado][Codigo];

Estado= Matriz_de_Transicion[Estado][Codigo];}return Estado;

}

int Verifica(){ Caracter_Act=getchar();

if(isalpha(Caracter_Act)) return 0;

else if((Caracter_Act=='(')) return 1;

else if((Caracter_Act==')')) return 2;

else if((Caracter_Act==';')) return 3;

else if(isdigit(Caracter_Act)) return 4;

else if((Caracter_Act=='+')) return 5;

else if((Caracter_Act=='-')) return 6;

else if((Caracter_Act=='?')) return 7;

else if((Caracter_Act=='!')) return 8;

else if((Caracter_Act=='>')) return 9;

else if((Caracter_Act=='<')) return 10;

else return 11;

}

ANALIZADOR SINTACTICO

INTRODUCCION

El análisis sintáctico convierte el texto de entrada en otras estructuras

(comúnmente árboles), que son más útiles para el posterior análisis y capturan la

jerarquía implícita de la entrada. Un analizador léxico crea tokens de una

secuencia de caracteres de entrada y son estos tokens los que son procesados

por el analizador sintáctico para construir la estructura de datos.

GRAMÁTICA LIBRE DE CONTEXTO (CON RECURSIVIDAD)

A -> Ap (b); B|B

B -> BC (e); C|C

C -> Ca (e); D|D

D -> Db (e); E|E

E -> Em (b); F|F

F -> Fd (a, ab, der, izq); G|G

G -> Ge (e); H|H

H -> Ԑ

GRAMÁTICA LIBRE DE CONTEXTO (SIN RECURSIVIDAD)

A -> A∞|ᵦ

A -> Ap (b); B|B

B -> Bc (e); C|C

C -> Ca (e); D|D

D -> Db (e) E|E

E -> Em (b); F|F

F -> Fd (a, ab, der, izq) G|G

A -> ᵦ A’

A -> BA’

B -> CB’

C ->DC’

D -> ED’

E ->FE’

F -> GF’

A’ -> ∞ A’ | Ԑ

A’ -> p (b); B A’| Ԑ

B’ -> c (e);C B’| Ԑ

C’ -> a (e);D C’| Ԑ

D’ -> b(e);E D’| Ԑ

E’ -> m(b);F E’| Ԑ

F’ -> d (a, ab, der, iz); GF’| Ԑ

NOTACION BNF

<CONTROL REMOTO>::= {<POWER> [<CHANEL> | <VOLUMEN> | <MENU>] }

<POWER>::= power(<opcion>);

<CHANEL>::=chanel ({ <digito> [<digito>] } );

<opcion>::=on|off

<digito>::=0,1,2,3,4,5,6,7,8,9

<VOLUMEN>::= volumen (<accion>);

<accion>::={+|-}

<MENU>::=menu({ <Direcciones> [<Enter>]});

<direcciones>::= (<arriba> | <izquierda>| <abajo> | <derecha>);

<ENTER>::={enter}

DIAGRAMA DE SINTAXIS

NOTACION BNF (COCO-R)

CONTROL REMOTO=POWER {(“CHANEL”| “VOLUMEN ” | “MENU”)POWER}

POWER = power “(“ opcion”)” “;”

CHANEL = chanel { “(” digito “)” | “(” digito “)” “;” chanel }

VOLUMEN =volumen { “(” accion “)” }

MENU= MENU { “(“ direcciones “)” | “(”enter”)” }

ENTER = enter { “(” enter “)” }

opcion ={ (“ON” | “OFF”) }

digito ={ ( “0” | “1” | “2” | “3” |“4” | “5” | “6” |“7” |“8” | “9” ) }

accion ={ (“+” | “-”) }

direcciones ={ ( “arriba” | “abajo” | “derecha” | “izquierda” ) }

CONCLUSION

A través de la realización de este proyecto mediante el uso de los autómatas

finitos deterministas y de los lenguajes léxico y sintáctico, de acuerdo a lo anterior

y a lo visto en clases hemos creado un lenguaje de un control remoto de

televisión con seis instrucciones básicas las cuales se han presentado en el

trabajo realizando su analizador léxico y sintáctico respectivamente.

En primera instancia hicimos la construcción del AFD, y la tabla del mismo

posteriormente, basándonos en esta información creamos el analizador léxico que

es el que nos arroja los tokens que es el que indican en qué orden van y si está

dentro de la cadena.

Creamos así mismo la gramática libre de contexto y le quitamos la recursividad y

la representamos mediante la notación BNF y lo representamos en diagrama de

sintaxis.

Posteriormente utilizamos el compilador COCO- R para que nos fuera más fácil

obtener si nuestras instrucciones estaban correctas.

De acuerdo a las acciones implementadas hemos logrado comprender la

complejidad que trae consigo la realización de un compilador, y que se debe tomar

en cuenta todas las opciones de vialidad posible, siempre y cuando se busque la

eficiencia en los procesos.