SLR(1) Table Generator — アルゴリズム解説とベンチマーク結果

対象パッケージ: example.com/slrone_table_generator 対象文法（ハードコード）:

S'              -> SelectStatement
SelectStatement -> SELECT IDENTIFIER FROM IDENTIFIER

これは SELECT <id> FROM <id> という単純なSQL文を受理するための文法で、このパッケージはこの文法から SLR(1) 構文解析表（ACTION表 / GOTO表）を機械的に構築する。

1. 全体パイプライン

SLR1TableGenerator は4段階のパイプラインで構文解析表を組み立てる。各段階は前段の出力に依存する。

flowchart LR
    G["文法定義\n(productions / terminals / non-terminals)"] --> A
    A["BuildFirstSets()\nFIRST集合を不動点計算"] --> B
    B["BuildFollowSets()\nFOLLOW集合を不動点計算"] --> C
    C["BuildStates()\nLR(0)正準集合を構築\n(Closure + GoTo)"] --> D
    D["BuildTables()\nACTION/GOTO表を確定\n(REDUCEはFOLLOW集合で決定)"] --> E["SLR(1) 構文解析表\n(ParserData)"]

FIRST/FOLLOW（BuildFirstSets / BuildFollowSets）: 各非終端記号がどの終端記号から始まりうるか（FIRST）、どの終端記号が後続しうるか（FOLLOW）を、変化がなくなるまで反復して求める不動点アルゴリズム。
LR(0)状態集合（BuildStates）: Closure と GoTo を使って「ドット付き生成規則（item）」の集合＝状態を再帰的に展開し、状態遷移グラフ（LR(0)オートマトン）を作る。
表構築（BuildTables）: 各状態内のitemを見て、ドットが終端記号の前ならSHIFT、非終端記号の前ならGOTO、末尾に達していれば対応する非終端のFOLLOW集合を使ってREDUCE（SLR(1)特有の手順）を割り当てる。ドットが生成規則0の末尾ならACCEPT。

2. FIRST / FOLLOW 集合

このパッケージが実際に計算する値（TestBuildFirstSets / TestBuildFollowSets で検証済み）:

非終端記号	FIRST	FOLLOW
`S'`	`{ SELECT }`	`{ EOF }`
`SelectStatement`	`{ SELECT }`	`{ EOF }`

SelectStatement -> SELECT IDENTIFIER FROM IDENTIFIER の右辺先頭が終端記号 SELECT なので FIRST は単純に {SELECT} になる。FOLLOW は「S'の直後は文末（EOF）」という初期条件と、S' -> SelectStatement の右辺末尾が SelectStatement であることから、FOLLOW(S') がそのまま FOLLOW(SelectStatement) に伝播して {EOF} になる。

3. LR(0) 正準集合（状態オートマトン）

BuildStates が構築する状態は次の6つ（TestBuildStates で状態数=6を検証）。• はドット位置。

状態	Item集合
S0 (初期)	`S' -> • SelectStatement` `SelectStatement -> • SELECT IDENTIFIER FROM IDENTIFIER`
S1	`S' -> SelectStatement •`
S2	`SelectStatement -> SELECT • IDENTIFIER FROM IDENTIFIER`
S3	`SelectStatement -> SELECT IDENTIFIER • FROM IDENTIFIER`
S4	`SelectStatement -> SELECT IDENTIFIER FROM • IDENTIFIER`
S5	`SelectStatement -> SELECT IDENTIFIER FROM IDENTIFIER •`

状態遷移図:

stateDiagram-v2
    [*] --> S0
    S0 --> S1 : SelectStatement (GOTO)
    S0 --> S2 : SELECT (SHIFT)
    S2 --> S3 : IDENTIFIER (SHIFT)
    S3 --> S4 : FROM (SHIFT)
    S4 --> S5 : IDENTIFIER (SHIFT)
    S1 --> [*] : EOF / ACCEPT
    S5 --> [*] : EOF / REDUCE production#1

S0 は初期item S' -> •SelectStatement の Closure（右辺先頭が非終端 SelectStatement なので、その生成規則 SelectStatement -> •SELECT... も追加）。S0から SelectStatement で GoTo すると、ドットが末尾まで進んだ S' -> SelectStatement• のみの状態 S1 になり、これがACCEPT状態。S0から SELECT でGoToすると S2、以降 IDENTIFIER→FROM→IDENTIFIER と辿って S5（reduce状態）に至る。

ACTION / GOTO 表

状態	SELECT	IDENTIFIER	FROM	EOF	GOTO(SelectStatement)
0	shift 2				1
1				accept
2		shift 3
3			shift 4
4		shift 5
5				reduce #1

（TestBuildTablesShiftsAndAccept / TestBuildTablesAcceptState / TestBuildTablesNoConflicts で検証。SLR(1)の定義上、この文法は衝突なしに一意に決定できる。）

4. 構文解析の実行例（shift-reduce トレース）

入力 SELECT IDENTIFIER FROM IDENTIFIER EOF を上記の表で駆動した場合の動作（TestParseAcceptsValidSentence が検証）。

ステップ	スタック（状態）	残り入力	アクション
1	`0`	SELECT IDENTIFIER FROM IDENTIFIER EOF	shift → `2`
2	`0 2`	IDENTIFIER FROM IDENTIFIER EOF	shift → `3`
3	`0 2 3`	FROM IDENTIFIER EOF	shift → `4`
4	`0 2 3 4`	IDENTIFIER EOF	shift → `5`
5	`0 2 3 4 5`	EOF	reduce #1 (4記号pop) → goto(0, SelectStatement) = `1`
6	`0 1`	EOF	ACCEPT

不正な入力（例: SELECT FROM EOF、IDENTIFIERが抜けている）は、状態2でACTION表に FROM のエントリが存在しないため、エラーとして拒否される（TestParseRejectsInvalidSentence で検証）。

5. テスト

slrone_table_generator_test.go に9個のテストケースを追加し、全て PASS。

=== RUN   TestBuildFirstSets                    --- PASS
=== RUN   TestBuildFollowSets                   --- PASS
=== RUN   TestBuildStates                       --- PASS
=== RUN   TestBuildStatesTransitionChain        --- PASS
=== RUN   TestBuildTablesShiftsAndAccept        --- PASS
=== RUN   TestBuildTablesAcceptState            --- PASS
=== RUN   TestBuildTablesNoConflicts            --- PASS
=== RUN   TestParseAcceptsValidSentence         --- PASS
=== RUN   TestParseRejectsInvalidSentence       --- PASS
PASS
ok      example.com/slrone_table_generator  0.004s

テスト	検証内容
`TestBuildFirstSets`	FIRST(S'), FIRST(SelectStatement) が `{SELECT}` になること
`TestBuildFollowSets`	FOLLOW(S'), FOLLOW(SelectStatement) が `{EOF}` になること
`TestBuildStates`	正準集合の状態数が6、初期状態のitem数が2であること
`TestBuildStatesTransitionChain`	`SELECT→IDENTIFIER→FROM→IDENTIFIER` の遷移を辿ると生成規則1の完全ドット状態に到達すること
`TestBuildTablesShiftsAndAccept`	4回のSHIFTの連鎖と、最終状態でのREDUCE(#1)が正しいこと
`TestBuildTablesAcceptState`	GOTO後の状態でACCEPTアクションが設定されること
`TestBuildTablesNoConflicts`	`BuildTables()` がSLR(1)衝突(panic)を起こさないこと
`TestParseAcceptsValidSentence`	表を実際にshift-reduce駆動して正しい文を受理できること（end-to-end）
`TestParseRejectsInvalidSentence`	文法違反の入力を正しく拒否すること

6. ベンチマーク詳細

実行環境

項目	値
OS / Arch	linux / amd64
CPU	AMD Ryzen 5 5500U with Radeon Graphics（6コア12スレッド）
Go	go1.27.0
実行コマンド	`go test -run '^$' -bench . -benchmem -count 5`
反復回数	各ベンチマーク5回（`-count 5`）、下表は5回の単純平均

結果一覧（各5回の平均）

ベンチマーク	ns/op	B/op	allocs/op	何を計測しているか
`BenchmarkNewSLR1TableGenerator`	339.0	368	14	`NewSLR1TableGenerator()`。FIRST/FOLLOWエントリの箱（非終端記号2個分）を用意するだけの初期化コスト
`BenchmarkBuildFirstSets`	109.6	16	2	FIRST集合の不動点ループ単体。2つの生成規則を1〜2周で収束
`BenchmarkBuildFollowSets`	93.2	16	2	FOLLOW集合の不動点ループ単体（FIRST計算済み前提）
`BenchmarkBuildStates`	1667	1008	56	LR(0)正準集合の構築（`Closure`+`GoTo`をワークリスト方式で全状態に適用）。6状態・5遷移を生成
`BenchmarkBuildTables`	715.7	392	18	構築済み状態集合からACTION/GOTO表を確定させる処理
`BenchmarkFullPipeline`	2729.6	1800	92	`New→BuildFirstSets→BuildFollowSets→BuildStates→BuildTables` を通しで実行した合計コスト
`BenchmarkClosure`	142.76	96	6	`BuildStates`内で最も頻繁に呼ばれる`Closure`単体の1回あたりコスト
`BenchmarkParse`	368.0	112	3	完成した表を使い`SELECT IDENTIFIER FROM IDENTIFIER EOF`をshift-reduce駆動する（生成した表を「使う」側のコスト）

生データ（-count 5、抜粋・各ベンチマークの5サンプル全て）:

BenchmarkNewSLR1TableGenerator-12    3552787   343.4 ns/op   368 B/op   14 allocs/op
BenchmarkNewSLR1TableGenerator-12    3488185   337.1 ns/op   368 B/op   14 allocs/op
BenchmarkNewSLR1TableGenerator-12    3611790   335.7 ns/op   368 B/op   14 allocs/op
BenchmarkNewSLR1TableGenerator-12    3578470   343.1 ns/op   368 B/op   14 allocs/op
BenchmarkNewSLR1TableGenerator-12    3644223   335.7 ns/op   368 B/op   14 allocs/op

BenchmarkBuildFirstSets-12          10877290   110.2 ns/op    16 B/op    2 allocs/op
BenchmarkBuildFirstSets-12          10979670   109.3 ns/op    16 B/op    2 allocs/op
BenchmarkBuildFirstSets-12          11483030   109.5 ns/op    16 B/op    2 allocs/op
BenchmarkBuildFirstSets-12          10877172   109.8 ns/op    16 B/op    2 allocs/op
BenchmarkBuildFirstSets-12           9640189   109.0 ns/op    16 B/op    2 allocs/op

BenchmarkBuildFollowSets-12         13389686    93.49 ns/op   16 B/op    2 allocs/op
BenchmarkBuildFollowSets-12         13975772    94.50 ns/op   16 B/op    2 allocs/op
BenchmarkBuildFollowSets-12         13193731    92.45 ns/op   16 B/op    2 allocs/op
BenchmarkBuildFollowSets-12         13062498    92.27 ns/op   16 B/op    2 allocs/op
BenchmarkBuildFollowSets-12         13573288    93.32 ns/op   16 B/op    2 allocs/op

BenchmarkBuildStates-12                798087  1562  ns/op  1008 B/op   56 allocs/op
BenchmarkBuildStates-12                803323  1542  ns/op  1008 B/op   56 allocs/op
BenchmarkBuildStates-12                799620  1811  ns/op  1008 B/op   56 allocs/op
BenchmarkBuildStates-12                637086  1687  ns/op  1008 B/op   56 allocs/op
BenchmarkBuildStates-12                627758  1734  ns/op  1008 B/op   56 allocs/op

BenchmarkBuildTables-12               1647218   698.9 ns/op   392 B/op  18 allocs/op
BenchmarkBuildTables-12               1838769   750.7 ns/op   392 B/op  18 allocs/op
BenchmarkBuildTables-12               1798724   709.4 ns/op   392 B/op  18 allocs/op
BenchmarkBuildTables-12               1780263   700.5 ns/op   392 B/op  18 allocs/op
BenchmarkBuildTables-12               1747594   719.0 ns/op   392 B/op  18 allocs/op

BenchmarkFullPipeline-12               415910  2892  ns/op  1800 B/op   92 allocs/op
BenchmarkFullPipeline-12               408030  2715  ns/op  1800 B/op   92 allocs/op
BenchmarkFullPipeline-12               427839  2695  ns/op  1800 B/op   92 allocs/op
BenchmarkFullPipeline-12               427594  2657  ns/op  1800 B/op   92 allocs/op
BenchmarkFullPipeline-12               392166  2689  ns/op  1800 B/op   92 allocs/op

BenchmarkClosure-12                   8518762   142.8 ns/op    96 B/op   6 allocs/op
BenchmarkClosure-12                   8128560   144.2 ns/op    96 B/op   6 allocs/op
BenchmarkClosure-12                   8376278   141.9 ns/op    96 B/op   6 allocs/op
BenchmarkClosure-12                   8639926   142.1 ns/op    96 B/op   6 allocs/op
BenchmarkClosure-12                   8501308   142.8 ns/op    96 B/op   6 allocs/op

BenchmarkParse-12                     3246822   366.3 ns/op   112 B/op   3 allocs/op
BenchmarkParse-12                     3244179   369.4 ns/op   112 B/op   3 allocs/op
BenchmarkParse-12                     3247762   370.2 ns/op   112 B/op   3 allocs/op
BenchmarkParse-12                     3306766   368.0 ns/op   112 B/op   3 allocs/op
BenchmarkParse-12                     3267879   365.9 ns/op   112 B/op   3 allocs/op

考察

BuildStates が最も重い（約1.67µs、56 allocs）。Closure が GoTo のたびに ItemSet をコピー・線形探索（Contains/SameAs）しながら再構築するため、状態数・生成規則数が増えるとコストは状態数と生成規則長に対しておおよそ二乗的に増える構造になっている（item_set.Contains や findState が線形スキャンのため）。この文法では状態数がわずか6なので実害はないが、文法が大きくなった場合はここがボトルネックになりやすい。
FullPipeline（≈2.73µs）はほぼ BuildStates + BuildTables の合計（1.67µs + 0.72µs ≈ 2.39µs、残差はNew/FIRST/FOLLOWの初期化コスト）に一致しており、パイプライン各段が単純に加算的であることが確認できる。
Parse（表を使う側、368ns）はBuildStatesより軽い。表の構築（オフライン処理）は一度きりで良いのに対し、構築済みの表を使った実際の構文解析（オンライン処理）は毎回発生するため、この非対称性は妥当な設計と言える。
FIRST/FOLLOWの計算（約100ns前後）は非終端記号がわずか2個・生成規則が2本しかないため、事実上「1〜2周のループを回すだけ」で無視できるコスト。

ベンチマーク実装上の注意（ハマったポイント）

初期実装では BuildFirstSets 等の単体ベンチマークを

for i := 0; i < b.N; i++ {
    b.StopTimer()
    s := NewSLR1TableGenerator() // 対象呼び出しに必要な前段セットアップ
    b.StartTimer()

    s.BuildFirstSets()
}

という形で書いていたが、これは -benchmem 併用時に実用不可能なレベルまで遅くなった（BenchmarkBuildFirstSets 単体で数分たっても終わらず、途中でプロセスをkillする事態になった）。

原因: -benchmem が有効な状態で StopTimer() / StartTimer() を呼ぶと、Goの testing パッケージは呼び出しのたびに runtime.ReadMemStats()（ストップ・ザ・ワールドを伴うGC統計収集）を実行する。これをループ内で1回転あたり2回（Stop+Start）、b.N が数百万〜一千万規模になる高速なベンチマークで呼び続けると、STWのオーバーヘッドがベンチマーク対象そのものを完全に支配してしまう。

対処: セットアップ（前段の呼び出し）を b.N 個ぶんタイマー計測開始前にまとめて事前生成し、計測ループでは対象メソッド呼び出しのみを行う形に書き換えた（buildUpTo ヘルパー、slrone_table_generator_bench_test.go）。これによりループ内の StopTimer/StartTimer 呼び出しが完全になくなり、上記の結果が数秒〜十数秒で得られるようになった。

7. 再現手順

# テスト
go test ./... -v

# ベンチマーク（5回計測、メモリ統計つき）
go test -run '^$' -bench . -benchmem -count 5

雑なメモ書き

気楽にいきます

SLR(1) Table Generator go