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?

I think you want a **recursive descent parser**; that should help in searching. — Joop Eggen, Oct 10 '14 at 13:38
Your E() method creates infinite recursions, because there is no method parameter or variable condition, that would affect the lexico. — SME_Dev, Oct 10 '14 at 13:42
See my SO answer on how to build recursive descent parsers once you have a grammar: http://stackoverflow.com/questions/2245962/is-there-an-alternative-for-flex-bison-that-is-usable-on-8-bit-embedded-systems/2336769#2336769 — Ira Baxter, Oct 10 '14 at 13:47

score 1 · Answer 1 · answered Oct 10 '14 at 13:44

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.

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

1 Answers1