什么是上下文无关文法？
What is a context-free grammar?
上下文无关文法用一组产生式规则描述程序设计语言的语法结构，每条规则把非终结符替换为符号串。它是语法分析器（如 LL、LR）的理论基础，能刻画嵌套、配对等层次结构。
A context-free grammar uses production rules to describe a programming language's syntax, each rule replacing a nonterminal with a string of symbols. It underlies parsers such as LL and LR and can express nested, paired hierarchical structures.
难度 专业 · 适合 高中(15-18)
CC BY 4.0 · 已核验 · Verified 2026-11-02
来源 · Source
《编译原理》（Aho 等，龙书）
Compilers: Principles, Techniques, and Tools (Aho et al.)
独立核验依据 · Independent verification: 核验依据 1 ISBN 9787111251217（豆瓣书目条目: 编译原理）
#上下文无关文法 #产生式 #语法
SSA 形式（静态单赋值）在编译优化中起什么作用？
What role does SSA (static single assignment) form play in compiler optimization?
SSA 要求每个变量只被赋值一次，并用 φ 函数在分支汇合处选择来源。这让“某个值从哪来、被谁用”一目了然，极大简化了常量传播、死代码删除等优化，是现代编译器的核心中间表示。
SSA makes every variable assigned exactly once, with φ functions at merges to pick the source. It makes 'where a value comes from and who uses it' explicit, simplifying constant propagation and dead-code elimination—core to modern compilers.
难度 专业 · 适合 大众
CC BY 4.0 · 已核验 · Verified 2026-11-03
来源 · Source
Cytron 等,Efficiently Computing Static Single Assignment Form and the Control Dependence Graph,ACM TOPLAS,1991;Appel《Modern Compiler Implementation》,Cambridge University Press
Cytron et al., Efficiently Computing Static Single Assignment Form and the Control Dependence Graph, ACM TOPLAS, 1991; Appel, Modern Compiler Implementation, Cambridge University Press
独立核验依据 · Independent verification: 核验依据 1 OPENLIBRARY 标识 /works/OL2704215W：Modern compiler impleme
#SSA #编译
一个典型的编译器包含哪些主要阶段？
What are the main phases of a typical compiler?
典型编译器依次经历词法分析（切分为单词/记号）、语法分析（按文法构造成语法树）、语义分析（类型与合法性检查）、中间表示生成、优化、以及目标代码生成。各阶段把源代码逐步翻译成可由机器执行的形式，前端与后端通过中间表示解耦。这一结构是《龙书》（Aho 等）等经典教材的核心内容。
A typical compiler proceeds through lexical analysis (splitting into tokens), syntax analysis (building a parse tree per grammar), semantic analysis (type and legality checks), intermediate representation generation, optimization, and target code generation. Each stage progressively translates source into machine-executable form, with the front end and back end decoupled by the intermediate representation. This structure is central to classics like the Dragon Book (Aho et al.).
难度 专业 · 适合 高中(15-18)
CC BY 4.0 · 来源待核验 · Source pending review
来源 · Source
出处备注：著录仅给书名，无版次与年份；同一书名常对应多个版次，不臆测具体版本。
Aho, Lam, Sethi & Ullman《编译器：原理、技术与工具》（龙书）
Aho, Lam, Sethi & Ullman, Compilers: Principles, Techniques, and Tools (Dragon Book)
#编译器 #词法分析 #语法分析 #龙书
图着色寄存器分配把变量分配建模为图着色，其核心机制是什么？当可用颜色不足时会发生什么？
Graph-coloring register allocation models variable assignment as graph coloring: what is the core mechanism, and what happens when there are not enough colors?
编译器先构建干扰图：节点是虚拟寄存器（变量），两个变量的活跃区间重叠就连一条边，表示不能共用同一物理寄存器；分配随即变成用 k 种颜色（k 为机器寄存器数）给图着色，使相邻节点异色。若某节点邻居数超过 k 而无法着色，就把对应变量溢出到栈内存，插入加载与存储指令、重写代码后再迭代分配，直到全部节点着色成功。
The compiler builds an interference graph whose nodes are virtual registers (variables); an edge joins two variables whose live ranges overlap, meaning they cannot share one physical register. Allocation becomes coloring this graph with k colors—k being the machine's register count—so adjacent nodes differ. When a node has more than k neighbors and cannot be colored, its variable is spilled to stack memory: load/store instructions are inserted, the code rewritten, and allocation iterates until coloring succeeds.
难度 专业 · 适合 高中(15-18)
CC BY 4.0 · 已核验 · Verified 2026-11-04
来源 · Source
Chaitin,《Register allocation & spilling via graph coloring》,ACM SIGPLAN 编译器构造研讨会论文集,1982 (DOI: 10.1145/800230.806984)
G. J. Chaitin, 'Register allocation & spilling via graph coloring', Proc. 1982 SIGPLAN Symposium on Compiler Construction, 1982, DOI: 10.1145/800230.806984
独立核验依据 · Independent verification: 核验依据 1 Crossref DOI 10.1145/800230.806984
#寄存器分配 #图着色 #溢出
静态类型检查与动态类型检查有什么区别？各有什么优劣？
What is the difference between static and dynamic type checking, and what are their trade-offs?
静态类型在编译期检查类型错误（如 Java、C），能在运行前捕获大量 bug 并便于优化，但语法更繁琐、灵活性较低。动态类型在运行期检查（如 Python、Ruby），开发更灵活快速，却把更多错误推迟到运行时才发现。该分类在《Types and Programming Languages》（Pierce）中有系统论述。
Static typing checks type errors at compile time (e.g., Java, C), catching many bugs before running and aiding optimization, but at the cost of more verbose syntax and less flexibility. Dynamic typing checks at runtime (e.g., Python, Ruby), enabling faster and more flexible development yet deferring more errors to execution. The distinction is treated systematically in Pierce's Types and Programming Languages.
难度 专业 · 适合 高中(15-18)
CC BY 4.0 · 已核验 · Verified 2026-11-03
来源 · Source
Pierce《类型与编程语言》；Aho 等《编译器：原理、技术与工具》
Pierce, Types and Programming Languages; Aho et al., Compilers: Principles, Techniques, and Tools
独立核验依据 · Independent verification: 核验依据 1 OPENLIBRARY 标识 /works/OL4078119W：Types and Programming L
#静态类型 #动态类型 #类型检查 #Pierce
编译器的主要阶段有哪些？
What are the main phases of a compiler?
编译器通常分前端与后端：前端做词法分析、语法分析、语义分析和中间代码生成；后端做优化与目标代码生成。这种分工让同一前端可对接不同硬件的后端。
A compiler usually splits into front end and back end: the front end does lexical analysis, syntax analysis, semantic analysis, and intermediate code generation; the back end does optimization and target code generation. This split lets one front end serve back ends for different hardware.
难度 进阶 · 适合 初中(12-15)
CC BY 4.0 · 已核验 · Verified 2026-11-02
来源 · Source
《编译原理》（Aho 等，龙书）
Compilers: Principles, Techniques, and Tools (Aho et al.)
独立核验依据 · Independent verification: 核验依据 1 ISBN 9787111251217（豆瓣书目条目: 编译原理）
#编译器 #词法分析 #语法分析
寄存器分配是什么，图着色怎么用来做它？
What is register allocation and how is graph coloring used for it?
寄存器比内存快但数量极少，寄存器分配决定哪些变量能同时放进寄存器。编译器建一张“冲突图”：同时存活的变量连边，然后给图上色，使相邻节点不同色，每种颜色对应一个物理寄存器；染不下的就只能 spill 到内存。
Registers are fast but scarce, so allocation decides which variables live there. The compiler builds an interference graph—edges between variables alive at once—then colors it so neighbors differ; each color is a register, and uncolorable ones get 'spilled' to memory.
难度 进阶 · 适合 大众
CC BY 4.0 · 已核验 · Verified 2026-11-03
来源 · Source
Chaitin,Register Allocation & Spilling via Graph Coloring,SIGPLAN Symposium on Compiler Construction,1982;Muchnick《Advanced Compiler Design and Implementation》,Morgan Kaufmann,1997
Chaitin, Register Allocation & Spilling via Graph Coloring, SIGPLAN Symposium on Compiler Construction, 1982; Muchnick, Advanced Compiler Design and Implementation, Morgan Kaufmann, 1997
独立核验依据 · Independent verification: 核验依据 1 OPENLIBRARY 标识 /works/OL2655436W：Advanced compiler desig
#寄存器 #图着色
循环不变量外提（loop-invariant code motion）是什么？
What is loop-invariant code motion?
如果循环体里某段计算每次结果都一样（不随循环变量改变），编译器就把它搬到循环外面只算一次。这样减少了重复运算，是循环优化的基本手段之一。
If some computation inside a loop yields the same result every iteration, the compiler hoists it outside the loop to run once. It removes redundant work and is a basic loop optimization.
难度 进阶 · 适合 大众
CC BY 4.0 · 已核验 · Verified 2026-11-02
来源 · Source
《编译原理》（Aho 等，龙书）
Compilers: Principles, Techniques, and Tools (Aho et al.)
独立核验依据 · Independent verification: 核验依据 1 ISBN 9787111251217（豆瓣书目条目: 编译原理）
#循环优化 #编译
什么是词法分析？
What is lexical analysis?
词法分析是编译的第一步，把字符流切分成有意义的词素并标记成单词（token），如关键字、标识符、数字。它相当于先给句子断词，方便后续语法分析。
Lexical analysis is the first compilation step: it splits a character stream into meaningful lexemes tagged as tokens such as keywords, identifiers, and numbers. It is like word segmentation, preparing input for later syntax analysis.
难度 进阶 · 适合 初中(12-15)
CC BY 4.0 · 已核验 · Verified 2026-11-02
来源 · Source
《编译原理》（Aho 等，龙书）
Compilers: Principles, Techniques, and Tools (Aho et al.)
独立核验依据 · Independent verification: 核验依据 1 ISBN 9787111251217（豆瓣书目条目: 编译原理）
#词法分析 #token #扫描器
正则表达式在编译器词法分析中起什么作用？
What role do regular expressions play in a compiler's lexical analysis?
在词法分析阶段，程序员用正则表达式描述各类单词（标识符、数字、运算符等）的构成规则，词法分析器据此把字符流切分为记号。正则表达式可机械地转换为有限自动机（如 Thompson 在 1968 年给出的构造），从而被高效执行。它把繁琐的字符串匹配变成可自动生成的识别器。
In lexical analysis, programmers use regular expressions to specify the formation rules of token classes (identifiers, numbers, operators), and the lexer uses them to split the character stream into tokens. Regular expressions can be mechanically converted into finite automata—as in Thompson's 1968 construction—and executed efficiently. This turns tedious string matching into automatically generated recognizers.
难度 进阶 · 适合 初中(12-15)
CC BY 4.0 · 已核验 · Verified 2026-11-03
来源 · Source
Aho 等《编译器：原理、技术与工具》（龙书）；Thompson 1968
Aho et al., Compilers: Principles, Techniques, and Tools; Thompson (1968)
独立核验依据 · Independent verification: 核验依据 1 OPENLIBRARY 标识 /works/OL3509433W：Compilers, principles,
#正则表达式 #词法分析 #有限自动机 #Thompson
编译器到底把我们写的代码变成了什么？
What does a compiler actually turn our code into?
编译器把你写的、人能读懂的高级语言，经过分析、优化，翻译成计算机 CPU 能直接执行的机器指令（或中间的字节码）。它就像一位把“中文菜谱”改写成“厨房操作清单”的翻译官。
A compiler analyzes and optimizes your human-readable code and translates it into machine instructions (or intermediate bytecode) the CPU can run directly—like rewriting a recipe into kitchen steps.
难度 入门 · 适合 大众
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
#编译器 #翻译