Table of Contents

FIRST Β· Implementation (code)

πŸŽ“ This is the Advanced track Β· Implementation.
In the previous page, FIRST Β· Computation Rules, we saw the three cases (terminal / nonterminal / Ξ΅) and the repetition as a rule.
This time we trace how that rule went into the FirstFollowAnalyzer code almost line for line.
(If you haven't read from Definition & Derivation, I recommend starting there.)

Trying it out β€” the public API (one line)

Before going into the details, let's start with how you actually use it.
From the parser, one line gives you the FIRST/FOLLOW of every symbol. (This entrance is shared with FOLLOW β€” a single call gives you both.)

var parser = new LALRParser(grammar);

foreach (var item in parser.GetFirstAndFollow())   // FirstAndFollowCollection
{
    Console.WriteLine($"{item.Symbol}");
    Console.WriteLine($"   FIRST  = {item.First}");
    Console.WriteLine($"   FOLLOW = {item.Follow}");
}

The very sets we worked out by hand in Computation Rules get printed out as is.
So let's go inside and see how this FIRST is built internally.

First β€” the code is two kinds: the calculator and the getter

When you first open the code, there are several methods called First…, which can be confusing.
But really they split into exactly two kinds.

  • FirstSet(...) = the calculator.
    It computes FIRST directly via recursion and fills it into a cache (_cache). The real algorithm is all here.
  • First(...) = the getter.
    Once the computation is done, it just looks up or assembles the result from the cache.

And both have overloads by argument type β€” because FIRST is defined for all three of a single symbol (Symbol), a sequence of symbols (Concat), and a specific production (Single).

So we only have to follow the calculator FirstSet.
The three cases + βŠ• + repetition we saw earlier are all in there.

Where to keep it β€” _cache and _bChanged

private bool _bChanged = false;                                    // "did anything grow this round?" (for ending the loop)
private Dictionary<NonTerminalSingle, TerminalSet> _cache = new(); // FIRST stored per production (filled in gradually)

_cache is the ledger that collects the FIRST of each individual production (Single).
_bChanged is the flag that remembers "did anything grow this round." (It decides when to stop the repetition.)

The calculator (1) β€” FIRST of a single symbol: FirstSet(Symbol)

This is where Case β‘  (terminal) Β· Case β‘‘ (nonterminal) sit, as is.

public TerminalSet FirstSet(Symbol symbol, HashSet<NonTerminalSingle> seenNT = null)
{
    if (symbol is Terminal)                                       // ── Case β‘  : if terminal
        return new TerminalSet(symbol as Terminal);               //    return a set holding just itself

    TerminalSet result = new TerminalSet();                       // ── Case β‘‘ : if nonterminal
    foreach (NonTerminalSingle singleNT in symbol as NonTerminal) //    go through every production
    {
        … (left-recursion guard β€” below) …
        result.UnionWith(FirstSet(singleNT, seenNT));             //    union the FIRST
        result.UnionWith(_cache[singleNT]);                       //    of each production
    }
    return result;
}
  • If the symbol is a terminal, it returns a set holding just itself, as is β†’ exactly Case β‘ .
  • If the symbol is a nonterminal, it goes through every production of that nonterminal with foreach and unions each FIRST.
    β†’ exactly Case β‘‘ + "a nonterminal's FIRST is the union of all its productions' FIRST."
    (Remember how foreach-ing a NonTerminal yields its productions (Single) one at a time?)

The calculator (2) β€” FIRST of a production (sequence): FirstSet(Concat) = βŠ•

A production is, after all, a sequence of symbols (Term '*' Factor).
Its FIRST is β€” per the previous chapter's conclusion β€” the βŠ• (ring-sum) of the symbols' FIRST.

public TerminalSet FirstSet(NonTerminalConcat singleNT, ...)
{
    TerminalSet result = new TerminalSet();
    foreach (var symbol in singleNT)                        // the symbols in order
    {
        result = result.RingSum(FirstSet(symbol, seenNT));  // βŠ• one slot
        if (!result.IsNullAble) break;                      // no more Ξ΅ to look at β†’ stop
    }
    return result;
}

RingSum is exactly βŠ•. The definition is 1:1, so all three cases are inside it.

// TerminalSet.RingSum
if (result.IsNull)            result.UnionWith(param);   //  βˆ… βŠ• B = B
else if (result.IsNullAble) { result.Remove(Ξ΅);          //  if it has Ξ΅ (= can disappear), drop Ξ΅
                              result.UnionWith(param); }  //          and add the next slot B too  β†’ Case β‘’
// otherwise leave it = A   (don't look at B)              β†’ Cases β‘ Β·β‘‘
  • IsNullAble = "does it hold Ξ΅" (Contains(Epsilon)), i.e. the nullable check.
  • if (!result.IsNullAble) break; = "if the front can't disappear, it ends there" β†’ Cases β‘ Β·β‘‘ stop here.
  • if it has Ξ΅, it doesn't break and moves to the next slot β†’ Case β‘’.

That is, all three cases are inside this one loop β€” it's just a matter of where βŠ• stops.

So it doesn't blow up on left recursion β€” the guard

In Case β‘‘ we saw left recursion like Term β†’ Term '*' ….
Recurse naively and it's FirstSet(Term) β†’ FirstSet(Term) β†’ … an infinite loop.
So there's a two-line guard inside FirstSet(Symbol).

if (seenNT.Contains(singleNT)) { result.UnionWith(_cache[singleNT]); … }  // already-seen production?
if (singleNT[0] == symbol)     { result.UnionWith(_cache[singleNT]); … }  // front is itself? (left recursion)

If it's an already-visited production or the front is itself, it doesn't recurse further and just brings in the cache value accumulated so far.
This breaks the infinite loop, while the repetition (next section) fills in the rest on another round.
The previous chapter's "add the so-far value of the front Term" is exactly these two lines.

The whole thing β€” repeat until nothing changes: CalculateAllFirst

public void CalculateAllFirst(HashSet<NonTerminal> nonTerminals)
{
    do
    {
        _bChanged = false;
        foreach (var nonTerminal in nonTerminals) FirstSet(nonTerminal);
    }
    while (_bChanged);     // a full round with no growth β†’ the answer
}

do { _bChanged = false; … } while(_bChanged) β€” that's the previous chapter's fixed-point iteration itself.
If the cache grows even a little inside FirstSet, it keeps _bChanged on, and when there's no change for a full round, it stops.

Getting the result out β€” First(...)

Once the computation (CalculateAllFirst) is done, you now read the result via the getter side, First(...).

public TerminalSet First(NonTerminalSingle key) => _cache[key];   // looks straight up in the cache
public TerminalSet First(NonTerminalConcat concat);               // assembles known FIRSTs with βŠ•
public TerminalSet First(Symbol key);                             // {itself} if terminal, gather from cache if nonterminal

The public API GetFirstAndFollow() we saw at the very start calls these First(...) inside, builds a FirstAndFollowCollection, and returns it.

Formula ↔ code at a glance

Computation rule Code
Case β‘  β€” starts with terminal if (symbol is Terminal) return new TerminalSet(...)
Case β‘‘ β€” starts with nonterminal (+ union) foreach (singleNT in NonTerminal) result.UnionWith(FirstSet(singleNT))
Case β‘’ β€” Ξ΅ / βŠ• result.RingSum(...) + if (!IsNullAble) break;
left-recursion guard if (singleNT[0] == symbol) …
fixed-point iteration do { _bChanged=false; … } while(_bChanged)
compute vs look up FirstSet(...) computes / First(...) gets out

πŸ“Œ The Advanced track always pairs up "rule ↔ our code" like this.

Following along with the example

Starting with FIRST(Factor). Factor : '(' Expr ')' | id.

  • production 1 '(' Expr ')' β†’ FirstSet(Concat): the first symbol '(' is a terminal β†’ RingSum result { '(' }, no Ξ΅ β†’ break immediately. β†’ { '(' }
  • production 2 id β†’ { id }
  • combine the two β†’ FIRST(Factor) = { '(', id } βœ“

FIRST(Term) is Term : Term '*' Factor | Factor.

  • production Factor β†’ { '(', id }
  • production Term '*' Factor β†’ the first symbol is Term (itself, left recursion) β†’ the guard brings in the cache value.
    As the repetition does one more round and Term's cache fills up to { '(', id }, that flows in.
  • converge β†’ FIRST(Term) = { '(', id } βœ“

Expr too, by the same flow, is { '(', id }.
Exactly the same as the answer worked out on the Computation Rules page and the Definition & Derivation page. βœ“

Let's also see Ξ΅ (nullable) actually run in the code. Since expr has no nullable, the trace above always flowed "no Ξ΅ β†’ break immediately." Here's the grammar we'll use for examples in this chapter:

S β†’ A B
A β†’ a | Ξ΅
B β†’ b | Ξ΅

Let's run FIRST(S) through FirstSet(Concat), symbol by symbol of S β†’ A B:

  • first slot A β†’ FirstSet(A) = { a, Ξ΅ }. The RingSum result has Ξ΅ in it (IsNullAble = true) β†’ don't break, move to the next slot (← this is exactly the Case β‘’ path!)
  • second slot B β†’ FirstSet(B) = { b, Ξ΅ }.
  • drop Ξ΅ (Remove(Ξ΅)) and combine with the previous slot: { a } βˆͺ { b, Ξ΅ } = { a, b, Ξ΅ }
  • β†’ FIRST(S) = { a, b, Ξ΅ }

The "don't stop, next slot" branch of if (!result.IsNullAble) break; β€” which never ran in the expr trace above β€” actually fires here at the first slot A.

At a glance β€” the whole FIRST-related spec

This is the skeleton of the FIRST side of FirstFollowAnalyzer.
The logic is emptied out, showing only what's there. (You can see it's split into the calculator FirstSet / the getter First.)

public partial class FirstFollowAnalyzer
{
    private bool _bChanged;
    private Dictionary<NonTerminalSingle, TerminalSet> _cache;

    // ── getter (look up / assemble the finished result) ─────
    public TerminalSet First(NonTerminalSingle key);     // get out of the cache
    public TerminalSet First(NonTerminalConcat concat);  // FIRST of a sequence (assembled with βŠ•)
    public TerminalSet First(Symbol key);

    // ── calculator (recursion + βŠ• + left-recursion guard) ───────
    public TerminalSet FirstSet(Symbol symbol, HashSet<NonTerminalSingle> seenNT = null);
    public TerminalSet FirstSet(NonTerminalConcat singleNT, HashSet<NonTerminalSingle> seenNT = null);

    // ── whole-grammar fixed-point iteration ─────────────────────
    public void CalculateAllFirst(HashSet<NonTerminal> nonTerminals);
}

The helper type TerminalSet : HashSet<Terminal> holds IsNull (empty set) Β· IsNullAble (contains Ξ΅) Β· RingSum (βŠ•).

Next chapter

We've gone a full lap around FIRST β€” definition Β· derivation Β· computation rules Β· code.
That's the answer to "which token does it start with."

Now its partner β€” "which token comes after this," that is, FOLLOW.
Because FOLLOW uses FIRST as raw material (the first line of CalculateAllFollow is CalculateAllFirst), what we just built carries straight over.

πŸ‘‰ FOLLOW Β· Definition & Derivation

Edit this page