UNIVERSIDAD DE SAN CARLOS DE GUATEMALA FACULTAD DE INGENIERIA ESCUELA DE CIENCIAS Y SISTEMAS LENGUAJES FORMALES Y DE PROGRAMACION Segundo Semestre 2013

Catedrática Tutor académico

Inga. Zulma Aguirre (sección B-) Randy Alberto Ruano Morales

Inga. Damaris Campos de López (sección A-) Jose Victor Tobias Romero

Enunciado de Practica No. 1

Objetivos:

Esta práctica tiene como objetivo reforzar los conocimientos de programación obtenidos en cursos

anteriores, así como también busca familiarizar al estudiante con el lenguaje de desarrollo

VisualBasic.NET.

Que el estudiante practique el análisis léxico.

Que el estudiante inicie con la practica el uso del lenguaje de programación VB .NET

Aplicar los conceptos aprendidos en clase y laboratorio.

Descripción:

La práctica consiste en realizar un pequeño editor utilizando el lenguaje Visual Basic .Net este procesará

gramáticas regulares (una o varias) con notación BNF.

Las gramáticas regulares podrán ser definidas de 2 maneras, la primera será a través de la carga de un

archivo, con extensión .LFP; y la segunda será escribiendo directamente en el editor.

La aplicación debe proveer la opción de analizar el contenido del editor, y deberá generar como salida

una página HTML con los datos analizados o en caso de que el archivo contenga errores, mostrara una

página HTML con el detalle de estos.

Marco Teórico:

La gramática es un ente formal para especificar, de una manera finita, el conjunto de símbolos que

constituye un lenguaje, así tenemos la gramática del español, del inglés, del francés, etc.

Una gramática regular está formada por cuatro elementos, y son G = {Σ,N,P,So}

Elemento Nombre Descripción

Σ alfabeto

(Terminales)

Símbolo o carácter permitido en el lenguaje específico, siempre entre

apóstrofos (‘). También se permiten conjuntos de terminales,

previamente definidos (se explica la sintaxis posteriormente).

N No terminales Símbolos auxiliares que no son parte de los caracteres permitidos.

P Reglas de

producción

Las producciones para las gramáticas regulares pueden ser de la

siguiente forma:

A → ‘a’B

A → B‘a’

A → ‘a’

A → ;

Dónde: No terminales ={A,B} y

Terminales ={‘a’}

So Inicio So es un No terminal.

Ejemplo. Sea una gramática con las siguientes reglas.

S →‘a’A

S → ‘b’A

A → ‘a’B

A → ‘b’B

A →

B → ‘a’A

B → ‘b’A

La presentación formal de la gramática de arriba sería de la siguiente manera:

Terminales = {‘a’, ‘b’}

No Terminales = {S,A,B}

Inicio = S

Producciones = {(S, ‘a’A),(S, ‘b’A),(A, ‘a’B),(A, ‘b’B),(A, ‘a’),(B, ‘a’A),(B, ‘b’A)}

Las gramáticas regulares pueden ser de 2 tipos:

Gramáticas regulares a la derecha, todas sus producciones siguen una de estas 3 formas:

o A →

o A →‘a’

o A →‘a’ B

Gramáticas regulares a la izquierda, todas sus producciones siguen una de estas 3 formas:

o A →

o A → ‘a’

o A → B ‘a’

La notación BNF (Notación de Backus-Naur), es un metalenguaje usado para expresar gramáticas; es

decir, una manera formal de describir lenguajes formales. Los componentes de la notación son:

Terminal Se puede escribir entre comillas, o sin ellas.

<No terminal> Símbolo auxiliar que se define, se escribe entre <>.

Regla de producción En lugar de la flecha se usa la siguiente secuencia de caracteres:::=

Meta símbolo Símbolo propio de la notación, está reservado y no puede

utilizarse como terminal:

o ::= Equivalencia

o | Alternativa

Requerimientos de la solución:

La aplicación debe analizar la o las gramáticas regulares que se encuentren en el editor en búsqueda de

errores léxicos. De encontrar errores léxicos, la aplicación debe informar al usuario y mostrar un reporte

en formato HTML. (Ver tabla 2).

Se podrán definir conjuntos para los terminales, en el área exclusiva para este fin (solamente al inicio del

archivo); se tendrá como palabra reservada: CONJUNTOS

Por ejemplo:

Conjuntos:

Dígito = {‘0’, ‘1’, ‘2’, ‘3’, ‘4’, ‘5’, ‘6’, ‘7’, ‘8’, ‘9’}

Vocal = { ‘a’, ‘e’, ‘i’, ‘o’, ‘u’}

De no encontrar error alguno, la aplicación debe pintar dentro del editor cada uno de los lexemas de un

color definido en la tabla de los anexos (Ver tabla 1); además debe generar una página HTML que

contendrá lo siguiente:

1. Tabla de tokens: Se deberá mostrar una tabla con cada uno de los lexemas, tokens y correlativo

encontrados en las gramáticas analizadas, el texto de cada token deberá ser del color definido en

la tabla de los anexos. (Ver tabla 3)

2. Grafo correspondiente al Autómata Finito de cada gramática reconocida.

Ejemplo de Entrada:

Conjuntos:

Dígito = {‘0’, ‘1’, ‘2’, ‘3’, ‘4’, ‘5’, ‘6’, ‘7’, ‘8’, ‘9’}

Terminales = {‘+’,‘-’, Dígito }

No Terminales = { <Número>, <Secuencia>, <OtroDigito> }

Inicio = <Número>

Producciones:

<Número> ::= dígito <OtroDigito>

<Número> ::= ‘+’<Secuencia>

| ‘-‘<Secuencia>

<Secuencia> ::= dígito <OtroDigito>

<OtroDigito> ::= dígito <OtroDigito>

|

Ejemplo de la Salida:

CONJUNTOS:

Dígito = { ’0’,‘1’,‘2’,‘3’,‘4’,‘5’,‘6’,‘7’,‘8’,‘9’}

GRAMÁTICA REGULAR # 1:

Terminales = {’+’,‘-‘,Dígito}

No Terminales = { <Número>,<Secuencia>,<OtroDigito> }

Inicio = <Número>

Producciones:

<Número>::=dígito <OtroDigito>

<Número>::=’+’<Secuencia>

<Número>::=‘-‘<Secuencia>

<Secuencia>::=dígito<OtroDigito>

<OtroDigito>::=dígito<OtroDigito>

<OtroDigito>::=

Tabla de Lexemas:(esta tabla no está completa y no corresponde al presente ejemplo) No. Lexema Token Posición

1 <Número> 2 Fila 10 Columna 1

Autómata Finito:

Interfaz gráfica:

Componentes mínimos de la interfaz:

1. Editor de texto: Debe ser un campo de texto en el cual se puedan escribir nuevas gramáticas

regulares o bien cargar desde archivos con extensión .LFP

2. Abrir: La interfaz debe proveer la capacidad de abrir archivos con extensión .LFP, cada archivo

contendrá 1 o varias gramáticas regular.

3. Guardar: La aplicación debe proveer la capacidad de guardar las gramáticas regular que está en el

editor, sobrescribiendo las gramáticas en el archivo existente. Si la gramática no ha sido guardada nunca

debe proveer una opción para ingresar el nombre del nuevo archivo.

4. Guardar como: Está opción permite guardar la gramática como un nuevo archivo, se debe preguntar

el nombre del nuevo archivo.

5. Analizar: Debe realizar el análisis léxico de las gramáticas regulares que se encuentra actualmente en

el editor y generar la salida correspondiente.

6. Acerca de: Debe mostrar en una ventana desplegable los datos del estudiante y del curso.

7. Salir: Debe terminar la ejecución de la aplicación.

Documentación a Entregar en el CD:

Manual de Usuario

Manual Técnico

Código fuente de la práctica.

Documentación a Entregar de forma física:

Diagrama de autómatas y gramáticas regulares por cada cadena reconocida en el lenguaje (Se definirá en el laboratorio el formato)

Hoja de calificación

Notas importantes:

La práctica se debe de desarrollar de forma individual

Esta práctica se deberá de desarrollar utilizando VisualBasic.Net con Visual Studio 2010 o 2012.

No se deberá de utilizar ninguna herramienta aparte para la lectura del archivo del archivo de entrada.

No se deberá de utilizar ninguna herramienta auxiliar; solamente Graphviz para generar el grafo en

formato png, jpg o jpeg; o la librería Graphics para graficar directamente en la aplicación.

Copia parcial o total de las practicas tendrán una nota de 0 puntos y se notificará a la escuela

para que se apliquen las sanciones correspondientes.

La calificación de la práctica será personal y durara como máximo 30 minutos, en un horario que posteriormente será establecido, se debe de tomar en cuenta que durante la calificación no podrán

estar terceras personas alrededor de lo contrario no se calificará la práctica.

No se dará prórroga para la entrega de la práctica. Fecha de entrega: 24 de Agosto de 2013.

Anexos

Tabla 1, colores por token (puede ser que se usen otros tokens, los cuales serán en color NEGRO).

Código Token Nombre del Token Color de token

1 Terminal VERDE

2 <No terminal> ROJO

3 Equivalencia ::= AZUL

4 Alternativa | MORADO

…. …. NEGRO

Tabla 2, errores léxicos.

No. Lexema Token Posición Error

1 % Desconocido Fila 3 columna 4 Error léxico, token no reconocido.

Tabla 3, tabla de lexemas por token encontrados en el análisis.

No. Lexema Token Posición

1 <Número> 2 Fila 1 Columna 1

2 ::= 3 Fila 1 Columna 9

3 <Signo> 2 Fila 1 Columna 12

4 8 1 Fila 1 Columna 13