Table of Contents

Single — 一つの生成規則

🎓 発展コース です。前の Concat 章で 順序(連接) を入れる方法を見ましたね。
いよいよその順序に 「ラベル」 を貼って、本物の 生成規則一つ に仕立てる段階です。

まず、前の章で作った Concat 一つをもう一度思い出してみましょう。

   [ Expr ] · [ '+' ] · [ Term ]      ← NonTerminalConcat (順序だけを入れたリスト)

これは 順序 は分かります。
ところが — これが どの規則 の、何番目 の選択肢なのかは分かりません。

著者の悩み — 「この順序が 誰の何番目 なのか分からないと困るときがある」

私たちの例をもう一度見ましょう。

Expr : Expr '+' Term | Term ;

Expr を作る方法は二つでしたね。
0番目は Expr '+' Term、1番目は Term です。

ところがパーサが仕事をしていると — 表を描いたり、診断を出したり、後で LR 状態を作るときなど — 「今 これは Expr 規則の0番目の選択肢 だよ」 とはっきり指し示さなければならない場面が多いのです。

裸の Concat(ただの [Expr, '+', Term])だけでは、それを言うことができません。
そこで著者はこう 判断したのでしょう。

「順序を入れる Concat はもうある。そこに 「どの規則」 と 「何番目の選択肢」 というラベルを 二つだけ付け足せば、それがそのまま 生成規則一つ になるじゃないか。」

そうして作ったのが NonTerminalSingle です。
名前のとおり 「一個の(single)生成規則」 です。

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

ここで : NonTerminalConcat が肝心です。
Single は Concat を 継承 します — つまり 順序(RHS)はすでに自分の中に持って いて、そこにラベルだけを載せたのです。

public class NonTerminalSingle : NonTerminalConcat   // ← 順序(RHS)は継承ですでに持っている
{
    private NonTerminal _wholeExpression;   // ラベル① "どの規則"  (Expr 全体)
    private sbyte       alterIndex = 0;     // ラベル② "何番目の選択肢" (0, 1, …)
}

図で — Concat の上にラベル二つ

言葉だけでは抽象的なので描いてみます。
Expr の 0番目 の選択肢を Single にするとこうなります。

   Expr : Expr '+' Term | Term ;
                  │  (0番目の選択肢を取り出して)
                  ▼
   NonTerminalSingle
     ├ Name        = "Expr"                 ← _wholeExpression から取得
     ├ alterIndex  = 0                       ← "何番目の選択肢"
     └ (RHS — Concat 継承)  [ Expr ] · [ '+' ] · [ Term ]

そしてこの Single を文字に起こすと(ToGrammarString())、本物の 生成規則一行 が出てきます。

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

1番目の選択肢も同じように作れます。

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

見てください — Concat はただの 記号の列 でしたが、Single になると 「Expr の生成規則一つ」 という れっきとした単位になりました。

なぜ名前(Name)だけを写さず 規則全体 を掴むのか?

ここに小さいけれど著者らしい決定が一つ見えます。

ラベル①はただの文字列 "Expr" だけを保存すればよさそうですよね?
ところがコードは 規則全体 (_wholeExpression、NonTerminal そのもの)を掴んでいます。
そして必要な情報をそこから その都度取り出して 使います。

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;

なぜこうしたのでしょうか?

「この生成規則は 生きている Expr 規則の一部 だ。Expr の正体(UniqueKey)や開始記号 かどうかが変わったら、この Single も 自動的に 一緒に追従すべきだ。コピーしておいたら別々に動いてしまうじゃないか。」

つまり — 名札を写し貼りするのではなく、元のものに つなげて おいた のです。
Symbol 章で 見た「正体は UniqueKey」という哲学ともつながります。
Single の正体も結局は元の規則のキーに従うのですから。

正体 — 「同じ規則の同じ選択肢」なら同じ

では二つの Single が 同じかどうか はどう見るのでしょう?
コードを見れば答えが出ます。

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

ハッシュを UniqueKey と alterIndex をつなぎ合わせて 作ります。
かみくだいて言うと — 「どの規則(UniqueKey)の、何番目の選択肢(alterIndex)か」がそのまま正体 なのです。

具体的に見てみましょう。
Expr の UniqueKey が 7 だとすると:

   Expr-0  ( UniqueKey=7, alterIndex=0 )  ─┐
   Expr-0  ( UniqueKey=7, alterIndex=0 )  ─┴→  同じ   (ハッシュ "70" が同一)
   Expr-1  ( UniqueKey=7, alterIndex=1 )  ───→  異なる   (ハッシュ "71")

どこで別々に作られたとしても Expr の0番目 同士は同じものとして扱われ、Expr の0番目 と 1番目 は 別の生成規則として区別されます。
パーサが「この生成規則、さっきのあれと同じものだよね?」を正確に問い詰めることが できるわけです。

一歩先取り — これが LR項目 の種です

少しだけ前もって耳打ちしておきます。
前の Concat 章で LR パーサが「どこまで読んだか」をドット(•) で示すと言いましたね?
A → α • β のように。

その ドットを打つ対象がまさにこの Single(生成規則) です。

   Single        :  Expr -> Expr '+' Term          ("生成規則" そのもの)
   ここにドットを打つと →  Expr -> Expr '+' • Term     ("LR項目")

つまり Single は ドットを打つ前の生成規則の本体 です。
だからこそ「どの規則の何番目の選択肢」という 正体がそれほど重要だったのです。
(ドットを打って LR項目を作る話は、ずっと後の LR項目 章で続けます。)

ひと目で — Single の全体像

NonTerminalSingle の 全体の骨格 です。
ロジックは省いて 何があるか だけを見せます。
(順序関連のメンバは 親 NonTerminalConcat からそのまま受け継ぎます。)

public class NonTerminalSingle : NonTerminalConcat, IShowable
{
    // ── ラベル (Single が足したもの) ───────────
    private NonTerminal _wholeExpression;   // どの規則 (元のものに連結)
    private sbyte       alterIndex;          // 何番目の選択肢

    // ── 元の規則からそのまま取得する情報 ───
    public UInt32 UniqueKey      { get; }    // = _wholeExpression.UniqueKey
    public string Name           { get; }    // = _wholeExpression.Name
    public bool   IsStartSymbol  { get; }
    public bool   AutoGenerated  { get; }
    public bool   IsInduceEpsilon{ get; }

    // ── 生成 ────────────────────────────────
    public NonTerminalSingle(NonTerminal target, int index, uint priority, MeaningUnit mu = null);
    public NonTerminalSingle(NonTerminalSingle target);   // 複製

    // ── 変換 ────────────────────────────────
    public NonTerminal       ToNonTerminal();
    public NonTerminalConcat ToNonTerminalConcat();

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

    // ── 正体 (規則 + 選択肢番号) ─────────────
    public override int GetHashCode();         // UniqueKey と alterIndex をつなぎ合わせる
    public bool Equals(NonTerminalSingle other);
    public static bool operator ==(NonTerminalSingle left, NonTerminalSingle right);
    public static bool operator !=(NonTerminalSingle left, NonTerminalSingle right);

    // … 順序(RHS) 関連のメンバはすべて NonTerminalConcat 継承 …
}

一行にまとめると — Single = Concat(順序) + 「どの規則」 + 「何番目の選択肢」。 だから 生成規則 一つ になります。

📐 著者の設計ダイアグラム

(著者本人の設計ノートなので閲覧権限が必要な場合があります。)

次の章

Single で 生成規則一つ を表現する方法を見ました。

ところが Expr は生成規則が 複数(0番目、1番目…)ありましたね。
この複数を 一つにまとめて入れる 器 が最後のピースです。
まさに NonTerminal が抱えていたあの alters の 正体でもあります。

👉 Alter — 択一(選択肢の集合)

Edit this page