Wyrażenia regularne - automaty

Witam, czy jst ktoś kto pisał podobny projekt: obsługa wyrazeń regularnych w javie - to zaliczenie na automaty. mam kod źródłowy - swój, ale utknąłem. bardzo prosze o pomoc.

Ale na czym utknąłeś?

oparte jest to o działający automat z epsilon przejsciami.

test, ktorego nie przechodzi, bo sie zapetla, to

    @Test
    public void test_parens_regexp_1() throws Exception {
        check_with_java_regexps("(abc)","abcd");

Kod automatu, tj fragment do obslugi wyr. reg:

 //funkcje budujace automat //qs - start
  public void przetworz_wyrazenie(String wyrazenie)
  {
  Object qs = Automat.addState();
  Automat.markAsInitial(qs);   //ustaw jako stan poczatkowy
  Para para = przetworz_podwyrazenie('(' + wyrazenie + ')', 0, qs); //przypisz do pary
                                                                   // to z funkcji ponizej
  Automat.markAsFinal(para.stan_od);
  }

  public Para przetworz_podwyrazenie(String wyrazenie, int indeks, Object stan)
  {
  int index=indeks; //zaczynamy od 0
  ++index;          //i dodajemy od razu 1

  Object alt_q = Automat.addState();
  Automat.addEpsilonTransition(stan, alt_q);  // ze startowego z powyzszej funkcji do alt_q
  Object fq = Automat.addState();
  Object cq = Automat.addState();
  Automat.addEpsilonTransition(alt_q, cq);  //

  // alt_q(qs) -> cq -> fq

  while (( index < wyrazenie.length()) && (wyrazenie.charAt(index) != ')' )) {

   if (( wyrazenie.charAt(index)=='(') && (wyrazenie.charAt(index+1) == '(' )){
    Para para = przetworz_podwyrazenie(wyrazenie, index+1, cq);
    }
    else
   if ( wyrazenie.charAt(index) == '|' ){
    Automat.addEpsilonTransition(cq, fq);
    cq = Automat.addState();
    Automat.addEpsilonTransition(alt_q, cq);
    ++index;
    }else
   if ( wyrazenie.charAt(index+1) == '\\' ){
   Object nq = Automat.addState(); //do zrobienia
    Automat.addTransition(cq, nq, wyrazenie.charAt(index));
    Automat.addEpsilonTransition(cq, nq);
    cq = nq;
    index += 2;
    } else
   if ( wyrazenie.charAt(index+1) == '*' ){
    Object nq = Automat.addState();
    Automat.addEpsilonTransition(cq, nq);
    Automat.addTransition(nq, nq, wyrazenie.charAt(index));
    cq = nq;
    index += 2;
    }else
   if ( wyrazenie.charAt(index+1) == '+' ){
    Object nq = Automat.addState();
    Automat.addTransition(cq, nq, wyrazenie.charAt(index));
    Automat.addTransition(nq, nq, wyrazenie.charAt(index));
    cq = nq;
    index += 2;
    }else
   if ( wyrazenie.charAt(index+1) == '?' ){
    Object nq = Automat.addState(); 
    Automat.addTransition(cq, nq, wyrazenie.charAt(index));
    Automat.addEpsilonTransition(cq, nq);
    cq = nq;
    index += 2;
    }
    else{
    Object nq = Automat.addState();
    Automat.addTransition(cq, nq, wyrazenie.charAt(index));
    cq = nq;
    ++index;
    }
  }


  Automat.addEpsilonTransition(cq, fq);

  if (index+1 < wyrazenie.length()){

  if (wyrazenie.charAt(index+1) == '*'){
  Automat.addEpsilonTransition(alt_q, fq);
  Automat.addEpsilonTransition(fq, alt_q);
  Automat.addTransition(alt_q,fq, wyrazenie.charAt(index));
  ++index;
  }else
  if (wyrazenie.charAt(index+1) == '+'){
  Automat.addEpsilonTransition(fq, alt_q);
  ++index;
  }else
  if (wyrazenie.charAt(index+1) == '?'){
  Automat.addEpsilonTransition(alt_q, fq);
  ++index;
  }
  }

  return new Para(fq,index+1);
  }

}

test zapetla, robi przepełnienie stosu. jak zaimplementowac nawiasy?
lub jak spełnic wymagania testu:

 @Test
    public void test_parens_plus_regexp_2() throws Exception {
        check_with_java_regexps("(ab)+","aabbc");
    }

z przyjemnoscia wkleje wszystkie klasy, badz wrzuce zrarowany pakiet - wszystkie klasy w javie oraz testy. po prostu nie wiem co poprawic bądź dopisać by automat przechodził testy.

Sprawdź czy index jest prawidłowo inkrementowany. na początku metody wstaw wypis parametru index.

Kombinacje z indeksem bezsennie sięgają wczorajszego wieczora. problem w tym, ze automat zapetla się, a ja nie wiem mimo dopisywania println'ów gdzie i jak. zdaję sobie sprawe ze to problem z interpretacją nawiasów. zwiekszanie indexu działa jak powinno, przynajmniej w mojej teorii.

jeśli urodzi to jakąś szczególną wskazówkę - klasa para wygląda nastepująco:

 public class Para {
  public Para(Object state_from, int index)
  {
  stan_od = (Integer) state_from;
  indeks = index;
  }

  public Integer stan_od;
  public Integer indeks;

}

Jedna rada, do debugowania nie uważaj println, tylko debuggera, przynajmniej się wyśpisz.
Użyj typów prostych int a nie Integer.
Object jako typ parametru metody?

  while (( index < wyrazenie.length()) && (wyrazenie.charAt(index) != ')' )) {

   if (( wyrazenie.charAt(index)=='(') && (wyrazenie.charAt(index+1) == '(' )){
    Para para = przetworz_podwyrazenie(wyrazenie, index+1, cq);
    }
   (....)

}

Dlaczego nie zwiększasz zmiennej index? Przecież w każdym obrocie pętli robisz to samo.

@__krzysiek85, to nie to. Też na początku tak myślałem, ale tu siedzi rekurencja pogrzebana i nie ma potrzeby zwiększania index. Jest on przekazywany do metody większy o jeden.

GhostDog napisał(a)

Użyj typów prostych int a nie Integer.

W czym to pomoże podczas debugowania? Używam Evaluate Expression lub po prostu definiuje Watch-e czyli zmienne.