Package Algoritmos
Enviado por darkjesus • 27 de Junio de 2014 • 3.017 Palabras (13 Páginas) • 238 Visitas
package algoritmos;
import estructuras.*;
import analisis.Alfabeto;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
public class Subconjuntos {
/**
* Log para el algoritmo de subconjuntos.
*/
private static Log log = new Log();
/**
* Realiza la conversión de un AFN a un AFD, aplicando el
* algoritmo 3.20 del libro de Compiladores de Aho (2a. ed).
* @param afn El <code>AFN</code> a convertir.
* @return El <code>AFD</code> equivalente a <code>afn</code>.
*/
public static AFD getAFD(Automata afn) {
Estado estadoOrigen, estadoDestino;
// Logging
log.vaciar();
log.agregar("Cálculo de conjuntos de estados".toUpperCase()).nuevaLinea();
log.agregar("-------------------------------").nuevaLinea().nuevaLinea();
/* AFD resultante */
AFD afd = new AFD(afn.getAlfabeto(), afn.getExprReg());
/* Conjunto de estados finales del AFD */
Conjunto<Conjunto<Estado>> estadosD = new Conjunto<Conjunto<Estado>>();
/*
* En esta cola se iran almacenando temporalmente los conjuntos de
* estados y la operación de marcarlos consistirá en quitarlos la misma
* y guardarlos en estadosD.
* La condición de que no haya estados marcados se dará cuando la cola
* esté vacía.
*/
Queue<Conjunto<Estado>> colaTemp = new LinkedList<Conjunto<Estado>>();
/* Contador de estados procesados del AFD */
int estadosProcesados = 0;
/* Calculamos la Cerradura Epsilon del estado inicial */
Conjunto<Estado> resultado = cerraduraEpsilon(afn.getEstadoInicial());
// Logging
log.agregar("cerradura(" + afn.getEstadoInicial() + ") = " + resultado).nuevaLinea().nuevaLinea();
/*
* Agregamos la Cerradura Epsilon del estado
* inicial del AFN a estadosD sin marcar
*/
estadosD.agregar(resultado);
colaTemp.add(resultado);
/*
* Iniciamos el ciclo principal del algoritmo
*/
while (!colaTemp.isEmpty()) {
/* Marcar T */
Conjunto<Estado> T = colaTemp.remove();
/* Agregamos el correspondiente estado al AFD */
if (afd.cantidadEstados() < estadosD.cantidad())
afd.agregarEstado(new Estado(afd.cantidadEstados()));
/* Estado del AFD a procesar */
estadoOrigen = afd.getEstado(estadosProcesados++);
/* Buscar transiciones por cada simbolo */
for (String simbolo : afn.getAlfabeto()) {
/* Aplicar cerraduraEpsilon(mueve(T, simbolo)) */
Conjunto<Estado> M = mover(T, simbolo);
Conjunto<Estado> U = cerraduraEpsilon(M);
// Logging
log.agregar("cerradura(mover(" + T + ", " + simbolo + ")) = ")
.agregar("cerradura(" + M + ") = " + U)
.nuevaLinea();
if (estadosD.contiene(U)) {
int posicion = estadosD.obtenerPosicion(U);
estadoDestino = afd.getEstado(posicion);
}
else if (!U.estaVacio()) {
estadoDestino = new Estado(afd.cantidadEstados());
afd.agregarEstado(estadoDestino);
/* Agregar U a estadosD (sin marcar) si no está aún */
estadosD.agregar(U);
colaTemp.add(U);
}
else {
/*
* Encontramos un conjunto vacío, por tanto,
* no debemos agregar ninguna transición y
* debemos saltar directamente a evaluar el
* siguiente simbolo del alfabeto.
*/
continue;
}
// Agregamos la transición al AFD
Transicion trans = new Transicion(estadoDestino, simbolo);
estadoOrigen.getTransiciones().agregar(trans);
}
// Logging
log.nuevaLinea();
}
/* Establecemos los estados finales del AFD */
for (int i=0; i < estadosD.cantidad(); i++) {
Estado estadoAFD = afd.getEstado(i);
for (Estado e : estadosD.obtener(i)) {
if (e.getEsFinal()) {
estadoAFD.setEsFinal(true);
break;
}
}
}
afd.setEstadosD(estadosD);
return afd;
...