PDF de programación - Compilador de pseudocódigo como herramienta para el aprendizaje en la construcción de algoritmos

COMPILADOR DE PSEUDOCÓDIGO COMO HERRAMIENTA PARA EL

APRENDIZAJE EN LA CONSTRUCCIÓN DE ALGORITMOS

RAFAEL ANIBAL VEGA CASTRO

PROGRAMA DE INGENIERÍA DE SISTEMAS

DIVISIÓN DE INGENIERÍAS

UNIVERSIDAD DEL NORTE

2008

COMPILADOR DE PSEUDOCÓDIGO COMO HERRAMIENTA PARA EL

APRENDIZAJE EN LA CONSTRUCCIÓN DE ALGORITMOS

RAFAEL ANIBAL VEGA CASTRO

Tesis para optar al título de Ingeniero de Sistemas

Ing. ALFONSO MANUEL MANCILLA HERRERA

Director del Proyecto

PROGRAMA DE INGENIERÍA DE SISTEMAS

DIVISIÓN DE INGENIERÍAS

UNIVERSIDAD DEL NORTE

2008

Nota de aceptación
_______________________________
_______________________________
_______________________________
_______________________________
_______________________________

_______________________________
Firma del presidente del jurado

_______________________________
Firma del jurado

_______________________________
Firma del jurado

Barranquilla, Diciembre de 2008

DEDICATORIA

A Dios, que siempre me iluminó.

A mi padre y madre, por el apoyo que siempre me han brindado, por confiar en mi, por
darme todo lo que hoy tengo y por hacerme todo lo que soy.

A mi hermano, quien siempre se alegra por los logros que consigo y quien quiere seguir
los mismo pasos que yo seguí gracias a la vocación que Dios nos dio.

A mi novia, que siempre me apoyaba y me llenaba de fuerzas para continuar cuando quería
rendirme..

A mi primo, que desde el cielo siempre me acompaña, al que nunca olvidaré.

Al Ing. Alfonso Mancilla, quien siempre ha confiado en mi, me ha tendido su mano y me ha
aconsejado en la toma de muchas de las decisiones mas importantes en mi vida.

A mis tías, abuelas, primos, demás familiares y amigos.,

AGRADECIMIENTOS

En mi vida he tenido la posibilidad de trabajar en varios proyectos, pero ninguno que me

diera la satisfacción que siento al terminar los objetivos de este. Digo terminar los objetivos

porque a este proyecto se le puede llevar muy lejos.

Agradezco enormemente a todas las ayudas recibidas por parte del Ingeniero Jose Marquez,

jefe del programa de Ingeniería de Sistemas de la Universidad del Norte, quien siempre saca-

ba un rato de su valioso tiempo para resolver mis dudas o darme consejos para resolver mis

problemas. No tengo como agradecer al Ingeniero Alfonso Mancilla, docente de planta del

programa de Ingeniería de Sistemas de la Universidad del Norte, mi director de tesis, quien

me dio la oportunidad y me apoyó en la idea que le plantee en un principio, la cual era un

poco ambiciosa, pero el día de hoy nos damos cuenta que cualquier cosa puede lograrse si

tiene la dedicación y las ganas que se necesitan.

Rafael Anibal Vega Castro

Barranquilla, Colombia

Octubre 29 de 2008

Tabla de Contenido

Lista de Figuras

Lista de Tablas

Introducción

1. Objetivos

1.1. Objetivo General

.

. . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.2. Objetivos Específicos . . . . . . . . . . . . . . . . . . . . . . . . . . . .

.

.

2. Teoría de Compiladores
.

2.1. Introducción .

.

. . . . . . . . . . . . . . . . . . . . . . . . . . . . .

.

2.1.1. Concepto de traductor

. . . . . . . . . . . . . . . . . . . . . . . .

2.1.2. Tipo de traductores . . . . . . . . . . . . . . . . . . . . . . . . . .

Traductores de idioma . . . . . . . . . . . . . . . . . . . . . . .

Compiladores . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Intérpretes

. . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Preprocesadores

. . . . . . . . . . . . . . . . . . . . . . . . . .

Intérpretes de comandos . . . . . . . . . . . . . . . . . . . . . .

Conversores fuente-fuente . . . . . . . . . . . . . . . . . . . . .

Compilador cruzado . . . . . . . . . . . . . . . . . . . . . . . .

I

VI

VII

1

2
2

2

3
3

3

4

4

4

5

5

6

6

7

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

2.1.3. Teoría básica relacionada con la traducción . . . . . . . . . . . . .

Pasadas de compilación . . . . . . . . . . . . . . . . . . . . . .

Compilación incremental . . . . . . . . . . . . . . . . . . . . . .

Autocompilador

. . . . . . . . . . . . . . . . . . . . . . . . . .

Descompilador . . . . . . . . . . . . . . . . . . . . . . . . . . .

Metacompilador

. . . . . . . . . . . . . . . . . . . . . . . . . .

2.1.4. Estructura de un traductor

. . . . . . . . . . . . . . . . . . . . . .

2.1.5. Tabla de símbolos

. . . . . . . . . . . . . . . . . . . . . . . . . .

2.2. Análisis lexicográfico . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.2.1. Proceso de un analizador léxico . . . . . . . . . . . . . . . . . .

.

2.2.2. Expresiones Regulares . . . . . . . . . . . . . . . . . . . . . . . .

Definición de expresiones regulares . . . . . . . . . . . . . . . .

Extensiones para las expresiones regulares

. . . . . . . . . . . .

2.3. Gramáticas libres de contexto . . . . . . . . . . . . . . . . . . . . . . . .

2.3.1. Convenciones de notación . . . . . . . . . . . . . . . . . . . . . .

2.3.2. Derivación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.3.3. Ambigüedad . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.3.4. Escritura de una gramática . . . . . . . . . . . . . . . . . . . . .

.

Expresiones regulares, o gramáticas libres de contexto . . . . . .

Comprobación del lenguaje generado por una gramática . . . .

.

Eliminación de la recursión por la izquierda . . . . . . . . . . . .

Factorización por la izquierda . . . . . . . . . . . . . . . . . . .

2.4. Análisis sintáctico ascendente . . . . . . . . . . . . . . . . . . . . . . . .

2.4.1. Visión general

. . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.4.2. Elementos LR(0) y análisis sintáctico LR(0) . . . . . . . . . . . . .

Elemento LR(0)

. . . . . . . . . . . . . . . . . . . . . . . . . .

El algoritmo de análisis sintáctico LR(0) . . . . . . . . . . . . . .

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

7

7

8

8

8

8

9

. 11

. 11

. 13

. 13

. 14

. 16

. 17

. 18

. 19

. 20

. 21

. 21

. 22

. 22

. 23

. 23

. 24

. 26

. 26

. 27

II

2.4.3. Análisis sintáctico LALR(1) y LR(1) general

. . . . . . . . . . . .

EL algoritmo de análisis sintáctico LR(1)

. . . . . . . . . . . . .

Análisis sintáctico LALR(1) . . . . . . . . . . . . . . . . . . . .

3. JFlex - Analizador Léxico

3.1. Principales características

. . . . . . . . . . . . . . . . . . . . . . . . . .

3.2. Escribir un analizador léxico con JFlex . . . . . . . . . . . . . . . . . . .

3.2.1. Estructura de un archivo jflex . . . . . . . . . . . . . . . . . . . .

3.2.2. Opciones .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.2.3. Reglas y acciones . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.3. Método de escaneo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.4. Generación de código . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.5. Codificación de caracteres . . . . . . . . . . . . . . . . . . . . . . . . . .

3.6. Reglas léxicas .

.

.

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.6.1. Sintaxis . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.6.2. Operadores en las expresiones regulares . . . . . . . . . . . . . . .

3.6.3. Precedencia de operadores . . . . . . . . . . . . . . . . . . . . .

.

3.7. Métodos y atributos de JFlex asequibles en el código de acción . . . . . . .

4. CUP - Analizador Sintáctico

4.1. Especificación de la sintaxis de un fichero .CUP . . . . . . . . . . . . . .

.

4.1.1. Definición de paquete y sentencias import . . . . . . . . . . . .

4.1.2. Sección de código de usuario . . . . . . . . . . . . . . . . . . . .

4.1.3. Declaración de símbolos terminales y no terminales

. . . . . . . .

4.1.4. Declaraciones de precedencia . . . . . . . . . . . . . . . . . . . .

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

. 28

. 28

. 29

31
. 31

. 31

. 31

. 33

. 34

. 35

. 36

. 37

. 37

. 37

. 39

. 40

. 41

43
. 44

. 44

. 45

. 46

. 47

4.1.5. Definición del símbolo inicial de la gramática y reglas de producción . 48

4.2. Ejecutando CUP .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4.3. Uso de las clases Java

. . . . . . . . . . . . . . . . . . . . . . . . . . .

.

.

.

. 49

. 50

III

4.4. Gestión de errores en CUP . . . . . . . . . . . . . . . . . . . . . . . . . .

4.5. Gramática de las especificaciones de un archivo CUP . . . . . . . . . . . .

5. Otras Herramientas utilizadas

5.1. C++ .

. .

. .

. .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5.1.1. E/S Consola de C++ . . . . . . . . . . . . . . . . . . . . . . . . .

5.1.2. Variables .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Nombre .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Tipos de datos

. . . . . . . . . . . . . . . . . . . . . . . . . . .

5.1.3. Estructuras de control

. . . . . . . . . . . . . . . . . . . . . . . .

If - Si

.

.

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

If-Else - Si-Sino . . . . . . . . . . . . . . . . . . . . . . . . . .

switch - Dependiendo-De

. . . . . . . . . . . . . . . . . . . . .

5.1.4. Ciclos .

.

.

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

while - Mientras-Que . . . . . . . . . . . . . . . . . . . . . . . .

for - Para . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

do-while - Haga-Hasta . . . . . . . . . . . . . . . . . . . . . . .

5.2. JAVA .

. .

. .

. .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5.2.1. Entornos de desarrollo para Java . . . . . . . . . . . . . . . . . .

.

5.2.2. Sintaxis del lenguaje . . . . . . . . . . . . . . . . . . . . . . . . .

Sintaxis básica . . . . . . . . . . . . . . . . . . . . . . . . . . .

Tipo de datos primitivos . . . . . . . . . . . . . . . . . . . . . .

Declaración de variables . . . . . . . . . . . . . . . . . . . . . .

5.3. PHP .

.

.

.

.

.

.

.

. . . . . . .