パーサージェネレーターでも優れたエラーを生成できる。

Go言語開発者のラス・コックスが2010年に投稿した文章の翻訳。

• yacc のような構文生成器は構文エラーをうまく生成できないという迷信が広まっていた。

• しかしこの問題はクリントン・ジェフリーが2003年に解決していた問題であり、手書きでパーサーを書かなければ解決できない問題ではない。

• （bison）状態と入力トークンに一致する内容をテーブルから見つければ、単純な構文エラーより優れたエラーを使うことができる。

[lifthrasiir]

（以下、韓国の Rust Discord サーバーに書いた内容を整理しました。）

この記事の最大の問題は、では Go が今パーサジェネレータを使っているのか、という点です。使っていません。現在でもメインの Go パーサは手書きのままです。理由はよく分かりませんが、rsc がオーケーと言ったからといって、ほかの Go 開発者たちもオーケーだと考えたわけではない可能性が高いです。

Jeffrey のアイデアは、コンパイラで言えば peephole optimizer にたとえられます。機械語を吐き出す前に、直近で出力した機械語命令を固定個数だけ保持し（その window をのぞく peep hole だからこの名前です）、特定のパターンが見えたらその場で該当命令をより高速な命令に置き換えます。peephole optimizer は、ほかの一般的な最適化パスと並行して使える便利な仕組みですが、peephole optimizer だけでコンパイラが要求するあらゆる種類の最適化を行えるわけではありません。同様に、直近のトークンからエラーを生成するアプローチでは、すべての構文解析エラーをカバーすることはできません。しかも、これは別にパーサジェネレータでなくても準用できる独立したアプローチなので、このアプローチが存在するからといってパーサジェネレータの問題が解消すると主張するのは正しくありません。

個人的には、パーサジェネレータという概念自体が悪いのではなく、パーサジェネレータが「強いる」考え方に問題があると思っています。パーサを書くことになると、たとえば生成するにせよ手書きするにせよ left recursion と right recursion を考慮しなければならず、「自然な」文法をそのままコード化することはできません。しかし手書きならそれを承知のうえでそうしているわけですが、パーサジェネレータを使ったところで、LL/LR のような特定の構文解析アルゴリズムに縛られた「文法」の部分集合に合わせて書かなければならないのであれば、ジェネレータの利点は半減します。（GLR のようなアルゴリズムは多少余裕を持たせてくれますが、限界はあります。）現在、多くのプロダクションレベルの言語実装がパーサジェネレータを使っていない、あるいは時おり PEG のようにパーサジェネレータではあるものの、まったく 一般的なジェネレータの利点を取らないアプローチを使っているのには、それなりの理由があります。

[dynalloc]

パーサジェネレータが制約する文法に縛られたくなくてパーサジェネレータを使わないという点には共感しますが、だからといってパーサジェネレータがユーザーに特定の文法を強要していると主張するのはおかしいです。

パーサジェネレータは、線形時間パースという利点を持つLR文法のパーステーブル作成があまりにも難しいため、それを支援するために登場したのであって、パースが非決定的なcontext-sensitive文法や、いつ終わるかも分からない再帰的なパーサを生成することは、パーサジェネレータの研究者や開発者の関心対象ではないでしょう。

したがって、パーサジェネレータは非直感的なLR/LALR文法を盲信して押し付けるプログラムではなく、線形時間パースとそのためのパーステーブル作成という非常に難しい問題を解くための道具として、その役割を十分に果たしていると思います。

[lifthrasiir]

現実に存在するほぼすべての言語は LL(1) 文法を持っているため、LR パーサを使わなくても線形時間でのパースが可能です。（その言語で好まれる文法が LL(1) であるという意味ではありません。）したがって、線形時間パースのために LR パーサを使う必要があるが、パーステーブルの作成が難しいのでジェネレータが必要だ、という話は因果関係が逆になっています。また、パーステーブルを作る過程そのものは本質的に複雑ではありません（難しいのはアルゴリズムの証明です）。