注：计算部分请参考 编译原理实验报告
编译器：编译阶段，用户输入源程序，经编译器翻译生成目标程序，目标程序在运行时接受输入数据，得到数据输出
解释器：将源程序的翻译和目标程序的运行结合起来，翻译一段源程序，紧接着就执行它，这种方式称为解释
记忆：编译器和解释器的功能都是翻译和运行目标程序，编译器将二者分开进行，而解释器同时进行翻译和运行工作。
词法分析：根据词法规则，识别源程序中的各个记号（token），每个token代表一类单词（lexeme）
语法分析：根据语法规则，识别记号流中的语法结构，并构造反应该结构的语法分析树
语义分析：根据语义规则，对语法树进行静态语义检查，确保结构正确的语句在语义上也正确
中间代码生成：根据语义分析的结果生成与具体机器无关的中间代码，之后根据具体的机器对中间代码进行解释和执行
中间代码优化：中间代码的生成是机械且固定的，对中间代码进行等价变换，提高代码的时间和空间效率
目标代码生成：将中间代码变换成特定机器上运行的指令代码
符号表：记录源程序中符号的相关信息，合理组织后，在编译器的各个阶段进行快速、准确的增删改查等操作
出错处理：遇到一个错误就使编译器停止工作的做法是不负责的，所以编译器应具有广泛的查错能力，准确报告错误种类和出错位置
语言：语言 L L L是有限字母表 Σ \Sigma Σ上有限长度符号串的集合
正规式：有限字母表 Σ \Sigma Σ上的正规式及正规集 L L L的定义为
记忆：定义有限字母表上的正规式和其对应的正规集，首先 ϵ \epsilon ϵ是正规式，其正规集为 { ϵ } \{\epsilon\} {ϵ}. 其次，字母表中的每个字母构成正规式，对应正规集为该字母的集合。接着定义正规式的基本操作：或运算、连接运算、闭包运算、括号规定优先级。
模式：产生和识别单词的规则
记号：根据某种规则（模式）识别出的元素
NFA：Nondeterministic Finite Automata（不确定有限状态机）是一个五元组 ( Q , Σ , δ , S , F ) (Q,\Sigma,\delta,S,F) (Q,Σ,δ,S,F)，其中
DFA：Deterministic Finite Automata（确定有限状态机）是一个五元组 ( Q , Σ , δ , S , F ) (Q,\Sigma,\delta,S,F) (Q,Σ,δ,S,F)，其中
记忆：与NFA相比，DFA具有确定性，因此DFA的 Σ \Sigma Σ不包含 ϵ \epsilon ϵ、 δ \delta δ是单值映射函数、 S S S是唯一初态。
上下文无关文法：四元组 ( V N , V T , P , S ) (V_N,V_T,P,S) (VN,VT,P,S)，其中
终结符：组成一个语言的不可再分的基本符号
非终结符：产生式左部可以派生出符号或符号串的符号
文法产生式：递归描述终结符与非终结符构成的句型。一般形式为： α → β \alpha \to \beta α→β. 其中， α , β ∈ ( V N ∪ V T ) ∗ \alpha, \beta \in (V_N\cup V_T)^* α,β∈(VN∪VT)∗，且 α \alpha α至少含有一个非终结符
推导：从文法开始符号 S S S开始，反复使用产生式，将产生式左部非终结符替换为右部文法符号序列，直至得到一个终结符序列
归约：是推导的逆过程，反复用产生式左部替换右部，直至输入串分析完毕
句型和句子：设文法 G [ S ] G[S] G[S]，若 S ⇒ ∗ x , x ∈ ( V N ∪ V T ) ∗ S\stackrel{*}{\Rightarrow}x,x \in (V_N\cup V_T)^* S⇒∗x,x∈(VN∪VT)∗，则 x x x称为该文法的句型。若 S ⇒ ∗ x , x ∈ V T ∗ S\stackrel{*}{\Rightarrow}x,x \in V_T^* S⇒∗x,x∈VT∗，则 x x x称为该文法的句子
二义性：如果一个文法存在某个句子对应两棵不同的语法树，即具有不同的最左（最右）推导，这个文法就是二义性的
下推自动机：扩展DFA使之可以存取一个栈，称为下推栈。输入一串记号流，下推自动机将根据“有限状态转移控制”，决定是否接受该记号流
First集： F i r s t ( α ) = { a ∣ α ⇒ ∗ a … a n d a ∈ V T } First(\alpha)=\{a|\alpha\stackrel{*}{\Rightarrow} a\dots\ and\ a\in V_T \} First(α)={a∣α⇒∗a… and a∈VT}，若 α ⇒ ∗ ϵ \alpha \stackrel{*}{\Rightarrow} \epsilon α⇒∗ϵ，则 ϵ ∈ F i r s t ( α ) \epsilon \in First(\alpha) ϵ∈First(α)
Follow集： F o l l o w ( A ) = { a ∣ S ⇒ ∗ … A a … , a ∈ V T } Follow(A)=\{a|S\stackrel{*}{\Rightarrow}\dots Aa\dots,a\in V_T \} Follow(A)={a∣S⇒∗…Aa…,a∈VT}，若 S ⇒ ∗ … A S\stackrel{*}{\Rightarrow}\dots A S⇒∗…A，则 # ∈ F o l l o w ( A ) \#\in Follow(A) #∈Follow(A)
活前缀：规范句型前缀，不含句柄之后的任何符号。若 S ⇒ ∗ δ A ω S\stackrel{*}{\Rightarrow}\delta A\omega S⇒∗δAω，且可继续规范推导出 S ⇒ ∗ δ α β ω S\stackrel{*}{\Rightarrow}\delta \alpha \beta \omega S⇒∗δαβω，其中， δ ∈ V ∗ , A ∈ V N , ω ∈ V N ∗ , α ∈ V + \delta \in V^*,A\in V_N,\omega\in V_N^*,\alpha\in V^+ δ∈V∗,A∈VN,ω∈VN∗,α∈V+，则 α β \alpha\beta αβ是 δ α β ω \delta\alpha\beta\omega δαβω的句柄， δ α β \delta\alpha\beta δαβ的任意前缀都是 δ α β ω \delta\alpha\beta\omega δαβω的活前缀
移进规约冲突：一个项目集中，既有移进项目，又有规约项目，则此时不能决定产生移进动作还是规约动作
语法制导翻译：为每一个产生式配上相应的语义规则，在推导或规约的过程中根据产生式的语义规则执行对应的语义动作
综合属性：若 A → α , b : = f ( c 1 , c 2 , … , c k ) A\to \alpha,b:=f(c_1,c_2,\dots,c_k) A→α,b:=f(c1,c2,…,ck)，其中， b b b是 A A A的属性， c 1 , c 2 , … , c k c_1,c_2,\dots,c_k c1,c2,…,ck是 α \alpha α中某些文法符号的属性或 A A A的其他属性，则 b b b是综合属性
继承属性：若 A → α , b : = f ( c 1 , c 2 , … , c k ) A\to \alpha,b:=f(c_1,c_2,\dots,c_k) A→α,b:=f(c1,c2,…,ck)，其中， b b b是 α \alpha α中某文法符号的属性， c 1 , c 2 , … , c k c_1,c_2,\dots,c_k c1,c2,…,ck是 A A A的属性或 α \alpha α中其他文法符号的属性，则 b b b是继承属性
记忆：综合属性“自下而上，包含自身”；继承属性“自上而下，包含兄弟”。
三地址代码：每条代码包含一个运算和三个地址，例如 x = y o p z x=y\ op\ z x=y op z，运算op，两个地址 y , z y,z y,z用于存放运算对象，地址 x x x用于存放运算结果
四元式： ( o p , a r g 1 , a r g 2 , r e s u l t ) (op,arg1,arg2,result) (op,arg1,arg2,result)，四元式是具有四个域的记录结构，其含义是arg1和arg2进行op指定的操作，结果存放到result中
拉链与回填：当三地址码中的转向不确定时，将所有转向同一地址的三地址码拉成一个链，一旦转向地址确定，沿此链回填转向地址
编译器和解释器的比较：
编译器和解释器的功能都是翻译和运行目标程序，从翻译的角度来说，二者相类似，但编译器将源程序的翻译和目标代码的运行分开进行，而解释器同时进行翻译和运行工作。
解释器的优点：
解释器的缺点：
记忆：（相同）翻译过程类似。（区别）编译器分别进行翻译和运行工作，解释器则同时进行。（解释器的优缺点）“移动时空”——（优）可移植性、动态特性，（缺）时空损失大、运行效率低。
编译的一般过程：
多遍扫描与一遍扫描的比较：
记忆：（定义）多遍扫描是编译器编译过程中对源程序进行多遍完整的扫描和分析，一遍扫描指的是编译器将若干阶段的工作结合起来，只进行一遍扫描和分析工作。（一遍扫描的优缺点）——优：效率高，减少重复工作；缺点：（算法、代码优化、错误处理）算法逻辑不清晰、不利于代码优化、语法语义分析过程中出现错误导致前面分析过程的结果作废。
语言的运算：
记忆：交、并、差、连接、闭包、正闭包
构造正规式：
正规式等价证明：
若正规式P、Q表示同一个正规集，则称P、Q等价，记为P=Q. 可以利用正规式的恒等运算的代数性质，化简复杂正规式，从而判断正规式是否等价。
记忆：“或”运算具有交换律、结合律，连接运算具有结合律，正闭包运算 r + = r r ∗ = r ∗ r r^+=rr^*=r^*r r+=rr∗=r∗r，闭包运算 r ∗ = r + ∣ ϵ r^*=r^+|\epsilon r∗=r+∣ϵ，可缺省运算 r ? = r ∣ ϵ r?=r|\epsilon r?=r∣ϵ.
DFA三种形式的转换：
汤普森算法：
作用——构造识别正规式的NFA.
形式——
r
1
r
2
,
r
1
∣
r
2
,
r
1
∗
r_1r_2,r_1|r_2,r_1^*
r1r2,r1∣r2,r1∗
记忆：Thompson算法构造的NFA中，不存在“自回路”且某状态至多只能引出一个非 ϵ \epsilon ϵ转移。
改进：在根据正规式构造NFA的实际操作中，常采用“改进的Thompson算法”，以简化NFA的状态。
消除二义性：
else悬空问题：
S → i f b t h e n S S\to if\ b\ then\ S S→if b then S
∣ i f b t h e n S e l s e S | if\ b\ then\ S\ else\ S ∣if b then S else S
∣ A |A ∣A
if b then if b then A else A具有二义性。产生该二义性的原因是else和then数目不同，不能确定else和第一个then对应还是和第二个then对应。因此，将S分为完全匹配（MS）和不完全匹配（UMS），完全匹配中else-then数目相同，每个else都能找到then与之对应，而UMS中else-then数目不同。MS和UMS中都要体现else的右结合性，即与最靠近else左边的then匹配。消除二义性后的结果：
S → M S ∣ U M S S\to MS|UMS S→MS∣UMS
M S → i f b t h e n M S e l s e M S MS\to if\ b\ then\ MS\ else\ MS MS→if b then MS else MS
U M S → i f b t h e n S ∣ i f b t h e n M S e l s e U M S UMS\to if\ b\ then\ S\ |\ if\ b\ then\ MS\ else\ UMS UMS→if b then S ∣ if b then MS else UMS
预测分析器：
由驱动器、符号栈和预测分析表组成。输入缓冲区存放待分析的串，以#标记输入串的结束，最终输出语法分析的结果。驱动器控制读入记号，根据栈顶符号和当前读入符号，由预测分析表决定对符号栈进行何种操作。
移进规约分析器：
由驱动器、符号状态栈和移进归约分析表组成，其工作模式与预测分析器完全相同。输入缓冲区存放待分析的串，以#标记输入串的结束，最终输出语法分析的结果。驱动器控制读入记号，根据栈顶状态和当前读入符号，由移进归约分析表决定对符号状态栈进行何种操作。
中缀式与后缀式的转换：
记忆：后缀式的引入消除了括号，方便计算。