Making Sense of LALR Parser Construction

mgcadmin 07-29-2026

When Donald Knuth published "On the translation of language from left to right" in 1965 he introduced the concept of LR parsers to the world. LR(k) parsers are a family of bottom-up parsers that perform a rightmost derivation in reverse. At the time of their conception the complexity and size requirements meant the computers of the day could not handle them, and so they languished until 1969 when DeRemer published his paper on SLR and LALR construction. 

Since then LR parsing, LALR in particular has come to fairly dominate the parser generator landscape, and with good reason: LALR parsers have nearly the language recognition power of full LR(1) while maintaining the same number of states of the weaker SLR parsers. To understand how this is possible you need to understand SLR and CLR closure, how they differ from eachother, and how they are similar.

LALR - Look Ahead Left Right is truth be told, a terrible choice of name. Not because it is a particularly bad description, in that regard its actually fine. The problem is that both SLR and CLR parsers also use lookahead! In fact, if you were take an SLR parser, and give it's states the look ahead sets from a CLR parser you'd end up at an LALR parser! It was this last realization that made the whole thing click for me, so in todays post I figured i'd share it with all of you.

SLR Parsers and LR(0) Closure

SLR parsers, and indeed LALR parsers as well, make use of an underlying finite state machine (FSM) whos states are made up of collections of LR "items". This FSM and it's states are built using lexical closure. The type of machine used by SLR parsers is called an LR(0) machine, as that is the class of grammars which it was designed to consume. It has the advantage of being a bit simpler than LR(1) closure, while also being a touch more efficient.

LRState closure(const Grammar& G, const LRState& state) {
    LRState ret;
    queue<LRItem> work;
    for (const LRItem& item : state.getItems()) {
        work.push(item);
        ret.addItem(item);
    }
    while (!work.empty()) {
        LRItem item = work.front();
        Symbol X = item.symbolAfterDot();
        work.pop();
        if (G.nonterminals.count(X)) {
            for (const Production& p : G.productions.at(X)) {
                LRItem newItem(p, 0);
                if (!ret.hasItem(newItem)) {
                    work.push(newItem);
                    ret.addItem(newItem);
                }
            }
        }
    }
    return ret;
}

LRState lr_goto(Grammar& G, const LRState& state, Symbol X) {
    LRState next;
    for (LRItem item : state.getItems()) {
        if (item.symbolAfterDot() == X) {
            next.addItem(item.advance());
        }
    }
    return closure(G, next);
}

There is no concept of lookahead in an LR(0) machine because a) LR(0) grammars don't use lookaheads, and b) SLR parsers derive their lookahead info from a symbols FOLLOW set. This is the reason for their decrease in language recognition power. LALR parsers, despite using LR(1) closure end up having a machine with the same states and transitions as an equivelant LR(0) machine, but with the added context brought by the lookahead sets. 

LR(1) Closure Includes lookahead Info

Unlike LR(0) closure which blindly (but quickly) adds items to states, LR(1) closure has more context to work with and so is a bit more selective albeit slower. It gets this added context by taking into account not just what type of symbol X is, but also by looking at the symbols immediately following it, called the beta first set.

LRState LRGenerator::closure(const Grammar& G, const LRState& state) {
    LRState ret;
    queue<LRItem> work;
    for (const LRItem& item : state.getItems()) {
        work.push(item);
        ret.addItem(item);
    }
    while (!work.empty()) {
        LRItem item = work.front();
        Symbol X = item.symbolAfterDot();
        work.pop();
        if (G.nonterminals.count(X)) {
            //Get First for this positions
            unordered_set<Symbol> betaFirst = firstFromSequence(G, item.betaSymbols());
            if (betaFirst.count(EPS)) {
                betaFirst.erase(EPS);
                betaFirst.insert(item.lookaheads().begin(), item.lookaheads().end());
            }
            for (const Production& p : G.productions.at(X)) {
                LRItem newItem(p, 0);
                //Add first to item
                newItem.lookaheads().insert(betaFirst.begin(), betaFirst.end());
                newItem.rehash();
                if (!ret.hasItem(newItem)) {
                    work.push(newItem);
                    ret.addItem(newItem);
                }
            }
        }
    }
    return ret;
}

LRState lr_goto(Grammar& G, const LRState& state, Symbol X) {
    LRState next;
    for (LRItem item : state.getItems()) {
        if (!item.complete() && item.symbolAfterDot() == X) {
            LRItem nextItem = item.advance();
            nextItem.lookaheads().insert(item.lookaheads().begin(), item.lookaheads().end());
            nextItem.rehash();
            next.addItem(nextItem);
        }
    }
    return closure(G, next);
}

The beta first set is computed using the firstFromSequence() method, who's input sequence is the substring of symbols in the current production starting from dot position + 1.

unordered_set<Symbol> firstFromSequence(const Grammar& G, SymbolString seq) {
    unordered_set<Symbol> result;
    for (Symbol X : seq) {
        if (G.terminals.count(X)) {
            result.insert(X);
            return result;
        }
        if (G.nonterminals.count(X)) {
            result.insert(G.firsts.at(X).begin(), G.firsts.at(X).end());
            if (result.find(EPS) == result.end())
                return result;
        }
    }
    result.insert(EPS);
    return result;
} 

Having looked now at both LR(0) and LR(1) closure we can turn our attention to the actual process of building the CFSM.

Building LALR Machines

While LALR machines can be made by starting with an LR(0) machine and post-processing it to add lookahead info, it is much more straight forward of a process to build an LALR machine by merging LR(1) states instead. This merging can be done either after performing the full LR(1) construction, or - more practically, it can be performed "on the fly" as states are being created.

void LRGenerator::generate_CFSM(Grammar& G, Symbol ss) {
    LRState start;
    queue<int> fq;
    unordered_map<string,int> seen;
    LRItem first_item(G.productions[ss][0], 0); 
    first_item.lookaheads().insert("$");  
    start.addItem(first_item);
    LRState I0 = closure(G, start);
    I0.setStateNum(0);
    fq.push(0);
    seen.insert({I0.coreKey(),I0.getStateNum()});
    states.push_back(I0);
    while (!fq.empty()) {
        LRState curr = states[fq.front()]; fq.pop();
        unordered_set<Symbol> valid;
        for (auto item : curr.getItems()) {
            Symbol tmp = item.symbolAfterDot();
            if (tmp != "<fin>")
                valid.insert(tmp);
        }
        for (auto X : valid) {
            LRState gt = lr_goto(G, curr, X);
            if (gt.getItems().empty())
                continue;
            int target;
            if (seen.find(gt.coreKey()) == seen.end()) {
                gt.setStateNum(states.size());
                fq.push(gt.getStateNum());
                states.push_back(gt);
                seen.insert({gt.coreKey(),gt.getStateNum()});
                target = gt.getStateNum();
            } else {
                target = seen[gt.coreKey()];
                if (states[target].mergeLookaheadsFrom(gt)) {
                    fq.push(states[target].getStateNum()); 
                    cout<<"\t - Existing state: I"<<target<<" merged lookaheads"<<endl;
                }
            }
            if (!cfsm.hasEdge(curr.getStateNum(), target, X)) {
                cfsm.addEdge(curr.getStateNum(), target, X);   
            }
        }
    }
}

This construction is very similar to the CLR CFSM construction, practically identical if not for two slight changes:

 - First, where the full LR(1) construction uses the full key identity - production number, dot position, and look ahead set - the LALR construction relies on LR(0) core identity, via the coreKey() method which does not include the lookahead info.

- Second, when we encounter a state with the same core as a state we've already seen we merge their lookahead sets and discard the new state instead of keeping it as we did for CLR(1).

Aside from those two changes, everything else from closure through to table generation and even the parsing algorithm itsself is exactly the same. This is why LALR is not so much its own class of grammar as it is a space saving optimization of LR(1) grammars that can only be applied to a (large) subset of larger LR(1) class of grammars.

---