文法作为图结构
编译器通过构建解析树来翻译源代码——一棵有根树，其中每个节点代表所应用的文法规则，每个叶子代表一个终端符号(变量名、字面值、运算符)。
树的几何
具有n个节点和n−1条边的树。深度d：从根到任何叶子的最大距离。对于深度为d的平衡二叉树：最多2^d个叶子和2^(d+1)−1个总节点。
典型表达式的解析树不是平衡的：运算符优先级创建右倾斜或左倾斜的树。A + B C产生一棵树，其中比+更深，编码*的绑定更紧密。
BNF与ALGOL
Backus-Naur Form (BNF)为指定ALGOL而发明，将文法形式化为生产规则：
``
<expr> ::= <term> | <expr> + <term>
<term> ::= <factor> | <term> * <factor>
<factor> ::= id | (<expr>)
``
每个生产规则定义树的一个级别。文法是非终端符号上的有向图；解析一个句子通过该图从起始符号追踪一条路径到叶子。
解析树深度与表达式复杂性
对于表达式(A + B) * (C + D)，解析树在标准运算符优先级下具有特定结构。
解析树的深度影响编译器性能：在递归下降解析期间，更深的树需要更多的栈帧。
Shannon熵与冗余
Hamming注意到口语约60%冗余，书面语言约40%。这具有精确的信息论含义。
Shannon熵
对于从字母表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个设置操作(哈希表构造)。