/* * Scanner.java */package Gramaticas;import java.util.ArrayList;import java.util.HashMap;import java.util.LinkedList;import java.util.Observable;public class Scanner extends Observable { /** * La cola contiene nodos que pueden estar formados por varios simbolos * (terminales y no terminales) */ public LinkedList<ArrayList<Simbolo>> Q; /** */ public ArrayList<Simbolo> u; /** */ public ArrayList<Simbolo> v; /** */ public ArrayList<Simbolo> w; /** */ public ArrayList<Simbolo> uwv; /** */ public ArrayList<Simbolo> q; /** */ public No_terminal A; /** */ public ReglaGIC[] reglasArray; /** */ public boolean done; /** */ public int index; /** */ public int i; /** */ public int j; /** Contador de nodos */ public int cont; /** Contador de nodos */ public int contNodos; /** hijo uwv -> padre q */ public HashMap<ArrayList<Simbolo>, ArrayList<Simbolo>> T; /** */ public boolean stopondone = true; /** * @param s simbolo inical * @param w cadena * @param G gramatica * @return true/false dependiendo si w se puede derivar de G */ public boolean scanAnchura(Simbolo S, Cadena p, GIC G) throws G_Exception { Q = new LinkedList<ArrayList<Simbolo>>(); u = new ArrayList<Simbolo>(); v = new ArrayList<Simbolo>(); w = new ArrayList<Simbolo>(); uwv = new ArrayList<Simbolo>(); A = null; reglasArray = (ReglaGIC[]) G.reglas.toArray(new ReglaGIC[] {}); cont = 0; contNodos = 1; ArrayList<Simbolo> simIni = new ArrayList<Simbolo>(); simIni.add(S); Q.addFirst(simIni); do { q = Q.getFirst(); Q.removeFirst(); i = 0; System.out.println("////"); done = false; /*Obtenemos q=uAv*/ index = obtenerPrimeroNoTerminal(q); A = new No_terminal(q.get(index).get_id()); u = new ArrayList<Simbolo>(); v = new ArrayList<Simbolo>(); for (int j=0; j<q.size(); j++) { if (j<index) u.add(q.get(j)); else if (j>index) v.add(q.get(j)); } /*Solo consideramos las reglas que se derivan de el simbolo no terminal mas a la izq de q*/ do { // Para cada nodo if (i >= reglasArray.length) /*Si no hay mas reglas*/ done = true; if (!done) { if (reglasArray[i].izqda.toString().equals(A.toString())) { w = new ArrayList<Simbolo>(); w= cloneList(reglasArray[i].drcha); uwv = new ArrayList<Simbolo>(); uwv.addAll(u); uwv.addAll(w); uwv.addAll(v); if (containsNoTerminal(uwv) && coincidePrefijo(uwv, p, obtenerPrimeroNoTerminal(uwv))) { contNodos++; Q.addLast(uwv); this.notifyObservers(); T.put(uwv,q); } } } cont++; i++; } while (!done && !coincideCadena(uwv, p)); } while (stopondone && !Q.isEmpty() && !coincideCadena(uwv, p)); if (coincideCadena(uwv, p)) return true; else return false; } /** * * @param array_s * @return */ public static int obtenerPrimeroNoTerminal(ArrayList<Simbolo> array_s) { for (Simbolo s: array_s) { if (s instanceof No_terminal) return(array_s.indexOf(s)); } return(-1); } /** * * @param array_s * @return */ public static boolean containsNoTerminal(ArrayList<Simbolo> array_s) { if (array_s.isEmpty()) return(true); for (Simbolo s: array_s) { if (s instanceof No_terminal) return true; } return false; } /** * * @param uwv * @param p * @param index * @return */ public static boolean coincidePrefijo(ArrayList<Simbolo> uwv, Cadena p, int index) { int i=0; for (Simbolo s: uwv) { if (i< index) { if (s.id != p.get(i).id) return(false); i++; } } return(true); } /** * * @param uwv * @param p * @return */ public static boolean coincideCadena(ArrayList<Simbolo> uwv, Cadena p) { if (uwv.size() != p.size()) return false; return(coincidePrefijo(uwv, p, uwv.size())); } /** * * @param list * @return */ public static ArrayList<Simbolo> cloneList(ArrayList<Simbolo> list){ ArrayList<Simbolo> newlist = new ArrayList<Simbolo>(); for (Simbolo obj : list) { //if (obj is ICloneable) newlist.add((Simbolo) obj.clone()); } return newlist; }}