Keep Calm And Parse On: Error Handling for LR Parsers

mgcadmin 11-06-2026

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" productions, which tend to nuke any sparse matrix savings. As the title would suggest, the method I'm going to discuss is an adaptation of "panic mode recovery". Panic mode recovery was originally developed for, and is really meant to be used with top down parsing. Its  bottom up variant is slightly less "panicky", and actually works pretty well, so with that said, lets check it out.

Stumble, Don't Fall!

The truth is, If we encounter an error during parsing then we probably won't be able to recover enough to continue with building a working AST. At least not one that would reliably represent what the user intended. Regardless, that doesn't mean that if we encounter an error to immediately exit. If we can, we should try find all of the errors present during a parse, not just the first. In order to be able to do that we need to be able to recover from an error, announce its presence, and resume parsing.

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

There are three actions we can take on encountering an error state to try and remedy the situation: (1) We can pop a state from the state stack, (2) advance the input stream until we find a state/token pair which we can resume parsing from, or (3) push a state to the stack to resume from.

The general idea translates pretty directly into the actual algorithm. 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/statements to our parser, like the following:

println 1 + * 2;
let i := 2;
while (i < 13 {
        println i;
        i := i + 1;
}

we will get output similar to the following:

Syntax error at line 0:12 - *
         'println 1 + * 2;'
Syntax error at line 2:14 - {
         'while (i < 13 {'

Not bad.

---