我不知道如何实现递归语法分析器

Question

我有以下上下文无关语法：

E = (E)
E = i | ε

给定一个输入String，我必须用递归语法分析器来确定这个String是否被这个语法接受。例如，如果我有输入：

((i))<- this is valid
(((i))))<- this is invalid 
()<- this is valid

我有应该做所有这些的代码

public static boolean E() {
    int pOpen;
    pOpen = 0;
    if (lexico.equals("(")) {
        pOpen++;
        E();
    } else if (lexico.equals("i")) {
        if (pOpen == 0)
            return true; //this is valid
        else
            verifyParenthesis();
    }
}
public static boolean verifyParenthesis() {
    int pClose = 0;
    while ((lexico = nextSymbol()).equals(")"))
        pClose++;
}

但我不知道如何验证开括号(的数量与闭括号)的数量相同。

我必须在verifyParentification方法上使用while吗？

Answer 1

递归。享受

public static boolean expressionIsCorrect(String expr) {
        if(!expr.contains("(") && !expr.contains(")")) {
            return true;
        }
        int indexOfLeft = -1;
        int indexOfRight = -1;
        indexOfLeft = expr.indexOf("(");
        indexOfRight = expr.lastIndexOf(")");
        if (indexOfLeft>=indexOfRight) {
            return false;
        }
        return expressionIsCorrect(expr.substring(indexOfLeft+1, indexOfRight));
    }

若你们不明白发生了什么，不要犹豫地问问题，但试着先自己弄清楚。