グラフ構造としての文法
コンパイラは構文解析木を構築してソースコードを翻訳します — 各ノードが適用された文法規則を表し、各葉が終端記号(変数名、リテラル、演算子)を表す根付き木です。
木の幾何学
n個のノードとn−1本のエッジを持つ木。深さd: ルートから任意の葉までの最大距離。深さdのバランスの取れた二分木: 最大2^dの葉と2^(d+1)−1の合計ノード。
一般的な式の構文解析木はバランスが取れていません: 演算子の優先順位は右に偏った木または左に偏った木を作成します。A + B Cはが+より深い木を生成し、*がより強く結合することを符号化します。
BNFとALGOL
バッカス・ナウア記法(BNF)はALGOLを指定するために発明され、文法を生成規則として形式化します:
``
<expr> ::= <term> | <expr> + <term>
<term> ::= <factor> | <term> * <factor>
<factor> ::= id | (<expr>)
``
各生成規則は木の1つのレベルを定義します。文法は非終端記号上の有向グラフです。文を解析することは、開始記号から葉までそのグラフのパスをたどることです。
構文解析木の深さと式の複雑性
式(A + B) * (C + D)について、構文解析木は標準的な演算子の優先順位の下で特定の構造を持ちます。
構文解析木の深さはコンパイラのパフォーマンスに影響します: より深い木は再帰的下降解析中により多くのスタックフレームが必要です。
シャノン熵と冗長性
ハミングは、話言葉は約60%冗長で、書き言葉は約40%冗長であることに気づきました。これは正確な情報理論的な意味を持ちます。
シャノン熵
確率{p₁、p₂、...、pₙ}でアルファベットAからシンボルを生成するソースについて:
H = −Σ pᵢ log₂(pᵢ) (ビット/シンボル)
最大熵: 均等分布(すべてのシンボルが等しく起こりうる)。H_max = n個のシンボルに対するlog₂(n)。
冗長性R: 情報を伝えないビットの割合(コンテンツを失わずに削除可能):
R = 1 − H / H_max
R = 0.4(40%冗長)の場合: ビットの40%はコンテキストから予測できます。8ビット/文字でEnglishテキストを伝えるチャネルは、その容量の60%のみを情報に使用しています。40%は受信者が既に知っている構造です。
エラー検出は冗長性を使用します: ビットの40%が予測可能な場合、送信エラーは冗長性構造に違反するシーケンスを生成する可能性があります — エラー訂正コードがなくても検出可能です。
APLのほぼゼロ冗長性: 1文字の変更はコンテキストからだけではほぼ検出できません。Englishの60%冗長性: 文字が欠落または間違っている場合でも、周囲のコンテキストから単語を再構築できることが多いです。
冗長性の計算
英語の文字頻度(概算): 'e'は約12.7%の確率で現れます。'z'は約0.07%現れます。Englishの実際の熵は約H ≈ 1.0ビット/文字です(単語レベルのコンテキストを考慮)。26文字アルファベットの最大熵: H_max = log₂(26) ≈ 4.70ビット/文字。
幾何学としての成長曲線
コンパイラアルゴリズムはサイズnのプログラムを処理します(トークン、行、またはノード)。アルゴリズムの選択は、コンパイル時間がプログラムサイズとどのようにスケーリングするかを決定します。
一般的な複雑性クラス
| クラス | 実行時間 | 例 | |---|---|---| | O(n) | 線形 | 字句解析 | | O(n log n) | 準線形 | 最適ソート | | O(n²) | 二次 | 単純な重複検出 | | O(n³) | 三次 | 行列乗算、CYK解析 | | O(2ⁿ) | 指数 | 素朴な定理証明 |
幾何学的な図: 実行時間対nをプロット。O(n)は線です。O(n²)は放物線です。O(2ⁿ)は指数曲線で、n=0の近くで平らに見え、n=50の近くでほぼ垂直です。
一般的な文脈自由文法の解析(CYKアルゴリズム)はO(n³)で実行されます。ほとんどの実用的なプログラミング言語では、文法はLR(1)解析可能に設計されており、O(n)解析が可能になります。ALGOLの文法はFORTRANのものより複雑で、遅いコンパイラにつながりました — 1958年にコンパイルに数時間かかったことが重要な実用的な摩擦。
交差点
単純なシンボルテーブルルックアップは、n個の識別子を持つプログラムのO(n²)の総操作を使用します(n個のルックアップのそれぞれについて線形スキャン)。ハッシュテーブルシンボルテーブルはO(n)の予想される総操作を使用します。
仮定: O(n²)アルゴリズムは1958年ハードウェアで10⁶操作/秒で実行されます。O(n)アルゴリズムは同じ速度で実行されますが、100n個のセットアップ操作(ハッシュテーブル構築)が必要です。