Search code examples
c++parsingrecursive-descent

Parsing Fully Parenthesized expression

I'm trying to Parse a Fully Parenthesized Exp for this grammar:

exp->(exp + exp)
    |(exp - exp)
    | num
num->[0-9]

...but I have a problem: when I enter "1+4" no error appears. How can I solve it ??

Solution

  • This is a classic problem of recursive descent parsers: your grammar does not require that the entire input is consumed. Once it finishes with the "while isdigit" loop, it considers its job done, ignoring the +4 portion of the input.

    Add a check that the end of line is reached after the call of the top-level expression to address this problem:

    void TopExp() {
    Expr();
    Match('\n');
}

    You need to modify Match to allow matching \n when no additional input is available:

    void Match(char c) {
    int p = cin.peek();
    if(p==c) {
        cin>>c;
    } else if (p == EOF && c == '\n') {
        return
    } else {
        cout<<"Syntax Error! "<<(char)cin.peek()<<endl;
        cin.ignore();
    }
}