lalrone_multi_statement_parser ベンチマーク go

テスト & ベンチマーク実施レポート

対象リポジトリ: example.com/lalrone_multi_statement_parser（lalrone_multi_statement_parser4）

このレポートは、expression/qualified_name/table_referenceの3パッケージにテスト・ベンチマークを追加した後にリポジトリ全体の go test と go test -bench を実行した結果をまとめたものである。各パッケージ個別の設計・アルゴリズム解説は既存の */docs/*_ALGORITHM_AND_BENCHMARKS.md を参照し、本レポートは「今回の変更を含めた全パッケージの現在値」に焦点を当てる。

実行環境

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

---

1. テスト結果

go test ./... -v

パッケージ	結果	PASSしたテスト数
lalrone_multi_statement_parser（ルート）	ok	16
lalrone_table_generator	ok	16
lalrone_table_generator/symbol_set	ok	4
semantic_value	ok	4
sql_lexer	ok	20
state_stack	ok	5
statement	ok	6
value_stack	ok	4
expression（今回追加）	ok	5
qualified_name（今回追加）	ok	3
table_reference（今回追加）	ok	3
合計	全てPASS	86 / 86

FAIL は0件。go vet ./... と gofmt -l . も警告なし。

---

2. ベンチマーク結果（5回平均）

以下は各ベンチマークの5サンプル（-count 5）の単純平均。生データは各パッケージで go test <pkg> -run '^$' -bench . -benchmem -count 5 を実行すれば再現できる。

2.1 value_stack / state_stack（スタック基本操作）

ベンチマーク	ns/op	B/op	allocs/op
ValueStackPush（容量内）	35.0	0	0
ValueStackPushWithGrow（毎回grow）	7025	18560	6
ValueStackPushPop	247	256	1
ValueStackPeek	1.01	0	0
StateStackPush（容量内）	57.4	0	0
StateStackPushWithGrow（毎回grow）	6878	16128	6
StateStackPushPop	254	256	1
StateStackPeek	1.02	0	0
StateStackPopCount	57.6	0	0

容量内Pushは0alloc（事前確保したelements配列への書き込みのみ）。growを毎回強制するケースは2桁〜3桁ns重くなり、確保サイズ相応のB/opが乗る。Peekはいずれも約1ns/0allocで、インライン化されたフィールド参照とほぼ同等のコスト。

2.2 semantic_value

ベンチマーク	ns/op	B/op	allocs/op
Token	30.0	80	1
Expression	30.4	80	1
Statement	30.2	80	1
Getters（4アクセサ一括）	1.90	0	0

注目点: 各コンストラクタは80B/1allocで、既存ドキュメント（semantic_value/docs/...）に記載の48B/1allocから増加している。これは今回SELECT_LIST種別（columns []string + selectAll bool）をSemanticValueに追加したことで共用体全体のサイズが増えたため（タグ付き共用体は使わないフィールドがあっても構造体全体を確保する設計のため、既存コンストラクタのコストにも波及する）。

2.3 statement

ベンチマーク	ns/op	B/op	allocs/op
Select	67.0	112	2
Insert	47.6	96	1
Update	48.3	96	1
Delete	48.1	96	1
Drop	50.6	96	1
GetKind	1.50	0	0
Getters（4アクセサ一括）	2.02	0	0

注目点: Selectだけ2allocs（他は1alloc）。Statement構造体自体の確保に加え、ベンチ内で渡している[]string{"id"}という列名スライスリテラル自体がヒープへエスケープしてもう1回確保されるため。実際の構文解析パス（reduce()のcase 9/10）でもColumnListを1列ずつappendで積み上げていくため、複数カラムのSELECTは列数に応じてスライスの再確保が発生し得る（詳細はコードレビューの回答参照）。

2.4 sql_lexer

ベンチマーク	ns/op	B/op	allocs/op	MB/s
Tokenize_Short（短いSELECT文）	652	456	15	56.7
Tokenize_Long（長い複合WHERE）	141,873	80,913	4,794	47.2
Tokenize_Numbers	8,282	9,240	207	193.1
Tokenize_Strings	157,776	62,041	6,607	26.6
Tokenize_Identifiers	25,715	12,440	407	132.2

文字列リテラルのトークナイズ（Tokenize_Strings）が最もスループットが低い（26.6 MB/s）。これはreadString()がbuilder += string(c)という1文字ずつの文字列連結でトークンテキストを構築しており（sql_lexer.go）、Goの文字列は不変なので毎回新しいバッファへコピーが発生するため。数値・識別子はスライスs.input[start:s.position]をそのまま参照するだけなので大幅に速い。

2.5 lalrone_table_generator/symbol_set

ベンチマーク	ns/op	B/op	allocs/op
Add（n=10）	6.0	0	0
Add（n=100）	45.4	0	0
Add（n=1000）	412.9	0	0
Contains（n=10）	34.3	0	0
Contains（n=100）	353.4	0	0
Contains（n=1000）	3483.0	0	0

Add/Containsともにnに対してほぼ線形（n=10→100→1000で約7〜10倍ずつ増加）で、内部実装が線形走査（スライスベースの重複チェック）であることと整合する。0allocなのは追加先のSymbolSetを使い回すベンチ設計のため。

2.6 lalrone_table_generator（LALR(1)表構築パイプライン）

ベンチマーク	ns/op	B/op	allocs/op
NewLALR1TableGenerator	1,165	1,440	43
BuildFirstSets	16,471	728	39
BuildCanonicalStates	15,044,183	4,160,649	192,323
MergeToLalrStates	2,931,457	846,528	11,112
BuildLalrTables	392,129	37,080	1,499
FullPipeline（New→...→BuildLalrTables 一式）	18,617,570	5,046,424	205,016
Closure（単発呼び出し）	3,427	1,544	77

注目点: BuildCanonicalStates（約15.0ms）がFullPipeline（約18.6ms）の8割強を占める、パイプライン中の圧倒的なボトルネック。カノニカルLR(1)状態集合の構築は状態数×クロージャ計算のコストで、今回SELECT_LIST/ColumnList用に4生成規則を追加した結果カノニカル状態数が140→145、LALR併合後の状態数が72→77に増加しており（前回のレビュー参照）、文法追加のたびにこの部分の相対コストが上がっていく。NewLALR1MultiStatementParserはテーブルをコンストラクタで1回だけ構築して使い回す設計になっており、この約18.6msのコストはSQL文1件ごとには発生しない。

2.7 lalrone_table_generator（表を使ったパース: runParseヘルパー経由）

ベンチマーク	ns/op	B/op	allocs/op
ParseSelectStatement	1,883	112	3
ParseInsertStatement	649	112	3
ParseUpdateStatement	2,349	240	4
ParseDeleteStatement	1,767	112	3
ParseDropStatement	461	48	2
ParseSelectStatementWithComplexWhere	9,436	240	4

こちらはASTを組み立てない、表の妥当性検証用の軽量シミュレータ（runParse）による計測。

2.8 ルートパッケージ（Parse() = 実際にASTを組み立てる本番パス）

ベンチマーク	ns/op	B/op	allocs/op
ParseSelect	2,726	1,344	18
ParseInsert	609	576	7
ParseUpdate	2,913	1,408	18
ParseDelete	2,450	1,168	15
ParseDrop	423	416	5
ParseSelectWithComplexWhere（括弧+論理+比較）	10,882	4,192	56
TokenizeAndParseSelect（Tokenize込み）	3,562	1,776	32

runParse（2.7節）と比べ、Parse()（本番パス）は同じ文でも allocs/op が大きい（例: ParseSelectStatement 3allocs → ParseSelect 18allocs）。これはrunParseが状態遷移の正否しか見ないのに対し、Parse()はreduce()内でsemantic_value.*・expression.*・statement.*の各値オブジェクトを実際に構築しながら進むため。

2.9 qualified_name

ベンチマーク	ns/op	B/op	allocs/op
NewQualifiedNameWithQualifier	20.9	32	1
NewQualifiedNameWithoutQualifier	20.2	32	1
StringWithQualifier（"t.id"結合）	28.4	4	1
StringWithoutQualifier（結合なし）	1.52	0	0
Getters（3アクセサ一括）	1.51	0	0

詳細と考察はqualified_nameのドキュメントを参照。

2.10 table_reference

ベンチマーク	ns/op	B/op	allocs/op
NewTableReferenceWithAlias	20.9	32	1
NewTableReferenceWithoutAlias	20.3	32	1
StringWithAlias（"users AS u"結合）	36.7	16	1
StringWithoutAlias（結合なし）	1.01	0	0
Getters（3アクセサ一括）	1.52	0	0

qualified_nameと同型のフラット2-stringラッパーだが、区切り文字列が" AS "（4バイト）で"."（1バイト）より長いぶんStringWithAliasのB/opが大きい。詳細はtable_referenceのドキュメントを参照。

2.11 expression（唯一の再帰的データ構造）

ベンチマーク	ns/op	B/op	allocs/op
Identifier / Number / Binary（各コンストラクタ）	25.1〜25.6	64	1
Getters（5アクセサ一括）	2.02	0	0
StringDepth1（BINARYノード1個）	55.6	16	1
StringDepth5（BINARYノード9個）	564	304	9
StringDepth10（BINARYノード19個）	1392	1072	19

注目点: Expressionはleft/rightで自分自身を指す木構造で、このリポジトリの他パッケージ（semantic_value/statementのようなフラットなタグ付き共用体）とは質的に異なる。String()の再帰呼び出しはBINARYノード1個につき1回の文字列結合（1alloc）を行うため、allocs/opは木のBINARYノード数と正確に一致する。1ノードあたりのコストは深さとともに緩やかに増加する（55.6→62.7→73.3 ns/node）——外側のノードほど、既に組み上がった長い部分文字列をコピーするコストを払うため。詳細はexpressionのドキュメントを参照。

---

3. 補足: SelectList実装メモ

今回のベンチマーク対象コードは、直前のセッションで追加した以下の変更を含む：

• 文法: SelectStatement -> SELECT SelectList FROM IDENTIFIER WhereClause、SelectList -> * | ColumnList、ColumnList -> IDENTIFIER | ColumnList COMMA IDENTIFIER（lalrone_table_generator.go、production #6〜#10）
• semantic_value.SemanticValueにSELECT_LIST種別（columns []string + selectAll bool）を追加
• statement.Selectのシグネチャを(column, table string, where)から(columns []string, selectAll bool, table string, where)に変更
• 併せて、文法に未使用のまま残っていたSTATEMENT_LIST/VALUE_LIST/VALUE/ASSIGNMENT_LIST/ASSIGNMENT/SEMICOLONシンボル宣言（複数文・複数カラムINSERT/UPDATE用の未実装機能の残骸）を削除

これらの変更後もカノニカルLR(1)状態数145・LALR(1)状態数77で衝突（shift/reduce・reduce/reduce）は発生していない（TestBuildLalrTablesNoConflictsでPASS）。

---

4. 再現手順

# 全パッケージのテスト
go test ./... -v

# パッケージごとのベンチマーク（-count 5 で本レポートと同条件）
go test .                                          -run '^$' -bench . -benchmem -count 5
go test ./lalrone_table_generator/...              -run '^$' -bench . -benchmem -count 5
go test ./semantic_value/...                       -run '^$' -bench . -benchmem -count 5
go test ./statement/...                            -run '^$' -bench . -benchmem -count 5
go test ./sql_lexer/...                            -run '^$' -bench . -benchmem -count 5
go test ./value_stack/...                          -run '^$' -bench . -benchmem -count 5
go test ./state_stack/...                          -run '^$' -bench . -benchmem -count 5
go test ./lalrone_table_generator/symbol_set/...   -run '^$' -bench . -benchmem -count 5
go test ./expression/...                            -run '^$' -bench . -benchmem -count 5
go test ./qualified_name/...                        -run '^$' -bench . -benchmem -count 5
go test ./table_reference/...                       -run '^$' -bench . -benchmem -count 5

LALR1MultiStatementParser go

LALR1MultiStatementParser — アルゴリズム解説とベンチマーク結果

対象パッケージ: example.com/lalrone_multi_statement_parser（ルートパッケージ、lalrone_multi_statement_parser.go）

このパッケージはリポジトリ全体のパイプラインを最終的につなぎ合わせる場所である。

入力SQL文字列
  → sql_lexer.Tokenize()                              トークン列を生成
  → lalrone_table_generator.LALR1TableGenerator        ACTION/GOTO表を構築（オフライン、1回だけ）
  → LALR1MultiStatementParser.Parse()                  表を使ったshift-reduce駆動ループ
      → reduce()                                       生成規則ごとの意味アクション
          → select_statement / insert_statement / update_statement /
            delete_statement / drop_statement            各AST（値オブジェクト）を構築
          → statement.From*                              5種類のASTをタグ付き共用体Statementに包む
          → semantic_value.*                              StatementをValueStackで運べる形にラップ
  → []*statement.Statement                             最終的な構文解析結果

SelectStatement/InsertStatement/...自体は各パッケージのドキュメントが説明する「フィールドを保持するだけの値オブジェクト」だが、それらをいつ・どの順で・どのスタックの状態から組み立てるかを制御しているのがこのパッケージのParse/reduceである。

---

1. Parse の shift-reduce 駆動ループ

flowchart TD
    START(["Parse(tokens)"]) --> INIT["states.Push(0)\nposition = 0"]
    INIT --> LOOP{"ループ"}
    LOOP --> LOOKUP["state = states.Peek()\ntoken = tokens[position]\nterminal = tokenToTerminalName(token)\nentry = findAction(state, terminal)"]
    LOOKUP --> NILCHECK{"entry == nil?"}
    NILCHECK -- yes --> PANIC1["panic(\"error\")\n(構文エラー)"]
    NILCHECK -- no --> KIND{"entry.GetAction().GetKind()"}

    KIND -- SHIFT --> SH["states.Push(shift先state)\nvalues.Push(semantic_value.Token(token.GetText()))\nposition++"]
    SH --> LOOP

    KIND -- REDUCE --> RE1["production = GetProduction(productionIndex)\nstates.PopCount(len(production.GetRight()))"]
    RE1 --> RE2["reduced = reduce(productionIndex, values)\n(valuesからもPopしてASTを組み立てる)"]
    RE2 --> RE3["currentState = states.Peek()\ngotoState = findGoto(currentState, production.GetLeft())"]
    RE3 --> GOTONIL{"gotoState < 0?"}
    GOTONIL -- yes --> PANIC2["panic(\"error\")"]
    GOTONIL -- no --> RE4["states.Push(gotoState)\nvalues.Push(reduced)"]
    RE4 --> LOOP

    KIND -- ACCEPT --> ACC["result = values.Peek()\nkind != STATEMENT_LIST なら panic"]
    ACC --> RETURN(["return result.GetStatements()"])

このループ自体はlalrone_table_generatorのテスト内runParseヘルパーが表の検証用に実装している標準的なLR駆動ループと同型だが、runParseが「ACCEPTに到達したかどうか」というbool値しか返さないのに対し、こちらは実際にvalue_stack上にASTを組み立てながら進み、最終的に[]*statement.Statementを返す——つまりrunParseは表が正しいかを検証するテスト用シミュレータ、Parseは実際にASTを生成する本番のドライバという関係にある。

REDUCEが1ステップで「状態のPop」「reduce()呼び出し」「GOTO先の決定」という3段階を踏む点、特にstates.PopCountとreduce()内のvalues.Pop()の回数（＝生成規則の右辺の記号数）が常に一致していなければならない点は暗黙の不変条件で、state_stack/value_stackのどちらか一方だけPop数を間違えるとスタックの対応がずれて後続のREDUCE/GOTOが誤動作する（テストではこの不変条件そのものは直接検証していないが、reduce()のswitch文の各caseが生成規則の右辺長と1対1で書かれていることで担保されている）。

---

2. reduce — 生成規則ごとの意味アクション

24個の生成規則のうち、AST構築の中心になるのはStatementを直接生成する5規則（1〜5）とその構成要素（6〜21）、そして複数文をまとめるStatementList（22〜24）である。SELECT文（生成規則1がラップする生成規則6）を例に、呼び出しの流れを追う:

sequenceDiagram
    participant P as Parse (REDUCE production#6)
    participant R as reduce()
    participant SS as select_statement
    participant ST as statement
    participant SV as semantic_value

    P->>R: reduce(6, values)
    R->>R: where := values.Pop()<br/>table := values.Pop()<br/>values.Pop() // FROM<br/>column := values.Pop()<br/>values.Pop() // SELECT
    R->>SS: NewSelectStatement(column.GetText(), table.GetText(), where.GetWhereColumn())
    SS-->>R: *SelectStatement
    R->>SV: semantic_value.SelectStatement(s)
    SV-->>R: *SemanticValue (kind=SELECT_STATEMENT)
    R-->>P: values.Push(結果) して次のループへ

    Note over P,R: 後続のREDUCE production#1<br/>(Statement -> SelectStatement) で:
    P->>R: reduce(1, values)
    R->>R: v := values.Pop()
    R->>ST: statement.FromSelect(v.GetSelectStatement())
    ST-->>R: *Statement (kind=SELECT)
    R->>SV: semantic_value.Statement(s)
    SV-->>R: *SemanticValue (kind=STATEMENT)
    R-->>P: values.Push(結果)

INSERT/UPDATEはこれと同じ形の2段構成（部品構文 → statement.From*でラップ）に加えて、ColumnList/ValueList/AssignmentListという左再帰の可変長リストを先にたたむ必要がある点が異なる（3節参照）。

3. 可変長リストの組み立て（ColumnList / ValueList / AssignmentList）

flowchart LR
    subgraph "ColumnList -> IDENTIFIER (production#10)"
    A["values.Pop()"] --> B["StringList([]string{id.GetText()})"]
    end
    subgraph "ColumnList -> ColumnList COMMA IDENTIFIER (production#11)"
    C["id := values.Pop()\nvalues.Pop() // COMMA\nlist := values.Pop()"] --> D["StringList(append(list.GetItems(), id.GetText()))"]
    end
    B -.->|"次のCOMMA IDENTIFIERで\nさらに畳み込まれる"| C

ColumnList/ValueListは同じ形の左再帰規則で、production#11/#13のappend(list.GetItems(), ...)が生成規則の入力順そのままでリストを伸ばしていく（末尾に追加）。これはINSERT INTO users (id, name) VALUES (1, 'bob')でGetColumns() == []string{"id", "name"}（書いた順）になることの直接的な根拠であり、TestParseInsertWithMultipleColumnsAndValuesで検証している。AssignmentList（production#17/#18）も同型で、UPDATE ... SET name = 'bob', age = 20がGetColumns() == []string{"name", "age"}の順になる（TestParseUpdateWithMultipleAssignmentsAndWhere）。

---

4. tokenToTerminalName とテーブル検索の線形走査

tokenToTerminalNameはsql_lexer.Tokenのkind（int定数）を、lalrone_table_generatorが文法記号として使う文字列名にマッピングするだけの純粋な変換表:

sql_lexer kind	終端記号名
SELECT / FROM / WHERE / INSERT / INTO / VALUES / UPDATE / SET / DELETE / DROP / TABLE	同名の終端記号
COMMA / LPAREN / RPAREN / EQUAL	同名の終端記号
IDENTIFIER / NUMBER / STRING	同名の終端記号
SEMICOLON / EOF	同名の終端記号
AND / OR / GREATER / LESS / GREATER_EQUAL / LESS_EQUAL / NOT_EQUAL / PLUS / MINUS / STAR / SLASH	未対応 — default節でpanic。sql_lexerはこれらをトークン化できるが、この文法（WhereClause -> WHERE IDENTIFIER | εのみ）はそもそも比較演算子や算術式を受理しないため、到達した場合は必ずエラーになる

これ自体はO(1)のswitch文だが、直後に呼ばれるfindAction/findGotoは次のようにACTION表・GOTO表を毎回先頭から線形走査する:

func (l *LALR1MultiStatementParser) findAction(state int, terminal string) *action_entry.ActionEntry {
    for _, entry := range l.data.GetActionTable() {
        if entry.GetState() == state && entry.GetTerminal().GetName() == terminal {
            return entry
        }
    }
    return nil
}

ACTION表のエントリ数は文法の状態数×終端記号数のオーダーで、この文法ではLALR(1)状態数53に対して実際に登録されるエントリ数はそれよりだいぶ小さい（疎）が、findAction/findGotoはその疎な表をエントリ順（state, terminalでソートされているわけではない）に先頭から舐めるため、1回のSHIFT/REDUCEごとにO(表のエントリ数)がかかる。GOTO表も同様の線形走査（findGoto）。トークン数がn個の入力なら、Parse全体でこの線形走査がおよそ2n回（SHIFT/REDUCEの回数分）発生する。

実務のLRパーサ実装であればACTION[state][terminal]のような2次元配列（またはstateごとのmap[string]*Action）でO(1)に落とすのが定石で、これは本パッケージが意図的に単純さを優先している箇所——lalrone_table_generatorのドキュメントがテーブル構築側のfindLalrAction等について指摘しているのと同種の「正しさ優先・O(1)化はしていない」設計である。6節の考察でこの線形走査が実測コストにどう現れているかを見る。

---

5. テスト

lalrone_multi_statement_parser_test.go：

テスト	検証内容
TestParseSelectWithoutWhere	SELECT id FROM usersがStatement{kind=SELECT}に、SelectStatementの3フィールドが正しく入ること（WHERE句なし＝空文字列）
TestParseSelectWithWhere	SELECT id FROM users WHERE ageのWHERE句（単一のIDENTIFIERのみ。比較演算子は文法非対応）が正しく反映されること
TestParseInsertWithMultipleColumnsAndValues	INSERT INTO users (id, name) VALUES (1, 'bob')のColumnList/ValueListが書いた順そのままでリストに入ること
TestParseUpdateWithMultipleAssignmentsAndWhere	UPDATE ... SET name='bob', age=20 WHERE idのAssignmentListが列/値それぞれ書いた順で分離され、WHERE句も同時に反映されること
TestParseUpdateWithoutWhere	UPDATEでWHERE句を省略した場合、whereColumnが空文字列になること
TestParseDeleteWithWhere / TestParseDeleteWithoutWhere	DELETEのtable/whereColumnがWHERE句の有無で正しく変わること
TestParseDropTable	DROP TABLE usersがStatement{kind=DROP}になること
TestParseMultipleStatements	SELECT ...; DROP ...がSEMICOLON区切りで[]*Statementの2要素になり、順序と中身が両方保たれること
TestParseTrailingSemicolon	末尾に;だけ余分についた1文（生成規則24、StatementList -> StatementList SEMICOLON）が幽霊文を生まず1要素のままであること
TestParsePanicsOnInvalidSentence	SELECT FROM users（IDENTIFIER欠落）がfindActionのnil判定経由でpanic("error")すること——構造化されたエラー型を持たない、この実装の現状の挙動をそのまま検証する

go test . -v

---

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回の単純平均

テーブル構築（New→BuildFirstSets→BuildCanonicalStates→MergeToLalrStates→BuildLalrTables）は各ベンチマークにつきb.ResetTimer()前に1回だけ行い、計測対象はParse()（またはTokenize()+Parse()）呼び出しのみに絞っている。

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

ベンチマーク	ns/op	B/op	allocs/op	何を計測しているか
BenchmarkParseDrop	2448.0	1464	10	DROP TABLE users（トークン4個、生成規則2個をreduce）。全ベンチマーク中最軽量
BenchmarkParseDelete	3172.4	2153	13	DELETE FROM users WHERE id（WHERE句あり、トークン6個）
BenchmarkParseSelect	3303.2	2393	14	SELECT id FROM users WHERE age（トークン6個）
BenchmarkTokenizeAndParseSelect	3956.0	2649	25	上記SELECTをTokenize()から通しで実行
BenchmarkParseUpdate	6382.2	5211	30	UPDATE users SET name='bob', age=20 WHERE id（AssignmentList2件+WHERE、トークン13個）
BenchmarkParseInsert	6889.2	5419	31	INSERT INTO users (id, name) VALUES (1, 'bob')（ColumnList/ValueList各2件、トークン15個）
BenchmarkParseMultiStatement	13424.8	9757	57	SELECT; INSERT; DROP の3文をSEMICOLON区切りで一括parse
BenchmarkTokenizeAndParseMultiStatement	16163.2	10910	98	上記3文をTokenize()から通しで実行

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

BenchmarkParseSelect-12                       346026   3284 ns/op   2393 B/op   14 allocs/op
BenchmarkParseSelect-12                       361735   3288 ns/op   2393 B/op   14 allocs/op
BenchmarkParseSelect-12                       310875   3325 ns/op   2393 B/op   14 allocs/op
BenchmarkParseSelect-12                       443617   3294 ns/op   2393 B/op   14 allocs/op
BenchmarkParseSelect-12                       419058   3325 ns/op   2393 B/op   14 allocs/op

BenchmarkParseInsert-12                       183873   6858 ns/op   5419 B/op   31 allocs/op
BenchmarkParseInsert-12                       173384   7047 ns/op   5419 B/op   31 allocs/op
BenchmarkParseInsert-12                       184572   6646 ns/op   5419 B/op   31 allocs/op
BenchmarkParseInsert-12                       143871   6982 ns/op   5419 B/op   31 allocs/op
BenchmarkParseInsert-12                       187840   6913 ns/op   5419 B/op   31 allocs/op

BenchmarkParseUpdate-12                       193342   6367 ns/op   5211 B/op   30 allocs/op
BenchmarkParseUpdate-12                       195758   6346 ns/op   5211 B/op   30 allocs/op
BenchmarkParseUpdate-12                       180076   6614 ns/op   5211 B/op   30 allocs/op
BenchmarkParseUpdate-12                       206546   6396 ns/op   5211 B/op   30 allocs/op
BenchmarkParseUpdate-12                       204610   6188 ns/op   5211 B/op   30 allocs/op

BenchmarkParseDelete-12                       380694   3142 ns/op   2153 B/op   13 allocs/op
BenchmarkParseDelete-12                       396205   3066 ns/op   2153 B/op   13 allocs/op
BenchmarkParseDelete-12                       401044   3261 ns/op   2153 B/op   13 allocs/op
BenchmarkParseDelete-12                       391700   3050 ns/op   2153 B/op   13 allocs/op
BenchmarkParseDelete-12                       407487   3343 ns/op   2153 B/op   13 allocs/op

BenchmarkParseDrop-12                         495195   2560 ns/op   1464 B/op   10 allocs/op
BenchmarkParseDrop-12                         512875   2289 ns/op   1464 B/op   10 allocs/op
BenchmarkParseDrop-12                         576560   2546 ns/op   1464 B/op   10 allocs/op
BenchmarkParseDrop-12                         554518   2501 ns/op   1464 B/op   10 allocs/op
BenchmarkParseDrop-12                         480428   2344 ns/op   1464 B/op   10 allocs/op

BenchmarkParseMultiStatement-12                91416  13459 ns/op   9757 B/op   57 allocs/op
BenchmarkParseMultiStatement-12                95235  13558 ns/op   9758 B/op   57 allocs/op
BenchmarkParseMultiStatement-12                99039  12764 ns/op   9757 B/op   57 allocs/op
BenchmarkParseMultiStatement-12                84835  13570 ns/op   9757 B/op   57 allocs/op
BenchmarkParseMultiStatement-12                73360  13773 ns/op   9757 B/op   57 allocs/op

BenchmarkTokenizeAndParseSelect-12            318561   4134 ns/op   2649 B/op   25 allocs/op
BenchmarkTokenizeAndParseSelect-12            343153   3639 ns/op   2649 B/op   25 allocs/op
BenchmarkTokenizeAndParseSelect-12            306638   4037 ns/op   2649 B/op   25 allocs/op
BenchmarkTokenizeAndParseSelect-12            292869   4045 ns/op   2649 B/op   25 allocs/op
BenchmarkTokenizeAndParseSelect-12            327121   3925 ns/op   2649 B/op   25 allocs/op

BenchmarkTokenizeAndParseMultiStatement-12     70024  16052 ns/op  10910 B/op   98 allocs/op
BenchmarkTokenizeAndParseMultiStatement-12     84400  16208 ns/op  10910 B/op   98 allocs/op
BenchmarkTokenizeAndParseMultiStatement-12     82341  15761 ns/op  10910 B/op   98 allocs/op
BenchmarkTokenizeAndParseMultiStatement-12     82189  16214 ns/op  10910 B/op   98 allocs/op
BenchmarkTokenizeAndParseMultiStatement-12     81806  16581 ns/op  10910 B/op   98 allocs/op

考察

• コストはほぼ「トークン数×可変長リストの有無」で説明できる。最軽量のDROP（トークン4個、2448ns、10 allocs）を基準にすると、DELETE（6トークン、3172ns、13 allocs）とSELECT（6トークン、3303ns、14 allocs）はほぼ同水準で、WHERE句1つぶんの差（DROPにはWHERE句が存在しない）がおよそ700〜850ns・3〜4allocsに相当する。一方UPDATE（13トークン、6382ns、30 allocs）とINSERT（15トークン、6889ns、31 allocs）はDROPのほぼ2.5〜2.8倍で、AssignmentList/ColumnList+ValueListという左再帰リストが1件追加されるたびにStringList/AssignmentListの構造体確保が発生する（4節のappendはコピーではなく既存structを包み直す形だが、semantic_value.*でのラップ自体が毎回1 allocを要する）ことが直接効いている。
• findAction/findGotoの線形走査（4節）はSHIFT/REDUCEのたびに発生するため、トークン数に比例してコストが積み上がる。ParseMultiStatement（SELECT+INSERT+DROPの3文、13424.8ns）は単純に3文のParse個別コストの合計（3303.2+6889.2+2448.0 ≈ 12640.4ns）に近いが、実測はそれよりわずかに大きい（+784ns、約6%増）。差分の主因は、複数文をまとめるStatementList側の生成規則（22〜24）自体のreduceが単独parseでは発生しないコストとして追加されること、および線形走査対象のACTION/GOTO表がstateをまたいでも同じ配列を毎回先頭から舐める構造上、文が増えるほど「その文の中で通過する状態番号」がわずかに大きくなり得ることによる。
• Tokenize()+Parse()の合算（TokenizeAndParseSelect3956.0ns）とParse単体（ParseSelect3303.2ns）の差（≈653ns、11 allocs増）がTokenize自体のコスト。これはsql_lexerのベンチマークの短いSQL文向けの数値と同じオーダーで、Parse本体のコストと比べて無視できない割合（Selectでは全体の約17%）を占める——このパッケージ単体のプロファイリングでは見落としがちだが、実際にSQL文字列から結果を得るまでの体感コストはTokenize込みで評価すべきという裏付けになっている。
• ParseMultiStatementとWHERE句のないINSERT等を含むTokenizeAndParseMultiStatement（16163.2ns）の差分（≈2738ns）もほぼ丸ごとTokenizeコストで、TokenizeAndParseSelectとの差分（653ns）のおよそ4.2倍——3文ぶんのトークン化コストが単純に積み上がっている。
• 全体としてlalrone_table_generatorパッケージ側のテーブル構築コスト（そちらのドキュメント参照）に比べれば、このParse()単体のコストはいずれのケースでも遥かに小さい——テーブル構築はプロセス起動時に1回で済む「オフライン」コストなのに対し、Parse()は入力SQL文字列ごとに毎回発生する「オンライン」コストであり、この非対称性は他パッケージのドキュメントでも繰り返し指摘されている設計上の妥当性と一致する。

ベンチマーク実装上の注意

reduce()内の各caseがfmt.Println(" CREATE ... AST:", s)を実行するため（lalrone_multi_statement_parser.go側の既存コード、このドキュメント作成にあたって変更していない）、上記ベンチマークは実行するたびに大量の標準出力を伴う。このfmt.Println呼び出し自体（文字列フォーマット・書き込みシステムコール）も計測対象の一部として数値に含まれており、標準出力をリダイレクトしない場合はベンチマーク実行そのものがI/Oで律速される可能性がある。これは意図的に手を入れず、現状の実装をそのまま計測した結果である。

各ベンチマークはselect_statement等の他パッケージと同様、b.Loop()の外で1回だけnewTestParser（表構築）とトークン列の事前準備を行い、b.ResetTimer()でその準備コストを計測から除外している。戻り値はパッケージレベルのbenchStatementsSinkに代入し、Parse呼び出しがデッドコードとして最適化されるのを防いでいる。

---

関連ドキュメント

• lalrone_table_generator — このパッケージが使うACTION/GOTO表そのものを構築するパイプライン
• sql_lexer — Parseに渡すトークン列を生成するレキサ
• semantic_value — value_stack上でASTを運ぶためのタグ付き共用体
• value_stack / state_stack — Parseのループが使う2本のスタック
• statement — 5種類のASTをまとめるタグ付き共用体（このフォークと並行してstatement/docs/STATEMENT_ALGORITHM_AND_BENCHMARKS.mdが作成中）
• select_statement / insert_statement / update_statement / delete_statement / drop_statement — reduce()が最終的に構築する5種類のAST（select_statementのドキュメントが同型構造の代表例）

---

7. 再現手順

# テスト
go test . -v

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

LALR1SqlParser 3 go

LALR1SqlParser — アルゴリズム解説とベンチマーク結果

対象パッケージ: example.com/lalrone_sql_parser（ルートパッケージ）

これまでのドキュメント群（sql_lexer、lalrone_table_generator、state_stack、value_stack、semantic_value）はそれぞれ字句解析・表生成・スタック・意味値という部品単体を扱ってきた。LALR1SqlParser（lalrone_sql_parser.go）はそれらを組み合わせて実際に構文解析を駆動する本体——生成された ACTION/GOTO 表を読みながらトークン列をshift-reduceし、最終的にSELECT/INSERT/UPDATE/DELETE/DROPの5種の文をセミコロン区切りで並べた複数SQL文（[]*statement.Statement）を組み立てて返す。

本ドキュメントは以前のバージョン（SELECT専用・単一文のみ対応）を全面的に更新したもの。文法・reduce()・Parse()の戻り値がいずれも変わったため、ベンチマーク数値も総入れ替えしている。

---

1. 全体構成

flowchart LR
    G["lalrone_table_generator\nBuildFirstSets→BuildCanonicalStates\n→MergeToLalrStates→BuildLalrTables"] -->|"ParserData\n(ACTION表/GOTO表)"| N["NewLALR1SqlParser(generator)"]
    SQL["SQL文字列\n(SEMICOLON区切りで複数文可)"] --> L["sql_lexer.Tokenize()"] -->|"[]*Token"| P["Parse(tokens)"]
    N --> P
    P --> R["[]*statement.Statement\n(SELECT/INSERT/UPDATE/DELETE/DROPの並び)"]

NewLALR1SqlParserはすでにBuildLalrTables()まで完了したLALR1TableGeneratorを受け取り、generator.GetLalrData()をキャッシュするだけの薄いラッパー。テーブル生成という重い処理（FullPipelineの実測はlalrone_table_generatorのドキュメント参照）はアプリケーション起動時に1回だけ行い、Parseは生成済みの表を何度も再利用する設計になっている。

2. 文法：StatementListによる複数文対応

Statement（SELECT/INSERT/UPDATE/DELETE/DROPのいずれか1文）を、SEMICOLON区切りで1個以上並べたものがStatementList——増大された開始規則S' -> StatementListのトップレベル非終端記号になっている（lalrone_table_generator.goの生成規則22〜24）。

StatementList -> Statement                              // #22: 最初の1文
StatementList -> StatementList SEMICOLON Statement       // #23: ; で次の文を継続
StatementList -> StatementList SEMICOLON                 // #24: 末尾の ; だけを許容（次の文は無くてよい）

• StatementListにε規則は無い——先頭がいきなりSEMICOLONの入力（; SELECT ...）はStatementList -> .StatementのどのアイテムにもマッチせずfindActionが該当エントリなしを返すため、既存の構文エラー経路（panic）でそのまま弾かれる（TestParsePanicsOnLeadingSemicolon）。
• 末尾の;は#24が単独で吸収するため、"SELECT ...;"（1文+末尾;）と"SELECT ...; DROP ...;"（2文+末尾;）のどちらも同じ規則で受理できる。
• 以前の実装はParseの前処理removeSemicolonでSEMICOLONトークンを構文解析前に全て取り除いていた（文法自体にSEMICOLONが存在しなかった）。この方式は複数文の区切りごと消してしまうため1文しか解析できず、今回SEMICOLONを正式な終端記号として文法に組み込み、removeSemicolonごと削除した。

3. Parseのshift-reduce駆動ループ

flowchart TD
    S0["states=[0], values=[], position=0"] --> L{"ループ"}
    L --> Peek["state = states.Peek()\ntoken = tokens[position]\nterminal = tokenToTerminalName(token)"]
    Peek --> F["entry = findAction(state, terminal)"]
    F -->|"nil"| E1["panic（構文エラー）"]
    F --> K{"entry.GetAction().GetKind()"}
    K -- SHIFT --> SH["states.Push(次状態)\nvalues.Push(Token(token.text))\nposition++"] --> L
    K -- REDUCE --> RE["states.PopCount(右辺長)\nvalue = reduce(生成規則index, values)\ngotoState = findGoto(states.Peek(), 左辺名)\nstates.Push(gotoState)\nvalues.Push(value)"] --> L
    K -- ACCEPT --> AC["values.Peek()がSTATEMENT_LISTであることを確認\nGetStatements()（[]*statement.Statement）を返して終了"]

• 状態はStateStack、意味値はValueStackという2本のスタックが1:1で並走する——標準的なLR系パーサの実装形。SHIFTは両方に1件ずつpush、REDUCEは生成規則の右辺長ぶんを両方から取り除いてから新しい状態・値を1件ずつpushし直す（このpop/pushの非対称なコストについてはstate_stackのドキュメントのPopCountの考察を参照）。
• ParseはもうremoveSemicolonで前処理しない——受け取ったトークン列をそのまま使う。SEMICOLONはACTION表上の通常の終端記号として扱われる。
• REDUCEのreduce()は生成規則インデックスで分岐する意味アクション（lalrone_table_generatorが使う文法の生成規則1〜24に対応。規則0＝S' -> StatementListはACCEPT側で消費されるためreduce()には現れない）。文法自体はlalrone_table_generator.goにハードコードされているため、Parse側のreduceもそれと同じ生成規則番号にハードコードで対応している——文法が変わったらこの2箇所を手で同期させる必要がある密結合な設計。
• ACCEPTの判定対象もSTATEMENTからSTATEMENT_LISTに変わった——最終的にスタックに残る意味値は常にStatementList（[]*statement.Statement）であり、1文だけの入力でもStatementList -> Statement（規則22）を経由して1要素のスライスに包まれる。

reduce()の生成規則対応表

#	生成規則	意味アクションの要点
1〜5	Statement -> SelectStatement | InsertStatement | UpdateStatement | DeleteStatement | DropStatement	各具象文をstatement.From*()でStatement（判別共用体）に包む
6	SelectStatement -> SELECT IDENTIFIER FROM IDENTIFIER WhereClause	5値pop（逆順でwhere,table,FROM,column,SELECT）→NewSelectStatement
7,8	WhereClause -> WHERE IDENTIFIER | ε	WhereClause(column)／WhereClause("")
9	InsertStatement -> INSERT INTO IDENTIFIER LPAREN ColumnList RPAREN VALUES LPAREN ValueList RPAREN	10値pop→NewInsertStatement
10,11	ColumnList -> IDENTIFIER | ColumnList COMMA IDENTIFIER	StringListの構築／append
12,13	ValueList -> Value | ValueList COMMA Value	同上
14,15	Value -> NUMBER | STRING	トークンのテキストをそのままToken()化
16	UpdateStatement -> UPDATE IDENTIFIER SET AssignmentList WhereClause	5値pop→NewUpdateStatement
17,18	AssignmentList -> Assignment | AssignmentList COMMA Assignment	列名・値の2本のスライスを並行してappend
19	Assignment -> IDENTIFIER EQUAL Value	Assignment(column, value)
20	DeleteStatement -> DELETE FROM IDENTIFIER WhereClause	4値pop→NewDeleteStatement
21	DropStatement -> DROP TABLE IDENTIFIER	3値pop→NewDropStatement
22	StatementList -> Statement	1値pop→[]*statement.Statement{stmt}で1要素スライスを生成
23	StatementList -> StatementList SEMICOLON Statement	3値pop（Statement, SEMICOLON, StatementList）→既存スライスにappend
24	StatementList -> StatementList SEMICOLON	2値pop（SEMICOLON, StatementList）→スライスはそのまま素通し（末尾;は値を持たない）

太字の3規則（22〜24）が今回のドキュメント更新で追加された部分。1〜21は文法・意味アクションともに変更していない。

4. findAction/findGoto：ACTION/GOTO表の線形探索

lalrone_table_generator.ParserDataが保持するActionTable/GotoTableは単純なスライスで、findAction/findGotoは毎回先頭から線形走査する（lalrone_table_generatorの内部実装も同じ探索方式）。今回の文法は状態数55（canonical）／53（LALR）・ACTION/GOTOあわせて数百エントリ程度で実用上ほぼ無視できるコストだが（後述のベンチマークで実測）、状態数・終端記号数がさらに大きい文法では(state, terminal)をキーにしたmapなど定数時間探索への置き換えが有効になる規模になりうる。

---

5. テスト

lalrone_sql_parser_test.go：

テスト	検証内容
TestParseSelectWithoutWhereClause	SELECT id FROM usersがε還元経由で正しくSelectStatement{column:"id", table:"users", whereColumn:""}になること
TestParseSelectWithWhereClause	SELECT id FROM users WHERE ageがwhereColumn:"age"を含めて正しく組み立てられること
TestParseIgnoresTrailingSemicolon	末尾に;がある単一文の入力がStatementList -> StatementList SEMICOLON経由で1件だけの結果になること
TestParseMultipleStatements	SELECT ...; INSERT ...; DROP ...の3文が順序通り[]*statement.Statementとして返ること
TestParseMultipleStatementsWithTrailingSemicolon	DELETE ...; DROP ...;（末尾;つき2文）が正しく2件になること
TestParseAllFiveStatementKindsChained	SELECT/INSERT/UPDATE/DELETE/DROPの5種を;で連結した入力が、順序通り5件のStatement（各GetKind()が対応する定数）になること
TestParsePanicsOnLeadingSemicolon	StatementListにε規則が無いため、先頭が;の入力（"; SELECT ..."）は構文エラーとしてpanicすること
TestParseInsertStatement	INSERT INTO users (id, name) VALUES (1, 'bob')が列・値の対応を保ったまま組み立てられること
TestParseUpdateStatement	UPDATE ... SET a = 'x', b = 30 WHERE idが複数代入・WHERE句を含めて組み立てられること
TestParseDeleteStatement	DELETE FROM users WHERE idが正しく組み立てられること
TestParseDeleteStatementWithoutWhereClause	DELETE FROM users（WHERE無し）がε還元経由でwhereColumn:""になること
TestParseDropStatement	DROP TABLE usersが正しく組み立てられること
TestParsePanicsOnMissingIdentifier	SELECT FROM users（IDENTIFIER抜け）でfindActionがエントリなしを返しpanicすること
TestParsePanicsOnTokenOutsideGrammar	SELECT 1 FROM usersのNUMBERトークンで、その位置にACTIONエントリが無くpanicすること
TestTokenToTerminalName	全終端記号（SEMICOLON含む）が正しい終端記号名にマップされること
TestTokenToTerminalNamePanicsOnUnknownKind	ANDのような未対応のToken種別でpanicすること
TestFindActionAndFindGoto	存在するエントリを正しく返し、存在しないエントリにはnil/-1を返すこと

go test . -v

---

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回の単純平均

ベンチマーク一覧

ベンチマーク	内容
BenchmarkNewLALR1SqlParser	構築済みLALR1TableGeneratorからLALR1SqlParserを作るだけのコスト（GetLalrData()呼び出し含む）
BenchmarkParseWithoutWhereClause	SELECT id FROM usersを事前トークン化した状態でParse()のみを計測（ε還元経路、1文）
BenchmarkParseWithWhereClause	SELECT id FROM users WHERE ageを事前トークン化した状態でParse()のみを計測（WHERE経路、1文）
BenchmarkParseTwoStatements	SELECT ...; DROP TABLE ...（2文）を事前トークン化した状態でParse()のみを計測
BenchmarkParseThreeStatements	SELECT ...; DELETE ... WHERE ...; DROP ...（3文）を事前トークン化した状態でParse()のみを計測
BenchmarkTokenizeAndParseWithoutWhereClause	トークン化＋Parse()を通しで計測（表は事前構築済みを使い回す、実運用に近い1クエリあたりのコスト、1文）
BenchmarkTokenizeAndParseWithWhereClause	同上、WHERE句あり・1文
BenchmarkTokenizeAndParseTwoStatements	同上、2文（SELECT ...; DROP TABLE ...）をトークン化から通しで計測
BenchmarkFindAction	findAction(0, "SELECT")（ACTION表の線形探索）単体
BenchmarkFindGoto	findGoto(0, "SelectStatement")（GOTO表の線形探索）単体

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

ベンチマーク	ns/op	B/op	allocs/op	何を計測しているか
BenchmarkNewLALR1SqlParser	16.80	16	1	LALR1SqlParser構造体（フィールド2個＝ポインタ2個＝16B）1個ぶんの確保のみ
BenchmarkParseWithoutWhereClause	1173.0	1896	11	事前トークン化済み・ε還元経路のParse()単体（1文）
BenchmarkParseWithWhereClause	1555.2	2344	13	事前トークン化済み・WHERE経路のParse()単体（1文、Withoutよりトークン2個・reduce1回ぶん重い）
BenchmarkParseTwoStatements	2310.0	3544	21	2文目（DROP TABLE users）をSEMICOLON区切りで追加したParse()単体
BenchmarkParseThreeStatements	4103.4	5896	34	3文目（DELETE FROM users WHERE id）をさらに追加したParse()単体
BenchmarkTokenizeAndParseWithoutWhereClause	1614.4	2096	19	トークン化＋Parse()の合計（実運用の1クエリぶん、1文）
BenchmarkTokenizeAndParseWithWhereClause	2199.0	2600	24	同上、WHERE句あり・1文
BenchmarkTokenizeAndParseTwoStatements	3148.0	3976	35	同上、2文をトークン化から通しで計測
BenchmarkFindAction	2.281	0	0	ACTION表の線形探索、状態0×"SELECT"のヒット
BenchmarkFindGoto	4.739	0	0	GOTO表の線形探索、状態0×"SelectStatement"のヒット

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

BenchmarkNewLALR1SqlParser-12                     63578785        16.36 ns/op       16 B/op      1 allocs/op
BenchmarkNewLALR1SqlParser-12                     68189492        17.16 ns/op       16 B/op      1 allocs/op
BenchmarkNewLALR1SqlParser-12                     68895195        16.93 ns/op       16 B/op      1 allocs/op
BenchmarkNewLALR1SqlParser-12                     77625723        16.76 ns/op       16 B/op      1 allocs/op
BenchmarkNewLALR1SqlParser-12                     74592064        16.78 ns/op       16 B/op      1 allocs/op

BenchmarkParseWithoutWhereClause-12                  881892      1181   ns/op     1896 B/op     11 allocs/op
BenchmarkParseWithoutWhereClause-12                 1000000      1162   ns/op     1896 B/op     11 allocs/op
BenchmarkParseWithoutWhereClause-12                 1000000      1171   ns/op     1896 B/op     11 allocs/op
BenchmarkParseWithoutWhereClause-12                  870418      1176   ns/op     1896 B/op     11 allocs/op
BenchmarkParseWithoutWhereClause-12                 1000000      1175   ns/op     1896 B/op     11 allocs/op

BenchmarkParseWithWhereClause-12                     852619      1564   ns/op     2344 B/op     13 allocs/op
BenchmarkParseWithWhereClause-12                     825096      1521   ns/op     2344 B/op     13 allocs/op
BenchmarkParseWithWhereClause-12                     812886      1589   ns/op     2344 B/op     13 allocs/op
BenchmarkParseWithWhereClause-12                     739404      1540   ns/op     2344 B/op     13 allocs/op
BenchmarkParseWithWhereClause-12                     710608      1562   ns/op     2344 B/op     13 allocs/op

BenchmarkParseTwoStatements-12                       548624      2329   ns/op     3544 B/op     21 allocs/op
BenchmarkParseTwoStatements-12                       517113      2222   ns/op     3544 B/op     21 allocs/op
BenchmarkParseTwoStatements-12                       552126      2354   ns/op     3544 B/op     21 allocs/op
BenchmarkParseTwoStatements-12                       504646      2327   ns/op     3544 B/op     21 allocs/op
BenchmarkParseTwoStatements-12                       501000      2318   ns/op     3544 B/op     21 allocs/op

BenchmarkParseThreeStatements-12                     274137      4080   ns/op     5896 B/op     34 allocs/op
BenchmarkParseThreeStatements-12                     299824      4032   ns/op     5896 B/op     34 allocs/op
BenchmarkParseThreeStatements-12                     289928      4128   ns/op     5896 B/op     34 allocs/op
BenchmarkParseThreeStatements-12                     306774      4205   ns/op     5896 B/op     34 allocs/op
BenchmarkParseThreeStatements-12                     257152      4072   ns/op     5896 B/op     34 allocs/op

BenchmarkTokenizeAndParseWithoutWhereClause-12       733838      1551   ns/op     2096 B/op     19 allocs/op
BenchmarkTokenizeAndParseWithoutWhereClause-12       740020      1614   ns/op     2096 B/op     19 allocs/op
BenchmarkTokenizeAndParseWithoutWhereClause-12       763269      1655   ns/op     2096 B/op     19 allocs/op
BenchmarkTokenizeAndParseWithoutWhereClause-12       710250      1621   ns/op     2096 B/op     19 allocs/op
BenchmarkTokenizeAndParseWithoutWhereClause-12       697968      1631   ns/op     2096 B/op     19 allocs/op

BenchmarkTokenizeAndParseWithWhereClause-12          573080      2216   ns/op     2600 B/op     24 allocs/op
BenchmarkTokenizeAndParseWithWhereClause-12          607150      2210   ns/op     2600 B/op     24 allocs/op
BenchmarkTokenizeAndParseWithWhereClause-12          565208      2184   ns/op     2600 B/op     24 allocs/op
BenchmarkTokenizeAndParseWithWhereClause-12          592300      2225   ns/op     2600 B/op     24 allocs/op
BenchmarkTokenizeAndParseWithWhereClause-12          567556      2160   ns/op     2600 B/op     24 allocs/op

BenchmarkTokenizeAndParseTwoStatements-12            351808      3168   ns/op     3976 B/op     35 allocs/op
BenchmarkTokenizeAndParseTwoStatements-12            339648      3154   ns/op     3976 B/op     35 allocs/op
BenchmarkTokenizeAndParseTwoStatements-12            368845      3158   ns/op     3976 B/op     35 allocs/op
BenchmarkTokenizeAndParseTwoStatements-12            390325      3125   ns/op     3976 B/op     35 allocs/op
BenchmarkTokenizeAndParseTwoStatements-12            366870      3135   ns/op     3976 B/op     35 allocs/op

BenchmarkFindAction-12                            529770681         2.265 ns/op       0 B/op      0 allocs/op
BenchmarkFindAction-12                            526229962         2.281 ns/op       0 B/op      0 allocs/op
BenchmarkFindAction-12                            530789895         2.260 ns/op       0 B/op      0 allocs/op
BenchmarkFindAction-12                            527249193         2.266 ns/op       0 B/op      0 allocs/op
BenchmarkFindAction-12                            515676440         2.335 ns/op       0 B/op      0 allocs/op

BenchmarkFindGoto-12                              252471416         4.739 ns/op       0 B/op      0 allocs/op
BenchmarkFindGoto-12                              255125877         4.712 ns/op       0 B/op      0 allocs/op
BenchmarkFindGoto-12                              254610610         4.721 ns/op       0 B/op      0 allocs/op
BenchmarkFindGoto-12                              255403158         4.725 ns/op       0 B/op      0 allocs/op
BenchmarkFindGoto-12                              254541000         4.797 ns/op       0 B/op      0 allocs/op

考察

• NewLALR1SqlParser（16.8ns、16B、1alloc）は変わらずほぼ最小コスト。LALR1SqlParser{generator, data}はポインタ2個＝16Bのみで、文法の大きさに一切依存しない。表そのものの生成コストはこのベンチマークの外（buildParser()のセットアップ側）にある。
• ParseWithoutWhereClauseは1文でも1173ns・11allocsかかる。これは以前のドキュメント（SELECT専用9状態の文法を計測していた版）から大きく増えているが、要因は今回の変更単体ではなく、①この文法がすでにSELECT/INSERT/UPDATE/DELETE/DROPの5種を扱うようになっていた（findAction/findGotoが毎回スキャンするACTION/GOTO表がその分肥大化）ことと、②今回StatementList -> Statement（規則22）の還元が1文の入力にも必ず1回追加されたこと（values.Pop()→1要素スライス生成で+1alloc）の複合。findAction/findGoto自体は表全体を毎回線形走査する実装（本ドキュメント4節）なので、文法が大きくなるほど1回あたりの探索コストも比例して重くなる。
• 文を1つ追加するごとの限界コストはおよそ+1.1〜1.8μs、+10〜13allocs：1文(1173ns/11allocs)→2文(2310ns/21allocs、DROP TABLE追加で+1137ns/+10allocs)→3文(4103ns/34allocs、DELETE ... WHERE ...追加で+1793ns/+13allocs)。差分の大きさは追加した文の種類（トークン数・WhereClauseの有無）に依存し、DELETE文はWHERE句ぶんSHIFT/REDUCEが多いため増分も大きい。いずれの追加分にも共通して、SEMICOLONのSHIFT1回＋StatementList -> StatementList SEMICOLON Statement（規則23）の還元1回（appendで1alloc）が含まれる。
• ParseWithWhereClause（1555ns、13allocs）はWithoutより+382ns・+2allocs。WHERE句を含む経路ではSHIFTが2回増え（WHERE, IDENTIFIER）、その分Token()の確保も2回増える一方、ε還元（1回の確保）の代わりにWhereClause -> WHERE IDENTIFIERの非ε還元（同じく1回の確保）が起きるため還元側の回数は変わらない——allocs差分（+2）はSHIFT2回ぶんのToken()確保のみで説明できる。
• TokenizeAndParse*はsql_lexer.Tokenize()とParse()の合計にほぼ一致する：例えばTokenizeAndParseTwoStatements（3148ns、35allocs）はTokenize()単体のコスト（sql_lexerのベンチマーク参照）とParseTwoStatements（2310ns、21allocs）を合わせた程度になっている。実運用でクエリ文字列を受け取ってから構文木を得るまでの総コストとしてはこちらが実態に近い数字になる。
• FindAction（2.28ns）とFindGoto（4.74ns）は今回の文法規模（LALR状態数53）でも依然として無視できるコストだが、FindGotoは以前の計測（3.11ns、LALR状態数50）よりわずかに重くなっている——GOTO表のエントリ数がStatementListの3規則ぶん増えた影響。状態数・終端記号数が数百〜数千規模になる実用的な文法では、この線形探索がParse()全体（1トークンあたり1回のACTION探索＋reduceのたびに1回のGOTO探索）の支配的コストになりうる——(state, terminal)をキーとしたmapや、状態ごとに二次元配列化した表への置き換えが有効な最適化ポイントになる。

---

7. 再現手順

# テスト
go test . -v

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

LALR1SqlParser 2 go

LALR1SqlParser — アルゴリズム解説とベンチマーク結果

対象パッケージ: example.com/lalrone_sql_parser（ルートパッケージ）

これまでのドキュメント群（sql_lexer、lalrone_table_generator、state_stack、value_stack、semantic_value）はそれぞれ字句解析・表生成・スタック・意味値という部品単体を扱ってきた。LALR1SqlParser（lalrone_sql_parser.go）はそれらを組み合わせて実際に構文解析を駆動する本体——生成された ACTION/GOTO 表を読みながらトークン列をshift-reduceし、最終的にselect_statement.SelectStatementを組み立てて返す。

---

1. 全体構成

flowchart LR
    G["lalrone_table_generator\nBuildFirstSets→BuildCanonicalStates\n→MergeToLalrStates→BuildLalrTables"] -->|"ParserData\n(ACTION表/GOTO表)"| N["NewLALR1SqlParser(generator)"]
    SQL["SQL文字列"] --> L["sql_lexer.Tokenize()"] -->|"[]*Token"| P["Parse(tokens)"]
    N --> P
    P --> R["select_statement.SelectStatement"]

NewLALR1SqlParserはすでにBuildLalrTables()まで完了したLALR1TableGeneratorを受け取り、generator.GetLalrData()をキャッシュするだけの薄いラッパー。テーブル生成という重い処理（FullPipelineで約7μs）はアプリケーション起動時に1回だけ行い、Parseは生成済みの表を何度も再利用する設計になっている。

2. Parseのshift-reduce駆動ループ

flowchart TD
    S0["removeSemicolon(originalTokens)\nstates=[0], values=[], position=0"] --> L{"ループ"}
    L --> Peek["state = states.Peek()\ntoken = tokens[position]\nterminal = tokenToTerminalName(token)"]
    Peek --> F["entry = findAction(state, terminal)"]
    F -->|"nil"| E1["panic（構文エラー）"]
    F --> K{"entry.GetAction().GetKind()"}
    K -- SHIFT --> SH["states.Push(次状態)\nvalues.Push(Token(token.text))\nposition++"] --> L
    K -- REDUCE --> RE["states.PopCount(右辺長)\nvalue = reduce(生成規則index, values)\ngotoState = findGoto(states.Peek(), 左辺名)\nstates.Push(gotoState)\nvalues.Push(value)"] --> L
    K -- ACCEPT --> AC["values.Peek()がSELECT_STATEMENTであることを確認\nSelectStatementを返して終了"]

• 状態はStateStack、意味値はValueStackという2本のスタックが1:1で並走する——標準的なLR系パーサの実装形。SHIFTは両方に1件ずつpush、REDUCEは生成規則の右辺長ぶんを両方から取り除いてから新しい状態・値を1件ずつpushし直す（このpop/pushの非対称なコストについてはstate_stackのドキュメントのPopCountの考察を参照）。
• REDUCEのreduce()は生成規則インデックスで分岐する意味アクション（lalrone_table_generatorが使う文法の生成規則0〜3に対応）。文法自体はlalrone_table_generator.goにハードコードされているため、Parse側のreduceもそれと同じ生成規則番号にハードコードで対応している——文法が変わったらこの2箇所を手で同期させる必要がある密結合な設計。

flowchart LR
    subgraph "reduce(productionIndex, values)"
    direction TB
    P1["#1: SelectStatement -> SELECT IDENTIFIER FROM IDENTIFIER WhereClause\n5値pop（逆順でwhere,table,FROM,column,SELECT）\n→ NewSelectStatement→SelectStatement()"]
    P2["#2: WhereClause -> WHERE IDENTIFIER\n2値pop（column,WHERE）\n→ WhereClause(column)"]
    P3["#3: WhereClause -> ε\n0値pop\n→ WhereClause(\"\")"]
    end

3. findAction/findGoto：ACTION/GOTO表の線形探索

lalrone_table_generator.ParserDataが保持するActionTable/GotoTableは単純なスライスで、findAction/findGotoは毎回先頭から線形走査する（lalrone_table_generatorの内部実装も同じ探索方式）。今回のSELECT文法は状態数9・エントリ数十数個程度なので実用上ほぼ無視できるコストだが（後述のベンチマークで実測）、状態数・終端記号数が大きい文法では(state, terminal)をキーにしたmapなど定数時間探索への置き換えが有効になる規模になりうる。

4. removeSemicolon：前処理

Tokenize()が生成するトークン列に含まれうるSEMICOLONをパース前に取り除く。文法自体にSEMICOLONが存在しない（SelectStatementの生成規則にセミコロンの項がない）ため、これを取り除かないとtokenToTerminalNameが未対応のトークン種別としてpanicする。空スライスからappendで構築するだけの単純な前処理だが、複数文（SELECT ...; SELECT ...;）を1つのトークン列として扱おうとすると文の区切りごと消えてしまう点には注意——この文法・実装は1文だけを解析する前提になっている。

---

5. テスト

lalrone_sql_parser_test.go：

テスト	検証内容
TestParseSelectWithoutWhereClause	SELECT id FROM usersがε還元経由で正しくSelectStatement{column:"id", table:"users", whereColumn:""}になること
TestParseSelectWithWhereClause	SELECT id FROM users WHERE ageがwhereColumn:"age"を含めて正しく組み立てられること
TestParseIgnoresTrailingSemicolon	末尾に;がある入力でもremoveSemicolonにより正しく解析できること
TestParsePanicsOnMissingIdentifier	SELECT FROM users（IDENTIFIER抜け）でfindActionがエントリなしを返しpanicすること
TestParsePanicsOnTokenOutsideGrammar	SELECT 1 FROM usersのNUMBERトークンでtokenToTerminalNameがpanicすること
TestTokenToTerminalName	SELECT/FROM/WHERE/IDENTIFIER/EOFの5種が正しい終端記号名にマップされること
TestTokenToTerminalNamePanicsOnUnknownKind	NUMBERのような未対応のToken種別でpanicすること
TestRemoveSemicolon	セミコロンが1つ除去され、末尾のEOFは保持されたまま返ること
TestFindActionAndFindGoto	存在するエントリを正しく返し、存在しないエントリにはnil/-1を返すこと

go test . -v

---

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回の単純平均

ベンチマーク一覧

ベンチマーク	内容
BenchmarkNewLALR1SqlParser	構築済みLALR1TableGeneratorからLALR1SqlParserを作るだけのコスト（GetLalrData()呼び出し含む）
BenchmarkParseWithoutWhereClause	SELECT id FROM usersを事前トークン化した状態でParse()のみを計測（ε還元経路）
BenchmarkParseWithWhereClause	SELECT id FROM users WHERE ageを事前トークン化した状態でParse()のみを計測（WHERE経路）
BenchmarkTokenizeAndParseWithoutWhereClause	トークン化＋Parse()を通しで計測（表は事前構築済みを使い回す、実運用に近い1クエリあたりのコスト）
BenchmarkTokenizeAndParseWithWhereClause	同上、WHERE句あり
BenchmarkFindAction	findAction(0, "SELECT")（ACTION表の線形探索）単体
BenchmarkFindGoto	findGoto(0, "SelectStatement")（GOTO表の線形探索）単体

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

ベンチマーク	ns/op	B/op	allocs/op	何を計測しているか
BenchmarkNewLALR1SqlParser	16.5	16	1	LALR1SqlParser構造体（フィールド2個＝ポインタ2個＝16B）1個ぶんの確保のみ
BenchmarkParseWithoutWhereClause	383.4	400	8	事前トークン化済み・ε還元経路のParse()単体
BenchmarkParseWithWhereClause	481.8	496	10	事前トークン化済み・WHERE経路のParse()単体（トークン2個・reduce内容が増える分Withoutより重い）
BenchmarkTokenizeAndParseWithoutWhereClause	762.1	600	16	トークン化＋Parse()の合計（実運用の1クエリぶん）
BenchmarkTokenizeAndParseWithWhereClause	998.6	752	21	同上、WHERE句あり
BenchmarkFindAction	2.27	0	0	ACTION表（数エントリ）の線形探索、状態0×"SELECT"のヒット
BenchmarkFindGoto	3.11	0	0	GOTO表の線形探索、状態0×"SelectStatement"のヒット

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

BenchmarkNewLALR1SqlParser-12                   62034158    16.51 ns/op     16 B/op    1 allocs/op
BenchmarkNewLALR1SqlParser-12                   67184077    16.62 ns/op     16 B/op    1 allocs/op
BenchmarkNewLALR1SqlParser-12                   70593787    16.48 ns/op     16 B/op    1 allocs/op
BenchmarkNewLALR1SqlParser-12                   69340016    16.34 ns/op     16 B/op    1 allocs/op
BenchmarkNewLALR1SqlParser-12                   67123688    16.54 ns/op     16 B/op    1 allocs/op

BenchmarkParseWithoutWhereClause-12               3216024   379.0 ns/op    400 B/op    8 allocs/op
BenchmarkParseWithoutWhereClause-12               3095702   385.5 ns/op    400 B/op    8 allocs/op
BenchmarkParseWithoutWhereClause-12               3155306   385.4 ns/op    400 B/op    8 allocs/op
BenchmarkParseWithoutWhereClause-12               3117808   383.4 ns/op    400 B/op    8 allocs/op
BenchmarkParseWithoutWhereClause-12               3148032   383.9 ns/op    400 B/op    8 allocs/op

BenchmarkParseWithWhereClause-12                  2472174   482.3 ns/op    496 B/op   10 allocs/op
BenchmarkParseWithWhereClause-12                  2497508   478.9 ns/op    496 B/op   10 allocs/op
BenchmarkParseWithWhereClause-12                  2513029   482.0 ns/op    496 B/op   10 allocs/op
BenchmarkParseWithWhereClause-12                  2465248   486.1 ns/op    496 B/op   10 allocs/op
BenchmarkParseWithWhereClause-12                  2479166   479.8 ns/op    496 B/op   10 allocs/op

BenchmarkTokenizeAndParseWithoutWhereClause-12    1585039   763.2 ns/op    600 B/op   16 allocs/op
BenchmarkTokenizeAndParseWithoutWhereClause-12    1588574   756.1 ns/op    600 B/op   16 allocs/op
BenchmarkTokenizeAndParseWithoutWhereClause-12    1568354   763.2 ns/op    600 B/op   16 allocs/op
BenchmarkTokenizeAndParseWithoutWhereClause-12    1578576   757.9 ns/op    600 B/op   16 allocs/op
BenchmarkTokenizeAndParseWithoutWhereClause-12    1553764   770.0 ns/op    600 B/op   16 allocs/op

BenchmarkTokenizeAndParseWithWhereClause-12       1000000   1011   ns/op   752 B/op   21 allocs/op
BenchmarkTokenizeAndParseWithWhereClause-12       1206126    995.7 ns/op   752 B/op   21 allocs/op
BenchmarkTokenizeAndParseWithWhereClause-12       1208571    991.7 ns/op   752 B/op   21 allocs/op
BenchmarkTokenizeAndParseWithWhereClause-12       1211421    989.8 ns/op   752 B/op   21 allocs/op
BenchmarkTokenizeAndParseWithWhereClause-12       1000000   1005   ns/op   752 B/op   21 allocs/op

BenchmarkFindAction-12                          531129937     2.264 ns/op    0 B/op    0 allocs/op
BenchmarkFindAction-12                          527236568     2.266 ns/op    0 B/op    0 allocs/op
BenchmarkFindAction-12                          518388350     2.284 ns/op    0 B/op    0 allocs/op
BenchmarkFindAction-12                          530320267     2.259 ns/op    0 B/op    0 allocs/op
BenchmarkFindAction-12                          526721725     2.266 ns/op    0 B/op    0 allocs/op

BenchmarkFindGoto-12                            385689368     3.122 ns/op    0 B/op    0 allocs/op
BenchmarkFindGoto-12                            385099357     3.112 ns/op    0 B/op    0 allocs/op
BenchmarkFindGoto-12                            385891538     3.115 ns/op    0 B/op    0 allocs/op
BenchmarkFindGoto-12                            387427468     3.103 ns/op    0 B/op    0 allocs/op
BenchmarkFindGoto-12                            383588157     3.113 ns/op    0 B/op    0 allocs/op

考察

• NewLALR1SqlParser（16.5ns、16B、1alloc）はほぼ最小コスト。LALR1SqlParser{generator, data}はポインタ2個＝16Bのみで、GetLalrData()は既存フィールドを返すだけ。表そのものの生成コスト（FullPipelineで約7μs）はこのベンチマークの外（buildParser()のセットアップ側）にあり、ここで測っているのは純粋に「既存の表をラップするだけ」のコスト。
• ParseWithoutWhereClause（8 allocs, 400B）の確保は大きく4種類に分けられる（コード上の発生源からの整理。Goのインライン化・スライス再確保の粒度に依存するため厳密な内訳は変動しうる）: (1) removeSemicolonが空スライスからappendで新しいトークン列を組み立てる際の確保、(2) SHIFTのたびにsemantic_value.Token()（各48B、semantic_valueのベンチマーク参照）を4回（SELECT, IDENTIFIER, FROM, IDENTIFIER）、(3) ε還元でWhereClause("")を1回、(4) 最終reduceでselect_statement.NewSelectStatement()とsemantic_value.SelectStatement()ラップの2回。合計7回の意味値生成＋前処理1回で8allocsという実測とおおむね符合する。
• ParseWithWhereClause（10 allocs, 496B）はWithoutより+2 allocs・+96B。WHERE句を含む経路ではSHIFTが2回増え（WHERE, IDENTIFIER）、その分Token()の確保も2回増える一方、ε還元（1回の確保）の代わりにWhereClause -> WHERE IDENTIFIERの非ε還元（同じく1回の確保）が起きるため還元側の回数は変わらない。結果として純増分はSHIFT2回ぶんのToken()確保のみ（+2 allocs, +2×48B=96B）——実測の差分とちょうど一致する。
• TokenizeAndParse*はsql_lexer.Tokenize()（短文で約650ns・15allocs）とParse()の合計にほぼ一致する: Without側は762ns（≈650+383−オーバーラップ分の測定誤差）・16allocs（≈15＋1、Parse内のTokenize結果由来の追加確保は最小限）。実運用でクエリ文字列を受け取ってから構文木を得るまでの総コストとしてはこちらが実態に近い数字になる。
• FindAction（2.27ns）とFindGoto（3.11ns）はこの文法規模（状態数9、ACTION/GOTOあわせて十数エントリ）では無視できるコスト。FindGotoがFindActionよりわずかに重いのは、GOTO表のエントリ判定がGetNonTerminal().GetName()という文字列比較を要する一方、実装上のテーブル走査ロジック自体はほぼ同型であるため。状態数・終端記号数が数百〜数千規模になる実用的な文法では、この線形探索がParse()全体（1トークンあたり1回のACTION探索＋reduceのたびに1回のGOTO探索）の支配的コストになりうる——(state, terminal)をキーとしたmapや、状態ごとに二次元配列化した表への置き換えが有効な最適化ポイントになる。

---

7. 再現手順

# テスト
go test . -v

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

LALR1SqlParser go

LALR1SqlParser — アルゴリズム解説とベンチマーク結果

対象パッケージ: example.com/lalrone_sql_parser（ルートパッケージ）

これまでのドキュメント群（sql_lexer、lalrone_table_generator、state_stack、value_stack、semantic_value）はそれぞれ字句解析・表生成・スタック・意味値という部品単体を扱ってきた。LALR1SqlParser（lalrone_sql_parser.go）はそれらを組み合わせて実際に構文解析を駆動する本体——生成された ACTION/GOTO 表を読みながらトークン列をshift-reduceし、最終的にselect_statement.SelectStatementを組み立てて返す。

---

1. 全体構成

flowchart LR
    G["lalrone_table_generator\nBuildFirstSets→BuildCanonicalStates\n→MergeToLalrStates→BuildLalrTables"] -->|"ParserData\n(ACTION表/GOTO表)"| N["NewLALR1SqlParser(generator)"]
    SQL["SQL文字列"] --> L["sql_lexer.Tokenize()"] -->|"[]*Token"| P["Parse(tokens)"]
    N --> P
    P --> R["select_statement.SelectStatement"]

NewLALR1SqlParserはすでにBuildLalrTables()まで完了したLALR1TableGeneratorを受け取り、generator.GetLalrData()をキャッシュするだけの薄いラッパー。テーブル生成という重い処理（FullPipelineで約7μs）はアプリケーション起動時に1回だけ行い、Parseは生成済みの表を何度も再利用する設計になっている。

2. Parseのshift-reduce駆動ループ

flowchart TD
    S0["removeSemicolon(originalTokens)\nstates=[0], values=[], position=0"] --> L{"ループ"}
    L --> Peek["state = states.Peek()\ntoken = tokens[position]\nterminal = tokenToTerminalName(token)"]
    Peek --> F["entry = findAction(state, terminal)"]
    F -->|"nil"| E1["panic（構文エラー）"]
    F --> K{"entry.GetAction().GetKind()"}
    K -- SHIFT --> SH["states.Push(次状態)\nvalues.Push(Token(token.text))\nposition++"] --> L
    K -- REDUCE --> RE["states.PopCount(右辺長)\nvalue = reduce(生成規則index, values)\ngotoState = findGoto(states.Peek(), 左辺名)\nstates.Push(gotoState)\nvalues.Push(value)"] --> L
    K -- ACCEPT --> AC["values.Peek()がSELECT_STATEMENTであることを確認\nSelectStatementを返して終了"]

• 状態はStateStack、意味値はValueStackという2本のスタックが1:1で並走する——標準的なLR系パーサの実装形。SHIFTは両方に1件ずつpush、REDUCEは生成規則の右辺長ぶんを両方から取り除いてから新しい状態・値を1件ずつpushし直す（このpop/pushの非対称なコストについてはstate_stackのドキュメントのPopCountの考察を参照）。
• REDUCEのreduce()は生成規則インデックスで分岐する意味アクション（lalrone_table_generatorが使う文法の生成規則0〜3に対応）。文法自体はlalrone_table_generator.goにハードコードされているため、Parse側のreduceもそれと同じ生成規則番号にハードコードで対応している——文法が変わったらこの2箇所を手で同期させる必要がある密結合な設計。

flowchart LR
    subgraph "reduce(productionIndex, values)"
    direction TB
    P1["#1: SelectStatement -> SELECT IDENTIFIER FROM IDENTIFIER WhereClause\n5値pop（逆順でwhere,table,FROM,column,SELECT）\n→ NewSelectStatement→SelectStatement()"]
    P2["#2: WhereClause -> WHERE IDENTIFIER\n2値pop（column,WHERE）\n→ WhereClause(column)"]
    P3["#3: WhereClause -> ε\n0値pop\n→ WhereClause(\"\")"]
    end

3. findAction/findGoto：ACTION/GOTO表の線形探索

lalrone_table_generator.ParserDataが保持するActionTable/GotoTableは単純なスライスで、findAction/findGotoは毎回先頭から線形走査する（lalrone_table_generatorの内部実装も同じ探索方式）。今回のSELECT文法は状態数9・エントリ数十数個程度なので実用上ほぼ無視できるコストだが（後述のベンチマークで実測）、状態数・終端記号数が大きい文法では(state, terminal)をキーにしたmapなど定数時間探索への置き換えが有効になる規模になりうる。

4. removeSemicolon：前処理

Tokenize()が生成するトークン列に含まれうるSEMICOLONをパース前に取り除く。文法自体にSEMICOLONが存在しない（SelectStatementの生成規則にセミコロンの項がない）ため、これを取り除かないとtokenToTerminalNameが未対応のトークン種別としてpanicする。空スライスからappendで構築するだけの単純な前処理だが、複数文（SELECT ...; SELECT ...;）を1つのトークン列として扱おうとすると文の区切りごと消えてしまう点には注意——この文法・実装は1文だけを解析する前提になっている。

---

5. テスト

lalrone_sql_parser_test.go：

テスト	検証内容
TestParseSelectWithoutWhereClause	SELECT id FROM usersがε還元経由で正しくSelectStatement{column:"id", table:"users", whereColumn:""}になること
TestParseSelectWithWhereClause	SELECT id FROM users WHERE ageがwhereColumn:"age"を含めて正しく組み立てられること
TestParseIgnoresTrailingSemicolon	末尾に;がある入力でもremoveSemicolonにより正しく解析できること
TestParsePanicsOnMissingIdentifier	SELECT FROM users（IDENTIFIER抜け）でfindActionがエントリなしを返しpanicすること
TestParsePanicsOnTokenOutsideGrammar	SELECT 1 FROM usersのNUMBERトークンでtokenToTerminalNameがpanicすること
TestTokenToTerminalName	SELECT/FROM/WHERE/IDENTIFIER/EOFの5種が正しい終端記号名にマップされること
TestTokenToTerminalNamePanicsOnUnknownKind	NUMBERのような未対応のToken種別でpanicすること
TestRemoveSemicolon	セミコロンが1つ除去され、末尾のEOFは保持されたまま返ること
TestFindActionAndFindGoto	存在するエントリを正しく返し、存在しないエントリにはnil/-1を返すこと

go test . -v

---

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回の単純平均

ベンチマーク一覧

ベンチマーク	内容
BenchmarkNewLALR1SqlParser	構築済みLALR1TableGeneratorからLALR1SqlParserを作るだけのコスト（GetLalrData()呼び出し含む）
BenchmarkParseWithoutWhereClause	SELECT id FROM usersを事前トークン化した状態でParse()のみを計測（ε還元経路）
BenchmarkParseWithWhereClause	SELECT id FROM users WHERE ageを事前トークン化した状態でParse()のみを計測（WHERE経路）
BenchmarkTokenizeAndParseWithoutWhereClause	トークン化＋Parse()を通しで計測（表は事前構築済みを使い回す、実運用に近い1クエリあたりのコスト）
BenchmarkTokenizeAndParseWithWhereClause	同上、WHERE句あり
BenchmarkFindAction	findAction(0, "SELECT")（ACTION表の線形探索）単体
BenchmarkFindGoto	findGoto(0, "SelectStatement")（GOTO表の線形探索）単体

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

ベンチマーク	ns/op	B/op	allocs/op	何を計測しているか
BenchmarkNewLALR1SqlParser	16.5	16	1	LALR1SqlParser構造体（フィールド2個＝ポインタ2個＝16B）1個ぶんの確保のみ
BenchmarkParseWithoutWhereClause	383.4	400	8	事前トークン化済み・ε還元経路のParse()単体
BenchmarkParseWithWhereClause	481.8	496	10	事前トークン化済み・WHERE経路のParse()単体（トークン2個・reduce内容が増える分Withoutより重い）
BenchmarkTokenizeAndParseWithoutWhereClause	762.1	600	16	トークン化＋Parse()の合計（実運用の1クエリぶん）
BenchmarkTokenizeAndParseWithWhereClause	998.6	752	21	同上、WHERE句あり
BenchmarkFindAction	2.27	0	0	ACTION表（数エントリ）の線形探索、状態0×"SELECT"のヒット
BenchmarkFindGoto	3.11	0	0	GOTO表の線形探索、状態0×"SelectStatement"のヒット

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

BenchmarkNewLALR1SqlParser-12                   62034158    16.51 ns/op     16 B/op    1 allocs/op
BenchmarkNewLALR1SqlParser-12                   67184077    16.62 ns/op     16 B/op    1 allocs/op
BenchmarkNewLALR1SqlParser-12                   70593787    16.48 ns/op     16 B/op    1 allocs/op
BenchmarkNewLALR1SqlParser-12                   69340016    16.34 ns/op     16 B/op    1 allocs/op
BenchmarkNewLALR1SqlParser-12                   67123688    16.54 ns/op     16 B/op    1 allocs/op

BenchmarkParseWithoutWhereClause-12               3216024   379.0 ns/op    400 B/op    8 allocs/op
BenchmarkParseWithoutWhereClause-12               3095702   385.5 ns/op    400 B/op    8 allocs/op
BenchmarkParseWithoutWhereClause-12               3155306   385.4 ns/op    400 B/op    8 allocs/op
BenchmarkParseWithoutWhereClause-12               3117808   383.4 ns/op    400 B/op    8 allocs/op
BenchmarkParseWithoutWhereClause-12               3148032   383.9 ns/op    400 B/op    8 allocs/op

BenchmarkParseWithWhereClause-12                  2472174   482.3 ns/op    496 B/op   10 allocs/op
BenchmarkParseWithWhereClause-12                  2497508   478.9 ns/op    496 B/op   10 allocs/op
BenchmarkParseWithWhereClause-12                  2513029   482.0 ns/op    496 B/op   10 allocs/op
BenchmarkParseWithWhereClause-12                  2465248   486.1 ns/op    496 B/op   10 allocs/op
BenchmarkParseWithWhereClause-12                  2479166   479.8 ns/op    496 B/op   10 allocs/op

BenchmarkTokenizeAndParseWithoutWhereClause-12    1585039   763.2 ns/op    600 B/op   16 allocs/op
BenchmarkTokenizeAndParseWithoutWhereClause-12    1588574   756.1 ns/op    600 B/op   16 allocs/op
BenchmarkTokenizeAndParseWithoutWhereClause-12    1568354   763.2 ns/op    600 B/op   16 allocs/op
BenchmarkTokenizeAndParseWithoutWhereClause-12    1578576   757.9 ns/op    600 B/op   16 allocs/op
BenchmarkTokenizeAndParseWithoutWhereClause-12    1553764   770.0 ns/op    600 B/op   16 allocs/op

BenchmarkTokenizeAndParseWithWhereClause-12       1000000   1011   ns/op   752 B/op   21 allocs/op
BenchmarkTokenizeAndParseWithWhereClause-12       1206126    995.7 ns/op   752 B/op   21 allocs/op
BenchmarkTokenizeAndParseWithWhereClause-12       1208571    991.7 ns/op   752 B/op   21 allocs/op
BenchmarkTokenizeAndParseWithWhereClause-12       1211421    989.8 ns/op   752 B/op   21 allocs/op
BenchmarkTokenizeAndParseWithWhereClause-12       1000000   1005   ns/op   752 B/op   21 allocs/op

BenchmarkFindAction-12                          531129937     2.264 ns/op    0 B/op    0 allocs/op
BenchmarkFindAction-12                          527236568     2.266 ns/op    0 B/op    0 allocs/op
BenchmarkFindAction-12                          518388350     2.284 ns/op    0 B/op    0 allocs/op
BenchmarkFindAction-12                          530320267     2.259 ns/op    0 B/op    0 allocs/op
BenchmarkFindAction-12                          526721725     2.266 ns/op    0 B/op    0 allocs/op

BenchmarkFindGoto-12                            385689368     3.122 ns/op    0 B/op    0 allocs/op
BenchmarkFindGoto-12                            385099357     3.112 ns/op    0 B/op    0 allocs/op
BenchmarkFindGoto-12                            385891538     3.115 ns/op    0 B/op    0 allocs/op
BenchmarkFindGoto-12                            387427468     3.103 ns/op    0 B/op    0 allocs/op
BenchmarkFindGoto-12                            383588157     3.113 ns/op    0 B/op    0 allocs/op

考察

• NewLALR1SqlParser（16.5ns、16B、1alloc）はほぼ最小コスト。LALR1SqlParser{generator, data}はポインタ2個＝16Bのみで、GetLalrData()は既存フィールドを返すだけ。表そのものの生成コスト（FullPipelineで約7μs）はこのベンチマークの外（buildParser()のセットアップ側）にあり、ここで測っているのは純粋に「既存の表をラップするだけ」のコスト。
• ParseWithoutWhereClause（8 allocs, 400B）の確保は大きく4種類に分けられる（コード上の発生源からの整理。Goのインライン化・スライス再確保の粒度に依存するため厳密な内訳は変動しうる）: (1) removeSemicolonが空スライスからappendで新しいトークン列を組み立てる際の確保、(2) SHIFTのたびにsemantic_value.Token()（各48B、semantic_valueのベンチマーク参照）を4回（SELECT, IDENTIFIER, FROM, IDENTIFIER）、(3) ε還元でWhereClause("")を1回、(4) 最終reduceでselect_statement.NewSelectStatement()とsemantic_value.SelectStatement()ラップの2回。合計7回の意味値生成＋前処理1回で8allocsという実測とおおむね符合する。
• ParseWithWhereClause（10 allocs, 496B）はWithoutより+2 allocs・+96B。WHERE句を含む経路ではSHIFTが2回増え（WHERE, IDENTIFIER）、その分Token()の確保も2回増える一方、ε還元（1回の確保）の代わりにWhereClause -> WHERE IDENTIFIERの非ε還元（同じく1回の確保）が起きるため還元側の回数は変わらない。結果として純増分はSHIFT2回ぶんのToken()確保のみ（+2 allocs, +2×48B=96B）——実測の差分とちょうど一致する。
• TokenizeAndParse*はsql_lexer.Tokenize()（短文で約650ns・15allocs）とParse()の合計にほぼ一致する: Without側は762ns（≈650+383−オーバーラップ分の測定誤差）・16allocs（≈15＋1、Parse内のTokenize結果由来の追加確保は最小限）。実運用でクエリ文字列を受け取ってから構文木を得るまでの総コストとしてはこちらが実態に近い数字になる。
• FindAction（2.27ns）とFindGoto（3.11ns）はこの文法規模（状態数9、ACTION/GOTOあわせて十数エントリ）では無視できるコスト。FindGotoがFindActionよりわずかに重いのは、GOTO表のエントリ判定がGetNonTerminal().GetName()という文字列比較を要する一方、実装上のテーブル走査ロジック自体はほぼ同型であるため。状態数・終端記号数が数百〜数千規模になる実用的な文法では、この線形探索がParse()全体（1トークンあたり1回のACTION探索＋reduceのたびに1回のGOTO探索）の支配的コストになりうる——(state, terminal)をキーとしたmapや、状態ごとに二次元配列化した表への置き換えが有効な最適化ポイントになる。

---

7. 再現手順

# テスト
go test . -v

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

LALR(1) Table Generator go

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

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

S'              -> SelectStatement
SelectStatement -> SELECT IDENTIFIER FROM IDENTIFIER WhereClause
WhereClause     -> WHERE IDENTIFIER
WhereClause     -> ε

これは SELECT <id> FROM <id> に加えて任意の WHERE <id> 句を受理できる文法で、 slrone_table_generator の文法に WhereClause（ε生成規則を含む）を1つ追加したもの。 このパッケージは、この文法から一旦 正準LR(1)集合 を構築し、それを LALR(1) に併合して構文解析表（ACTION表 / GOTO表）を機械的に構築する。

---

1. 全体パイプライン

LALR1TableGenerator は5段階のパイプラインで構文解析表を組み立てる。SLR(1)版と異なり、FOLLOW集合は使わず、各itemが自分専用のlookahead記号を持つ（正準LR(1)方式）。

flowchart LR
    G["文法定義\n(productions / non-terminals)"] --> A
    A["BuildFirstSets()\nFIRST集合を不動点計算\n(εも記号として扱う)"] --> B
    B["BuildCanonicalStates()\n正準LR(1)集合を構築\n(Closure + GoTo, itemごとにlookahead付き)"] --> C
    C["MergeToLalrStates()\n同じcoreを持つ状態をLALR(1)へ併合\n(lookaheadを和集合でマージ)"] --> D
    D["BuildLalrTables()\nACTION/GOTO表を確定\n(REDUCEはitem自身のlookaheadで決定)"] --> E["LALR(1) 構文解析表\n(lalrData: ParserData)"]

• FIRST（BuildFirstSets）: SLR版と同じ不動点計算だが、WhereClause -> ε のような空生成規則があるため ε 自体を FIRST の要素として明示的に追加する。firstOfSequence はitem のクロージャ計算時に「ドットの後ろの記号列 + 現在のlookahead」から新しいlookaheadを導出するために使う。
• 正準LR(1)状態集合（BuildCanonicalStates）: SLR(1)/LR(0)のitemが (生成規則, ドット位置) だけを持つのに対し、LR(1)のitem（LR1Item）は追加で lookahead記号1つ を持つ。Closure はitemを展開するたびに FIRST(β lookahead) を計算し、新しいitemそれぞれに正しいlookaheadを割り当てる。これにより同じ「core（生成規則+ドット位置）」でもlookaheadが異なれば別itemとして扱われ、状態数がLR(0)/SLR(1)より増える可能性がある。
• LALR(1)併合（MergeToLalrStates）: 正準LR(1)の状態を走査し、同じcore集合（ItemSet.SameCore）を持つ状態をひとつのLALR状態にまとめ、lookaheadを和集合でマージする（MergeLookaheads）。遷移（Transition）も併合後の状態番号に付け替える。
• 表構築（BuildLalrTables）: SLR(1)のようにFOLLOW集合を使わず、item自身が持つlookaheadをそのままREDUCEの対象terminalとして使う。これがLALR(1)とSLR(1)の決定的な違い（SLR(1)はFOLLOW集合、LALR(1)/正準LR(1)はitem付随のlookaheadでREDUCEを決める）。

---

2. FIRST 集合

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

非終端記号	FIRST
S'	{ SELECT }
SelectStatement	{ SELECT }
WhereClause	{ WHERE, ε }

WhereClause -> WHERE IDENTIFIER の右辺先頭が終端記号 WHERE なので FIRST に WHERE が入り、WhereClause -> ε（右辺が空）は無条件に FIRST へ ε を追加する。この ε の有無が、Closure 内で WhereClause を含むitemを展開する際に「lookaheadをそのまま引き継ぐか、FIRST(β)を使うか」の分岐に直結する。

---

3. 正準LR(1)集合とLALR(1)への併合

BuildCanonicalStates が構築する正準LR(1)状態は次の9つ（TestBuildCanonicalStates で状態数=9を検証）。• はドット位置、, X はlookahead。

状態	Item集合
S0 (初期)	S' -> • SelectStatement, EOF SelectStatement -> • SELECT IDENTIFIER FROM IDENTIFIER WhereClause, EOF
S1	S' -> SelectStatement •, EOF
S2	SelectStatement -> SELECT • IDENTIFIER FROM IDENTIFIER WhereClause, EOF
S3	SelectStatement -> SELECT IDENTIFIER • FROM IDENTIFIER WhereClause, EOF
S4	SelectStatement -> SELECT IDENTIFIER FROM • IDENTIFIER WhereClause, EOF
S5	SelectStatement -> SELECT IDENTIFIER FROM IDENTIFIER • WhereClause, EOF WhereClause -> • WHERE IDENTIFIER, EOF WhereClause -> •, EOF
S6	SelectStatement -> SELECT IDENTIFIER FROM IDENTIFIER WhereClause •, EOF
S7	WhereClause -> WHERE • IDENTIFIER, EOF
S8	WhereClause -> WHERE IDENTIFIER •, EOF

状態遷移図（正準LR(1)とLALR(1)で共通。理由は後述）:

stateDiagram-v2
    [*] --> S0
    S0 --> S1 : SelectStatement (GOTO)
    S0 --> S2 : SELECT (SHIFT)
    S2 --> S3 : IDENTIFIER (SHIFT)
    S3 --> S4 : FROM (SHIFT)
    S4 --> S5 : IDENTIFIER (SHIFT)
    S5 --> S6 : WhereClause (GOTO)
    S5 --> S7 : WHERE (SHIFT)
    S7 --> S8 : IDENTIFIER (SHIFT)
    S1 --> [*] : EOF / ACCEPT
    S6 --> [*] : EOF / REDUCE production#1
    S5 --> [*] : EOF / REDUCE production#3 (ε)
    S8 --> [*] : EOF / REDUCE production#2

S5 が最も重要な状態: SELECT IDENTIFIER FROM IDENTIFIER まで読んだ直後の状態で、WhereClause のクロージャが Closure によって展開され、WHERE IDENTIFIER に進むitemと、何も読まずに ε で還元するitemが同じ状態内に共存する。次のlookaheadが WHERE ならSHIFT、EOF ならREDUCE（ε生成規則）と、1つの状態が2種類のアクションを持つ（TestBuildLalrTablesShiftsAndEpsilonReduce で検証）。

LALR(1)への併合（MergeToLalrStates）について

この文法は SelectStatement を生成する経路が唯一（S' -> SelectStatement の1本だけ）で、WhereClause を生成する経路もS5から1本だけしかない。そのため、異なるコンテキストから同じcoreの状態に合流するケースが存在せず、MergeToLalrStates はLALR併合を試みても実際にはマージが1件も発生しない（TestMergeToLalrStatesPreservesStateCount で検証: LALR状態数 = 正準LR(1)状態数 = 9）。

これは「LALR(1)はLR(1)より状態数が少ない」という一般論が常に成り立つわけではなく、文法内に同一coreへの複数経路が存在しない限り、LALR(1)は正準LR(1)と一致するという具体例である。より大きい・再帰的な文法（例えば式の文法など）ではこの併合が実際に状態数を減らす。

ACTION / GOTO 表

状態	SELECT	IDENTIFIER	FROM	WHERE	EOF	GOTO(SelectStatement)	GOTO(WhereClause)
0	shift 2					1
1					accept
2		shift 3
3			shift 4
4		shift 5
5				shift 7	reduce #3 (ε)		6
6					reduce #1
7		shift 8
8					reduce #2

（TestBuildLalrTablesShiftsAndEpsilonReduce / TestBuildLalrTablesAcceptState / TestBuildLalrTablesNoConflicts で検証。この文法はLALR(1)の範囲で衝突なく一意に決定できる。）

---

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

4-1. WHERE句なし: SELECT IDENTIFIER FROM IDENTIFIER EOF

（TestParseAcceptsSentenceWithoutWhereClause が検証）

ステップ	スタック（状態）	残り入力	アクション
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 #3 (ε, 0記号pop) → goto(5, WhereClause) = 6
6	0 2 3 4 5 6	EOF	reduce #1 (5記号pop) → goto(0, SelectStatement) = 1
7	0 1	EOF	ACCEPT

ε生成規則の還元はトークンを1つも消費せず、単に現在の状態の上に GOTO(WhereClause) の遷移先を積むだけである点に注意（ステップ5→6で残り入力が変化していない）。

4-2. WHERE句あり: SELECT IDENTIFIER FROM IDENTIFIER WHERE IDENTIFIER EOF

（TestParseAcceptsSentenceWithWhereClause が検証）

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

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

---

5. テスト

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

=== RUN   TestBuildFirstSets                              --- PASS
=== RUN   TestBuildCanonicalStates                        --- PASS
=== RUN   TestBuildCanonicalStatesEpsilonClosure           --- PASS
=== RUN   TestMergeToLalrStatesPreservesStateCount         --- PASS
=== RUN   TestBuildLalrTablesShiftsAndEpsilonReduce        --- PASS
=== RUN   TestBuildLalrTablesAcceptState                  --- PASS
=== RUN   TestBuildLalrTablesNoConflicts                  --- PASS
=== RUN   TestParseAcceptsSentenceWithoutWhereClause       --- PASS
=== RUN   TestParseAcceptsSentenceWithWhereClause          --- PASS
=== RUN   TestParseRejectsInvalidSentence                  --- PASS
PASS
ok      example.com/lalrone_table_generator 0.003s

テスト	検証内容
TestBuildFirstSets	FIRST(S'), FIRST(SelectStatement) が {SELECT}、FIRST(WhereClause) が {WHERE, ε} になること
TestBuildCanonicalStates	正準LR(1)集合の状態数が9、初期状態のitem数が2であること
TestBuildCanonicalStatesEpsilonClosure	SELECT→IDENTIFIER→FROM→IDENTIFIER を辿った状態(S5)のクロージャが3item（SHIFT用item + ε還元用item + 生成規則1のドット進行item）であり、ε還元itemのlookaheadがEOFであること
TestMergeToLalrStatesPreservesStateCount	この文法には同coreへの複数経路がないため、LALR併合後も状態数が正準LR(1)と変わらない（=9）こと
TestBuildLalrTablesShiftsAndEpsilonReduce	4回のSHIFTの連鎖の末尾状態が、lookahead=EOFならREDUCE(#3, ε)、lookahead=WHEREならSHIFTという2方向のアクションを持つこと
TestBuildLalrTablesAcceptState	GOTO後の状態でACCEPTアクションが設定されること
TestBuildLalrTablesNoConflicts	BuildLalrTables() がLALR(1)衝突(panic)を起こさないこと
TestParseAcceptsSentenceWithoutWhereClause	WHERE句を省略した文をε還元経由で正しく受理できること（end-to-end）
TestParseAcceptsSentenceWithWhereClause	WHERE句を含む文を正しく受理できること（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	何を計測しているか
BenchmarkNewLALR1TableGenerator	306.5	368	11	NewLALR1TableGenerator()。FIRSTエントリの箱（非終端記号3個分）を用意するだけの初期化コスト
BenchmarkBuildFirstSets	274.5	40	4	FIRST集合の不動点ループ単体。3つの生成規則を1〜2周で収束（εを明示的に扱う分、SLR版よりわずかに重い）
BenchmarkBuildCanonicalStates	3490.8	1992	99	正準LR(1)集合の構築（Closure+GoToをワークリスト方式で全状態に適用）。9状態・8遷移を生成。itemごとにlookaheadを計算・比較する分、SLR版のBuildStates(約1.67µs/6状態)より単位状態あたりのコストが高い
BenchmarkMergeToLalrStates	2954.6	1280	51	正準LR(1)状態をLALR(1)へ併合する処理。9状態それぞれについて「同coreの既存LALR状態」を線形探索するため、この文法では併合が起きなくてもコストは発生する
BenchmarkBuildLalrTables	1813.2	720	29	併合済みLALR状態集合からACTION/GOTO表を確定させる処理。SLR版と異なりFOLLOW集合を引かず、item自身のlookaheadをそのまま使うためロジック自体は単純
BenchmarkFullPipeline	7052.4	4400	194	New→BuildFirstSets→BuildCanonicalStates→MergeToLalrStates→BuildLalrTables を通しで実行した合計コスト
BenchmarkClosure	342.5	200	12	BuildCanonicalStates内で最も頻繁に呼ばれるClosure単体の1回あたりコスト（開始item1個からの展開）
BenchmarkParseWithoutWhereClause	387.1	112	3	完成した表を使いSELECT IDENTIFIER FROM IDENTIFIER EOF（ε還元経由）をshift-reduce駆動する
BenchmarkParseWithWhereClause	413.0	112	3	完成した表を使いSELECT IDENTIFIER FROM IDENTIFIER WHERE IDENTIFIER EOFをshift-reduce駆動する（トークン2個・状態遷移2回分、上より重い）

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

BenchmarkNewLALR1TableGenerator-12     3900216   306.9 ns/op    368 B/op   11 allocs/op
BenchmarkNewLALR1TableGenerator-12     3859873   306.3 ns/op    368 B/op   11 allocs/op
BenchmarkNewLALR1TableGenerator-12     3974302   308.2 ns/op    368 B/op   11 allocs/op
BenchmarkNewLALR1TableGenerator-12     3709036   304.9 ns/op    368 B/op   11 allocs/op
BenchmarkNewLALR1TableGenerator-12     3863604   306.1 ns/op    368 B/op   11 allocs/op

BenchmarkBuildFirstSets-12             4362571   276.3 ns/op     40 B/op    4 allocs/op
BenchmarkBuildFirstSets-12             4670176   271.3 ns/op     40 B/op    4 allocs/op
BenchmarkBuildFirstSets-12             4763436   275.9 ns/op     40 B/op    4 allocs/op
BenchmarkBuildFirstSets-12             4761742   272.7 ns/op     40 B/op    4 allocs/op
BenchmarkBuildFirstSets-12             4749864   276.2 ns/op     40 B/op    4 allocs/op

BenchmarkBuildCanonicalStates-12        377847  3274   ns/op   1992 B/op   99 allocs/op
BenchmarkBuildCanonicalStates-12        311091  3628   ns/op   1992 B/op   99 allocs/op
BenchmarkBuildCanonicalStates-12        308690  3388   ns/op   1992 B/op   99 allocs/op
BenchmarkBuildCanonicalStates-12        314509  3572   ns/op   1992 B/op   99 allocs/op
BenchmarkBuildCanonicalStates-12        316230  3592   ns/op   1992 B/op   99 allocs/op

BenchmarkMergeToLalrStates-12           411033  2977   ns/op   1280 B/op   51 allocs/op
BenchmarkMergeToLalrStates-12           466284  2964   ns/op   1280 B/op   51 allocs/op
BenchmarkMergeToLalrStates-12           422347  2959   ns/op   1280 B/op   51 allocs/op
BenchmarkMergeToLalrStates-12           469724  2967   ns/op   1280 B/op   51 allocs/op
BenchmarkMergeToLalrStates-12           465328  2906   ns/op   1280 B/op   51 allocs/op

BenchmarkBuildLalrTables-12             764875  2023   ns/op    720 B/op   29 allocs/op
BenchmarkBuildLalrTables-12             716302  1550   ns/op    720 B/op   29 allocs/op
BenchmarkBuildLalrTables-12             964287  2005   ns/op    720 B/op   29 allocs/op
BenchmarkBuildLalrTables-12             890586  1562   ns/op    720 B/op   29 allocs/op
BenchmarkBuildLalrTables-12             937086  1926   ns/op    720 B/op   29 allocs/op

BenchmarkFullPipeline-12                163237  7473   ns/op   4400 B/op  194 allocs/op
BenchmarkFullPipeline-12                166263  7051   ns/op   4400 B/op  194 allocs/op
BenchmarkFullPipeline-12                176608  6955   ns/op   4400 B/op  194 allocs/op
BenchmarkFullPipeline-12                169735  6908   ns/op   4400 B/op  194 allocs/op
BenchmarkFullPipeline-12                170878  6875   ns/op   4400 B/op  194 allocs/op

BenchmarkClosure-12                    3569677   340.1 ns/op    200 B/op   12 allocs/op
BenchmarkClosure-12                    3489171   343.3 ns/op    200 B/op   12 allocs/op
BenchmarkClosure-12                    3523848   343.5 ns/op    200 B/op   12 allocs/op
BenchmarkClosure-12                    3466208   342.7 ns/op    200 B/op   12 allocs/op
BenchmarkClosure-12                    3536394   342.9 ns/op    200 B/op   12 allocs/op

BenchmarkParseWithoutWhereClause-12    3075199   383.7 ns/op    112 B/op    3 allocs/op
BenchmarkParseWithoutWhereClause-12    3126412   386.4 ns/op    112 B/op    3 allocs/op
BenchmarkParseWithoutWhereClause-12    3065058   389.7 ns/op    112 B/op    3 allocs/op
BenchmarkParseWithoutWhereClause-12    3094768   388.6 ns/op    112 B/op    3 allocs/op
BenchmarkParseWithoutWhereClause-12    3062438   387.3 ns/op    112 B/op    3 allocs/op

BenchmarkParseWithWhereClause-12       2889519   413.0 ns/op    112 B/op    3 allocs/op
BenchmarkParseWithWhereClause-12       2894422   414.0 ns/op    112 B/op    3 allocs/op
BenchmarkParseWithWhereClause-12       2894446   414.4 ns/op    112 B/op    3 allocs/op
BenchmarkParseWithWhereClause-12       2895122   411.5 ns/op    112 B/op    3 allocs/op
BenchmarkParseWithWhereClause-12       2877098   412.2 ns/op    112 B/op    3 allocs/op

考察

• BuildCanonicalStates が最も重い（約3.49µs、99 allocs）。slrone_table_generatorのBenchmarkBuildStates（約1.67µs、56 allocs、6状態）と比べると、状態数は9/6=1.5倍だがコストは約2.1倍・allocsは約1.8倍。差分の主因はLR(1)のClosureがitemごとにlookaheadを持つためitem_set.Containsの比較対象が増え、かつfirstOfSequence（FIRST(β lookahead)の計算）がClosureの展開のたびに毎回走ること。SLR(1)/LR(0)のClosureはcoreの重複チェックのみで済むのに対し、LR(1)は「core + lookahead」の組み合わせで重複チェックする必要があり、本質的に計算量が増える。
• MergeToLalrStates（約2.95µs）も無視できないコスト。この文法では実際のマージ（複数の正準状態を1つのLALR状態に統合する処理）は1件も発生しない（TestMergeToLalrStatesPreservesStateCount参照）にもかかわらず、9状態それぞれについてfindLalrStateByCore（既存LALR状態への線形探索、SameCoreは内部でさらにuniqueCoresのO(n²)重複除去を行う）とcopyItemSet、遷移の付け替え（addLalrTransitionの線形探索）を行うため、実質「マージが起きない場合の下限コスト」がこの数字になる。文法が大きくなり実際にマージが発生するケースでは、findLalrStateByCoreの呼び出し回数はそのままだがMergeLookaheadsのコストが追加される。
• FullPipeline（≈7.05µs）はほぼ各段の合計（274.5ns + 3490.8ns + 2954.6ns + 1813.2ns ≈ 8533ns 弱ではなく実測7052ns。差は各ベンチが独立したNewLALR1TableGenerator呼び出しを含む一方、FullPipelineは1回のNew呼び出しで済むため、および測定オーバーヘッドの違いによる）。段階ごとの相対的な重さの序列（CanonicalStates > Merge > BuildTables > First）はFullPipelineの内訳としてそのまま観察できる。
• Parse（表を使う側、387〜413ns）はBuildCanonicalStatesより軽い。SLR版と同様、表の構築（オフライン処理）は一度きりで良いのに対し、構築済みの表を使った実際の構文解析（オンライン処理）は毎回発生するため、この非対称性は妥当な設計と言える。WHERE句ありのケース（413ns）はトークンを2個・状態遷移を2回多く消費するため、WHERE句なしのケース（387ns）よりわずかに重い。

ベンチマーク実装上の注意（SLR版からの継承事項）

slrone_table_generatorのベンチマーク実装で判明した知見をそのまま踏襲している。単体ベンチマーク（BuildFirstSets、BuildCanonicalStates、MergeToLalrStates、BuildLalrTables）はいずれも「対象呼び出しに必要な前段のセットアップ」を持つが、これをループ内でb.StopTimer()/b.StartTimer()を使って毎回やり直すと、-benchmem併用時にruntime.ReadMemStats()（ストップ・ザ・ワールド）のオーバーヘッドがベンチマーク対象を完全に支配してしまう。

このためbuildUpTo(n, stage)ヘルパー（lalrone_table_generator_bench_test.go）で、計測対象メソッド呼び出しに必要な前段の生成器をb.N個ぶんタイマー計測開始前にまとめて事前生成し、計測ループでは対象メソッドの呼び出しのみを行う形にしている。

---

7. 再現手順

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

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

LR(1) Table Generator go

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

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

S'              -> SelectStatement
SelectStatement -> SELECT IDENTIFIER FROM IDENTIFIER WhereClause
WhereClause     -> WHERE IDENTIFIER
WhereClause     -> ε

SELECT <id> FROM <id> [WHERE <id>] — WHERE句が省略可能なSQL文を受理する文法。 このパッケージはこの文法から 正準LR(1) 構文解析表（ACTION表 / GOTO表）を機械的に構築する。

姉妹パッケージ slrone_table_generator（ALGORITHM.md 相当）との最大の違いは、WhereClause -> ε という ε生成規則を含む点。これによりACTION表上で「shiftすべきか、空生成規則をreduceすべきか」を1個のFOLLOW集合だけでは正しく決められない場面が生じうる（この文法自体はSLRでも解けるほど単純だが、一般にはLR(1)のitemごとの先読みが必要になる代表例になっている）。

---

1. 全体パイプライン

LR1TableGenerator は3段階のパイプラインで構文解析表を組み立てる。SLR(1)と異なり FOLLOW集合の計算が存在しない ことに注意（LR(1)は各itemが個別に先読み記号を持つため、非終端記号ごとのグローバルなFOLLOW集合を使わない）。

flowchart LR
    G["文法定義\n(productions / terminals / non-terminals)"] --> A
    A["BuildFirstSets()\nFIRST集合を不動点計算"] --> B
    B["BuildStates()\n正準LR(1)状態集合を構築\n(Closure + GoTo、各itemが先読み記号を保持)"] --> C
    C["BuildTables()\nACTION/GOTO表を確定\n(REDUCEはitemのlookaheadで決定)"] --> D["LR(1) 構文解析表\n(ParserData)"]

• FIRST（BuildFirstSets）: 各非終端記号がどの終端記号から始まりうるかを、変化がなくなるまで反復して求める不動点アルゴリズム。WhereClause -> ε があるため FIRST(WhereClause) は {WHERE, ε} になる。
• 正準LR(1)状態集合（BuildStates）: 「ドット付き生成規則 + 先読み記号（lookahead）」＝LR(1) item の集合＝状態を、Closure と GoTo を使って再帰的に展開し、状態遷移グラフ（LR(1)オートマトン）を作る。SLR(0)/LR(0)との違いは、Closureが新しいitemを追加するたびに firstOfSequence(β a)（βはドットの直後から生成規則末尾までの記号列、aは元のitemの先読み記号）を計算し、item固有の先読み記号を割り当てる点。
• 表構築（BuildTables）: 各状態内のitemを見て、ドットが終端記号の前ならSHIFT、非終端記号の前ならGOTO、末尾に達していれば そのitem自身が持つ先読み記号 に対してREDUCEを割り当てる（SLR(1)のようにFOLLOW集合全体を使うのではなく、item単位でピンポイントに決まる）。ドットが生成規則0の末尾かつ先読みがEOFならACCEPT。

---

2. FIRST 集合

TestBuildFirstSets で検証済みの値:

非終端記号	FIRST
S'	{ SELECT }
SelectStatement	{ SELECT }
WhereClause	{ WHERE, ε }

WhereClause は2本の生成規則を持つ（WHERE IDENTIFIER と 空）ため、FIRST(WhereClause) は先頭終端記号 WHERE に加えて ε（空生成規則があることを示すマーカー）を含む。この ε を含む点が、後述する Closure の先読み計算 (firstOfSequence) で重要な役割を果たす。

---

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

BuildStates が構築する状態は次の9つ（TestBuildStates で状態数=9を検証）。全itemの先読みは偶然どれも EOF になる — この文法には先読みで状態を分岐させる文脈（同じitem集合が異なる先読みで別状態に分かれるケース）が存在しないため。それでも Closure は各itemごとに firstOfSequence で先読みを導出しており、後述のS5でその効果が現れる。

状態	Item集合（先読みは全て EOF）
S0（初期）	S' -> •SelectStatement SelectStatement -> •SELECT IDENTIFIER FROM IDENTIFIER WhereClause
S1	S' -> SelectStatement•
S2	SelectStatement -> SELECT•IDENTIFIER FROM IDENTIFIER WhereClause
S3	SelectStatement -> SELECT IDENTIFIER•FROM IDENTIFIER WhereClause
S4	SelectStatement -> SELECT IDENTIFIER FROM•IDENTIFIER WhereClause
S5	SelectStatement -> SELECT IDENTIFIER FROM IDENTIFIER•WhereClause WhereClause -> •WHERE IDENTIFIER WhereClause -> •
S6	SelectStatement -> SELECT IDENTIFIER FROM IDENTIFIER WhereClause•
S7	WhereClause -> WHERE•IDENTIFIER
S8	WhereClause -> WHERE IDENTIFIER•

状態遷移図:

stateDiagram-v2
    [*] --> S0
    S0 --> S1 : SelectStatement (GOTO)
    S0 --> S2 : SELECT (SHIFT)
    S2 --> S3 : IDENTIFIER (SHIFT)
    S3 --> S4 : FROM (SHIFT)
    S4 --> S5 : IDENTIFIER (SHIFT)
    S5 --> S6 : WhereClause (GOTO)
    S5 --> S7 : WHERE (SHIFT)
    S7 --> S8 : IDENTIFIER (SHIFT)
    S1 --> [*] : EOF / ACCEPT
    S6 --> [*] : EOF / REDUCE production#1
    S5 --> [*] : EOF / REDUCE production#3 (ε)
    S8 --> [*] : EOF / REDUCE production#2

S5が本文法の核心（TestBuildStatesTransitionChain / TestClosureComputesLookaheadFromContext で検証）。SELECT IDENTIFIER FROM IDENTIFIER まで読んだ状態でドットが WhereClause の直前に来ると、Closure が2つの新item WhereClause -> •WHERE IDENTIFIER と WhereClause -> • を追加する。両方の先読みは firstOfSequence(β a) で決まる — ここで β は空（ドットが生成規則1の末尾記号の直前なので後続記号がない）なので firstOfSequence は元のitemの先読み a（＝EOF）をそのまま返す。結果としてS5では

• 次のトークンが WHERE なら shift（S7へ）
• 次のトークンが EOF なら WhereClause -> ε を reduce（WhereClauseは空文字列として確定）

という一意な判断ができる。これがまさにLR(1)がSLR(1)と比べて「item単位の先読み」を扱える理由の具体例（この文法ではFOLLOW集合を使ってもたまたま同じ結果になるが、一般のε生成規則を含む文法ではitem単位の先読みでないと衝突が起きるケースがある）。

ACTION / GOTO 表

状態	SELECT	IDENTIFIER	FROM	WHERE	EOF	GOTO(SelectStatement)	GOTO(WhereClause)
0	shift 2					1
1					accept
2		shift 3
3			shift 4
4		shift 5
5				shift 7	reduce #3(ε)		6
6					reduce #1
7		shift 8
8					reduce #2

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

---

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

4.1 WHERE句ありの入力

入力 SELECT IDENTIFIER FROM IDENTIFIER WHERE IDENTIFIER EOF（TestParseAcceptsSentenceWithWhereClause が検証）。

ステップ	スタック（状態）	残り入力	アクション
1	0	SELECT ... EOF	shift → 2
2	0 2	IDENTIFIER FROM IDENTIFIER WHERE IDENTIFIER EOF	shift → 3
3	0 2 3	FROM IDENTIFIER WHERE IDENTIFIER EOF	shift → 4
4	0 2 3 4	IDENTIFIER WHERE IDENTIFIER EOF	shift → 5
5	0 2 3 4 5	WHERE IDENTIFIER EOF	shift → 7（S5でlookahead=WHEREなのでshift）
6	0 2 3 4 5 7	IDENTIFIER EOF	shift → 8
7	0 2 3 4 5 7 8	EOF	reduce #2（WhereClause -> WHERE IDENTIFIER、2記号pop）→ goto(5, WhereClause) = 6
8	0 2 3 4 5 6	EOF	reduce #1（5記号pop）→ goto(0, SelectStatement) = 1
9	0 1	EOF	ACCEPT

4.2 WHERE句なしの入力（ε-reduce のケース）

入力 SELECT IDENTIFIER FROM IDENTIFIER EOF（TestParseAcceptsSentenceWithoutWhereClause が検証）。

ステップ	スタック（状態）	残り入力	アクション
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 #3（WhereClause -> ε、0記号pop）→ goto(5, WhereClause) = 6
6	0 2 3 4 5 6	EOF	reduce #1（5記号pop）→ goto(0, SelectStatement) = 1
7	0 1	EOF	ACCEPT

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

---

5. テスト

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

=== RUN   TestBuildFirstSets                                    --- PASS
=== RUN   TestBuildStates                                       --- PASS
=== RUN   TestBuildStatesTransitionChain                        --- PASS
=== RUN   TestClosureComputesLookaheadFromContext                --- PASS
=== RUN   TestBuildTablesShiftsAndReduceAtEmptyWhereClause       --- PASS
=== RUN   TestBuildTablesReduceAfterWhereClause                  --- PASS
=== RUN   TestBuildTablesAcceptState                             --- PASS
=== RUN   TestBuildTablesNoConflicts                             --- PASS
=== RUN   TestParseAcceptsSentenceWithWhereClause                --- PASS
=== RUN   TestParseAcceptsSentenceWithoutWhereClause             --- PASS
=== RUN   TestParseRejectsInvalidSentence                        --- PASS
PASS
ok      example.com/lrone_table_generator   0.003s

テスト	検証内容
TestBuildFirstSets	FIRST(S')={SELECT}, FIRST(SelectStatement)={SELECT}, FIRST(WhereClause)={WHERE, ε}
TestBuildStates	正準集合の状態数が9、初期状態のitem数が2、先読みが全てEOFであること
TestBuildStatesTransitionChain	SELECT→IDENTIFIER→FROM→IDENTIFIER の遷移を辿るとS5（3item、shift用/ε-reduce用のWhereClause item両方を含む）に到達すること
TestClosureComputesLookaheadFromContext	ClosureがfirstOfSequence(β a)経由で正しい先読み（この場合EOF）をWhereClause側のitemに割り当てること
TestBuildTablesShiftsAndReduceAtEmptyWhereClause	S5でWHEREはSHIFT、EOFはREDUCE(#3, ε生成規則)になること
TestBuildTablesReduceAfterWhereClause	WHERE IDENTIFIERを読んだ後の状態でEOFがREDUCE(#2)になること
TestBuildTablesAcceptState	GOTO後の状態でACCEPTアクションが設定されること
TestBuildTablesNoConflicts	BuildTables() がLR(1)衝突(panic)を起こさないこと
TestParseAcceptsSentenceWithWhereClause	WHERE句ありの文を表を実際にshift-reduce駆動して受理できること（end-to-end）
TestParseAcceptsSentenceWithoutWhereClause	WHERE句なし（ε-reduce経由）の文を受理できること（end-to-end、LR(1)ならではのケース）
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	何を計測しているか
BenchmarkNewLR1TableGenerator	266.5	272	10	NewLR1TableGenerator()。FIRSTエントリの箱（非終端記号3個分）を用意するだけの初期化コスト
BenchmarkBuildFirstSets	274.5	40	4	FIRST集合の不動点ループ単体。3つの生成規則を1〜2周で収束（ε生成規則の分だけSLR版よりわずかに重い）
BenchmarkBuildStates	3547.2	1992	99	正準LR(1)状態集合の構築（Closure+GoToをワークリスト方式で全9状態に適用）。SLR版（6状態・1008B・56allocs）よりおよそ2倍重い
BenchmarkBuildTables	1563.6	720	29	構築済み状態集合からACTION/GOTO表を確定させる処理
BenchmarkFullPipeline	4768.2	3024	142	New→BuildFirstSets→BuildStates→BuildTables を通しで実行した合計コスト
BenchmarkClosure	422.9	280	15	BuildStates内で最も頻繁に呼ばれるClosure単体の1回あたりコスト（S5直前のitemを起点。firstOfSequence呼び出しを含むためSLR版のClosure(142.8ns/6allocs)よりおよそ3倍重い）
BenchmarkParse	401.4	112	3	完成した表を使いSELECT IDENTIFIER FROM IDENTIFIER WHERE IDENTIFIER EOFをshift-reduce駆動する（生成した表を「使う」側のコスト）

生データ（-count 5、5サンプル全て）:

BenchmarkNewLR1TableGenerator-12    4410764   264.0 ns/op   272 B/op   10 allocs/op
BenchmarkNewLR1TableGenerator-12    4570023   269.4 ns/op   272 B/op   10 allocs/op
BenchmarkNewLR1TableGenerator-12    4564868   268.7 ns/op   272 B/op   10 allocs/op
BenchmarkNewLR1TableGenerator-12    4486573   265.2 ns/op   272 B/op   10 allocs/op
BenchmarkNewLR1TableGenerator-12    4389478   265.4 ns/op   272 B/op   10 allocs/op

BenchmarkBuildFirstSets-12          4160438   294.1 ns/op    40 B/op    4 allocs/op
BenchmarkBuildFirstSets-12          4262932   289.2 ns/op    40 B/op    4 allocs/op
BenchmarkBuildFirstSets-12          4510918   257.7 ns/op    40 B/op    4 allocs/op
BenchmarkBuildFirstSets-12          4956218   257.4 ns/op    40 B/op    4 allocs/op
BenchmarkBuildFirstSets-12          4947603   273.9 ns/op    40 B/op    4 allocs/op

BenchmarkBuildStates-12              369514   3392  ns/op  1992 B/op   99 allocs/op
BenchmarkBuildStates-12              304166   3526  ns/op  1992 B/op   99 allocs/op
BenchmarkBuildStates-12              297802   3602  ns/op  1992 B/op   99 allocs/op
BenchmarkBuildStates-12              293401   3587  ns/op  1992 B/op   99 allocs/op
BenchmarkBuildStates-12              292615   3629  ns/op  1992 B/op   99 allocs/op

BenchmarkBuildTables-12             1000000   1537  ns/op   720 B/op   29 allocs/op
BenchmarkBuildTables-12             1000000   1590  ns/op   720 B/op   29 allocs/op
BenchmarkBuildTables-12              812493   1550  ns/op   720 B/op   29 allocs/op
BenchmarkBuildTables-12              845523   1549  ns/op   720 B/op   29 allocs/op
BenchmarkBuildTables-12              952377   1592  ns/op   720 B/op   29 allocs/op

BenchmarkFullPipeline-12             248599   4982  ns/op  3024 B/op  142 allocs/op
BenchmarkFullPipeline-12             244430   4659  ns/op  3024 B/op  142 allocs/op
BenchmarkFullPipeline-12             251725   4815  ns/op  3024 B/op  142 allocs/op
BenchmarkFullPipeline-12             243554   4710  ns/op  3024 B/op  142 allocs/op
BenchmarkFullPipeline-12             246165   4675  ns/op  3024 B/op  142 allocs/op

BenchmarkClosure-12                 2814622   428.1 ns/op   280 B/op   15 allocs/op
BenchmarkClosure-12                 2808974   421.6 ns/op   280 B/op   15 allocs/op
BenchmarkClosure-12                 2854810   415.8 ns/op   280 B/op   15 allocs/op
BenchmarkClosure-12                 2948082   421.4 ns/op   280 B/op   15 allocs/op
BenchmarkClosure-12                 2829309   427.8 ns/op   280 B/op   15 allocs/op

BenchmarkParse-12                   3000613   398.4 ns/op   112 B/op    3 allocs/op
BenchmarkParse-12                   2992520   400.2 ns/op   112 B/op    3 allocs/op
BenchmarkParse-12                   2976548   407.0 ns/op   112 B/op    3 allocs/op
BenchmarkParse-12                   2956528   401.2 ns/op   112 B/op    3 allocs/op
BenchmarkParse-12                   2987973   400.3 ns/op   112 B/op    3 allocs/op

考察

• BuildStates が圧倒的に最も重い（約3.55µs、99 allocs、FullPipelineの約74%を占める）。LR(1)のClosureはitemごとに firstOfSequence(β a) を呼んで先読み記号集合を求め、さらにlrone_item.NewLR1Itemは先読み記号込みでitemを生成するため、SLR(0)版のClosure（先読みなしのitem比較のみ）よりアロケーション・比較コストが大きい。加えてこの文法はSLR版より状態数が9（SLR版は6）、生成規則が4本（SLR版は2本）多く、状態集合探索(findStateによるItemSet同士のSameAs線形比較。これもitem_set.Contains経由でO(n²)的）の対象も増えている。文法規模が大きくなるほど、先読み付きitemの比較コストと状態数の掛け算でここが真っ先にボトルネックになる。
• Closure単体（423ns、15 allocs）はSLR版（143ns、6 allocs）のおよそ3倍。差分の主因は firstOfSequence の呼び出し（β+aの記号列を都度スライスで組み立ててFIRST集合を線形走査）と、NewLR1Itemが保持する先読みポインタ分のフィールドが増えていること。
• FullPipeline（≈4.77µs）はおおむね BuildStates + BuildTables の合計（3547ns + 1564ns ≈ 5111ns）に近いオーダーだが、単体ベンチマークはbuildUpToで事前生成した[]*LR1TableGeneratorからgens[i]を読む間接参照コストを含むため、完全に一致はしない（実測は単体合計よりやや軽い）。New/BuildFirstSetsの寄与は数百nsのオーダーで、全体に対しては小さい。
• Parse（表を使う側、401ns）はBuildStatesより一桁近く軽い。表の構築（オフライン処理、状態集合の再帰的探索を伴う）は一度きりで良いのに対し、構築済みの表を使った実際の構文解析（オンライン処理、ACTION表の線形探索×トークン数）は毎回発生するため、この非対称性は妥当な設計と言える。SLR版のParse（368ns）と近い値なのは、Parseが読むのはACTION/GOTO表という「結果」であって、LR(1)固有の先読み計算コストはすでにBuildStates側で払い終わっているため。
• FIRST集合の計算（約275ns）はSLR版（110ns）よりやや重い。WhereClause -> ε の分岐処理（allNullable判定とEPSILON追加）が生成規則走査に加わるため。

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

slrone_table_generatorと同様、単体ベンチマークを素朴に

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

    l.BuildFirstSets()
}

という形で書くと、-benchmem併用時にStopTimer/StartTimerのたびにruntime.ReadMemStats()（ストップ・ザ・ワールド）が走り、b.Nが数百万回に達する高速なベンチマークでは計測不能なレベルまで遅くなる。そのため本パッケージでもbuildUpToヘルパー（lrone_table_generator_bench_test.go）で前段セットアップをb.N件ぶんタイマー計測開始前にまとめて用意し、計測ループでは対象メソッド呼び出しのみを行う形にしている。

---

7. 再現手順

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

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