自上而下解析 - Java的

Question

我被分配一个项目，实现自上而下的回溯解析器只包含一个在其重写规则的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是一个整数跟踪其生产我目前看语法，并确保我不扫描相同的语法两次（如1的pn在上面的语法中将对应于aaSa）。另外，我有\0代表空字符串。

我正确解析字符串吗？

谢谢！

Answer 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一个（给输入的字符数组的新方法）。 我也改变了“G”阵列为：

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

（以下简称“\ 0”给我与长度检查的麻烦，上述变化是最简单的解决方案）。

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

我试着用自己的代码输入各种各样的东西，我有一种感觉，就像我可能错过了某些东西，但是我找不到它。如果你发现问题，请让我知道:)

祝你好运。

Answer 2

这可以通过使用递归下降自顶向下分析以更简单的方式解决。

假设你的语法是

S - > aaSb | aaSa | aSa | ＃其中＃代表空字符串。

左保理后，它会像

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” - > ASS” |萨

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; 
     } 
    } 
} 

喜欢这张限定第三功能也（请注意，我必须通过引用传递）

。你可以参考任何自上而下的分析教程更详细的信息。U可以参考this一也。

希望这将有助于。