Acerca de ...

Este blog esta creado con fines educativos por los alumnos:

Roberto Díaz Díaz
Edgar Castañeda Pérez
Jose Guadalupe Valle Avellaneda
Carlos Javier Gómez Aparicio

Estudiantes del ITSH (Instituto Tecnológico Superior de Huetamo) que cursan la carrera de Ingenieria en Sistemas Computacionales, que publican información como apoyo para la materia de Automatas I.

Bibliografía

(Pedro Isasi, 2001)

(John E. Hopcroft, 2002)

(García, 1996)

(Leonardo Alonso Hernandez Rodriguez, 2010)

García, P. (1996). Apuntes sobre la teoría de autómatas y lenguajes formales -167 pages. Universidad Politécnica de Valencia: Pearson.

John E. Hopcroft, R. M. (2002). Introducción a la teoría de autómatas, lenguajes y computación. Panama: Pearson educacion.

Leonardo Alonso Hernandez Rodriguez, S. J. (2010). Practique la teoria de automatas y lengujes formales. Colombia: Armedia, Quindo.

Pedro Isasi, P. M. (2001). Lenguajes,Gramaticas y Automatas. Panama: Addison Wesley

1.7 Fases de un compilador

Fase de análisis sintáctico

Trabaja con una gramática de contexto libre y genera el árbol sintáctico que reconoce su sentencia de entrada. En nuestro caso las categorías gramaticales del análisis léxico son los terminales de la gramática. Para el ejemplo que nos ocupa podemos partir de la gramática: S ÷ <ID> <ASIG> expr <TERM> expr ÷    <ID> | <ID> <+> expr | <ID> <*> expr | <NUM>

De manera que el análisis sintáctico intenta generar un árbol sintáctico que encaje con la sentencia de entrada.

Fase de análisis semántico

Esta fase revisa el árbol sintáctico junto con los atributos y la tabla de símbolos para tratar de encontrar errores semánticos. Para todo esto se analizan los operadores y operan dos de expresiones y proposiciones. Finalmente reúne la información necesaria sobre los tipos de datos para la fase posterior de generación de código.

El componente más importante del análisis semántico es la verificación de tipos. Aquí, el compilador verifica si los operan dos de cada operador son compatibles según la especificación del lenguaje fuente. Si suponemos que nuestro lenguaje solo trabaja con números reales, la salida de esta fase sería su mismo árbol, excepto porque el atributo de <NUM>, que era el entero 8 a la entrada, ahora pasaría a ser el real 8,0. Además se ha debido controlar que las variables implicadas en la sentencia, a saber, comisión, fijo y valor son compatibles con el tipo numérico de la constante 8,0.

Etapa de síntesis

En la etapa anterior se ha controlado que el programa de entrada es correcto. Por tanto, el compilador ya se encuentra en disposición de generar el código máquina equivalente semánticamente al programa fuente. Para ello se parte de las estructuras generadas en dicha etapa anterior: árbol sintáctico y tabla de símbolos.

Fase de generación de código intermedio

Después de la etapa de análisis, se suele generar una representación intermedia explícita del programa fuente. Dicha representación intermedia se puede considerar como un programa para una máquina abstracta.

Fase de optimización de código

Esta fase trata de mejorar el código intermedio, de modo que en la siguiente fase resulte un código de máquina más rápido de ejecutar. Algunas optimizaciones son triviales. En nuestro ejemplo hay una forma mejor de realizar el cálculo de la comisión, y pasa por realizar sustituciones triviales en la segunda y cuarta instrucciones, obteniéndose: t2 = valor * 8.0 comisión= fijo + t2

Fase de generación de código máquina

La fase final de un compilador es la generación de código objeto, que por lo general consiste en código máquina reubicable o código ensamblador. Cada una de las variables usadas por el programa se traduce a una dirección de memoria (esto también se ha podido hacer en la fase de generación de código intermedio). Después, cada una de las instrucciones intermedias se traduce a una secuencia de instrucciones de máquina que ejecuta la misma tarea.

1.6 Estructura de un traductor

Un traductor divide su labor en dos etapas: una que analiza la entrada y genera estructuras intermedias y otra que sintetiza la salida a partir de dichas estructuras.

Básicamente los objetivos de la etapa de análisis son:

 a) controlar la corrección del programa fuente, y 

b) generar las estructuras necesarias para comenzar la etapa de síntesis.

Para llevar esto a cabo, la etapa de análisis consta de las siguientes fases:

Análisis lexicográfico. Divide el programa fuente en los componentes básicos del lenguaje a compilar. Cada componente básico es una su secuencia de caracteres del programa fuente, y pertenece a una categoría gramatical: números, identificadores de usuario (variables, constantes, tipos, nombres de procedimientos,...), palabras reservadas, signos de puntuación, etc.

Análisis sintáctico. Comprueba que la estructura de los componentes básicos sea correcta según las reglas gramaticales del lenguaje que se compila.

Análisis semántico. Comprueba que el programa fuente respeta las directrices del lenguaje que se compila (todo lo relacionado con el significado): chequeo de tipos, rangos de valores, existencia de variables, etc.

Etapa de análisis

En esta etapa se controla que el texto fuente sea correcto en todos los sentidos, y se generan las estructuras necesarias para la generación de código.

Fase de análisis lexicográfico

En esta fase, la cadena de caracteres que constituye el programa fuente se lee de izquierda a derecha y se agrupa en componentes léxicos, que son secuencias de caracteres que tienen un significado atómico; además el analizador léxico trabaja con la tabla de símbolos introduciendo en ésta los nombres de las variables.

1.5 Herramientas computadoras ligadas con lenguajes.

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.

Compilador.

El compilador es un programa informático que traduce un programa escrito en lenguaje de programación y lo pasa a lenguaje de programación, podemos decir que este programa nos permite traducir un código fuente de un programa en lenguaje de nivel alto, y lo pasmos a otro nivel inferior (lenguaje maquina).

Ensambladores.

El ensamblador es el programa en que se realiza la tracción de un programa escrito en ensamblador y lo pasa a lenguaje máquina. Directa o no directa la traducción en que las instrucciones no son más que instrucciones que ejecuta la computadora.

Interpretes.

Los intérpretes son los que realizan normalmente dos operaciones:

• Traducen el código fuente a un formato interno.
• Ejecuta o interpretan el programa traducido al formato interno.

Donde la primera pertenece al interprete el cual llama a veces al compilador, así se genera el código interno, pero no es el lenguaje de máquina, ni lenguaje de símbolos, ni mucho menos un lenguaje de nivel alto.

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 más utilizados como leguaje 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.

1.4 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 más 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.

1.3 Lenguajes

Es un conjunto de cadenas, de todas las seleccionadas de un Σ*. Donde Σ determinado el alfabeto se denomina lenguaje. Si Σ es un alfabeto y L Σ*, entonces L es un lenguaje de Σ. Observe que un lenguaje de Σ no necesita incluir cadenas con todos los símbolos de Σ, ya que una vez que hemos esta que L es un lenguaje de Σ, también sabemos que es un lenguaje de cualquier alfabeto que sea un súper conjunto de Σ.

La elección del término "lenguaje" puede parecer extraña. Sin embargo, los lenguajes habituales pueden interpretarse como conjuntos de cadenas. Un ejemplo seria el inglés, donde la colección de las palabras correctas inglesas es un conjunto de cadenas del alfabeto que consta de todas las letras. Otro ejemplo es el lenguaje C.