2

我被分配了一个项目来为任何语法实现一个自上而下的回溯解析器，该语法在其重写规则的 RHS 上仅包含一个非终结符（例如 S -> aaSb | aaSa | aSa）

到目前为止，我有三种方法，包括main，用于处理检查输入字符串的有效性。

我的目标是，使用char[][]语法数组，根据语法检查输入字符串中的每个字符，true如果字符串包含在语法中，则返回。

public class TDBP {
    public static void main(String[] args) {
        char[][] g = new char[][] 
            { {'a', 'a', 'S', 'b'}, 
              {'a', 'a', 'S', 'a'}, 
              {'a', 'S', 'a'}, 
              {'\0'} };

        SP(g);
    }
    public static void SP(char[][] g) {
        Scanner s = new Scanner(System.in);
        boolean again = true; int pn = 0;
        String test;

        while(again) {
            System.out.print("Next string? ");
            test = s.nextLine();

            if(S(pn, test, g))
                System.out.println("String is in the language");
            else
                System.out.println("String is not in the language");

            if(s.nextLine() == "\n") again = false;
        }

        s.close();
    }
    public static boolean S(int pn, String test, char[][] g) {
        char[] c = test.toCharArray();
        boolean exists = false;

        for(int i = pn; i < g.length; i++) {
            for(int j = 0; j < g[i].length; j++) {
                if(c[j] == 'S')
                    S(++pn, test, g);
                if(c[j] == g[i][j])
                    exists = true;
            }
        }

        return exists;
    }
}

在我的算法中，pn是一个整数，用于跟踪我当前正在查看的语法中的哪个产生式，并确保我不会两次扫描相同的语法（例如pn，上述语法中的 1 对应于aaSa）。另外，我\0代表了空字符串。

我是否正确解析了字符串？

谢谢！

4

2 回答 2

2

这可以使用递归下降自上而下解析以更简单的方式解决。

假设你的语法是

S -> aaSb | 阿萨 | 阿萨| # 其中 # 代表空字符串。

在左因子分解之后，它将类似于

S  -> aS' | #
S' -> aSS" | Sa
S" -> b | a

然后在单独的方法中定义每个规则并递归调用，如下所示。

对于第一条规则：S -> aS' | #

function S(char[] input, int &i) {
     if(input[i]=='a') {
       i++;
       return S1(input, i);
      } 
      return true;   //For empty string
}

对于第二条规则：S' -> asSS" | Sa

function s1(char[] input, int &i) {
    if(input[i]=='a') {
       i++;
       S(input, i);
       return S2(input, i);
    } else {
       S(input, i);
       if(input[i]=='a') {
          return true;
       } else {
          return false;
       }
    }
}

像这样定义第三个函数。（注意，我必须通过引用传递）

您可以参考任何自上而下的解析教程以获取更多详细信息。你也可以参考这个。

希望这会有所帮助。

于 2014-11-26T15:23:37.640 回答
1

我对我的 CS 课程有点生疏：但以下代码对我有用：

public static boolean fullCheck(char[] toTest, char[][] g) {
    int val = checkOnAll(0, toTest, g);

    if (val == toTest.length) {
        return true;
    }
    return false;
}

public static int checkOnAll(int charPos, char[] toTest, char[][] g) {
    for(int i = 0; i < g.length; i++) {
        int val = checkOne(charPos, toTest, g[i], g);
        if (val != -1) {
            return val;
        }
    }
    return -1;
}

//also needs length checks
public static int checkOne(int charPos, char[] toTest, char[] rule, char[][] rules) {
    for(int j = 0; j < rule.length; j++) {
        if (charPos >= toTest.length) {
            return -1;
        }
        if(rule[j] == 'S') {
            int value = checkOnAll(charPos, toTest, rules);
            if (value == -1) {
                return -1;
            } else {
                charPos = value - 1;
            }
        } else if (toTest[charPos] != rule[j]) {
            return -1;
        }
        charPos++;
    }
    return charPos;
}

代替“S”函数，使用 fullCheck 函数（将输入作为 char 数组提供给新方法）。我还将“g”数组更改为：

        char[][] g = new char[][]
            { {'a', 'a', 'S', 'b'},
              {'a', 'a', 'S', 'a'},
              {'a', 'S', 'a'},
              {} };

（“\0”给我带来了长度检查的麻烦，上面的更改是最简单的解决方案）。

我在你的代码中发现了一些问题，虽然我不完全确定我自己的代码没有错误，但我想我还是会分享：1.当 S 在你的递归中返回“false”时，但值是忽略。2.“pn”应该仅限于知道我们在哪个测试字符而不是规则字符。3. 即使返回的值为真，你也必须确保你检查了整个测试字符串，而不仅仅是它的一部分。我没有看到你这样做。4. 如果你有一个很长的规则但输入很短，你可能会得到一个数组越界异常，因为你从不查看测试字符串的长度。

我用各种输入尝试了我自己的代码，我觉得我可能错过了一些东西，但我找不到它。如果您发现问题，请告诉我:)

祝你好运。

于 2014-11-24T16:43:51.100 回答