我不知道如何實現一個遞歸語法分析器

Question

我有以下上下文無關文法：

E = (E) 
E = i | ε 

給定的輸入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++; 
} 

的代碼，但我不知道如何驗證開放括號的數量(與右括號)的數量相同。

我必須在verifyParenthesis方法上使用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)); 
    } 

如果你不明白髮生了什麼，請不要猶豫，問問自己是不是第一個問題。