1.解释程序：不生成目标代码编译程序：生成目标代码2.编译程序组成：8个分析< 前端>：(词法分析程序、语法分析程序、语义分析程序、中间代码生成程序) 综合< 后端>：（代码优化程序、目标代码生成程序）贯穿始末：表格管理程序、出错处理程序3.文法四元组：终结符号集合Vt 、非终结符号集合Vn、产生式集合P、识别符号(开始符号)SV T∩V N＝Φ文法-> 语言（推导、规约）唯一；语言-> 文法（凑规则）不唯一。

4.文法分类：0型文法(短语结构文法)：左侧至少含有一个非终结符1型文法(上下文有关文法)：左侧长度<= 右侧长度S->ε除外，S不能出现在右侧2型文法(上下文无关文法)：左侧只能有一个非终结符( 语法分析)3型文法(正规文法)：A-> aB A->a 右线性；( 词法分析)A->Ba 或A->a 左线性（看非终结符位置）5.A*＝A0 ∪A+ A0 ＝{ε} !={ } ＝Φ空集A+ ＝AA* ＝A*A6.句型：符号串x是从识别符号S推导出来的，x称为一个句型句子：x仅由终结符号组成，仅含终结符号的句型是一个句子短语：子树的末端（叶子）从左至右连成的串（包括整棵语法树）简单子树：只含有单层分枝的子树直接短语( 简单短语)：由简单子树的叶子组成句柄：最左边的直接短语（不一定含终结符）素短语：至少含有一个终结符的短语，并且除它自身之外不再含任何更小的素短语最左素短语：最左边的素短语短语：P（相对于T、E）、P+T（相对于E）、i（相对于P、F）、P+T+i（相对于E）直接短语：P、i 句柄：P (最左边的直接短语)素短语：P+T 、i （至少含有一个终结符的短语）最左素短语：P+T7.二义性文法：有两个不同的最左推导或有两个不同的最右推导或能产生两棵语法树8.文法产生式正规式规则1 A→xB B→y A = xy规则2 A→xA|y A = x*y 右线性A→Ax|y A = yx* 左线性规则3 A→x A→y A = x|y9.DFA 初态唯一，转换函数为单值映射表示方式：转移矩阵、状态转换图状态转换图上若存在一条从初态到某一终态的道路，且这条路上所有弧的标记符连成的字符串为t，则称t被DFA接受。

10.NFA初态可为多个，转换函数为多值映射确定化：与某一NFA等价的DFA不唯一1.状态集合I的ε-闭包2.move函数最小化：消除多余状态和合并等价状态多余状态：从自动机的开始状态出发，任何输入串也不能到达的那个状态；或者从这个状态没有通路到达终态。

11.左公因子显式左公因子提取若A→αβ1|αr，则将其改写为：i.A→α(β1|r)ii.或引入新非终结符A→αA’A’→β1|r隐式左公因子:产生式右部以非终结符开始用该非终结符的右部以终结符开始的产生式去替换它，再提取S→aSd|Ac A→aS|b把A的产生式代入S中：S→aSd|aSc|bcS→aS S’S’→d|c S→bc12.左递归1.简单左递归：消除左递归改写为右递归A→Aα|βA→βA’A’→αA’|ε2.间接左递归非终结符号排序(出现频率高的排后面)左部非终结符下标 > 右部时改写（替换右部）消除直接左递归13.自顶向下：LL（1）FIRST：A→X1X2X3…Xn若X1 ⇒εX2 ⇒εX3 !⇒ε后面不用管则FIRST（A）= First（X1）-{ε} U First（X2）-{ε} First（X3）若全能推出ε则先求所有FIRIST（X）-{ε}并集再并上{ε} FOLLOW：•(a)设S为开始符号，则#∈FOLLOW(S)•(b)若有产生式A→αBβ，β !⇒* ε，则FIRST(β) 加至FOLLOW(B)•(c)若β⇒*ε(即ε∈FIRST(β)），则FIRST(β)-{ε}和FOLLOW(A)加至FOLLOW(B) SELECT：A→α的可选集SELECTα !⇒ε，则SELECT(A→α)= FIRST(α)*α⇒ε，则SELECT(A→α)= FIRST(α)-{ε}∪FOLLOW(A)*一个上下文无关文法G是LL(1)文法的充要条件是：对于G的每个非终结符号A的任何两个不同产生式A→α，A→β满足：▪SELECT(A→α)∩SELECT(A→β)=∅▪α、β不同时推导出εLL（1）的含义：第一个L：从左到右扫描输入串第二个L：分析过程中用最左推导1：只需向右看1个输入符号（Look ahead)便可确定选用哪个产生式进行推导–LL(1)文法是无二义的。

–LL(1)文法不含左递归。

14.自底向上：算符优先、LR（0）、SLR（1）、LR（1）、LALR（1）15.规范归约：最右推导的逆过程(最左归约）•最右推导是规范推导右句型(最右推导可得的句型）是规范句型•规范句型的特点：句柄后（右边）不会出现非终结符•规范归约的中心问题是：如何寻找或确定一个句型的句柄。

•可归约串：•最左素短语(算符优先分析法）•句柄(LR分析法)算符优先分析法不是规范归约方法。

16.若文法G中不存在右部含有相邻非终结符的产生式，则G为算符文法算符优先分析的可归约串是句型的最左素短语。

起决定作用的是相邻两个终结符的优先关系a≡b 当且仅当G中存在产生式规则A→…ab…，或A→…aBb…a<⋅b 当且仅当G中存在产生式规则A→…aB…，且B⇒+b…或B⇒+Cb…a⋅>b 当且仅当G中存在产生式规则A→…Bb…，且B⇒+…a或B⇒+…aC 不允许有a<·b、a≡b、a·>b中的两种关系同时存在17.FIRSTVT计算如下：若有产生式A→a…或A→Ba…则a∈FIRSTVT(A) A左侧的终结符< FIRSTVT(A)若a∈FIRSTVT(B)且有产生式A→B…(B后面没有紧跟一个终结符)则a∈FIRSTVT(A)A->a.......，即以终结符开头，该终结符入FirstvtA->B.......，即以非终结符开头，该非终结符的Firstvt入A的FirstvtA->Ba.....，即先以非终结符开头，紧跟终结符，则终结符入FirstvtLASTVT计算如下：若有产生式A→…a或A→…aB则a∈LASTVT(A) A右侧的终结符< LASTVT (A)若a∈LASTVT(B)且有产生式A→…B则a∈LASTVT(A)A->.......a，即以终结符结尾，该终结符入LastvtA->.......B，即以非终结符结尾，该非终结符的Lastvt入A的LastvtA->.....aB，即先以非终结符结尾，前面是终结符，则终结符入Lastvt18.LR分析法的归约过程是规范推导的逆过程，所以LR分析过程是一种规范归约过程无回溯的“移进-归约”方法符号栈中的符号是规范句型的前缀，且不含句柄以后的任何符号(活前缀)ACTION 移进归约接受出错ACTION[i,a]=空白出错ACTION[i,a]=acc 符号栈中仅有#和文法开始符号S，输入串仅为#，分析结束。

19.一个句型的某个前缀的后缀是该句型的句柄，则这个前缀称为该句型的可归前缀。

一个规范句型的一个前缀，若不含句柄之后的任何符号，则称它为该句型的一个活前缀。

S -> a Ac. B e 项目中.之前a Ac为活前缀20.A→α⋅ aβ,a∈V T 移进项目A→α⋅ Bβ,B∈V N 待归约项目A→α⋅归约项目特别地：A→ε只有A→⋅S’→S, S’→S ⋅接受项目以上项目称作LR(0)项目。

21.LR(0) 项目集规范族（识别G的活前缀的DFA)如果不存在移进-归约冲突，归约-归约冲突，则称它是LR(0)文法。

拓展文法的目的：使文法只有一个以识别符号作为左部的产生式，从而使构造出来的分析器有唯一的接受状态。

22.对给定的文法，利用LR(0)方法判断符号串是否为该文法的句子：1.扩充文法为拓广文法；2.构造识别此文法的全部活前缀的DFA，即构造LR(0)项目集规范族；3.判断是否为LR(0)文法；4.是构造LR(0)分析表利用LR分析算法分析符号串。

5.否，做其他处理。

23.SLR（1）对所有非终结符都求出其FOLLOW集合发生冲突时，归约项目左部终结符FOLLOW集与移进项目.后的终结符交集为空时，才能按此规约项目的产生式进行归约。

–LR(0)分析对所有终结符均采用归约动作–SLR(1)分析参考FOLLOW集，以确定归约动作。

24.Follow集无法解决移进-归约冲突或归约-归约冲突，考虑后继符25.归约动作的选择：a)LR(0)分析考虑所有终结符b)SLR(1)分析参考FOLLOW 集，为了确定归约c)LR(1)分析仅考虑LR(1)项目中的后继符（归约展望集，向前搜索符）拓展文法的后继符为#，即[ S’->S , #] 为初态集的初始项目，S后first(ε，#) = {#}LR（1）项目集规范族中，每个状态中添加新的产生式时，需求产生式左部字母后面的First集作为新产生式的后继符;否则后继符照抄前一个状态的I : A->a.BβB->.e ，需求出First（β）作为B->.e的后继符26.任何二义文法决不是一个LR文法LL(k)文法都是LR(k)文法。

27.a=b*c+b*d 逆波兰式：abc*bd*+= （算符优先的一个应用）无括号; 运算对象顺序不变; 运算符号的位置反映运算顺序。

◆三元式运算结果用三元式编号表示b*c （*，b，c）◆四元式运算结果用临时变量表示b*c （*，b，c，t）a:=b*c+b*d的三元式表示a:=b*c+b*d的四元式表示注意最后一步写法四元式直观写法：t1:=b*c t2:=b*d t3:=t1+t2a:=t3中间代码优化处理时，四元式比三元式方便的多28.终结符只有综合属性，由词法程序提供；非终结符可有综合也可有继承属性，但文法开始符号无继承属性。

29.按优化所涉及的程序范围可分为三种级别：局部优化、循环优化、全局优化。

局部优化指在只有一个入口一个出口的基本块内进行的优化。

30.判定入口语句的规则：(a)代码序列的第1个语句。

(b)条件或无条件转移语句的转移目标语句。

If… goto Goto(c)紧跟在无条件转移语句或条件转移语句后面的语句。

例：B1 -> (1) read x(2) read yB2 -> (3) r:=x mod y(4) if r=0 goto (8)B3 -> (5) x:=y(6) y:=r(7) goto (3)B4 -> (8) write y(9) halt基本块i和基本块j满足如下条件之一,则从i引一条有向边到j 。