CYK algorithm implementation java

Question

I'm trying to implement the CYK algorithm based on wikipedia pseudocode. When I test the string "a b" for the grammar input:

S->A B

A->a

B->b

It gives me false, and I think it should be true. I have an arraylist called AllGrammar that contains all the rules. For the example above it would contain:

[0]: S->A B
[1]: A->a
[2]: B->b

For the example S->hello and the input string hello it gives me true as it should. More complex tests (more productions) gives me false :S

public static boolean cyk(String entrada) {
    int n = entrada.length();
    int r = AllGrammar.size();
    //Vector<String> startingsymbols = getSymbols(AllGrammar);
    String[] ent = entrada.split("\\s");
    n = ent.length;
    System.out.println("length of entry" + n);
    //let P[n,n,r] be an array of booleans. Initialize all elements of P to false.
    boolean P[][][] = initialize3DVector(n, r);
    //n-> number of words of string entrada, 
    //r-> number of nonterminal symbols

    //This grammar contains the subset Rs which is the set of start symbols
    for (int i = 1; i < n; i++) {
        for(int j = 0; j < r; j++) {
            String[] rule = (String[]) AllGrammar.get(j);
            if (rule.length == 2) {
                if (rule[1].equals(ent[i])) {
                    System.out.println("entrou");
                    System.out.println(rule[1]);
                    P[i][1][j + 1] = true;
                }
            }
        }
    }
    for(int i = 2; i < n; i++) {
        System.out.println("FIRST:" + i);

        for(int j = 1; j < n - i + 1; j++) {
            System.out.println("SECOND:" + j);

            for(int k = 1; k < i - 1; k++) {
                System.out.println("THIRD:" + k);
                for(int g = 0; g < r; g++) {
                    String[] rule = (String[]) AllGrammar.get(g);
                    if (rule.length > 2) {
                        int A = returnPos(rule[0]);
                        int B = returnPos(rule[1]);
                        int C = returnPos(rule[2]);
                        System.out.println("A" + A);
                        System.out.println("B" + B);
                        System.out.println("C" + C);
                        if (A!=-1 && B!=-1 && C!=-1) {
                            if (P[j][k][B] && P[j + k][i - k][C]) {
                                System.out.println("entrou2");
                                P[j][i][A] = true;
                            }
                        }
                    }
                }
            }
        }
    }

    for(int x = 0; x < r; x++) {
        if(P[1][n][x]) return true;
    }

    return false;
}

Answer 1

As compared to the CYK algorithm:

• you have indexing starting at 1, but the arrays would appear to start at 0
• the function returnpos() is not defined, and it's not obvious what it does.

It would seem the problems could be fairly basic in the the use of indexes. If you are new to the language, you might want to get a refresher.