文法作為圖結構
編譯器通過構建分析樹來轉譯原始程式碼——一棵有根樹，其中每個節點代表應用的文法規則，每個葉子代表終端符號（變數名稱、字面值、運算子）。
樹的幾何學
具有 n 個節點與 n−1 條邊的樹。深度 d：從根到任何葉子的最大距離。對於深度為 d 的平衡二元樹：最多 2^d 個葉子與 2^(d+1)−1 個總節點。
典型表達式的分析樹不是平衡的：運算子優先級創建右偏或左偏樹。A + B C 產生一棵樹，其中 比 + 更深，編碼 * 結合得更緊密。
BNF 與 ALGOL
為指定 ALGOL 而發明的 Backus-Naur 形式 (BNF) 將文法形式化為生成規則：
``
<expr> ::= <term> | <expr> + <term>
<term> ::= <factor> | <term> * <factor>
<factor> ::= id | (<expr>)
``
每條生成規則定義樹的一個層級。文法是非終端符號上的有向圖；分析句子會沿著該圖從開始符號到葉子追踪路徑。
分析樹深度與表達式複雜性
對於表達式 (A + B) * (C + D)，分析樹在標準運算子優先級下具有特定的結構。
分析樹的深度影響編譯器性能：在遞歸下降分析期間，更深的樹需要更多的堆疊框架。
香農熵與冗餘
漢明注意到口語約 60% 冗餘，書面語言約 40%。這有精確的資訊理論含義。
香農熵
對於從字母表 A 生成符號的來源，概率為 {p₁, p₂, ..., pₙ}：
H = −Σ pᵢ log₂(pᵢ) (每個符號的位元數)
最大熵：均勻分佈（所有符號等可能）。n 個符號時 H_max = log₂(n)。
冗餘 R：不攜帶資訊的位元比例（可以移除而不失去內容）：
R = 1 − H / H_max
如果 R = 0.4（40% 冗餘）：40% 的位元可以從上下文預測。以每字符 8 位元傳輸英文文本的通道僅使用其信息容量的 60%；40% 是接收者已知的結構。
錯誤檢測使用冗餘：如果 40% 的位元是可預測的，傳輸錯誤可能產生違反冗餘結構的序列——即使沒有錯誤更正代碼也可以檢測到。
APL 的近乎零冗餘：單個字符更改幾乎從不從上下文單獨檢測到。英文的 60% 冗餘：即使缺少或錯誤的字母，你也可以經常從周圍上下文重建一個詞。
計算冗餘
英文字母頻率（約）：'e' 出現約 12.7% 的時間；'z' 出現約 0.07%。英文的實際熵約為 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 設置操作（哈希表構造）。