はじめに

この数年、定期的にパーサジェネレータを作っているのですが、未だによそで書かれているパーサジェネレータの話をほとんど理解できずに苦しんでいました。（そのせいでパーサジェネレータを作る羽目になっていると言える）
今回、自分の中でかなり満足度の高いパーサジェネレータを作ることができたので、それを公開しつつ、

自分がパーサジェネレータをどう理解していたのか
どうして世の中のパーサジェネレータの話を理解できなかったのか
自分が作っているパーサジェネレータと既存のパーサジェネレータの違いは何か

みたいなところを整理しようと思い記事を書きました。
ただし、パーサジェネレータの製作にあたっての学習はすべて独学のため、一般論や歴史観の記述はすべてぼくの主観に基づいた非客観的な記述である事にご注意願います。

この話題ではBNF（またはそれをベースにした拡張）記法やその問題を特に説明なく使用します。参考になりそうなページを載せておきます。
バッカス・ナウア記法（BNF）の書き方をわかりやすく学ぶ
 Wikipedia

そもそもパーサジェネレータとはなんぞや

この記事に興味をもって読んでくれている人には意味のない話の可能性も高いですが、抽象的な認識としてパーサジェネレータは構文解析器の一種で構文解析器を作る構文解析器だと認識しています。（誰も教えてくれる人がいないのでパーサジェネレータって言葉自体、そういうものを作り始めてしばらくしてから知った）
自分のパーサジェネレータに対する認識・理解はついさっきまでここで止まっていました。
これがあると何が嬉しいって、構文解析器を作る細々した煩わしさがほとんどなくなり、テキストベースで構文定義をして、その意味を実装するだけで構文解析器が完成するので最高に幸せです。1個の構文解析器を手書きすると煩わしい部分ってけっこうあるので。
（構文解析器という括りでみると10年近くなにかしらやっている気がする。どうして独学なのか・・）

自分の理解しているパーサジェネレータの要件と実際のそれとの齟齬

自分の認識は前述のとおり、「構文解析器を作る構文解析器」で「テキストベースで構文定義をして、その意味を実装するだけ」のものなのですよね。
これはふわっふわな抽象的なレベルで見たときに恐らく間違っていないと思います。
ただ、より実装的な面から見たときに若干の嘘を孕んでいます。
構文を解析するだけならば構文定義だけでいいですし、意味を定義するだけならば意味定義だけでいいのですが、構文と意味を紐づけるにはトークン（終端記号）の概念を導入する必要があります。
ここでいうトークンとは意味解析上の最小単位です。

構文定義上の最小単位と意味定義上の最小単位

構文定義（？）上の最小単位は1文字です。では意味定義上の最小単位は同じでしょうか？答えは当然Noです。
数値であれば前後に数値以外が現れるまでが「意味としての最小単位」ですし、代入は「=」が最小単位であるのに対して比較では「==」や「===」が意味としての最小単位になります。
では、構文定義上1文字まで突き進んでしまうトークンを誰が意味上の最小単位で押しとめるのか？という情報を補完する必要があるわけです。
このやり方はパーサジェネレータによって違うようですが、どうやら現在世にあるの構文解析器というのは細分化すると最大で字句解析＋構文解析＋意味解析の3要素を持っていて、この役割をどこで分割するか（あるいはしないか）というのが各パーサジェネレータの設計の肝になっているようです。
Yaccは見ていると字句解析+(構文解析+意味解析)っぽく見えますし、PEGは(字句解析+構文解析)＋意味解析っぽく見えます。
恐らく、歴史的には字句解析と構文解析の間で分ける方が計算資源的な問題で簡単なのだと思います。単語を保証された構文解析は直感的にもやりやすそうに感じます。反面、人間の理解の単位としては字句解析と構文解析の方がよりニアリーで、意味解析は構文解析から一歩離れた部分にあるように感じます。

ここから先、ぼくの言う構文定義は特に言及のない限り字句解析を含み、意味解析を含まないものとして読むようお願いします。
（よその説明を読むときはこの境界線を意識して眺めるべきだと思います）

最小単位の差の吸収

さて、解析段階によって最小単位に違いが必要な事は分かりましたが、構文定義記法である標準的なBNFにこれを表現する能力はありません。

シンプルな加算のBNF(拡張記法)

ADD -> ADD  '+'  NUMBER | NUMBER 
NUMBER -> white ('0' | nonZero digit*) white
digit -> '0-9'
white -> ' ' | '\t' | e
e -> ""

ありませんが、僕の目から見るとわりとありそうに見えました。というか「ほぼ知ってるだろバカ、こんなんどう見てもNUMBERが最小単位じゃん」とアホなぼくは思ったのです。
この認識が不幸の始まりでした。ここまでの情報をこの順序に知っていたならば「最小単位の差を吸収する記述が必要である」という認識を持てたと思うのですが、自分はBNFを用いない方法でパーサジェネレータ（当時はその呼び方すら知らない）を作っている中で、もう少し自分に使いやすいパーサジェネレータが欲しいと思ってからBNFを知ったので、BNFがそんな質素なものだと知らなかったのです。
BNFを知る前に作っていたパーサジェネレータは、演算子の優先度や結合方向、項数ベースに構文解析器を生成するもので、これを2回くらい作って（この方向性は改造をするときに筋が悪いな）と思っていたので、構文定義をできる記法に求めるハードルが上ってしまっていました。

BNFに求めるハードルが高いので、既存のパーサジェネレータを見ても意味が分からないわけです。「どうしてそこで意味の分からない定義（意味解析上の最小単位定義ファイル）が出てくるんだ・・・」と苦しみます。バカですね。
そして至ったのが「BNFベースのパーサジェネレータを自分で作った方がいいや」というアホな結論です。
ちなみにPEGはこの視点で言うと非常に分かりやすいのですが、まず当初なぜかYaccやBisonばかりが目に付いて気付けなかったのに加え、後にPEG.jsのサンプルを見つけたとき（意味定義の名前空間が分からん）とか（構文解析器のソースコードを吐き出すとかまわりくどい）とかいくつかの理由をもって棄却されました。

パーサジェネレータを自作するにあたって幾度となく字句解析という言葉が出てきたのですが、それが構文定義と分離された全く別の存在であるという認識を持ったのがさっきChatGPTにこの記事を書くための認識合わせをしている最中でした。アホすぎた。BNFベースの構文解析っていうだけでももう1年半前から2、3回取り組んでいるのに・・。トークンてなんだろうってずっと思いながらパーサジェネレータ作ってるバカ。

自作パーサジェネレータ（RuleForger）について

さて、ここまでで「どうしてパーサジェネレータなんて既にありふれているのに新しい自作パーサジェネレータなんて作ったの？」という理由は分かったと思います。ぼくがアホで人の説明を読み込まず受け入れず理解できないバカだからです。
とはいえ、ここまで理解できなかった原因は「BNFが意味解析上の最小単位を表現しうる」という直感的な確信と「人類はもっと人間に読みやすい、作りやすいパーサジェネレータを製作できる」という思い込みがあったからなので、自分がアホだったおかげでこれを作る熱意になったような気はします。

RuleForgerの特徴

githubのReadmeに書いているのでここまできて詳述するような事はないのですが、いくつか列挙していきます。

準備物が少ない

RuleForgerで構文解析器を作るために用意するものは

構文の記述（BNF的記法による生テキスト）
意味の記述（生のjavascript）
実行されるべきコード（ユーザー定義に従う生テキスト）

の3点だけです。実行にあたって中間ファイルも生成されません。意味実装の名前空間は明らかに生のjavascript空間に依存します。
字句解析的な要素を定義する必要がない！嬉しい！！

左再帰を解決できる

特に触れてこなかったですが（特にトップダウン式の）構文解析において左再帰表現で無限再帰に陥る問題があります。が、これは解消しています。
具体的な実装は単にBNF読み込み時にTarjanアルゴリズムで（左再帰の）ループチェックをして、ループを検出したらループ入り口に対して再帰探索をループ探索に置き換えているだけなので、LR文法に対応しているわけではないですが。
ところでLR文法ってトークン定義の省略できるんですか？（勉強足りなさすぎてLR文法の骨子を理解していない。LLとLRという名称も先週くらいに知ったアホ。構文解析？そんなん前から読むに決まってるだろ！って思ってた）
左再帰を書けるからなんでも構文解析できる！嬉しい！！
（左再帰のnullabeな要素は解析不能だけどそんなギルティな要素は定義しないでください）

ドット記法によるOR表現とAnchorによる構文定義と意味定義の紐付け

これは多分ほかにないユニークな機能だと思っているのがドット記法によるOR表現です。
パーサジェネレータを作るときスタートにあったのが、
構文定義を足す度に少なくとも定義する1行、それを呼び出す右辺側の追記、その意味を定義する箇所の3か所の更新が必須になるのアホじゃないか？
という思いだったので、これを解消する方法としてドット記法によるOR表現と、トークンに別名（Anchor）を与え、いくつかのルールの意味定義を共通化しやすいようにしました。
更新箇所が減った！嬉しい！！
（AnchorはPEGのラベルとだいたい同じ。こちらは|で記述したOR要素の意味定義をAnchor経由で共通化できるので、それは多分差別化されている。分からなさすぎて他のパーサジェネレータを1個も触れたことないから本当は知らないですが）

製作上の小話的な

ここから先はただ生成AIってすごいなって話です。
RuleForgerを作るにあたって、コアとなる部分の大半は（過去数回積み重ねてきたゴミのようなパーサジェネレータの知識を基に）骨子が見えていたのでわりとすぐできたのですが、左再帰にまつわる問題やAnchor廻りなど、過去に自作したパーサジェネレータでは諦めていたり雑な実装で済ませていた部分に関してはかなり苦労しました。

特に左再帰は実装を進めるたびに、既に実装が終わったつもりになっていたAnchor部分やそれを参照するEvaluatorに悪影響を与え、ASTがフラットになったり無限再帰が再発生したりしていました。
コード自体がその時点で2000行くらいになっていたので無料のChatGPTに食わせても最初の文字列食べる部分とか抽象クラスだけを読み込んで解析を諦められていたので、コード全文を網羅してもらうのは難しかったですが、それでも抽象的なぼくの理解と説明に対して、想定されるミスケースをいくつも上げてくれて、頭の整理が非常にはかどりました。
（バグ取り、という点でジャストな回答は得られなかったですが、ChatGPTの言う方向性の説明は明確な分、その方向性ではバグっていなさそう、という当たりは付けられました）

また、左再帰解決の方法論は結局すべてChatGPTの提案通りでした。
ループ検知するためのアルゴリズムは、当初の自分の認識だと最短経路探索で最小ループを全て見つけ、その中から意味合いとして価値のあるループを選択し、重複箇所に対策を仕込むことが必要だと認識していました。
しかし、ChatGPTに最大ループを見つけてあげれば十分で、最大ループであればASTを1週するだけで見つけられると教えてもらい、実際最大ループ1個であってもループ入り口に対策を仕込めば十分である事に気付かされました。
左再帰の本質的な解決についても、要素毎の細かなロジックはぼくの書いたコードに依存する部分があるのでChatGPTには閃かない部分も多かったですが、大枠の管理ロジックはChatGPTがいなかったらぼくの知力でここまで手早く実装できていなかったと思います。（左再帰以外の部分が平日土日合わせて1週間弱、左再帰の部分がGW＋土日くらい）

また、Githubにあげるにあたってプロジェクト名（RuleForger）の相談とかReadmeの相談とか、そういう動作に影響しないけれど悩みたくなる名前・文章にまつわる部分の相談は非常にやりやすく捗りました。
英語は苦手ですが書いてある意味を辞書から雰囲気を拾うくらいはできるので、エラーメッセージやReadmeの英語訳はほぼ全部ChatGPT丸投げしました。

実際に動く部分にAIは一切かかわっていませんが、こういう関わり方で他者を使った場合、（特に人間だった場合）どういう形で当事者の権利を保護するんでしょうか。考えたくないですね。