Keep Calm And Parse On: Error Handling for LR Parsers

mgcadmin 11-06-2026

Generating meaningful error messages during parsing is more difficult than you might think. When it comes down to reporting errors when they do occur, top down parsers tend to have a much better go of it. This is one of the major arguments in favor of using recursive descent based parsers. That's not to say that we can't produce meaninful error messages from bottom up parsers, it's just a bit more difficult, and a whole lot less intuitive.

In todays post I'm going to cover a method of error recovery for LR based parsers that works without the need to add "error" transitions (which tend to nuke any sparse matrix savings). As the title would suggest, this method is an adaptation of "panic mode recovery". Panic mode recovery is really meant for top down parsing, and its  bottom up variant is slightly less "panicky". Lets check it out.

Stumble, Don't Fall!

If we encounter an error during parsing, then depending on the type of error we probably won't be able to recover enough to build a working AST. But we don't want to just encounter an error an immediately exit out. If we can, we should try and find all of the bugs in a program during parsing, not just the first, and to be able to do that we need to be able to recover from an error, announce its presence, and keep parsing.

We have two stacks, the state stack and the semantic stack, and both must be managed in lockstep as they do during parsing. We're going to manage two "back up" stacks so any state change performed while trying to resume can be undone if it turns out to not be productive.

We uncover the top symbol and state, moving them to the back up stacks as described above, and check to to see if the new configuration yields a valid transition.

 bool Parser::parseRecovery(int curr_state, int action, Token& curr_token) {
    stack<int> st_backup;
    stack<astnode*> semantic_backup;
    while (action == PARSE_ERR && !st.empty()) {
        st_backup.push(st.top());
        semantic_backup.push(semStack.top());
        st.pop();
        semStack.pop();
        if (st.empty())
            break;
        curr_state = st.top();
        action = getNext(actTab, curr_state, curr_token.getSymbol());
    }

This continues until we find a combination we can continue on, or we run out of symbols to try. When we run out of symbols, we rewind using our back up stacks, advance the input one position, and try again.

    if (st.empty() && action == PARSE_ERR) {
        while (!st_backup.empty()) {
            semStack.push(semantic_backup.top()); semantic_backup.pop();
            st.push(st_backup.top());
            st_backup.pop();
        }
        advance();
        curr_token = current();
        if (curr_token.getSymbol() != TK_EOI) {
            return parseRecovery(curr_state, action, curr_token);
        }
    }
    return action != PARSE_ERR;
}

And finally If we managed to consume all the input and pop all the states without finding a resumable state we return an error state. It is far more likely that we can resume parsing once we encounter either a semicolon, a closing bracket, or some other terminating/separating token.

Don't Panic And Keep Parsing

The parseRecovery method is wired into the main parsing loop, right where we check the result from the action table. If the action is a parse error, instead of immediately exiting as previously done, we call our new parseRecovery() method.

    bool did_panic = false;
    for (;;) {
        Token curr_token = current();
        int curr_state = st.top();
        int action = getNext(actTab, curr_state, curr_token.getSymbol());
        if (action == PARSE_ERR) {
            cout<<"Syntax error at line "<<curr_token.line()<<":"<<curr_token.column()<<" - "<<curr_token.getString()<<endl;
            cout<<"\t '"<<((FileStringBuffer*)buff)->getLine(curr_token.line())<<"'"<<endl;
            did_panic = parseRecovery(curr_state, action, curr_token);
        } else {
            int rule = actTab[curr_state][action];
            if (rule > 0) {
                doShift(rule);
            } else if (rule < 0) {
                doReduce(rule);
            } else {
                if (did_panic) {
                    cleanUp();
                    return nullptr;
                }
                return cleanUpAndAccept();
            }
        }
    }

We also track whether or not we had to use parseRecovery(), so we know whether or not to return the generated AST.

Now if we were to supply a malformed expression to our parser, we will get output similar to the following:

Syntax error at line 0:12 - *
         'println 1 + * 2;'

Not bad.

---