Реализация алгоритма CYK Java

Question

Я пытаюсь реализовать алгоритм CYK на основе псевдокода Википедии. Когда я проверяю строку "a b" для ввода грамматики:

S-> AB

A-> а

В-> б

Это дает мне ложь, и я думаю, что это должно быть правдой. У меня есть arraylist под названием AllGrammar, который содержит все правила. Для приведенного выше примера он будет содержать:

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

Для примера S->hello и входной строки hello он дает мне true, как и должно быть. Более сложные тесты (больше производств) дают мне ложь: 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

По сравнению с алгоритмом CYK:

• индексирование начинается с 1, но массивы начинаются с 0
• функция returnpos() не определена, и не очевидно, что она делает.

Казалось бы, проблемы могут быть довольно простыми при использовании индексов. Если вы новичок в этом языке, вы можете получить повышение квалификации.