编译原理复习重点

1、 编译原理复习重点1. 闭包概念用 S* 表示S上的一切符号串（包括）组成的集合。*称为的闭包。 S上的除外的所有符号串组成的集合记为S+ 。 +称为的正闭包。 2. 文法概念文法GS=（ VN ， VT， P ，S）VT ：终极符集合，即不可再分的基本符号集合；VN：非终极符集合，表示语法成分；S：开始符，是语言定义的目标；P：规则式集合。3. 句子句型推导句型：若由S广义推导出x，则称x是文法的一个句型句子：若x是终极符号串，则称x是文法的一个句子例： 文法GE E E + T| T T T * F|FF ( E )|a句子a+a*a的最左推导:EÞE+T ÞT+T &

2、#222;F+T Þa+T Þa+T*F Þa+F*F Þa+a*F Þa+a*a句子：用符号a，+，*，(和)构成的算术表达式 (T+a)*a+F是一个句型；（a+a）*a是一个句子。句子a+a*a的最右推导: EÞE+T ÞE+T*F ÞE+T*a ÞE+F*a ÞE+a*a ÞT+a*a ÞF+a*a Þa+a*a4. 正规文法构造1)已知字母表å1=a，L1G=a2n|n>=1,构造G1；S Saa | aaS | aSa2)已知字母表

3、29;2=a,b，L2G=abna|n>=1,构造G2；SaBa Bb | bB | Bb3)已知字母表å3=0,1，L3G=0n1n|n>=1,构造G3；S0S1 | 014)已知字母表å4=a,b,c，L4G=aibjck | i,j,k>=1,构造G4；SABC Aa | aA | Aa Bb | bB | Bb Cc | cC | Cc5. 语法树和推导例: GS: SaASASbAASSSaAba最左推导：SÞaASÞaSbASÞaabASÞaabbaSÞaabbaa最右推导：SÞaAS

4、ÞaAaÞaSbAaÞaSbbaaÞaabbaa若一个句子对应两棵结构不同的语法树，则该句子具有二义性。6. 单词类型（1）关键字（2）标识符（3）常数（4）运算符（5）界符7. 构造状态转化图（左线性正规文法G【Z】-进，右线性正规文法G【S】-出）右线性：1.以每个非终结符为状态结点，开始符号对应初态S ；2.增设一个终态 Z；3.对于规则 AaB，画从状态 A 到 B 的弧，标为 a；4.对于规则 Aa，画从状态 A 到终态 Z 的弧，标为 a。左线性。例：G： SaA|bB AbB|aD|a BaA|bD|b DaD|bD|a|b8. 非有限自动

5、机>有限自动机（状态转换矩阵）DFA定义：一个确定的有穷自动机（DFA）M是一个五元组：M=（K，f，S，Z）其中1.K是一个有穷集，它的每个元素称为一个状态；2.是一个有穷字母表，它的每个元素称为一个输入符号，所以也称为输入符号表；3.f是转换函数，是在K×K上的映4.SK是唯一的一个初态；5.ZÌK是一个终态集，终态也称可接受状态或结束状态。例： DFA M=（S，U，V，Q，a，b，f，S，Q）其中f定义为：f（S，a）=U f（V，a）=Uf（S，b）=Vf（V，b）=Qf（U，a）=Qf（Q，a）=Qf（U，b）=Vf（Q，b）=Q矩阵表示：由NFA构造DF

6、A：令DFA的初态是NFA的全部初态，即S=S1 ,S2 ,Sn 设DFA的状态Q=Q1,Q2.Qk令（ Q，a）=(Qi ,a)i=1,2,3k重复，直到无新状态出现。若DFA状态Q中包含NFA终态，则Q是DFA的终态。例：9. 自顶向下的语法分析LL(1)文法定义：（也用于判别）对于 G 的每个非终结符 A 的任何两个不同的候选式 A|1)文法不含左递归2) FIRST()FIRST()=3) 如果Þ*，则 FISRT()FOLLOW(A)= 文法是 LL(1) 的充要条件性质：LL(1)文法是无二义的LL(1)文法不含左递归LL(1)文法不含公共左因子10. 求First（）集

7、，Follow（）集首终结符集First（a）定义和计算：（书p82）（书p83例4.6）FIRST（a）=a|a =>* ab,aVT, a, bV* 若a=>* 则规定FRIST(a)后随符号集：Follow（A）定义和计算：（书p84）（书p84例4.8） FOLLOW（A）=a|S =>* m A b且a FRIST（b），m V*， bV+ 11. LL(1)分析表例：（书p92-93例4.12）（1）证明是LL（1）文法（不含左递归。）（2）求候选式First（）集，Follow（）集，若First（）集为，即为Follow（）集（3）画表，填候选式12. 刻画“

8、可归约串”句型的短语：S =>* A且 A =>+ ，则称是句型相对于非终结符A的短语句型的直接短语：若有A ，则称是句型相对于非终结符A 的直接短语句型的句柄：一个句型的最左直接短语称为该句型的句柄13. “移进归约”法 把输入符号自左至右逐个移进分析栈，1、栈顶的符号串形成某个句型的句柄时就进行一次归约，即用相应产生式的左部非终结符替换当前句柄。2、若栈顶不是句柄则继续向栈中移进后续输入符号。3、不断重复这一过程，直到将整个输入串处理完毕。若此时分析栈只剩有文法的开始符号则分析成功，即确认输入串是文法的一个句子；否则，即认为分析失败。 自上而下分析法采用移进、归约、错误处理、接

9、受等四种操作14.素短语，最左素短语素短语：句型的至少含一个终结符且除它自身外不含其它素短语的短语最左素短语：（1）至少含一个终结符（2）除它自身外不含其它素短语（3）在句型中最左边15. 算符优先分析法算符文法与算符优先文法：如果文法 中不存在具有相邻非终结符的产生式，则称为算符文法（OG）。设G=（V，T，P，S）为OG，如果" a,bVT, ab,ab,ab 至多有一个成立，则称之为算符优先文法(OPG)FIRSTVT(A)的定义和计算定义：FIRSTVT(A)=b| AÞ+b或者AÞ+Cb计算：1）若Aàa或AàBa，则a FIRSTV

10、T(A)2)若AàB ，则FIRSTVT(A)= FIRSTVT(A) FIRSTVT(B) LASTVT(A) 的定义和计算定义：LASTVT(A)=b|AÞ+b或者AÞ+bC计算：1）若Aà.a或Aà aB，则a LASTVT(A)2)若AàB，则LASTVT(A)= LASTVT(A) LASTVT(B)构造算符优先关系表例：（书p105例4.19）可以用来判断OPG：若表中无冲突它是OPG16.算符优先函数（书p108）如果存在优先函数，则一定存在多个优先函数；也有许多优先函数表不存在对应的优先函数。使用优先函数有两个明显的好

11、处：一是节省空间；二是便于进行比较运算。17.LR分析法分析句型时，应用算符优先分析技术时，每步被直接归约的是最左素短语，而应用 LR 分析技术时，每步被直接归约的是句柄。LR(k)分析法可分析LR(k)文法产生的语言L ：从左到右扫描输入符号，R ：最右推导对应的最左归约(反序完成最右推导)k ：超前读入k个符号，以便确定归约用的产生式18. LR(0)分析定义和判断：如果一个文法的LR（0）的项目集规范族中不存在移进归约冲突或归约归约冲突（冲突项目）时，称这个文法为LR（0）文法，所构造的分析表为LR（0）分析表。LR(0)项目集规范族：例：（书p116例4.25）LR(0)分析表：例：（

12、书p118例4.28）19.SLR(1)分析定义和判断：如果一个文法的LR（0）的项目集规范族的项目集中存在的冲突都能用SLR(1)方法解决，称这个文法为SLR(1)文法，所构造的分析表为SLR(1)分析表。SLR(1)分析表：例：（书p122例4.30）20.属性文法X0 X1X2 X3.Xn Xi.a:=f(Xj.b, Xk.c)f是表达式1）若Xi是X0 ，b、c等是规则式右部符号或X0 的其它属性，则a是X0 的综合属性；2）若Xi是规则式右部符号，b、c等是规则式右部其它符号或X0 的属性，则a是Xi 的继承属性；固有属性（单词属性）：语言中的标识符、常数、常量，它们的属性是用户给定

13、的、不变的。综合属性:依赖于其子结点的属性；仅仅使用综合属性的属性文法称为S-属性文法。继承属性:依赖于其父结点或兄弟结点的属性。21.注释分析树自底向上翻译方法：对S_属性文法自底向上分析时，计算属性值设一属性栈val,属性和符号一起做移入-归约归约时，新属性值由栈中句柄符号的属性值计算设归约前val栈顶位置是top,归约后val栈顶位置是ntop， ntop=top-r+1注释分析树见书p153图5.2，会画！22.中间代码后缀式（逆波兰式）定义：（1）E（常、变量）的后缀式为E自身（2）E1 op E2 的后缀式为E1E2op（3）(E)的后缀式为E的后缀式 三地址代码：一般形式 x := y op z其中 x, y, z 为变量名、常数或编译产生的临时变量四元式（op, y, z, x）三元式（op, y, z）种类：x := y op z 双目运算 x := op y 单目运算 x := y 赋值语句三地址语句的四元式、三元式表示：例：（书p151例5.4）24. 高级语言的控制结构顺序 begin 语句; 语句； end条件 if_then_el