Introducción
A
grandes rasgos, un compilador es un programa que lee un programa escrito en
algún lenguaje y lo traduce a un programa equivalente en otro lenguaje.es
importante que este proceso de traducción es presentar los errores del programa
fuente.
Objetivos
Resumir
de qué manera se compone una cadena un alfabeto y cuál es su estructura y
función de cada lenguaje en donde explicaremos como se realiza cada operación y
como se debe de analizar cada un de ellos.
Alfabeto
Un
alfabeto es un conjunto finito no vacío de símbolos y se denota como
.∑
La
pertenencia de un símbolo
a un alfabeto
se denota como ⥀∑
.
Ejemplo: Podemos representar el alfabeto de las letras minúsculas que utiliza el idioma español, el cual contiene los 27 símbolos siguientes:
Ejemplo: Podemos representar el alfabeto de las letras minúsculas que utiliza el idioma español, el cual contiene los 27 símbolos siguientes:
y sabemos que la letra
pertenece a este alfabeto, lo cual denotaremos como
.
Ya sabemos que los alfabetos son conjuntos, por lo que, todas las operaciones de conjuntos se pueden aplicar a los alfabetos también. Sean
alfabetos, y ya que los alfabetos son conjuntos finitos, no
vacíos, la unión de un número finito de ellos
resulta en un conjunto no vacío y finito, esto es, si
y
La unión de un número arbitrario finito de alfabetos resultará en un conjunto finito y no vacío, es más, si
y
, son conjuntos no vacíos, entonces
son conjuntos finitos, no vacíos, y por lo tanto serán considerados
alfabetos válidos.
Ya sabemos que los alfabetos son conjuntos, por lo que, todas las operaciones de conjuntos se pueden aplicar a los alfabetos también. Sean
La unión de un número arbitrario finito de alfabetos resultará en un conjunto finito y no vacío, es más, si
Cadenas
Una
cadena o palabra es una secuencia finita de símbolos que pertenecen a un
alfabeto y comúnmente se denota con la letra
. La
cadena vacía se denota como
y es una
secuencia vacía de símbolos tomados de cualquier alfabeto
.
Sí el alfabeto es el español, algunas cadenas
pueden ser. Dada la definición anterior, cualquier palabra que contenga
los símbolos del alfabeto es una cadena válida, sin importar si esta tiene o no
significado alguno.
Si
es cualquier cadena, su longitud se denota como
, la longitud de una cadena es el número de símbolos que
contiene, por ejemplo, si tenemos la cadena
sobre el alfabeto español,
. La cadena vacía
no tiene símbolos.
Si
Lenguajes,
tipos y herramientas
Podemos encontrar varios tipos de Lenguajes:
- Lenguaje
Declarativos.- Son los más parecidos al castellano o ingles en su potencia
expresiva y funcionalidad y están ene le nivel más alto respecto a los
otros. Son fundamentalmente lenguaje de órdenes, denominados por
sentencias que expresan “Lo que hay que hacer” en vez de “Como hacerlo”
- Lenguaje
de Alto Nivel.- Son los mas utilizados como lenguaje de programación,
Aunque no son fundamentalmente declarativos, estos lenguajes permiten que
los algoritmos se expresen en un nivel y estilo de escritura fácilmente
legible y comprensible por otros programadores. Además, los lenguajes de
alto nivel suelen tener la característica de “Transportabilidad”.
- Lenguajes
Ensamblador. Y Lenguaje Maquina.- Cada tipo de maquina tiene su propio
lenguajes de maquina distinto y su lenguaje ensamblador asociado. El
lenguaje ensamblador es simplemente una representación simbólica del
lenguaje maquina asociado, lo cual permite una programación menos tediosa
que con el anterior.
Tipos de lenguajes.
Lenguaje natural (castellano)
Nosotros estamos relacionados con el concepto tradicional de gramática que, de esta forma intuitiva, podemos considerar un conjunto de reglas el cual nos indican que es correcto y que no lo es del, lenguaje natural. Con este fin podemos acércanos a la definición mas clara y formal de la lengua castellana.
Lenguaje
artificial.
En este lenguaje aplicamos el mismo método en el cual definimos un fragmento del lenguaje de programación. Donde pretendemos describir las instrucciones el cual nos permite asignar un valor a una expresión ó a una variable en un lenguaje C.
Lenguaje regular.
Llamamos así a los lenguajes porque sus palabras contienen "regularidades" o repeticiones de los mismos componentes, por ejemplo en este lenguaje L1 = { ab, abab, ababab, abababab,...} Este ejemplo podemos apreciar las palabras de L1 son solo repeticiones de "ab" donde se repiten varias veces. Su regularidad consiste en las palabras que contienen "ab" varias veces.
Estructura de un traductor
Un traductor es un programa que tiene como entrada un texto escrito en
un lenguaje (lenguaje fuente) y como salida produce un texto escrito en un
lenguaje (lenguaje objeto) que preserva el significado de origen. Ejemplos de
traductores son los ensambladores y los compiladores.
En el proceso de traducción se identifican dos fases principales:
Fase de Analisis:
Fase de Analisis:
Fase de Sintesis:
Fases de un compilador
• Los compiladores son programas de computadora que
traducen de un lenguaje a otro. Un compilador toma como su entrada un programa escrito
en lenguaje fuente y produce un programa equivalente escrito en lenguaje
objeto.
• Un compilador se compone internamente de varias etapas, o fases, que realizan operaciones lógicas. Es útil pensar en estas fases como piezas separadas dentro del compilador, y pueden en realidad escribirse como operaciones codificadas separadamente aunque en la práctica a menudo se integran.
--Análisis Léxico
– Análisis Sintáctico
– Análisis Semántico
– Generación y Optimización de código intermedio
– Generación de código objeto
• Analizador léxico: lee la secuencia de caracteres de izquierda a derecha del programa fuente y agrupa las secuencias de caracteres en unidades con significado propio (componentes léxicos o “tokens” en ingles).
• Las palabras clave, identificadores, operadores, constantes numéricas, signos de puntuación como separadores de sentencias, llaves, paréntesis, etc. , son diversas clasificaciones de componentes léxicos.
• Análisis sintáctico: determina si la secuencia de componentes léxicos sigue la sintaxis del lenguaje y obtiene la estructura jerárquica del programa en forma de árbol, donde los nodos son las construcciones de alto nivel del lenguaje.
• Se determinan las relaciones estructurales entre los componentes léxicos, esto es semejante a realizar el análisis gramatical sobre una frase en lenguaje natural. La estructura sintáctica la definiremos mediante las gramáticas independientes del contexto.
Análisis semántico: realiza las comprobaciones necesarias sobre el árbol sintáctico para determinar el correcto significado del programa.
• Las tareas básicas a realizar son: La verificación e inferencia de tipos en asignaciones y expresiones, la declaración del tipo de variables y funciones antes de su uso, el correcto uso de operadores, el ámbito de las variables y la correcta llamada a funciones.
• Nos limitaremos al análisis semántico estático (en tiempo de compilación), donde es necesario hacer uso de la Tabla de símbolos, como estructura de datos para almacenar información sobre los identificadores que van surgiendo a lo largo del programa. El análisis semántico suele agregar atributos (como tipos de datos) a la estructura del árbol semántico.
• Generación y optimización de código intermedio: la optimización consiste en la calibración del árbol sintáctico donde ya no aparecen construcciones de alto nivel. Generando un código mejorado, ya no estructurado, más fácil de traducir directamente a código ensamblador o máquina, compuesto de un código de tres direcciones (cada instrucción tiene un operador, y la dirección de dos operándoos y un lugar donde guardar el resultado), también conocida como código intermedio.
• Generación de código objeto: toma como entrada la representación intermedia y genera el código objeto. La optimización depende de la máquina, es necesario conocer el conjunto de instrucciones, la representación de los datos (número de bytes), modos de direccionamiento, número y propósito de registros, jerarquía de memoria, encauzamientos, etc.
• Suelen implementarse a mano, y son complejos porque la generación de un buen código objeto requiere la consideración de muchos casos particulares.
• Tabla de Símbolos: es una estructura tipo diccionario con operaciones de inserción, borrado y búsqueda, que almacena información sobre los símbolos que van apareciendo a lo largo del programa como son: – los identificadores (variables y funciones) – Etiquetas – tipos definidos por el usuario (arreglos, registros, etc.)
Además almacena el tipo de dato, método de paso de parámetros, tipo de retorno y de argumentos de una función, el ámbito de referencia de identificadores y la dirección de memoria. Interacciona tanto con el analizador léxico, sintáctico y semántico que introducen información conforme se procesa la entrada. La fase de generación de código y optimización también la usan.
• Gestor de errores: detecta e informa de errores que se produzcan durante la fase de análisis. Debe generar mensajes significativos y reanudar la traducción.
Encuentra errores:
• Un compilador se compone internamente de varias etapas, o fases, que realizan operaciones lógicas. Es útil pensar en estas fases como piezas separadas dentro del compilador, y pueden en realidad escribirse como operaciones codificadas separadamente aunque en la práctica a menudo se integran.
--Análisis Léxico
– Análisis Sintáctico
– Análisis Semántico
– Generación y Optimización de código intermedio
– Generación de código objeto
• Analizador léxico: lee la secuencia de caracteres de izquierda a derecha del programa fuente y agrupa las secuencias de caracteres en unidades con significado propio (componentes léxicos o “tokens” en ingles).
• Las palabras clave, identificadores, operadores, constantes numéricas, signos de puntuación como separadores de sentencias, llaves, paréntesis, etc. , son diversas clasificaciones de componentes léxicos.
• Análisis sintáctico: determina si la secuencia de componentes léxicos sigue la sintaxis del lenguaje y obtiene la estructura jerárquica del programa en forma de árbol, donde los nodos son las construcciones de alto nivel del lenguaje.
• Se determinan las relaciones estructurales entre los componentes léxicos, esto es semejante a realizar el análisis gramatical sobre una frase en lenguaje natural. La estructura sintáctica la definiremos mediante las gramáticas independientes del contexto.
Análisis semántico: realiza las comprobaciones necesarias sobre el árbol sintáctico para determinar el correcto significado del programa.
• Las tareas básicas a realizar son: La verificación e inferencia de tipos en asignaciones y expresiones, la declaración del tipo de variables y funciones antes de su uso, el correcto uso de operadores, el ámbito de las variables y la correcta llamada a funciones.
• Nos limitaremos al análisis semántico estático (en tiempo de compilación), donde es necesario hacer uso de la Tabla de símbolos, como estructura de datos para almacenar información sobre los identificadores que van surgiendo a lo largo del programa. El análisis semántico suele agregar atributos (como tipos de datos) a la estructura del árbol semántico.
• Generación y optimización de código intermedio: la optimización consiste en la calibración del árbol sintáctico donde ya no aparecen construcciones de alto nivel. Generando un código mejorado, ya no estructurado, más fácil de traducir directamente a código ensamblador o máquina, compuesto de un código de tres direcciones (cada instrucción tiene un operador, y la dirección de dos operándoos y un lugar donde guardar el resultado), también conocida como código intermedio.
• Generación de código objeto: toma como entrada la representación intermedia y genera el código objeto. La optimización depende de la máquina, es necesario conocer el conjunto de instrucciones, la representación de los datos (número de bytes), modos de direccionamiento, número y propósito de registros, jerarquía de memoria, encauzamientos, etc.
• Suelen implementarse a mano, y son complejos porque la generación de un buen código objeto requiere la consideración de muchos casos particulares.
• Tabla de Símbolos: es una estructura tipo diccionario con operaciones de inserción, borrado y búsqueda, que almacena información sobre los símbolos que van apareciendo a lo largo del programa como son: – los identificadores (variables y funciones) – Etiquetas – tipos definidos por el usuario (arreglos, registros, etc.)
Además almacena el tipo de dato, método de paso de parámetros, tipo de retorno y de argumentos de una función, el ámbito de referencia de identificadores y la dirección de memoria. Interacciona tanto con el analizador léxico, sintáctico y semántico que introducen información conforme se procesa la entrada. La fase de generación de código y optimización también la usan.
• Gestor de errores: detecta e informa de errores que se produzcan durante la fase de análisis. Debe generar mensajes significativos y reanudar la traducción.
Encuentra errores:
– En tiempo de compilación: errores léxicos (ortográficos),
sintácticos (construcciones incorrectas) y semánticos (p.ej. errores de tipo)
–
En tiempo de ejecución: direccionamiento de vectores fuera de rango, divisiones
por cero, etc.
– De especificación/diseño: compilan correctamente pero no
realizan lo que el programador desea.
Se trataran sólo errores estáticos (en tiempo de compilación). Respecto a los errores en tiempo de ejecución, es necesario que el traductor genere código para la comprobación de errores específicos, su adecuado tratamiento y los mecanismos de tratamiento de excepciones para que el programa se continúe ejecutando.
La mayoría de los compiladores son dirigidos por la sintaxis, es decir, el proceso de traducción es dirigido por el analizador sintáctico. El análisis sintáctico genera la estructura del programa fuente a través de tokens. El análisis semántico proporciona el significado del programa basándose de la estructura del árbol de análisis sintáctico.
• Las fases de análisis léxico y análisis sintáctico se pueden automatizar de manera relativamente fácil, las verdaderas dificultades en la construcción de compiladores son el análisis semántico, la generación y la optimización de código.
• El número de pasadas, es decir, el número de veces que hay que analizar el código fuente, está en función del grado de optimización. Típicamente se realiza una pasada para realizar el análisis léxico y sintáctico, otra pasada para el análisis semántico y optimización del lenguaje intermedio y una tercera pasada para generación de código y optimizaciones dependientes de la máquina. Estructuras de datos Impla.
Concepto de Expresión Regular
El objetivo de las expresiones
regulares es representar todos los posibles lenguajes definidos sobre un
alfabeto Σ, en base a una serie de lenguajes primitivos, y unos operadores de
composición.
Lenguajes primitivos: el
lenguaje vacío, el lenguaje formado por la palabra vacía, y los lenguajes
correspondientes a los distintos símbolos del alfabeto.
Operadores de composición: la
unión, la concatenación y el cierre.
Ejemplo:
1.Lenguaje formado por las
cadenas que terminan en 01: {0,1}*.{01}= ({0}∪{1})*.{01}
⇒Expresión regular: (0+1)*01
Diseño de expresiones regulares
Lenguaje formado por palabras de
longitud par sobre
a’s y b’s: {aa,ab,ba,bb}*= ({aa}∪{ab}∪{ba}∪{bb})* ⇒Expresión:
(aa+ab+ba+bb)*
(0 + 1)*01 (aa + ab + ba + bb)*
a*(a + b) (aa)*(bb)*b
Aplicaciones en problemas reales
·
Comandos de
búsqueda, erg., grep de Unix
·
Sistema de formato
de texto: usan notación de tipo expresan regular para describir patrones.
·
Convierte la
expresión regular a un DFA o una NFA y simula el autómata en el archivo de
búsqueda.
·
Generadores de
analizadores -léxicos como lex o Flex.
·
Los analizadores
léxicos son parte de un compilador dividen el programa fuente en unidades
lógicas dividen el programa fuente en unidades.
·
Produce un DFA que
reconocen el token.
Las expresiones regulares
denotan lenguajes
Por ejemplo, la expresión
regular:01*+10* denota todas las cadenas que son o un 0 seguido de cualquier
cantidad 1´s o una 1 seguida de cualquier cantidad de o´s.
Ejercicios
1)
Definir 4 alfabetos
2)
Definir 2 cadenas por
alfabeto
3)
Obtener la longitud
por cadena
V1={v, ww,x,y,z}
V2={a,e,i, o,u,2,4,6,8,*,#}
V3={1/2!6-8,3,4}
V4={ford; z-y![%]}
Cadenas
Alou__________ v2
E4#__________ v2
Xyz__________ v1
Wyz__________ v1
1/68__________ v3
2!43__________ v3
z-y!]__________ v4
jforvi__________ v4
concatenación
determinar ∑0 ∑1 ∑2
∑3 ∑4
∑0 ={e}
∑1 ={a,
b}
∑2 ={aa, ab,ba,bb}
∑3={aaa,aab,aba,abb,baa,bab,bba,bbb}
∑4={aaaa,aaab,abaa,aabb,abaa,abab,abba,abbb,baaa,baab,baba,babb,bbaa,bbab,bbba,bbbb}
Expresiones regulares
1.-encuentra la
expresión regular para el conjunto de cadenas sobre el alfabeto {a,b,c} que
tiene el menos una a y al menos una b.
C*a(a+c)*b(a+b+c)*+c*b(b+c)*a(a+b+c)*
2.-encuentra la
expresión regular para el conjunto de cadenas de 0´s y 1´s tal que cada par de
0´s adyacentes aparece antes de cualquier par de 1´s adyacente.
(10+0)*(e+1)(01+1)*e+1)
(10+0)*(e+1)
Desarrollo
DESPUES DE TENER EL CODIGO, SE CREA UNA CARPETA ESPECIFICA
PARA GUARDAR EL “ARCHIVO.L”
UNA VEZ GUARDADO EL ARCHIVO, SE PROCEDE A ENTRAR A CONSOLA
DE COMANDOS
DESPUES DE COLOCAR LA RUTA DEL ARCHIVO, SE COLOCA “FLEX
(NOMBRE_DEL_ARCHIVO)”, PARA QUE NOS GENERE OTRO ARCHIVO EN LA RUTA ESPECIFICADA
UNA VEZ GENERADO, INGRESAMOS EL SIGUIENTE COMANDO “GCC
(NOMBRE_DEL_ARCHIVO) CON EXTENSION (YY.C) -LFL”
CAMBIA LETRAS DE ENTRADA Y SALIDA POR LA LETRA “a”
SE
INICIA CREANDO PROYECTO EN SUBLIME
SE INGRESA EL CODIGO EN SUBLIME
PROCEDE A CREAR LA CARPETA PARA EL ARCHIVO
UNA VEZ GUARDADO EL ARCHIVO, INGRESAMOS A SIMBOLO DE SISTEMA
PARA AGREGARLE LA RUTA DEL ARCHIVO
INGRESAMOS EL NOMBRE DE NUESTRO ARCHIVO PARA QUE NOS GENERE
EL ARCHIVO CON EXTENSION (YY.C)
UNA VEZ INGRESADOS LOS COMANDOS PARA GENERAR EL EJECUTABLE,
EL PROGRAMA ESTA TERMINADO
PROGRAMA QUE CAMBIA LAS LETRAS DE MAYUSCULAS A MINUSCULAS
DESPUES DE INGRESAR A CONSOLA OBTENEMOS LOS ARCHIVOS
DESEADOS
CALCULADORA
PROGRAMA QUE ANALIZA FRASES
Conclusiones
En
este manual vimos conceptos realizamos ejercicios de alfabetización y cadenas,
expresiones regulares y realizamos programas en
canvas.com este manual damos a conocer la importancia del programa que
queremos realizar y del como esta compuesto.
