字句解析と構文解析

字句解析と構文解析は、コンパイラのフロントエンドを構成し、ソーステキストをトークンに分割し、その文法構造を構文木として認識する。

Definition

字句解析は、入力文字をトークンにグループ化するフェーズであり、構文解析（パース）は、それらのトークンが文法に従って有効なプログラムを形成するかどうか、またどのように形成するかを決定し、構文木を生成するフェーズである。

Scope

このトピックでは、正規言語と有限オートマトンを用いて文字ストリームをトークンに変換する字句解析と、文脈自由文法に基づいてプログラムの句構造を認識する構文解析（パース）について扱う。これには、トップダウン（LL）およびボトムアップ（LR）パース、パーサジェネレータ、曖昧性とエラー回復、抽象構文木の構築が含まれる。

Core questions

• 正規言語と文脈自由言語は、プログラム構造を記述するためにどのように使用されるか？
• LLパースとLRパースのトレードオフは何か？
• 曖昧性やパースエラーはどのように検出され、処理されるか？
• トークンストリームから抽象構文木はどのように構築されるか？

Key theories

LRパース

クヌースが導入したLRパースは、線形時間でLR文法の広範なクラスを決定的にパースするボトムアップ手法であり、多くのパーサジェネレータの基礎を形成している。

一般的な文脈自由パース

アーリーのアルゴリズムは、曖昧なものを含む任意の文脈自由文法をパースし、限定された決定論的パーサでは不十分な場合に一般的な方法を提供する。

フロントエンドの正規言語と文脈自由言語の基礎

『ドラゴンブック』は、字句解析のための正規表現と有限オートマトン、構文解析のための文脈自由文法の使用を体系化しており、標準的なLLおよびLR構築アルゴリズムも含まれている。

Clinical relevance

字句解析と構文解析は、コンパイラだけでなく、インタプリタ、リンタ、フォーマッタ、IDE、データ形式プロセッサにとっても基盤となる。優れたエラー回復機能を備えた堅牢なパースは、あらゆる言語ツールにおける開発者の体験にとって不可欠である。

History

1950年代後半のチョムスキーの形式言語階層は、正規言語と文脈自由言語の理論を提供した。クヌースは1965年にLRパースを形式化し、アーリーは1970年に一般的な文脈自由アルゴリズムを提示した。yaccのようなパーサジェネレータはLRパースを実用的なものにし、その後の研究ではパース式文法やコンビネータベースのパーサが探求された。

Debates

生成されたパーサと手書きのパーサ

実務家の間では、簡潔で検証可能な形式文法からパーサジェネレータを使用することと、より多くのコードを要するものの、より良いエラーメッセージと制御を提供する手書きの再帰下降パーサを使用することについて議論がある。

Key figures

• Donald Knuth
• Jay Earley
• Alfred Aho
• Noam Chomsky

Seminal works

• knuth1965
• earley1970
• aho2006

Frequently asked questions

レキサーとパーサーの違いは何ですか？

レキサーは生文字を識別子や演算子などのトークンにグループ化し、パーサーはそれらのトークンを言語の文法に従って階層的な構文木に配置します。

LLパースとLRパースの違いは何ですか？

LLパーサーはトップダウンで動作し、入力プレフィックスからプロダクションを予測するのに対し、LRパーサーはボトムアップで動作し、認識された部分文字列を還元します。LRは厳密により広いクラスの文法を扱えますが、構築はより複雑です。