引言前两篇博客我们了解了编译器是什么、以及编译器内部的六大阶段。本篇将覆盖第1章剩余的四节内容这些内容构成了学习编译原理的背景知识。主要包括三大主题编程语言的发展历史及其对编译技术的影响 (1.3)编译器设计的科学方法与编译技术的广泛应用 (1.4-1.5)程序设计语言的核心概念——这是编写编译器之前必须透彻理解的基础 (1.6)其中第三部分最为重要我会重点展开。一、编程语言的发展简史 (1.3)1.1 从机器码到高级语言编程语言的发展可以按代来划分1.2 语言的分类维度同一种语言往往属于多个分类分类标准类别特征代表语言计算模型命令式 (Imperative)通过语句改变程序状态C, Java, Python声明式 (Declarative)描述做什么而非怎么做SQL, Prolog, Haskell计算模型函数式 (Functional)以函数应用为核心Haskell, ML, Lisp逻辑式 (Logic)以逻辑推理为核心Prolog体系结构冯·诺依曼式基于存储-计算模型C, Fortran编程范式面向对象数据抽象继承Simula, C, Java使用方式脚本语言解释执行高级操作符Python, Perl, JS一个小练习(Exercise 1.3.1): 你能判断 Python 属于以上哪些分类吗答案Python 是命令式的有赋值语句和可变状态、也支持函数式风格lambda、map、filter、是面向对象的一切皆对象、也是脚本语言解释执行。现代语言往往是多范式的。1.3 语言发展对编译器的影响每一代语言的新特性都给编译器设计带来了新挑战语言特性编译器需要解决的问题相关章节用户自定义类型数组、结构体数据流优化消除冗余的内存访问Ch9面向对象虚方法、继承过程内联、虚方法分派优化Ch8, Ch12Java类型安全、垃圾回收、字节码数组边界检查消除、逃逸分析、JIT编译Ch7, Ch9并行/并发编程自动并行化、数据依赖分析Ch11二、编译器设计的科学与应用 (1.4-1.5)2.1 建模用数学工具解决实际问题 (1.4.1)编译器设计的精髓在于为实际问题选择正确的数学模型数学模型对应的编译器组件详细章节有限状态机 正则表达式词法分析器Ch3上下文无关文法语法分析器Ch4属性文法语义分析、翻译Ch5树模型中间表示、代码生成Ch5-6, Ch8图模型流图、依赖图代码优化Ch8-9格 (Lattice)数据流分析框架Ch9这正是编译原理课程的学术价值所在——它是计算机科学中理论与实践完美结合的经典案例。2.2 代码优化的四大设计目标 (1.4.2)龙书强调编译器优化必须满足四个目标且有严格的优先级龙书原文的警告非常精辟如果不要求正确性写出一个生成快速代码的编译器是很容易的没有任何优化编译器是完全没有 bug 的。因此正确性永远是第一位的。2.3 编译技术的五大应用领域 (1.5)编译技术远不只用于编译器本身应用一高级语言实现 (1.5.1)数据流优化消除高级抽象引入的低效代码过程内联消除小方法的调用开销面向对象语言尤其重要逃逸分析判断对象是否逃逸出方法——如果没有可以在栈上分配而非堆上应用二体系结构优化 (1.5.2)指令级并行 (ILP)编译器重排指令以利用CPU流水线VLIW架构编译器负责显式打包可并行执行的指令缓存优化编译器调整数据布局和访问顺序以提高缓存命中率寄存器分配高效利用有限的寄存器资源应用三体系结构设计 (1.5.3)RISC 的故事研究发现编译器很少使用 CISC 的复杂指令于是简化指令集 好的编译器成为主流设计哲学现代CPU设计阶段就会开发编译器来评估架构方案应用四程序翻译 (1.5.4)二进制翻译将 x86 代码翻译为 ARM 代码如 Apple Rosetta 2硬件综合将 Verilog/VHDL 编译为门级电路数据库查询优化SQL 查询的编译和优化应用五软件生产力工具 (1.5.5)静态分析不运行程序就能发现 bug 和安全漏洞类型检查在编译时发现类型错误内存安全检查检测缓冲区溢出、空指针引用等三、程序设计语言基础 (1.6) ⭐重点这一节是第1章最需要仔细理解的部分因为它定义了后续各章频繁使用的核心概念。3.1 静态与动态的区别 (1.6.1)编译原理中最基本的一组对立概念静态 (Static)动态 (Dynamic)决定时机编译时 (compile time)运行时 (run time)作用域静态作用域由代码文本结构决定动态作用域由调用栈决定类型静态类型编译时确定变量类型动态类型运行时确定绑定静态绑定编译时确定方法调用目标动态绑定运行时确定虚方法存储分配静态分配全局/静态变量动态分配栈分配、堆分配代表语言C大部分静态, Java静态类型Python动态类型, JS编译器设计者的视角编译器能做的所有工作都在静态阶段完成。编译器越能在静态阶段确定的事情越多生成的代码就越高效。动态意味着需要在运行时付出额外的检查和决策开销。3.2 环境与状态 (1.6.2)理解编译器的核心在于理解名字 (name) → 值 (value)的映射过程。这个映射被拆成两步环境 (Environment)将名字映射到存储位置由声明和作用域规则决定例变量x在栈帧偏移量-16处状态 (State)将存储位置映射到值由赋值语句改变例内存地址0x7fff5c中存储着值42为什么要拆成两步因为同一个名字在不同的作用域中可以对应不同的存储位置而同一个存储位置在不同的时刻可以持有不同的值。voidfoo(){intx10;// x → 位置A → 值10{intx20;// x → 位置B → 值20 (不同的位置)}x30;// x → 位置A → 值30 (同一位置不同值)}3.3 静态作用域与块结构 (1.6.3) ⭐⭐作用域 (Scope)是指程序中一个声明起作用的区域。静态作用域 (Static / Lexical Scope)静态作用域由程序的文本结构即代码的嵌套层次决定与程序的执行过程无关。就近嵌套规则 (Most-Closely Nested Rule)如果一个标识符在当前块中没有声明就到包含它的外层块中查找如果还没有继续向外查找——直到找到声明或报错。intx1;// ← 声明① x 在全局块voidfoo(){inty2;// ← 声明② y 在 foo 的块voidbar(){intz3;// ← 声明③ z 在 bar 的块printf(%d,x);// 使用 x → 在 bar 中没有 → 在 foo 中没有// → 在全局找到声明① ✓printf(%d,y);// 使用 y → 在 bar 中没有 → 在 foo 中找到声明② ✓}}用图表示作用域的嵌套关系C/Java 中的块结构在 C 和 Java 中花括号{}界定一个块。每个块可以有自己的局部声明内层声明遮蔽 (shadow/hide)外层的同名声明intx1;voidexample(){intx2;// 遮蔽全局的 xprintf(%d\n,x);// 输出 2{intx3;// 遮蔽上一层的 xprintf(%d\n,x);// 输出 3}printf(%d\n,x);// 输出 2回到外层的 x}3.4 显式访问控制 (1.6.4)面向对象语言通过访问修饰符提供额外的可见性控制修饰符Java 中的含义public任何代码都可以访问private只有本类内部可以访问protected本类和子类可以访问(无修饰符)同一包内可以访问这些控制在语义分析阶段由编译器检查和强制执行。3.5 动态作用域 (1.6.5)在动态作用域中名字的绑定由运行时的调用栈决定而非代码的文本结构。假设使用动态作用域 int x 1; void foo() { print(x); // x 在 foo 中没有声明到调用者中查找 } void bar() { int x 2; foo(); // 从 bar 调用 foo → foo 中的 x 找到 bar 的 x 2 } void baz() { int x 3; foo(); // 从 baz 调用 foo → foo 中的 x 找到 baz 的 x 3 }同一个函数foo()因为调用者不同x的值也不同动态作用域 vs 静态作用域对比静态作用域动态作用域查找规则沿代码的嵌套结构向外查找沿调用栈向下查找可预测性高——看代码就能确定低——取决于运行时调用链编译器优化容易——绑定在编译时确定困难——绑定在运行时才确定使用者绝大多数现代语言早期 Lisp、部分宏系统、Perl(local)3.6 参数传递机制 (1.6.6) ⭐⭐参数传递方式直接影响编译器生成的代码和优化的安全性。值传递 (Call by Value)将实参的值复制一份传给形参。函数内部对形参的修改不影响实参。voidswap(inta,intb){// a, b 是实参的副本inttempa;ab;btemp;// 交换的是副本调用者的变量不受影响}intx1,y2;swap(x,y);// x 仍然是 1y 仍然是 2编译器实现将实参的值压入栈帧或放入寄存器被调用函数在自己的栈帧中操作副本。引用传递 (Call by Reference)将实参的地址传给形参。函数内部通过地址直接操作实参本身。// C 语言通过指针模拟引用传递voidswap(int*a,int*b){// a, b 是指向实参的指针inttemp*a;*a*b;*btemp;// 通过指针修改了调用者的变量}intx1,y2;swap(x,y);// x 变成了 2y 变成了 1// C 有原生的引用传递语法voidswap(inta,intb){inttempa;ab;btemp;}编译器实现将实参的地址压入栈帧被调用函数通过间接寻址访问实参的原始存储位置。Java 的参数传递Java 的情况常常引起困惑基本类型 (int, double, …)值传递复制值对象类型值传递——但传递的是引用的值即对象的地址的副本voidmodify(StringBuildersb){sb.append( world);// 通过引用修改了对象内容 ✓sbnewStringBuilder(new);// 修改了局部引用不影响调用者 ✗}StringBuildersnewStringBuilder(hello);modify(s);// s 的内容是 hello world对象被修改了// s 仍然指向原来的对象引用本身没被修改各传递方式对比方式传递内容函数能否修改实参代表语言值传递值的副本不能C (默认), Java (基本类型)引用传递地址能C (), C# (ref)值传递引用引用的副本能修改对象内容不能修改引用本身Java (对象), Python3.7 别名 (Aliasing) (1.6.7)别名 (Alias)是指两个或多个名字指向同一个存储位置的现象。intx10;int*px;int*qx;// p 和 q 是别名——它们指向同一个位置// *p 20 之后x、*p、*q 都变成了 20引用传递也会产生别名voidfoo(int*a,int*b){// 如果调用者传入 foo(x, x)// 那么 a 和 b 就是别名*a1;*b2;// 此时 *a 也变成了 2而非 1}别名对编译器优化的影响别名让很多优化变得不安全。例如*p10;*q20;x*p5;// x 是 15 还是 25如果编译器不知道p和q是否指向同一个位置它就不能假设*p在第三行仍然是 10——因为第二行的*q 20可能改变了*p的值。这就是为什么 C 语言引入了restrict关键字——告诉编译器这个指针没有别名从而允许更激进的优化。别名分析 (Alias Analysis)是编译器优化中最重要也最困难的问题之一将在第12章深入讨论。四、第1章完整小结经过三篇博客我们已经覆盖了第1章的全部内容。让我们做一个整体回顾你应该掌握的核心知识编译器 vs 解释器编译器翻译并生成目标程序解释器直接执行源程序编译器的六阶段词法分析→语法分析→语义分析→中间代码生成→代码优化→代码生成前端 vs 后端前端分析理解源程序后端综合生成目标程序中间表示是桥梁符号表贯穿全部阶段的核心数据结构环境与状态名字→存储位置→值的两步映射静态作用域由代码的嵌套文本结构决定变量绑定参数传递值传递复制值引用传递传地址别名对编译器优化构成根本性挑战你应该建立的直觉编译原理是理论与工程的完美结合——每个编译器组件背后都有精确的数学模型编译技术远不止于编译器——从数据库到硬件设计都在用理解编程语言的底层概念作用域、绑定、别名对写出高质量代码至关重要五、习题精选与思考Exercise 1.3.1 (语言分类)判断 C、C、Java、Python、Haskell 分别属于哪些语言分类Exercise 1.6 系列 (自测)画出以下代码在静态作用域和动态作用域下的变量查找过程有什么不同Java 中void foo(int[] arr)对 arr 的修改能否影响到调用者为什么给出一个因为别名导致优化不安全的具体例子。
编程语言的基石概念——从语言发展到作用域与参数传递（三）
发布时间：2026/6/2 12:06:12
引言前两篇博客我们了解了编译器是什么、以及编译器内部的六大阶段。本篇将覆盖第1章剩余的四节内容这些内容构成了学习编译原理的背景知识。主要包括三大主题编程语言的发展历史及其对编译技术的影响 (1.3)编译器设计的科学方法与编译技术的广泛应用 (1.4-1.5)程序设计语言的核心概念——这是编写编译器之前必须透彻理解的基础 (1.6)其中第三部分最为重要我会重点展开。一、编程语言的发展简史 (1.3)1.1 从机器码到高级语言编程语言的发展可以按代来划分1.2 语言的分类维度同一种语言往往属于多个分类分类标准类别特征代表语言计算模型命令式 (Imperative)通过语句改变程序状态C, Java, Python声明式 (Declarative)描述做什么而非怎么做SQL, Prolog, Haskell计算模型函数式 (Functional)以函数应用为核心Haskell, ML, Lisp逻辑式 (Logic)以逻辑推理为核心Prolog体系结构冯·诺依曼式基于存储-计算模型C, Fortran编程范式面向对象数据抽象继承Simula, C, Java使用方式脚本语言解释执行高级操作符Python, Perl, JS一个小练习(Exercise 1.3.1): 你能判断 Python 属于以上哪些分类吗答案Python 是命令式的有赋值语句和可变状态、也支持函数式风格lambda、map、filter、是面向对象的一切皆对象、也是脚本语言解释执行。现代语言往往是多范式的。1.3 语言发展对编译器的影响每一代语言的新特性都给编译器设计带来了新挑战语言特性编译器需要解决的问题相关章节用户自定义类型数组、结构体数据流优化消除冗余的内存访问Ch9面向对象虚方法、继承过程内联、虚方法分派优化Ch8, Ch12Java类型安全、垃圾回收、字节码数组边界检查消除、逃逸分析、JIT编译Ch7, Ch9并行/并发编程自动并行化、数据依赖分析Ch11二、编译器设计的科学与应用 (1.4-1.5)2.1 建模用数学工具解决实际问题 (1.4.1)编译器设计的精髓在于为实际问题选择正确的数学模型数学模型对应的编译器组件详细章节有限状态机 正则表达式词法分析器Ch3上下文无关文法语法分析器Ch4属性文法语义分析、翻译Ch5树模型中间表示、代码生成Ch5-6, Ch8图模型流图、依赖图代码优化Ch8-9格 (Lattice)数据流分析框架Ch9这正是编译原理课程的学术价值所在——它是计算机科学中理论与实践完美结合的经典案例。2.2 代码优化的四大设计目标 (1.4.2)龙书强调编译器优化必须满足四个目标且有严格的优先级龙书原文的警告非常精辟如果不要求正确性写出一个生成快速代码的编译器是很容易的没有任何优化编译器是完全没有 bug 的。因此正确性永远是第一位的。2.3 编译技术的五大应用领域 (1.5)编译技术远不只用于编译器本身应用一高级语言实现 (1.5.1)数据流优化消除高级抽象引入的低效代码过程内联消除小方法的调用开销面向对象语言尤其重要逃逸分析判断对象是否逃逸出方法——如果没有可以在栈上分配而非堆上应用二体系结构优化 (1.5.2)指令级并行 (ILP)编译器重排指令以利用CPU流水线VLIW架构编译器负责显式打包可并行执行的指令缓存优化编译器调整数据布局和访问顺序以提高缓存命中率寄存器分配高效利用有限的寄存器资源应用三体系结构设计 (1.5.3)RISC 的故事研究发现编译器很少使用 CISC 的复杂指令于是简化指令集 好的编译器成为主流设计哲学现代CPU设计阶段就会开发编译器来评估架构方案应用四程序翻译 (1.5.4)二进制翻译将 x86 代码翻译为 ARM 代码如 Apple Rosetta 2硬件综合将 Verilog/VHDL 编译为门级电路数据库查询优化SQL 查询的编译和优化应用五软件生产力工具 (1.5.5)静态分析不运行程序就能发现 bug 和安全漏洞类型检查在编译时发现类型错误内存安全检查检测缓冲区溢出、空指针引用等三、程序设计语言基础 (1.6) ⭐重点这一节是第1章最需要仔细理解的部分因为它定义了后续各章频繁使用的核心概念。3.1 静态与动态的区别 (1.6.1)编译原理中最基本的一组对立概念静态 (Static)动态 (Dynamic)决定时机编译时 (compile time)运行时 (run time)作用域静态作用域由代码文本结构决定动态作用域由调用栈决定类型静态类型编译时确定变量类型动态类型运行时确定绑定静态绑定编译时确定方法调用目标动态绑定运行时确定虚方法存储分配静态分配全局/静态变量动态分配栈分配、堆分配代表语言C大部分静态, Java静态类型Python动态类型, JS编译器设计者的视角编译器能做的所有工作都在静态阶段完成。编译器越能在静态阶段确定的事情越多生成的代码就越高效。动态意味着需要在运行时付出额外的检查和决策开销。3.2 环境与状态 (1.6.2)理解编译器的核心在于理解名字 (name) → 值 (value)的映射过程。这个映射被拆成两步环境 (Environment)将名字映射到存储位置由声明和作用域规则决定例变量x在栈帧偏移量-16处状态 (State)将存储位置映射到值由赋值语句改变例内存地址0x7fff5c中存储着值42为什么要拆成两步因为同一个名字在不同的作用域中可以对应不同的存储位置而同一个存储位置在不同的时刻可以持有不同的值。voidfoo(){intx10;// x → 位置A → 值10{intx20;// x → 位置B → 值20 (不同的位置)}x30;// x → 位置A → 值30 (同一位置不同值)}3.3 静态作用域与块结构 (1.6.3) ⭐⭐作用域 (Scope)是指程序中一个声明起作用的区域。静态作用域 (Static / Lexical Scope)静态作用域由程序的文本结构即代码的嵌套层次决定与程序的执行过程无关。就近嵌套规则 (Most-Closely Nested Rule)如果一个标识符在当前块中没有声明就到包含它的外层块中查找如果还没有继续向外查找——直到找到声明或报错。intx1;// ← 声明① x 在全局块voidfoo(){inty2;// ← 声明② y 在 foo 的块voidbar(){intz3;// ← 声明③ z 在 bar 的块printf(%d,x);// 使用 x → 在 bar 中没有 → 在 foo 中没有// → 在全局找到声明① ✓printf(%d,y);// 使用 y → 在 bar 中没有 → 在 foo 中找到声明② ✓}}用图表示作用域的嵌套关系C/Java 中的块结构在 C 和 Java 中花括号{}界定一个块。每个块可以有自己的局部声明内层声明遮蔽 (shadow/hide)外层的同名声明intx1;voidexample(){intx2;// 遮蔽全局的 xprintf(%d\n,x);// 输出 2{intx3;// 遮蔽上一层的 xprintf(%d\n,x);// 输出 3}printf(%d\n,x);// 输出 2回到外层的 x}3.4 显式访问控制 (1.6.4)面向对象语言通过访问修饰符提供额外的可见性控制修饰符Java 中的含义public任何代码都可以访问private只有本类内部可以访问protected本类和子类可以访问(无修饰符)同一包内可以访问这些控制在语义分析阶段由编译器检查和强制执行。3.5 动态作用域 (1.6.5)在动态作用域中名字的绑定由运行时的调用栈决定而非代码的文本结构。假设使用动态作用域 int x 1; void foo() { print(x); // x 在 foo 中没有声明到调用者中查找 } void bar() { int x 2; foo(); // 从 bar 调用 foo → foo 中的 x 找到 bar 的 x 2 } void baz() { int x 3; foo(); // 从 baz 调用 foo → foo 中的 x 找到 baz 的 x 3 }同一个函数foo()因为调用者不同x的值也不同动态作用域 vs 静态作用域对比静态作用域动态作用域查找规则沿代码的嵌套结构向外查找沿调用栈向下查找可预测性高——看代码就能确定低——取决于运行时调用链编译器优化容易——绑定在编译时确定困难——绑定在运行时才确定使用者绝大多数现代语言早期 Lisp、部分宏系统、Perl(local)3.6 参数传递机制 (1.6.6) ⭐⭐参数传递方式直接影响编译器生成的代码和优化的安全性。值传递 (Call by Value)将实参的值复制一份传给形参。函数内部对形参的修改不影响实参。voidswap(inta,intb){// a, b 是实参的副本inttempa;ab;btemp;// 交换的是副本调用者的变量不受影响}intx1,y2;swap(x,y);// x 仍然是 1y 仍然是 2编译器实现将实参的值压入栈帧或放入寄存器被调用函数在自己的栈帧中操作副本。引用传递 (Call by Reference)将实参的地址传给形参。函数内部通过地址直接操作实参本身。// C 语言通过指针模拟引用传递voidswap(int*a,int*b){// a, b 是指向实参的指针inttemp*a;*a*b;*btemp;// 通过指针修改了调用者的变量}intx1,y2;swap(x,y);// x 变成了 2y 变成了 1// C 有原生的引用传递语法voidswap(inta,intb){inttempa;ab;btemp;}编译器实现将实参的地址压入栈帧被调用函数通过间接寻址访问实参的原始存储位置。Java 的参数传递Java 的情况常常引起困惑基本类型 (int, double, …)值传递复制值对象类型值传递——但传递的是引用的值即对象的地址的副本voidmodify(StringBuildersb){sb.append( world);// 通过引用修改了对象内容 ✓sbnewStringBuilder(new);// 修改了局部引用不影响调用者 ✗}StringBuildersnewStringBuilder(hello);modify(s);// s 的内容是 hello world对象被修改了// s 仍然指向原来的对象引用本身没被修改各传递方式对比方式传递内容函数能否修改实参代表语言值传递值的副本不能C (默认), Java (基本类型)引用传递地址能C (), C# (ref)值传递引用引用的副本能修改对象内容不能修改引用本身Java (对象), Python3.7 别名 (Aliasing) (1.6.7)别名 (Alias)是指两个或多个名字指向同一个存储位置的现象。intx10;int*px;int*qx;// p 和 q 是别名——它们指向同一个位置// *p 20 之后x、*p、*q 都变成了 20引用传递也会产生别名voidfoo(int*a,int*b){// 如果调用者传入 foo(x, x)// 那么 a 和 b 就是别名*a1;*b2;// 此时 *a 也变成了 2而非 1}别名对编译器优化的影响别名让很多优化变得不安全。例如*p10;*q20;x*p5;// x 是 15 还是 25如果编译器不知道p和q是否指向同一个位置它就不能假设*p在第三行仍然是 10——因为第二行的*q 20可能改变了*p的值。这就是为什么 C 语言引入了restrict关键字——告诉编译器这个指针没有别名从而允许更激进的优化。别名分析 (Alias Analysis)是编译器优化中最重要也最困难的问题之一将在第12章深入讨论。四、第1章完整小结经过三篇博客我们已经覆盖了第1章的全部内容。让我们做一个整体回顾你应该掌握的核心知识编译器 vs 解释器编译器翻译并生成目标程序解释器直接执行源程序编译器的六阶段词法分析→语法分析→语义分析→中间代码生成→代码优化→代码生成前端 vs 后端前端分析理解源程序后端综合生成目标程序中间表示是桥梁符号表贯穿全部阶段的核心数据结构环境与状态名字→存储位置→值的两步映射静态作用域由代码的嵌套文本结构决定变量绑定参数传递值传递复制值引用传递传地址别名对编译器优化构成根本性挑战你应该建立的直觉编译原理是理论与工程的完美结合——每个编译器组件背后都有精确的数学模型编译技术远不止于编译器——从数据库到硬件设计都在用理解编程语言的底层概念作用域、绑定、别名对写出高质量代码至关重要五、习题精选与思考Exercise 1.3.1 (语言分类)判断 C、C、Java、Python、Haskell 分别属于哪些语言分类Exercise 1.6 系列 (自测)画出以下代码在静态作用域和动态作用域下的变量查找过程有什么不同Java 中void foo(int[] arr)对 arr 的修改能否影响到调用者为什么给出一个因为别名导致优化不安全的具体例子。
