CYK.java

//Algoritem CYK
 
public class CYK {
 
  public class Production  {
    final static char TERMINAL = 't';
    final static char VARIABLE = 'v';
    final static char UNDEFINED = 'u' ;
    char type ;
    Character terminal  ;
    String left, var1, var2;
    public void Production() {
       type = UNDEFINED ;
    }
    public Production(String l, char t) {
       type = TERMINAL ;
       left = l ;
       terminal = new Character(t) ;
    }
    public Production(String l, String v1, String v2) {
       type = VARIABLE ;
       left = l ;
       var1 = v1 ;
       var2 = v2 ;
    }
 
  boolean contains(String v1, String v2) {
      if (type == VARIABLE && var1.compareTo(v1)==0 && var2.compareTo(v2)==0)
        return true ;
      else return false ;
    }
  }
 
  void terminal(Set p, char x, Set s) {
    Production prod ;
    for (Object piter= p.first() ;  !p.overEnd(piter) ; piter=p.next(piter)) {
      prod = (Production) p.retrieve(piter);
      if (prod.type == Production.TERMINAL && prod.terminal.charValue() == x)
        s.insert(prod.left);
    }
  }
 
  void variable(Set p, Set a, Set b, Set c) {
    Production prod ;
    Object bi, ci ;
    for (Object piter= p.first() ;  !p.overEnd(piter) ; piter=p.next(piter)) {
      prod = (Production) p.retrieve(piter);
      for (bi= b.first() ;  !b.overEnd(bi) ; bi=b.next(bi))
        for (ci= c.first() ;  !c.overEnd(ci) ; ci=c.next(ci))
           if (prod.contains((String)b.retrieve(bi), (String)c.retrieve(ci)))
              a.insert(prod.left);
    }
  }
 
  public Production newProduction(String l, char t) {
      return new Production(l, t) ;
  }
 
  public Production newProduction(String l, String v1, String v2) {
    return new Production(l, v1, v2) ;
  }
 
  boolean algCYK(Set p, String s, String w) {
    int i, j, k ;
    Set v[][] = new SetLinked[w.length()][] ;
    for (i=0 ; i < w.length() ; i++) {
      v[i] = new SetLinked[w.length()-i] ;
      for (j=0 ; j < w.length() - i ; j++)
        v[i][j] = new SetLinked() ;
    }
 
    for (j=0 ; j < w.length() ; j++)
      terminal(p, w.charAt(j), v[0][j]) ;  // 1. nivo
    for (i=1 ; i < w.length() ; i++) { // nivoji od 2 do n
       for (j=0 ; j < w.length() - i ; j++) { // vsi podnizi na j-tem nivoju
         v[i][j].makenull();
         for (k = 0; k < i ; k++) // meja med levim in desnim poddrevesom
           variable(p, v[i][j], v[k][j], v[i-k-1][j +k+1]);
      }
   }
   String var ;
   for (Object iter= v[w.length()-1][0].first() ; !v[w.length()-1][0].overEnd(iter) ; iter=v[w.length()-1][0].next(iter)) {
     var = (String)v[w.length()-1][0].retrieve(iter);
     if (var.compareTo(s)==0)
       return true;
   }
   return false  ;
}
 
 
  public static void main(String[] args) {
    CYK cyk = new CYK();
    Production ps[] = new Production[6] ;
    ps[0] = cyk.newProduction("Oklepaji","Predklepaj","Zaklepaj") ;
    ps[1] = cyk.newProduction("Oklepaji", "Predklepaj","OklepajiZ") ;
    ps[2] = cyk.newProduction("Oklepaji", "Oklepaji","Oklepaji") ;
    ps[3] = cyk.newProduction("Predklepaj", '(') ;
    ps[4] = cyk.newProduction("Zaklepaj", ')') ;
    ps[5] = cyk.newProduction("OklepajiZ", "Oklepaji","Zaklepaj") ;
    Set p = new SetLinked() ;
    for (int i=0 ; i < ps.length ; i++)
       p.insert(ps[i]);
    String beseda = "(()())()" ;
    System.out.print("Beseda "+beseda);
    if (cyk.algCYK(p, "Oklepaji", beseda))
      System.out.println(" ustreza gramatiki");
    else System.out.println(" ne ustreza gramatiki");
  }
 
}