编译原理

对程序语言逐个地进行分析，根据每个语句的含义模拟执行

对程序整个进行分析，翻译成等价机器语言（或汇编语言）程序，然后执行

根据词法规则识别出具有独立意义的各各个语法单位——符号（单词），并把它们转化为通常是等长的内部形式（属性字），以供下一阶段语法分析阶段使用

读入由词法分析程序识别出的符号，根据给定的语法规则，识别出各个语法结构，同时也检查了语法的正确性

完成确定类型、类型检查、识别含义与相应的语义处理，并进行一些静态语义检查

编译时为了改进目标代码质量而进行的各项工作

可以在语义分析时生成，如果语义分析的结果是中间表示代码，就必须把中间表示代码变换成等价的目标程序，即目标语言代码

G[Z]是一个文法,w=xuy是该文法的一个句型，如果有Z=>* xUy，U∈V៷，且U=>+  u，u∈V⁺,则称u是句型w中相对于U的短语

如果满足Z=>*  xUy，且U=>u，则称u是句型w中相对于U的简单短语

一个句型的最左简单短语

V៷是非终结符号集

Vₜ是由终结符号组成的字母表

P是有穷非空的重写规则集

Z是识别符号，Z∈V៷

对于文法G，P中每个规则具有下列形式：U::=u其中U∈V៷，u∈V⁺，则称该文法G为2型文法或上下文无关文法，缩写CFG

对于某文法G,P中的每个规则具有下列形式：U::=T 或 U::=WT 其中T∈Vₜ，U、W∈V៷，则称该文法G为3型文法或正则型文法，有时又称有穷状态文法，缩写RG

书p51

书p52

自顶向下的分析技术

自底向上的分析技术

K是有穷非空的状态集合

∑是有穷非空的输入字母表

M是从K×∑到K的映象。如果M（R，T）=Q，则输入字符为T时，当前状态R将转到状态Q，Q成为下一当前状态

S是开始状态，S∈K

F是非空终止状态集合，F⊆K

参考书p76 例3.3

NFA可以有若干个开始状态，DFA仅一个

NFA的M是从K×∑到K的子集所组成集合的映象，而不是到K的映象，即映象M将产生一个状态集合（可能为空集），而不是单个状态

把一切开始状态S₁，S₂，S₃，...，Sₘ合并为一个新的开始状态[S₁，S₂，S₃，...，Sₘ]

从新开始状态出发，列表求出其他一切新状态

以状态名中包含原来终止状态名的一切新状态作为新终止状态

构造DFA N`

死状态为输入任何字符a都转化到本身而不能从它达到终止状态的那些非终止状态

无用状态为不可能从开始状态达到的状态

ε与∅都是∑上的正则表达式，这里ε是空串，而∅是空集

对于任何的a∈∑，a是∑上的正则表达式

如果e₁与e₂是∑上的正则表达式，则（e₁）、e₁e₂、e₁|e₂与{e₁}都是∑上的正则表达式

零正则表达式

单位正则表达式

交换律

结合律

分配律

书p88

无左递归

无回溯

如果X∈Vₜ，则FIRST（X）={X}

如果X∈V៷，并存在规则X::=T...，T∈Vₜ，则把T添入FIRST（X），如果存在规则X::= ε,则把 ε也添入其中

如果存在规则X::=X₁X₂...Xₖ,则对于满足下列条件的一切i（1≤i≤k），把FIRST（Xᵢ）中的每一个非ε符号添入FIRST（X）。该条件是：X₁,...Xᵢ₋₁都是非终结符号，且FIRST（Xⱼ），包含ε，j=1,2,...,i-1（即X₁X₂...Xᵢ₋₁=>*  ε）。如果ε∈FIRST（Xⱼ），j=1,2，...，k，则把ε添入FIRST（X）

#∈FOLLOW（Z），Z是文法识别符号

如果存在规则U::=xWy,则FIRST（y）中除ε外的一切符号都属于FOLLOW（W），其中W∈V៷

如果存在规则U::=xW或U::=xWy,其中FIRST（y）包含ε（即y=>*  ε）,则FOLLOW（U）中的一切符号都属于FOLLOW（W），其中W∈V៷

对文法的每个规则U::=u,执行步骤2与步骤3

对每个终结符号a∈FIRST（u），让A[U][a]='U::=u'

如果ε∈FIRST（u），则对FOLLOW（U）中的每个终结符号b或#，让A[U][b]='U::=u'或A[U][#]='U::=u'

把A的每个未定义元素置为ERROR（用空白表示）

每步被规约的总是最左的简单短语

动作

容易构造，查看一切规则的右部，是否包含TⱼTᵢ或TⱼVTᵢ形式的字符号串

书p152

G是压缩了的上下文无关文法（V៷，Vₜ，P，Z）

A是有穷属性集

R是有穷属性规则集

C是有穷条件集

时间效率

空间效率

机器相关优化

机器无关优化★

局部优化

全局优化

对中间表示代码进行优化

对目标语言代码进行优化

识别出循环

进行数据流信息的收集

对中间表示代码逐个进行分析，在基本块内进行局部等价变换，并基于控制流分析和数据流分析所获得的信息进行等价变换，从而实现循环的优化和其他全局优化