投稿にあたって
先週ほぼ同じ内容の記事を投稿して、ちょっと字句解析にもLRパーサにも不勉強な状態だったのですぐ削除したのですが、若干修正をして再投稿になります。
当初は「字句解析の段階を設けない方が、構文定義の変更を自由にできて楽だし字句定義なしいいだろ」というのがぼくの立場で、この本文の大半はそのスタンスで書いたままのものです。
はじめに
パーサジェネレータや構文解析の話を書いているのに字句解析の話にほとんど触れていませんでした。
自作パーサジェネレータでは字句解析（トークンの定義）を構文解析に含めて処理できる設計にしています。
これは、試験的に構文をいじる場面で「なんか変更箇所が多くて面倒だ」と感じたことがきっかけです。
そのため、これまで字句解析について意図的に触れてこなかったのですが、本来構文解析とは切っても切り離せない重要なフェーズです。
今回はその「字句解析」について、自分の整理を兼ねて書いてみます。
字句解析とは
字句解析とは、文字列から「意味のある単位（トークン）」を切り出す処理のことです。
多くの構文解析器（たとえば Yacc や Bison）は、文字列そのものではなく「トークン列」を入力として受け取ります。
たとえば if や =、変数名や数値などを「区別された単語」として扱うことで、構文解析器がより簡潔に、かつ高速に文法の解析を行えるようになります。
構文解析と字句解析のやることは一見似て見えますが、大きく異なるのは「予約語を正確に分類し、変数名として使わせない」「空白やコメントのような構文解析上意味のない文字の隠蔽」などの責任が字句解析側にあることです。
字句解析を行う利点
1. 曖昧性の除去による高速化
構文解析の段階で曖昧さが除去されていれば、必要な先読みの回数が減り、結果として解析処理が高速になります。
これは特にLRパーサのように構文解析表を用いる方式で効果が大きく、字句解析 + 構文解析で全体を O(n) に抑えることが可能です。
2. 予約語による曖昧性の抑制
字句解析では「if」や「for」などの予約語をあらかじめ分類しておくことで、構文解析での判別が単純になります。
その副次効果として、「変数名として 'if' を使えない」という制約がかかりますが、むしろ可読性の面でそれが好まれるケースも多いです。
3. 構文解析時点での空文字の除去
字句解析器は文字列をトークンに変換し、必要なものだけをスタックに積むことができます。
トークンに対して事前に除去可能かどうかをラベル付けしておけば、最初からスタックに積まない事ができるため、構文解析側は空白文字を構文定義に書く必要がなくなります。
空白文字を構文定義時点で組み込まないで済むのは記述量が減る、可読性が上がるという2点で非常に大きな利点です。
利用者（コンパイラユーザー）視点では字句解析があることで得られるメリットは多く、目に見えるデメリットは少ないと言えるかもしれません。
字句解析のデメリット
字句解析のデメリットは構文を定義する側が負う作業の手間です。
構文定義と字句定義はぱっと見で何が違うのかって思う程度にやりたい事はほとんど同じですが、字句解析をするためには必ず予約語を洗い出す必要があります。
また、C言語の * のように、出現位置によって「ポインタ演算子」か「乗算演算子」かが変わる要素もあります。こういったケースでは、字句解析と構文解析で協調して判断する必要があり、最終的な判断を構文解析側で行う事になります。
これは試験的に言語を色々と改良したいという要求に対して、変更箇所が複数個所に渡るため追従性が悪く、かなり面倒くさく嫌になる要素です。
空白文字の記述が減るという利点とのトレードオフとはなりますが、空白文字は「とりあえず構文定義の各所に空白を受け入れるような記述をしておけば動作する」のに対し、予約語の検討は「それなりに神経質に分類をしないといけない」面倒くささがあり、字句解析を敢えて使わない方が試作的な立場としては作業がしやすいように感じています。
字句解析を省略した場合の工夫と限界
キャッシュ利用 vs 構文解析表
字句解析を噛ませて構文解析表を使う事で計算量を減らせると書きましたが、実のところ構文解析表を使わずとも理想的には計算量を減らせます。
それは解析結果のキャッシュを作る方法です。
前述したように曖昧さを除去するときは先読みを行い、そのために先行してtest関数が走るわけですが、この先読み結果を全部覚えておけば、2度目以降(=parse時に)test関数はまともに走らないので、計算量は線形になる見込みです。
とはいえキャッシュを使う方法は、入力文字長がキャッシュに収まる程度という前提があり、構文定義と実際のコードではコードの方が長いと考えられるため、事前に構文解析表を作るより期待されるメモリ効率は悪いですし、構文の選択論理により計算量の傾きは悪化します。
また実装上の問題として、構文解析表による実装はLR(1)（正確にはLALR(1)）でないと実用的でないのに対し、キャッシュによる方式はLL(*)でないと実用的ではありません。
LLとLRパーサの特性の違い
LR(1)とLL(*)では解析可能な範囲に差があるため、LL(*)の試験で上手くできたからLR(1)にそのまま落とし込めるか、と言うとそうでもありません。
さらに、LLパーサは左再帰を解決する事が難しい（面倒くさい）という問題も抱えています。
特徴を改めて整理すると以下のような感じです。
| 手法 | パーサ | 長所 | 短所 |
|---|---|---|---|
| キャッシュ | LL(*) | 実装が簡単、順次処理 | メモリ消費大、左再帰解決が難しい |
| 構文解析表 | LR(1)、LALR | 高速・安定 | 解析表の実装が必要、字句定義が必要 |
結論
絶対にどっちか、という結論をぼくは出せていません。
現状でどういう方針を採用するべきか、という点で言うと
- 正式で正確な保守が目標 → 字句解析を分離した方がいい
- 試験的な実装や閉じた環境でのスピーディな展開が目標 → 字句解析と構文解析を統合した方がやりやすいように感じる
という回答になります。
字句解析は「確実・安定な性能の提供」「曖昧性除去の責任分離」と言った点で非常に重要です。
これは多くの人が使うシステムにおいて無視できない要素です。
実際に複数のパーサ実装が存在するような環境では、字句解析の設計次第で解析結果が揺らぎます。
そのため言語仕様の段階で字句解析を定義しておかないと、解析エンジンごとに動作が異なる事態を招きかねません。
おわりに
この記事を前に一度投稿してから、結論を自分の中で反芻し、自分のパーサジェネレータを眺め、最終的にLRパーサに切り替えるとき地獄だなと思いました。そこで自作ジェネレータにLRパーサとの選択機能を付けよう、と思い立ち実装方法を調べて色々と下準備をしていました。
高速なLRパーサを実現するためには字句解析は必須となりますが、そもそも字句定義と構文定義をまとめて一括で定義するのが面倒くさいと思ったのが発端だったのに、LRパーサをいきなり実装したら元の木阿弥だと気づきました。
そこで、現状のLL(*)パーサに字句解析を注入する事にしました。
今回のアプローチの面白い（変な？）ところは、字句解析を行うフェーズがあくまで構文解析の中に含まれていることです。
字句解析がなくとも実行できる事を前提にしているため、字句解析を最初に行う事ができなかった、とも言えます。
結果として、字句定義をすればトークンの左側の空白は構文定義上の記述が不要になる恩恵は受けられるようになりました。
実装が実装なので高速化には一切貢献していないどころか解析の階層が増えたので推定若干遅くなったはずですが・・。
最終的に、LRパーサに以降可能な状態か（すべてがトークナイズされているか）を判断して自動でLL(*)パーサかLR(1)パーサかを選択するようなツールを目指そうと考えています。
ちなみに前は「字句解析と構文解析、統合しちゃダメ？と思ってやってみた話」というちょっとキャッチーなタイトルにした結果、直前2回の構文解析に関する記事と比べて数倍のアクセス数が来て怖くなったのでもう少し堅実なタイトルにしました。（生成AIにキャッチ―なタイトル考えてもらった結果うまく行ったのに怖くなるアホ）