形式言語と構文解析

形式言語は、あるアルファベット上の有限文字列の集合です。文法は、その集合に含まれる 文字列を導出する生成規則を定義します。コンパイラーのフロントエンドはこのモデルを 使い、局所的なトークン認識と再帰的なプログラム構造を分離します。

Chomsky 階層 #

Chomsky 階層は、生成規則の制約によって文法を分類します。

1. Type 3 の 正規 文法は、有限オートマトンが認識する正規言語を記述します。正規表現と字句解析器がここで動作します。
2. Type 2 の 文脈自由 文法（CFG）は、各生成規則の左辺に非終端記号を 1 つだけ持ち、プッシュダウンオートマトンで認識されます。
3. Type 1 の 文脈依存 文法は、定義された開始記号の場合を除き、生成規則が文形式を短くしないよう制限します。
4. Type 0 の 無制限 文法には、同等の生成規則制約がありません。

対応する区切り記号は境界を示します。有限オートマトンは無制限のネスト深度を記憶できませんが、CFG は Group → '(' Group ')' Group | ε のような再帰を使用できます。

導出、構文木、曖昧性 #

導出は開始記号から終端記号へ生成規則を適用します。構文木は、その導出の階層構造を記録します。文字列に複数の構文木または同等の左端導出がある場合、文法は曖昧です。

Expr → Expr '-' Expr | number

入力 number - number - number には、その文法の下で競合するグループ化があります。左再帰の Expr → Expr '-' Term | Term などで結合性を文法に組み込むか、競合解決ポリシーを意図したものとしてパーサージェネレーターの優先順位宣言を使用します。生成される木が言語の意味論を直接表す必要がある場合は、文法構造を優先します。

トップダウン構文解析とボトムアップ構文解析 #

LL(\(k\)) パーサーは左から右へ読み、左端導出を構築し、限られた先読みから生成規則を選択します。再帰下降パーサーはこの方式を直接実装します。予測型文法では左再帰を除去し、判断地点で選択肢を区別できるようにする必要があります。

LR パーサーは左から右へ読み、トークンをシフトして認識済みハンドルを還元することで、右端導出の逆を構築します。LR 系パーサーは左再帰の式文法と、より広い決定性 CFG のクラスに対応しますが、パーサージェネレーターの競合は曖昧性または不十分に指定された優先順位ポリシーを示します。

フロントエンドの境界とエラー設計 #

字句解析器は文字を識別子、リテラル、演算子、ソース位置などのトークンにまとめます。パーサーは文法の生成規則に従ってそれらのトークンを消費し、構文木または意味アクションを生成します。コメント、エスケープ、数値表記などの字句上の関心事がネストや構造に影響しない場合は、生成規則から分離します。

エラーを文法インターフェイスの一部として設計します。字句解析器は無効な文字列を識別し、安全に先へ進まなければなりません。パーサーは予期しないトークンと位置を報告し、文末や閉じ中括弧など選択した区切り記号で同期します。回復規則は進行を保証しなければなりません。任意のトークンを受け入れるだけでは、後続のエラーを隠し、生成される木を損ないます。