Table of Contents

Single — a single production

🎓 This is an Advanced chapter. In the previous Concat chapter we saw how to hold an order (concatenation).
Now we add a "tag" to that order, turning it into a real single production.

First, let's recall one Concat we built in the previous chapter.

   [ Expr ] · [ '+' ] · [ Term ]      ← NonTerminalConcat (a list holding only the order)

This knows the order.
But — it does not know which rule this is, nor which alternative it is.

The author's worry — "sometimes you need to know whose, and which this order is"

Let's look at our example again.

Expr : Expr '+' Term | Term ;

There were two ways to make Expr.
The 0th is Expr '+' Term, the 1st is Term.

But as the parser does its work — drawing a table, emitting diagnostics, or later building LR states — there are many times it has to point precisely and say, "right now, this is the 0th alternative of the Expr rule."

A bare Concat (just [Expr, '+', Term]) cannot say that.
So the author probably judged it this way.

"I already have a Concat that holds the order. If I just add two more tags onto it — 'which rule' and 'which alternative' — then that's exactly a single production, isn't it?"

So what they made is NonTerminalSingle.
Just as the name says, it is "a single production."

📍 NonTerminalSingle : NonTerminalConcat · …/RegularGrammar/NonTerminalSingle.cs

Here : NonTerminalConcat is the key.
Single inherits Concat — that is, it already holds the order (RHS) inside itself, and it just lays the tags on top.

public class NonTerminalSingle : NonTerminalConcat   // ← the order (RHS) is already had via inheritance
{
    private NonTerminal _wholeExpression;   // tag ① "which rule"  (the whole Expr)
    private sbyte       alterIndex = 0;     // tag ② "which alternative" (0, 1, …)
}

In a picture — two tags on top of Concat

Words are abstract, so let's draw it.
If we make the 0th alternative of Expr into a Single, it looks like this.

   Expr : Expr '+' Term | Term ;
                  │  (peel off the 0th alternative)
                  ▼
   NonTerminalSingle
     ├ Name        = "Expr"                 ← taken from _wholeExpression
     ├ alterIndex  = 0                       ← "which alternative"
     └ (RHS — inherited from Concat)  [ Expr ] · [ '+' ] · [ Term ]

And if we print this Single as text (ToGrammarString()), a real single production line comes out.

   ToGrammarString()  →  "Expr -> Expr '+' Term"

You can make the 1st alternative the same way.

   NonTerminalSingle  (alterIndex = 1)
     └ (RHS)  [ Term ]          →  "Expr -> Term"

Look — Concat was just a row of symbols, but once it becomes a Single it turns into a proper unit meaning "one production of Expr."

Why grab the whole rule instead of just copying the name (Name)?

Here a small but author-like decision shows up.

It seems like tag ① could just store the string "Expr", right?
But the code holds onto the whole rule (_wholeExpression, the NonTerminal itself).
And it pulls out the needed pieces of information from there on demand.

public UInt32 UniqueKey      => _wholeExpression.UniqueKey;
public bool   IsStartSymbol  => _wholeExpression.IsStartSymbol;
public bool   AutoGenerated  => _wholeExpression.AutoGenerated;
public bool   IsInduceEpsilon=> _wholeExpression.IsInduceEpsilon;
public string Name           => _wholeExpression.Name;

Why do it this way?

"This production is a part of the living Expr rule. If Expr's identity (UniqueKey) or whether it's the start symbol changes, this Single should automatically follow along too. If you copy it, the two drift apart."

In other words — instead of copying and pasting the name tag, it links to the original.
This also connects to the "identity is UniqueKey" philosophy we saw in the Symbol chapter.
Because Single's identity, in the end, follows the original rule's key.

Identity — "same rule, same alternative" means equal

So how do we tell whether two Singles are the same?
Looking at the code gives the answer.

public override int GetHashCode()
    => Convert.ToInt32(this.UniqueKey.ToString() + this.alterIndex.ToString());

It builds the hash by concatenating UniqueKey and alterIndex.
Put plainly — "which rule (UniqueKey), and which alternative (alterIndex)" is exactly the identity.

Let's see it concretely.
Say Expr's UniqueKey is 7:

   Expr-0  ( UniqueKey=7, alterIndex=0 )  ─┐
   Expr-0  ( UniqueKey=7, alterIndex=0 )  ─┴→  equal   (same hash "70")
   Expr-1  ( UniqueKey=7, alterIndex=1 )  ───→  different   (hash "71")

No matter where they were made separately, two 0th-of-Exprs are treated as the same, and the 0th of Expr and the 1st are distinguished as different productions.
So the parser can ask precisely, "this production — is it really the same as that earlier one?"

A step ahead — this is the seed of an LR item

Let me give a small early hint.
In the previous Concat chapter we said the LR parser marks "how far it has read" with a dot (•), right?
Like A → α • β.

The thing you place that dot on is exactly this Single (a production).

   Single        :  Expr -> Expr '+' Term          ("the production" itself)
   place a dot here →  Expr -> Expr '+' • Term     ("the LR item")

So Single is the production body before the dot is placed.
That is why the identity of "which alternative of which rule" mattered so much.
(The story of placing the dot to make an LR item continues much later, in the LR item chapter.)

At a glance — the full shape of Single

This is the full skeleton of NonTerminalSingle.
The logic is emptied out, showing only what is there.
(Order-related members are inherited as-is from the parent NonTerminalConcat.)

public class NonTerminalSingle : NonTerminalConcat, IShowable
{
    // ── tags (what Single adds) ───────────
    private NonTerminal _wholeExpression;   // which rule (linked to the original)
    private sbyte       alterIndex;          // which alternative

    // ── info taken as-is from the original rule ───
    public UInt32 UniqueKey      { get; }    // = _wholeExpression.UniqueKey
    public string Name           { get; }    // = _wholeExpression.Name
    public bool   IsStartSymbol  { get; }
    public bool   AutoGenerated  { get; }
    public bool   IsInduceEpsilon{ get; }

    // ── construction ────────────────────────────────
    public NonTerminalSingle(NonTerminal target, int index, uint priority, MeaningUnit mu = null);
    public NonTerminalSingle(NonTerminalSingle target);   // clone

    // ── conversion ────────────────────────────────
    public NonTerminal       ToNonTerminal();
    public NonTerminalConcat ToNonTerminalConcat();

    // ── representation ────────────────────────────────
    public string ToGrammarString();          // → "Expr -> Expr '+' Term"
    public string ToTreeString(ushort depth = 1);
    public override string ToString();         // → ToGrammarString()

    // ── identity (rule + alternative number) ─────────────
    public override int GetHashCode();         // concatenates UniqueKey and alterIndex
    public bool Equals(NonTerminalSingle other);
    public static bool operator ==(NonTerminalSingle left, NonTerminalSingle right);
    public static bool operator !=(NonTerminalSingle left, NonTerminalSingle right);

    // … all order-related (RHS) members are inherited from NonTerminalConcat …
}

Boiled down to one line — Single = Concat (order) + "which rule" + "which alternative". That is how it becomes a single production.

📐 The author's design diagram

(This is the author's own design note, so it may require access permission.)

Next chapter

We saw how to express a single production with Single.

But Expr had several productions (the 0th, the 1st…).
The last piece is the container that bundles these several into one.
It is also the true identity of that alters which NonTerminal was holding.

👉 Alter — choice (the set of alternatives)

Edit this page