1.1.- Alfabeto
Un alfabeto es un conjunto finito no vacío, cuyos elementos
se denominan letras o símbolos. Denotamos un alfabeto arbitrario con la letra Σ.
De símbolos del alfabeto Notaciones:
|ω| denota la longitud de la cadena ω.
λ denota a una cadena de longitud 0, también conocida como palabra vacía
Vn denota al conjunto de todas las palabras de longitud n sobre V
V0 denota al conjunto cuyo unico elemento es la palabra vacia, es decir, V0={λ}
V*denota al conjunto de todas las cadenas de cualquier longitud sobre V.
V+ denota al conjunto de toda las cadenas de cualquier longitud sobre V, excepto la vacía.
Un elemento de Vn es una cadena del tipo a 1 a 2...an donde cada ai ∈ V.
1.2 CADENAS
John Martin en su
libro “Lenguajes formales y teoría de la computación” define como
Cadena en un alfabeto
Ʃ se obtiene al ordenar elementos de Ʃ, este autor no define la palabra cadena
en sí pero si la utiliza mucho en
Sus definiciones para
lenguajes y alfabeto. Otra definición de Jonh E. Hpocroft,
Rajeev Motwani y
Jeffrey D. Ullman en su libro “Introducción a la teoría de
Autómatas, Lenguajes
y Computación” nos dicen que una cadena (también
Llamada palabra) es
una secuencia finita de símbolos pertenecientes a un
Alfabeto.
Una cadena o una
palabra sobre un alfabeto, admitidos la existencia de una única cadena que no
tiene símbolo la cual se denomina cadena básica.
La longitud de cadena
es el único símbolo que contiene:
Ejemplo
|abc|= 4,
|a+2*b|+5
|000111|=6
|if a>b then a=b;|=9
Cadena vacía
Es la única cadena de
caracteres tamaño cero.
Concatenación de
cadenas
la concatenación de
dos cadenas u y v, escrita uv es pagar las dos cadenas para formar una sola.
Ejemplo
uw= cabb
(uv)= abcabb
u(vW)= abcabb
Universo del discurso.
Es un conjunto de
todas las cadenas donde podemos formar con símbolos del alfabeto V le
denominamos universo del discurso de V y la representamos de la siguiente
manera W (V). Es evidente que W(V) es un conjunto infinito y que la cadena
vacía pertenece a W(V).
Ejemplo:
Un afabeto con una
sola letra V = { a }, podemos decir que el universo del discurso es: W(V) = {
λ, a, aa, aaa, aaaa,....} y asi contiene una cadenas infinitas.
Faces de un
compilador.
Es un programa que
lee un programa escrito en un lenguaje, el lenguaje fuente y lo traduce a un
programa equivalente en otro lenguaje, el lenguaje objeto como parte de este
proceso de traducción el compilador informa al usuario de la presencia de erros
en el programa fuente.
Modelo de Análisis y síntesis
de la Compilación.
En la compilación hay
dos partes análisis y síntesis la parte del análisis divide al programa fuente
en sus elementos componentes y crea una representación intermedia del programa
fuente. La parte de síntesis construye el programa objeto deseado a partir de
la representación intermedia. De las dos partes, la síntesis es la que requiere
las técnicas más especializadas.
● Maigualida Perez Mrlgarejo
1.3
LENGUAJES, TIPOS Y HERRAMIENTAS
Un lenguaje es un conjunto de
cadenas, todas ellas seleccionadas de un subconjunto finito donde el conjunto
es un determinado alfabeto. Es una forma de representar información basada en
un conjunto finito de signos o símbolos.
TIPOS DE LENGUAJES
Lenguajes de bajo nivel: Son lenguajes totalmente dependientes de la máquina, es decir que el
programa que se realiza con este tipo de lenguajes no se puede migrar o
utilizar en otras máquinas. Al estar prácticamente diseñados a medida del
hardware, aprovechan al máximo las características del mismo. Dentro de este
grupo se encuentran:
· El
lenguaje maquina: este lenguaje ordena a la máquina las operaciones
fundamentales para su funcionamiento.
Su desventaja es que son bastantes difíciles de manejar y usar, además
de tener códigos fuente enormes donde encontrar un fallo es casi imposible.
· El
lenguaje ensamblador: es un derivado del lenguaje máquina y está formado por
abreviaturas de letras y números llamadas mnemotécnicos.
Las desventajas de este lenguaje siguen siendo prácticamente las mismas
que las del lenguaje ensamblador, añadiendo la dificultad de tener que aprender
un nuevo lenguaje difícil de probar y mantener.
Lenguajes
de alto nivel Son aquellos que se encuentran más
cercanos al lenguaje natural que al lenguaje máquina. Están dirigidos a
solucionar problemas mediante el uso de EDD's (Estructuras Dinámicas de Datos).
Son estructuras que pueden cambiar de
tamaño durante la ejecución del programa. Nos permiten crear estructuras de
datos que se adapten a las necesidades reales de un programa. Se tratan de
lenguajes independientes de la arquitectura del ordenador.
Lenguajes de Medio nivel Estos lenguajes se encuentran en un punto medio entre los dos
anteriores. Dentro de estos lenguajes podría situarse C ya que puede acceder a
los registros del sistema, trabajar con direcciones de memoria, todas ellas
características de lenguajes de bajo nivel y a la vez realizar operaciones de
alto nivel.
HERRAMIENTAS;
Editores de estructuras Un
editor de estructuras toma como entrada una secuencia de órdenes para construir
un programa fuente. El editor de estructuras no solo realiza las fuentes de
creación y modificación de textos de un editor de textos ordinarios, sino que
también analiza el texto del programa, imponiendo al programa fuente una
estructura jerárquica apropiada. Ejemplos:
Editores de C, Pascal, Visual Studio (Fox Pro, Basic, etc.).
mpresoras estéticas Una impresora estética analiza un programa y lo imprime de forma que la
estructura del programa resulte claramente visible. Por ejemplo, los
comentarios pueden aparecer con un tipo de letra especial, y las proposiciones
pueden aparecer con una identificación proporcional a la profundidad de su
anidamiento en la organización jerárquica de las proposiciones. EJEMPLOS: Word,
Excel, Power Point, Photoshop, etc.
· Verificadores estáticos: Un verificador
estático lee un programa, lo analiza e intenta descubrir errores potenciales
sin ejecutar el programa. Ejemplos: Editores de C y Pascal. Verificadores
estáticos de sintaxis (como lint) permiten detectar muchos errores antes de la
compilación. (Algo parecido a lo que se obtiene con la opción -fsyntax- only
del compilador de GNU).
· Intérpretes: Un intérprete realiza las
operaciones que implica el programa fuente. Para una proposición de asignación,
por ejemplo, un intérprete podría construir un árbol y después efectuar las
operaciones de los nodos con forme “recorre” el árbol. Ejemplos: Los
intérpretes (para lenguajes como Lisp o Basic, o para programas con sus propios
lenguajes interpretados como Derive o Mathematica) Shells de sistemas operativos
o de alguna aplicación como un SMBD.
http://slideshare.net/luyzmeyner/lenguajes-autmatas
● Reyes Castillo Blanca Estela
1.4.- 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 análisis
·
Fase de síntesis
Ensamblador.
El
programa ensamblador es el programa que realiza la traducción de un programa
escrito en ensamblador a lenguaje máquina. Esta traducción es directa e
inmediata, ya que las instrucciones en ensamblador no son más que nemotécnicos de
las instrucciones máquina que ejecuta directamente la CPU.
Tipos
de ensambladores
Podemos distinguir entre tres tipos de ensambladores:
·
Ensambladores básicos. Son de muy bajo nivel, y su
tarea consiste básicamente en ofrecer nombres simbólicos a las distintas
instrucciones.
·
Ensambladores modulares, o macro ensambladores.
Descendientes de los ensambladores básicos. Hacen todo lo que puede hacer un
ensamblador, y además proporcionan una serie de directivas para definir e
invocar macroinstrucciones.
·
Ensambladores modulares 32-bits o de alto nivel.
Son ensambladores que aparecieron como respuesta a una nueva arquitectura de
procesadores de 32 bits, realizan la misma tarea que los anteriores,
permitiendo también el uso de macros, permiten utilizar estructuras de
programación más complejas propias de los lenguajes de alto nivel.
Compilador
Un compilador es un programa informático que traduce un programa escrito en un lenguaje de programación a otro lenguaje de programación, es decir programa que permite traducir el código fuente de un programa en lenguaje de alto nivel, a otro lenguaje de nivel inferior (lenguaje máquina). Generando un programa equivalente a capaz de interpretar.
Componentes
en que se divide un compilador:
Análisis Léxico. En esta
fase se lee los caracteres del programa fuente y se agrupan en cadenas que
representan los componentes léxicos. A la secuencia de caracteres que
representa un componente léxico se le llama lexema (o con su nombre en inglés
token).
Análisis Sintáctico. Los
componentes léxicos se agrupan en frases gramaticales que el compilador utiliza
para sintetizar la salida.
Análisis Semántico. Intenta
detectar instrucciones que tengan la estructura sintáctica correcta, pero que
no tengan significado para la operación implicada.
Generación de código Intermedio. Se
puede considerar esta operación intermedia como un subprograma para una máquina
abstracta, a esta representación debe tener dos propiedades importantes: debe
ser fácil de producir y fácil de traducir al programa objeto.
Optimización de Código. Se
trata de mejorar el código intermedio, de modo que resulte un código de máquina
más rápido de ejecutar.
Generación de Código. Esta
constituye la fase final de un compilador.
Administrador de la tabla de símbolos. Se encarga de manejar los accesos a la tabla de símbolos, en cada una de las etapas de compilación de un programa.
Administrador de la tabla de símbolos. Se encarga de manejar los accesos a la tabla de símbolos, en cada una de las etapas de compilación de un programa.
Manejador de errores. Es
posible encontrar errores. De esta forma podrán controlarse más eficientemente
los errores encontrados en cada una de las fases de la compilación de un
programa.
●Rodríguez Medina Rodolfo.
1.5.- 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
-tabla de símbolos
-gestor de errores
• 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.
• 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.
•Análisis semántico: realiza las comprobaciones
necesarias sobre el árbol sintáctico para determinar el correcto significado
del programa.
• 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.
• 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.)
• 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.
• 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.
• 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.)
• 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.
Bibliografia:
Billhardt, H.
(2015). Teoria de automatas y lenguajes formales .
Mata, S. G.
(s.f.). Compiladores.
Serna,
E. (s.f.). Fases de un compilador. Obtenido de
http://www.paginasprodigy.com/edserna/cursos/compilador/notas/Notas1.pdf
●Santiago Reyes Edgarda
INTEGRANTES EQUIPO ROJO
- Martínez Bautista Marisa.
- Pérez Melgarejo Maigualida
- Reyes Castillo Blanca Estela.
- Rodriguez Medina Rodolfo
- Santiago Reyes Edgarda
