java - 自顶向下解析 - Java

Question

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

到目前为止，我有 3 个方法，包括 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 of above grammar 将对应于 aaSa)。另外，我用 \0 表示空字符串。

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

谢谢!

Answer 1

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

假设你的语法是

S -> aaSb |原子能机构 | 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"| 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;
       }
    }
}

像这样也定义了第三个函数。(注意i必须通过引用传递)

您可以引用任何自上而下的解析教程以获取更多详细信息。你可以引用this还有一个。

希望这会有所帮助。