はじめに

パーサジェネレータを作って構文解析について学ぶ中で、「違いの本質」が見えにくいと感じていました。数式が前面に出てくる専門的な記事は敷居が高く、かといって局所的な言葉だけで書かれた記事では全体の中の立ち位置が掴めず――と、なかなか自分に合う粒度の記事が見つかりませんでした。
本記事では、自作パーサやパーサジェネレータを作る中で得られた実感ベースの視点から、構文解析器の分類を整理してみます。

勉強中の身なので網羅的に把握できていないことはご承知おきください。

パーサジェネレータ・構文解析の分類

構文解析器を作るにあたって、現在の実装上の観点は

作りたい構文
文法のタイプ
構文解析の方向と比較方法
構文の選択論理

の4点があると感じました。構文解析器を実装する際の掴みとしてこれらそれぞれの分類と特徴を簡単ですが書いていこうと思います。

作りたい構文（目的から考える）

これは最終実装したいものが何かという観点で、次以降の分類でどの方式を採用すべきかを決定するための核となる部分です。
多くの場合、構文解析器を作りたい人は独自のプログラミング言語またはDSL（Domain-Specific Language、ドメイン特化言語：特定の用途に特化した構造的な言語）をつくる事を目指しているかと思いますが、さらに踏み込んで自然言語を解析する事を目論んでいる人や、逆にもっとシンプルにCSVやそれに近い平易な文法を読み込むことを目指している人もいるかと思います。

文法のタイプ（理論的背景）

チョムスキー階層と呼ばれる4種類の分類があります。

文法	特徴	表現記法の例	備考
正規文法	単純な羅列や繰り返し構造	/abc(d)+/	再帰表現不可、いわゆる正規表現
文脈自由文法	正規文法に加え、再帰的な表現に対応	A → B	左辺単項のみ、多くのプログラミング言語はここ
文脈依存文法	文脈自由文法に加え、左右の文脈に応じた変換が可能	B α C → B A C	左辺多項OK
（制約なし文法）	自然言語のより複雑な表現を取り扱う階層	-	汎用的表現なし

という4つで、下に行くほどなんでもできますが解析が複雑になり実現が難しくなります。
シンプルなCSVパーサ的なものであれば正規文法で足りる事が多く、プログラミング言語・DSLでは文脈自由文法（CFG：Context-Free Grammar）で十分なことがほとんどです。

構文解析の方向と比較方法（実装アプローチ）

これはいわゆるLLパーサ、LRパーサと言われる部分です。
フルネームで記載するとLLはLeft-to-right, Leftmost derivation、LRはLeft-to-right, Rightmost derivationです。
ここに先読みの深さを合わせてLL(0)、LL(1)、LL(k)、LL(*)、LR(0)、LR(1)などの実用面での分類が出てきます。（実用上LRの先読みはほとんどの場合1まで）
先読みとは、構文判定時に、次の文字（または単語）を先読み深さまで判断基準に加えることです。LL、LRの読み方と合わせて先読みの具体例は後述します。

LLとLRの違いは入力とルールの比較方法です。
ざっくり説明すると、

LL：入力を先頭（Left）から読み、ルール右辺を先頭（Left）から比べる
LR：入力を先頭（Left）から読み、ルール右辺を末尾（Right）から比べる

という違いになります。
LLは人間的な読み方で、文字を見たら辞書順に調べるような流れですので理解しやすい人が多いです。
LRは人間味の薄い読み方で「書かれているものはどうせいつか辞書にヒットする」事を前提にした読み方です。

どちらの読み方であっても「正しい文章」と「無限の先読み」を仮定すれば理論上は同じ言語を認識可能です。
ただし、実用的にはいくつかの大きな違いがあります。

まず、LLに関しては左再帰で構造的問題を抱えているため、LLパーサを作る際は左再帰の記述を諦めるか、左再帰をループに変換する処理を別途作る必要があります。
左再帰に特別な処理を加えない場合、1単語目を消費できないまま再帰関数を掘り進めていくことになるため、プログラムがスタックオーバーフローを起こします。

また、LR系では（LLと異なり）1単語の先読みでうまくいくパターンが多いです。
不勉強のため数理的な説明をできませんが、直感的にはLR系はスタックに読み込みの履歴を保存し、これらが一致するタイミングだけに先読みを確認すればいいのに対して、LL系では一致する候補がいくつもある中で先読みを続ける必要があるため・・みたいな感じです。

そしてLRは解析にかかる計算コストを圧縮する秘策を持っています。
LRは（先読み範囲内に衝突がない構文に限り）読み込んだ単語のパターンを定型に落とし込めるため、事前に処理パターンの表を作成し、計算時間を短縮できるようです。（自分で実装していないためよく知らない）

以上を踏まえ、高速で堅実な実装をするという事であればLRを選択することが多くなります。
一方、LLの利点は（左再帰を除いた部分の）実装が非常に人間的で分かりやすく、シンプルなキャッシュ機能を付ける事で小規模・中規模な用途において十分な能力を出せるため、初学者でもある程度のスピード感でそれなりに動くものを実装することができます。

LLとLRの読み込み手順例

日本語は（単語の区切りが分かりづらく）構文解析と相性が悪いので、一旦英語の辞書をイメージします。
（文頭の大文字小文字や三単現はここでは気にしない事として）you love meという文と、これを規定するルールとして
文 → ((S V) | (S V C) | (S V O) | (S V O O) | (S V O C))
S → "I" | "you" | "he" | "she"
V → "like" | "love" | "hate"
O → "me" | "you" | "him" | "her"
があるとします。

LLでは入力の1単語目(you)を見て、S（"I" | "you" | "he" | "she"のいずれか）に該当するかを調べます。
(この時点でSV, SVC,...のどのSかは分かりませんが）Sは一致してOKなので、2単語目以降も同様に実行し、最終的に全入力が「文(S V O)」のルールに合致したと分かります。
S Vの時点で一度、完全一致したように見えてしまうが、先読みを使うとyou loveの先が存在するのに対し、S V形の先が空であると分かるので、（先読みを使えば）S Vにはヒットしないです。

LRでは1単語目を見て、文の末尾のルールであるVまたはCまたはOと一致するかを調べます。
今回はたまたまyouなのでOと一致します。ここで念のため次の入力単語（love）とルールのOの先（空）を確認してみると明らかに一致しないので、youは何にも一致しなかったとします。
しかし~~人間が間違った文を書くはずはないので~~いつか一致するはずと期待しながら1単語目をスタックし、2単語目(love)を読み取ります。この2単語の配列を改めてルールと比較します。
今度の比較はyou loveの2単語を
S V
V C
V O
O O
O C
の5パターンで比較します。
やはり2単語だけで比べるとS Vに一致しているように見えますが、先読みをするとmeと空が不一致なので、棄却します。
さらに次の単語(me)を読み込みます。
するとどうでしょう、無事に「you love me」は「S V O」のルールと一致し、先読みも空と空で一致しています。
（やはり人間は間違っていなかったようです）

構文の選択論理（曖昧さとの向き合い方）

チョムスキー階層の話とも絡みますが、CFGは本来的に意味論を規定しない都合、複数の構文木を許容します。例えば
Expr → Expr "+" Expr | "a"
という構文定義はa+a+aという文字列を((a+a)+a)とも(a+(a+a))とも解釈することができます。
一方で実際のパーサはなにかしらの選択ロジック（最長マッチやファーストマッチ）でそれを一意に決定することが多いです。
ツールによってはEarley法というアルゴリズムを採用し、CFGによって発生するすべての構文木を保持できるものもあります。
これがあると自分の定義した構文にどのていどの曖昧性があるかを検証できます。
全探索を行うので代わりに計算量は（最悪ケースでn^3まで）増えますが、検証としてならばその時間をかける価値はあります。
用途に応じてファーストマッチ（速度重視）、最長マッチ（曖昧性と速度のバランス）、全保持（曖昧性の許容・デバッグ）を選択する事になります。

PEGという分類について

新しい（この20年くらいの？）パーサジェネレータを見ていると、PEGベースみたいなものをよく見かけます。¹
PEGについて補足すると、BNFでは|で記述していたOR表記を/と表記し、この記法において取りうる構文木は（最初にマッチした）1つに定まる、というものです。

このPEGについて調べているとPEGは文脈自由文法とは異なり～みたいな記述を見る事が多いです。Wikipediaにもそう読めるような書き方がされています。
この書かれ方には混乱する人も多いと思います。実際、ぼくはかなり混乱しました。

このため、文脈自由文法とは異なり、PEGには曖昧さは存在しない。文字列を構文解析する場合、正しい構文木は常に1つしかない。このためPEGはコンピュータ言語の構文解析に向いており、

PEGは文脈自由文法（CFG）ではないのか？

チョムスキー階層の話はあくまで生成文法としての機能の話であり、意味を解釈する責務は構文解析（チョムスキー階層の責務）の後にあるそうです。（日本語ソース見つけられず、英語ソース²読めないので真偽不明）

一方、PEGは先に一部説明したようにその記法自体が（LLパーサで）ファーストマッチに確定されます。このため『意味を含めない』ことができず、チョムスキー階層の議論とは別の枠組みになります。
（そこまで踏まえた上でそれでもチョムスキー階層の議論に加えるならば、表現能力として正規文法と文脈依存文法の間にあるので、文脈自由文法だとは思います）

PEGという単語が頻出する背景

ここまでで説明したことを踏まえるとPEGはパーサジェネレータが求められる多くの局面（プログラミング言語やDSLの設計）で、その設計方針を受け容れやすい作りとなっています。
このためPEG式のパーサジェネレータが一勢力として成立していると推測しますが、一方で分類的な立場から見ると既存の枠組みで捉えづらい存在となっていて、結果としてPEGという単語そのものが1つの分類となっているように思います。

おわりに

最初はかなりとっ散らかった本当に乱文なポエムを書いていたのですが、ChatGPTに甘えって言われてムカついたので自分なりにけっこう真面目に調べたり分類してみたりしてみました。
あとチョムスキー階層が意味論を含まない話のソースを自力（日本語）で見つけられないままChatGPTにPEGはCFGじゃねーよって言われまくったので、CFGじゃないならPEGは正規文法並か文脈依存並の能力かよって喧嘩しました。あいつ日本語喋る癖に日本語じゃないソースばっかり引っ張ってくるの反則だよ。
数理的な部分（計算量やオートマトン的な話）は結局少しも手を出さなかったので、そこに起因する話はかなり弱いですが、個人用途で構文解析器を作るうえで（それらを知らなくても過去に何度も構文解析器やパーサジェネレータを作れているし、個人ユースの範囲で速度に困ったことがないので）そこまで踏み込む必要性はないんじゃないか、というのが正直な感想です。
こういうふわっとしつつ全体を舐めるような記事を見た記憶がないので、真面目にまとめておこうと思った次第でした。
嘘や誤解があれば指摘お願いします。

PEG.jsやpestなど ↩
ChatGPTに紹介された英語ソース1, 2, 3 ↩