martes, 13 de septiembre de 2011

BIBLIOGRAFIA

  • http://www.google.com/
  • Encarta 2010.
  • Modulo de compiladores de la escuela de ciencias básicas e ingeniería.

Maquinas de estado finito MEF

AUTOMATAS FINITOS (Maquinas de estado finito MEF)

Las máquinas de estado finito son una herramienta muy útil para especificar aspectos relacionados con tiempo real, dominios reactivos o autónomos, computación reactiva, protocolos, circuitos, arquitecturas de software, etc.


Máquina de estado finito es un modelo matemático que realiza cómputos en forma automática sobre una entrada para producir una salida.

Este modelo está conformado por un alfabeto, un conjunto de estados y un conjunto de transiciones entre dichos estados. Su funcionamiento se basa en una función de transición, que recibe a partir de un estado inicial una cadena de caracteres pertenecientes al alfabeto (la entrada), y que va leyendo dicha cadena a medida que el autómata se desplaza de un estado a otro, para finalmente detenerse en un estado final o de aceptación, que representa la salida.


Una MEF consta de:


M= (I,O,S,F,G)
I=  conjunto finito de simbolos de entrada
O= conjunto finito  de simbolos de salida
S= conjunto finito de estados
F= función de estado siguiente S * I  en S
G= función de salida de S *I en O
= estado inicial



1. Encuentre el diagrama de transición de una máquina de estado finito:   



I  = {a, b}
O= {0, 1}
S= { 0, 1, 2 }

Funciones de Estado siguiente:

F ( 0, a) = 2
F ( 0, b) = 0
F ( 1, a)= 1
F ( 1, b)= 1
F ( 2, a)= 0
F ( 2, b)= 1



Funciones de salida.                                                   
G ( 0 ,a)=1                                                           
G ( 1 ,a)=1                                                           
G ( 1 ,b)=1
G ( 2,a)=0
G ( 2 ,b)=1



2. Encuentre el diagrama de transición de una máquina de estado finito:

   


I  = {a, b}
O= {0, 1}
S= { 0, 1}
Funciones de Estado siguiente:

F ( 0, a) = 1
F ( 0, b) = 0
F ( 1, a) = 0
F ( 1, a) = 0


Funciones de salida.                                                   
G ( 0, a)=0                                               
G ( 0, b)=1                                                           
kG ( 1, a)=1
G ( 1, b)=1




Diagrama de transición:

Qué es JFLAP

¿QUE ES EL JFLAT?

JFLAP es un software para la experimentación con temas lenguajes formales como autómatas finitos no deterministas, pushdown autómatas no deterministas, las máquinas multi-cinta de Turing, varios tipos de gramáticas, el análisis, y los sistemas-L. Además de la construcción y prueba de estos ejemplos, JFLAP permite experimentar con las pruebas de la construcción de una forma a otra, como la conversión de un NFA a un DFA a un estado mínimo de DFA a una expresión regular o gramática regular. Haga clic aquí para obtener más información sobre lo que uno puede hacer con JFLAP.

Autómatas finitos y expresiones regulares con JFLAP:

¿Qué es una expresión regular?

Una expresión regular es un lenguaje para poder definir exactamente qué es lo que queremos obtener en una entrada. (texto).

¿Qué es un autómata?Un autómata es un grafo, donde cada arista representa un paso y cada nodo es un estado.

Autómata finito determinístico y no determinístico:
Un Autómata finito NFA O DFA es: una forma gráfica de representar una expresión regular de esta manera es más fácil su comprensión  y sistematización, para permitir su programación.

¿Qué es JFLAP?

Es una aplicación construida en Java, y partiendo de una expresión regular obtener un NFA, además de proporcionar funcionalidades para gramáticas.

domingo, 11 de septiembre de 2011

Intentando programar en jflap 7.0

EJERCICIO

Para este ejemplo usaremos la expresión regular siguiente

´/´ ´*´l (l|D)*  ´.´$ ´*  ´/ ´

A partir de esto construiremos un automata utilizando JFLAP

Programando en assembler turbo versión 5.0

 CARACTERISTICAS DE ASSEMBLER.


  • Traduce programas a lenguaje ensamblador.
  • Para el desarrollo de programas en ensamblador se requiere de la arquitectura  del procesador.
  • Los programas hechos por un programador experto en lenguaje ensamblador son generalmente mucho más rápidos  y consumen menos recursos del sistema. (memoria RAM Y ROM).
  • Con el lenguaje ensamblador se tiene un control muy preciso de las tareas realizadas por un microprocesador.
  • Tiene su representación de instrucciones mediante cadenas alfanuméricas, con el fin de facilitar su escritura
EJERCICIO EN ASSEMBLER

; Un programa en ensamblador que envía un mensaje a pantalla

.model tiny

.stack
.data
         message db "hola que tal$"

.code
start:
         mov dx, OFFSET message
         mov ax, SEG Message
         mov ds, ax; DS; DX
         mov ah, 9
         int 21h
         mov ax,4c00h
         int 21h
end start

Explicacion del ejercicio


  • Se caracteriza porque tiene el punto (.model tiny): el cual es una directiva del modelo de programación que  le dice al ensamblador  el tamaño del programa que vamos a codificar en el ejemplo 01  tiny es porque es programa es pequeño.
  • . stack para hablar de directivas este se utiliza para almacenar todo lo que está en la pila.
  • . data en este coloco el mensaje que vamos a imprimir en pantalla.
  • . code este contiene todo el código del programa, sirve para la asignación  del segmento de código.
  • Sstar línea de código, en el que está el registro de propósito general (mov dx) y  la dirección de la instrucción ( offet message). En el dx almaceno el offet messege.
  • mov dx, ax; Ds:Dx, línea de código que nos permite posicionarnos en memoria.
  • move ah, 9 , en esta línea de código el ah se utiliza para almacenar el registro del numero decimal.
  • int 21h Esta instrucción sirve para llamar un procedimiento, es la llamada de una interrupción del DOS  que va a buscar un valor en ah en el ejemplo 01 permite que se imprima en pantalla hola que tal.
  • move ax, 4c00h  esta es otra línea de código, 4c que le dice al programa  que se salga, oo, dice que el programa no presento errores.

 














Compilador


Un compilador es un programa de cómputo que traduce un lenguaje a otro  generando un programa en el cual la computadora  pueda interpretar. También podemos decir que un  compilador es un programa que permite traducir el código fuente de un programa en lenguaje de alto nivel, a otro lenguaje de nivel inferior (típicamente lenguaje de máquina). De esta manera un programador puede diseñar un programa en un lenguaje mucho más cercano a cómo piensa un ser humano, para luego compilarlo a un programa más manejable por una computadora.



ANALISIS LEXICO.

El Analizador Léxico es la etapa del compilador que va a permitir saber si es un lenguaje de formato libre o no. Frecuentemente va unido al analizador sintáctico en la misma pasada, funcionando entonces como una subrutina de este último. Ya que es el que va leyendo los caracteres del programa, ignorará aquellos elementos innecesarios para la siguiente fase, como los tabuladores, comentarios, espacios en blanco, etc.


ANALISIS SINTACTICO.

Un analizador sintáctico (en inglés parser) es una de las partes de un compilador que transforma su entrada en un árbol de derivación.

El análisis sintáctico convierte el texto de entrada en otras estructuras (comúnmente árboles), que son más útiles para el posterior análisis y capturan la jerarquía implícita de la entrada
                                                            



ANALISIS  SEMANTICO.

El análisis semántico es posterior al sintáctico y mucho más difícil de formalizar que éste. Se trata de determinar el tipo de los resultados intermedios, comprobar que los argumentos que tiene un operador pertenecen al conjunto de los operadores posibles, y si son compatibles entre sí, etc. En definitiva, comprobará que el significado de lo que se va leyendo es válido.

SINTESIS.

En esta etapa se lleva el código del programa fuente a un código interno para poder trabajar más fácilmente sobre él. Esta representación interna debe tener dos propiedades, primero debe ser fácil de representar y segundo debe ser fácil de traducir al código objeto.

GENERACION DE CODIGO INTERMEDIO.

Después de los análisis sintáctico y semántico, algunos compiladores generan una representación intermedia explícita del programa fuente. Se puede considerar esta representación intermedia como un programa para una máquina imprecisa. Esta representación intermedia debe tener dos propiedades importantes; debe ser fácil de producir y fácil de traducir al programa objeto.

GENERACION DE CODIGO.

La generación de código es una de las fases mediante el cual un compilador convierte un programa sintácticamente correcto en una serie de instrucciones a ser interpretadas por una máquina. La entrada en esta fase viene representada, típicamente, por un Árbol Sintáctico

QUE ES UN COMPILADOR: