静态单赋值形式（SSA）如何简化编译器优化，Phi 函数的作用是什么？
How does static single assignment (SSA) form simplify compiler optimization, and what is the role of the Phi function?
SSA 要求每个变量只被赋值一次，并用 Phi 函数在控制流汇合处根据来源路径选择取值，从而让依赖关系显式化。这使定值-引用链（def-use chain）易于计算，极大简化了常量传播、死代码消除等优化。
SSA requires each variable to be assigned exactly once and uses Phi functions at control-flow merges to select a value based on the incoming path, making dependencies explicit. This makes def-use chains easy to compute and greatly simplifies optimizations such as constant propagation and dead-code elimination.
难度 专业 · 适合 大众
CC BY 4.0 · 已核验 · Verified 2026-08-23 · 2 条独立证据
来源 · Source
Cormen, Leiserson, Rivest, Stein,《Introduction to Algorithms》第3版,MIT Press,2009
T. H. Cormen et al., Introduction to Algorithms, 3rd ed., MIT Press, 2009
独立核验依据 · Independent verification: 核验依据 2 ISBN 978-0-262-04630-5
#SSA #Phi函数 #编译器优化
Hindley–Milner 类型系统如何在不写标注的情况下推断出表达式的最泛型类型？
How does the Hindley-Milner type system infer the most general type of an expression without annotations?
HM 把表达式生成类型约束，再用合一（unification）算法求解类型变量的最一般替换，从而得出最泛型类型（principal type）。其算法在线性时间内完成，是 ML、Haskell 等语言类型推断的基础。
HM generates type constraints from the expression and solves them with a unification algorithm to find the most general substitution for type variables, yielding the principal type. The algorithm runs in linear time and underpins type inference in languages like ML and Haskell.
难度 专业 · 适合 初中(12-15)
CC BY 4.0 · 已核验 · Verified 2026-10-04
来源 · Source
Milner, A Theory of Type Polymorphism in Programming, JCSS 1978
Milner, A Theory of Type Polymorphism in Programming, Journal of Computer and System Sciences 1978
独立核验依据 · Independent verification: 核验依据 1 DOI 10.1016/0022-0000(78)90014-4
#类型推断 #合一 #多态
数据流分析中的「到达定值」分析如何利用迭代算法求解，其单调性与不动点为何重要？
How does reaching-definitions data-flow analysis solve via iteration, and why do monotonicity and fixed points matter?
到达定值分析在控制流图上为每个基本块维护定值集合，并按逆后序反复传播直到集合不再变化（不动点）。由于状态格具有有限高度且传递函数单调，迭代必然在有限步内收敛到正确解。
Reaching-definitions analysis maintains a set of definitions at each basic block in the control-flow graph and repeatedly propagates them in reverse post-order until the sets stop changing (a fixed point). Because the lattice has finite height and the transfer functions are monotonic, iteration is guaranteed to converge to the correct solution in finite steps.
难度 专业 · 适合 大众
CC BY 4.0 · 已核验 · Verified 2026-11-02
来源 · Source
《编译原理》（Aho 等，龙书）
Compilers: Principles, Techniques, and Tools (Aho et al.)
独立核验依据 · Independent verification: 核验依据 1 ISBN 9787111251217（豆瓣书目条目: 编译原理）
#数据流分析 #不动点 #控制流图
静态类型系统在编译期能防范哪些错误，又付出了什么代价？
What errors can a static type system catch at compile time, and what is the cost?
静态类型在编译期检查变量与函数的类型一致性，可在运行前捕获大量类型错误并辅助自动补全与重构。代价是需要类型标注或推断，并可能限制某些动态灵活的写法。
A static type system checks type consistency of variables and functions at compile time, catching many type errors before runtime and aiding auto-completion and refactoring. The cost is the need for annotations or inference and some loss of dynamic flexibility.
难度 进阶 · 适合 高中(15-18)
CC BY 4.0 · 已核验 · Verified 2026-11-03
来源 · Source
Pierce, Types and Programming Languages, MIT Press
Pierce, Types and Programming Languages, MIT Press
独立核验依据 · Independent verification: 核验依据 1 OPENLIBRARY 标识 /works/OL4078119W：Types and Programming L
#类型系统 #静态类型 #类型安全
尾递归优化如何把递归调用转化为循环，避免栈溢出？
How does tail-call optimization turn recursion into a loop and avoid stack overflow?
当递归调用是函数最后一步时，编译器可复用当前栈帧而非新建帧，并将递归改写为跳转回函数开头的循环。这让尾递归在空间和效率上等价于迭代，避免深度递归的栈溢出。
When the recursive call is the last action in a function, the compiler can reuse the current stack frame instead of creating a new one, rewriting the recursion as a jump back to the function entry. This makes tail recursion equivalent to iteration in space and speed, avoiding stack overflow on deep recursion.
难度 进阶 · 适合 高中(15-18)
CC BY 4.0 · 已核验 · Verified 2026-11-02
来源 · Source
Appel, Compiling with Continuations, Cambridge University Press
Appel, Compiling with Continuations, Cambridge University Press
独立核验依据 · Independent verification: 核验依据 1 OPENLIBRARY 标识 /works/OL2704212W：Compiling with Continua
#尾递归 #栈帧 #编译优化
编译器做了哪些工作？
What does a compiler do?
编译器把人类可读的源代码翻译成计算机可执行的机器码，通常经历词法分析、语法分析、语义分析、优化和代码生成几个阶段。它能在运行前发现许多错误。不同语言的编译器在细节上差别很大。
A compiler translates human-readable source code into executable machine code, usually through lexical analysis, syntax analysis, semantic analysis, optimization, and code generation. It catches many errors before running. Compilers differ greatly in detail across languages.
难度 进阶 · 适合 初中(12-15)
CC BY 4.0 · 已核验 · Verified 2026-08-23
来源 · Source
Abelson & Sussman,《Structure and Interpretation of Computer Programs》MIT Press,1996 第二版
H. Abelson and G. J. Sussman, SICP, MIT Press, 1996
#编译器 #翻译 #机器码
抽象语法树（AST）在编译过程中起什么作用？
What role does the abstract syntax tree (AST) play in compilation?
解析器把源代码转化为去掉冗余括号与分隔符、只保留语法结构的树，即 AST。后续的类型检查、优化和代码生成都基于 AST 进行，它是连接前端语法分析与中后端处理的核心中间表示。
The parser turns source code into a tree that drops redundant parentheses and delimiters while keeping only the grammatical structure, the AST. Type checking, optimization, and code generation all operate on the AST, making it the central intermediate representation linking front-end parsing to back-end processing.
难度 进阶 · 适合 初中(12-15)
CC BY 4.0 · 已核验 · Verified 2026-11-02
来源 · Source
Aho, Lam, Sethi, Ullman, 编译原理（龙书）, Pearson 第2版
Aho, Lam, Sethi, Ullman, Compilers: Principles, Techniques, and Tools, Pearson 2nd ed.
独立核验依据 · Independent verification: 核验依据 1 ISBN 9787111251217（豆瓣书目条目: 编译原理）
#抽象语法树 #编译前端 #解析
什么是中间代码？
What is intermediate code?
中间代码是编译器在源代码和最终机器码之间生成的一种与机器无关的表示（如字节码），便于在不同平台上复用优化逻辑。Java 先编译成字节码，再由虚拟机解释或即时编译执行就是典型例子。它提高了语言的可移植性。
Intermediate code is a machine-independent representation, such as bytecode, generated by a compiler between source code and final machine code, easing reuse of optimization across platforms. Java compiles to bytecode that a virtual machine interprets or just-in-time compiles, a typical example. It improves language portability.
难度 进阶 · 适合 初中(12-15)
CC BY 4.0 · 已核验 · Verified 2026-08-23
来源 · Source
Abelson & Sussman,《Structure and Interpretation of Computer Programs》MIT Press,1996 第二版
H. Abelson and G. J. Sussman, SICP, MIT Press, 1996
#中间代码 #字节码 #可移植
寄存器分配为什么是编译优化的关键，图着色法如何工作？
Why is register allocation a key compiler optimization, and how does graph coloring work for it?
处理器寄存器远少于程序变量，编译器必须把频繁使用的变量装入寄存器以减少访存。图着色法把变量冲突关系建模为干涉图，再用着色把不冲突的变量映射到同一寄存器。
A processor has far fewer registers than program variables, so the compiler must keep frequently used variables in registers to reduce memory accesses. Graph coloring models variable conflicts as an interference graph and assigns non-conflicting variables to the same register via coloring.
难度 进阶 · 适合 初中(12-15)
CC BY 4.0 · 已核验 · Verified 2026-08-23 · 2 条独立证据
来源 · Source
Cormen, Leiserson, Rivest, Stein,《Introduction to Algorithms》第3版,MIT Press,2009
T. H. Cormen et al., Introduction to Algorithms, 3rd ed., MIT Press, 2009
独立核验依据 · Independent verification: 核验依据 2 ISBN 978-0-262-04630-5
#寄存器分配 #图着色 #编译优化