I don't know how to implement a recursive syntax analyzer

Question

I have the following context free grammar:

E = (E)
E = i | ε

Given an input String, I have to determine whether this String is accepted by this grammar or not, with a recursive syntax analyzer. For example, if I have the input:

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

and I have the code that is supposed to do all of these

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

But I am not sure how to verify that the number of open parentheses ( is the same as the number of close parentheses ).

Do I have to use a while on the verifyParenthesis method?

• Joop Eggen: I think you want a recursive descent parser; that should help in searching.
• SME_Dev: Your E() method creates infinite recursions, because there is no method parameter or variable condition, that would affect the lexico.
• Ira Baxter: See my SO answer on how to build recursive descent parsers once you have a grammar: stackoverflow.com/questions/2245962/…

Answer 1

Recursive as you with. Enjoy.

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

Don't hesitate to ask question if you don't understand what's going on, but try to get it yourself first.