3

我写了一些实现CYK 算法的代码。我的代码有一些问题，但我不知道我做错了什么。我还询问了 CYK 算法的伪代码。

你能帮我处理这段代码吗：

import java.util.ArrayList;

public class cyk {

    public static int findIndex(ArrayList<String[]> Grammar, String symbol) {
        for (int i = 0; i < Grammar.size(); i++) {
            String[] rule = Grammar.get(i);
            if (rule.length == 2) {
                if (symbol.equals(Grammar.get(i)[0]))
                    return i;
            }
        }
        for (int i = 0; i < Grammar.size(); i++) {
            if (symbol.equals(Grammar.get(i)[0]))
                return i;
        }
        return -1;

    }

    public static boolean cyk(String S, ArrayList<String[]> Grammar) {
        int n = S.length();
        int r = Grammar.size();

        boolean P[][][] = new boolean[n][n][r];
        initializeP(P, n, r);

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < r; j++) {
                String[] rule = (String[]) Grammar.get(j);
                if (rule.length == 2) {
                    if (rule[1].equals(String.valueOf(S.charAt(i)))) {
                        P[i][0][j] = true;

                        //System.out.println(S.charAt(i));
                    }
                }
            }
        }

        for (int i = 1; i < n; i++) {
            for (int j = 0; j < n - i + 1; j++) {
                for (int k = 0; k < i - 1; k++) {
                    // for each production RA -> RB RC
                    for (int m = 0; m < r; m++) {
                        String[] rule = Grammar.get(m);
                        if (rule.length > 2) {
                            int A = findIndex(Grammar, rule[0]);
                            int B = findIndex(Grammar, rule[1]);
                            int C = findIndex(Grammar, rule[2]);
                            if (P[i][k][B] && P[j + k][i - k][C])
                                P[j][i][A] = true;
                        }
                    }
                }
            }
        }

//       for (int i = 0; i < n; i++) {
//       for (int k = 0; k < r; k++) {
//       System.out.print(P[1][i][k] + " ");
//       }
//       System.out.println();
//       }
        for (int i = 0; i < r; i++) {
            if (P[0][n-1][i])
                return true;
        }
        return false;
    }

    public static void initializeP(boolean P[][][], int n, int r) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < r; k++) {
                    P[i][j][k] = false;
                }
            }
        }
    }

    public static void main(String args[]) {
        /*
         * If size of production is >2 its not unit production
         */
        String input = "aabb";
        ArrayList<String[]> Grammar = new ArrayList<String[]>();
        String[] rule = { "A", "a" };
        Grammar.add(rule);
        String[] rule1 = { "A", "A", "A" };
        Grammar.add(rule1);
        String[] rule2 = { "B", "B", "B" };
        Grammar.add(rule2);
        String[] rule5 = { "B", "b" };
        Grammar.add(rule5);
        String[] rule3 = { "S", "A", "B" };
        Grammar.add(rule3);
        System.out.println(cyk(input, Grammar));

    }
}

感谢你们！

编辑：

调试代码一段时间后，我发现代码的一部分不起作用。

它是：</p> 

for (int i = 1; i < n; i++) {
                for (int j = 0; j < n - i + 1; j++) {
                    for (int k = 0; k < i - 1; k++) {
                        // for each production RA -> RB RC
                        for (int m = 0; m < r; m++) {
                            String[] rule = Grammar.get(m);
                            if (rule.length > 2) {
                                int A = findIndex(Grammar, rule[0]);
                                int B = findIndex(Grammar, rule[1]);
                                int C = findIndex(Grammar, rule[2]);
                                if (P[i][k][B] && P[j + k][i - k][C])
                                    P[j][i][A] = true;
                            }
                        }
                    }
                }
            }

我怀疑这个错误与我遇到的第一个问题有关。很可能是关于我对 AB 和 C 索引的解释方式。有人可以看看 findIndex 是否是查找索引的正确方法吗？

4

0 回答 0