《《编译原理》复习纲要河南工业大学课件.ppt》由会员分享，可在线阅读，更多相关《《编译原理》复习纲要河南工业大学课件.ppt（50页珍藏版）》请在三一办公上搜索。
1、编译原理复习纲要2017.5,2,文法和语言,符号和符号串,文法的类型,文法和语言的形式化定义,句型分析语法树文法和语言的二义性,上下文无关文法,文法的定义推导的定义语言的定义,第三章,字母表和符号串符号串的运算集合的闭包运算,第三章：1、已知文法，为句子建立语法树，写出最左推导和最右推导。注意：推导用 表示概念：最左推导：在推导的任何一步，都是对当前句型的最左边的非终结符进行替换。最右推导：在推导的任何一步，都是对当前句型的最右边的非终结符进行替换。2、指出句子/句型的短语、直接短语和句柄。概念：短语子树的末端结点从左到右排列形成的符号串是相对于子树根的短语。直接短语简单子树(只有父子两代)
2、的末端结点从左到右排列形成的符号串是相对于简单子树的直接短语。句柄最左的简单子树的末端结点从左到右排列形成的符号串。注意，相同的字符按顺序加下标来区别。,4,T+T,F+T,a+T*F,E+T,E,a+F*F,a+a*F,a+a*a,练习：EE+TT TT*FF F(E)a 写出对符号串w=a+a*a的最左、最右推导过程。,E+T*F,E+T*a,E+F*a,E+a*a,E+T,E,T+a*a,F+a*a,a+a*a,最左推导,最右推导,EE+TT+TF+T a+Ta+T*F a+F*Fa+a*F a+a*a,EE+TE+T*FE+T*a E+F*aE+a*a T+a*aF+a*aa+a*a,
3、a+T,+E a+a*a,5,练习：对表达式文法GE，求句子a+a*a的全部短语，直接短语，句柄。方法：画出该句型或句子的语法树即可求得。,注意:符号串中有多个a所以，要加下标区分a，句子变为a1+a2*a3短语：a1 a2 a3 a2*a3 a1+a2*a3 直接短语：a1 a2 a3句柄：a1,E,E,+,T,T,F,a1,T,*,F,F,a2,a3,注意：短语中容易漏掉a1+a2*a3,3、根据要求构造文法方法：根据语言中符号串的特征写文法，练习：为只包含数字、,的表达式，例如 9 2 5等构造一个文法，使得 和运算满足右结合，的运算优先级高于。提示：参考：算数表达式的文法E E+T|T
4、 T T*F|F F F 0|1|2|.9通过构造一个算术表达式的语法树去理解结合性和运算优先性与语法树的层次，进而思考左、右递归产生式与运算符的结合性的关系。答案：E T E|TT F T|FF 0|1|2|.9,词法分析,自动构造工具,正规集,正规式,有穷自动机（NFA DFA),正规文法,第四章 知识结构,第四章,1、用自然语言给出正规式所描述的语言。问题：看得懂，但是不太会用自然语言较好的表达。说明：所谓用自然语言描述就是解释字符串的性质，一般情况下是已经有了形式化描述。如：10*1：首尾是1中间有零或若干个0的01串。(0|1)*011(0|1)*：至少含一个011的01串。注意：绝
5、对不允许用正规式形式表示，因为正规式已经给出。2、给出自然语言对应的正规式。如：a后跟随大于等于0个b的所有符号串。问题：拿到这类题该怎样思考，然后去解决？思路：分析题意，从最简单的例子考虑，然后找出统一规律。1）a,ab,abb,abbb2）正规式：ab*,9,练习：1、正规集:a后跟随大于等于0个b的所有符号串 正规式：ab*2、正规集:所有含有两个相继a或b的符号串 正规式：(ab)*(aabb)(ab)*3、正规集:空串和任何长度为偶数的a,b符号串 正规式：(aabaabbb)*4、正规集:任何以abb结尾的a,b符号串 正规式：(ab)*abb,自动机基础,简单有限自动机的构造,给
6、定一右线性文法，构造有限自动机FA,注意：1、新增终态Z2、形如 A 的产生式,11,例GS:SaA SbB S AaB AbA BaS BbA B,B,A,b,SaA,SbB,S,AaB,AbA,BaS,BbA,B,2 有限自动机的确定化。（子集法）,对给定的NFA N构造一张表，表的构成如下：（1）设字母表=a1,ak，表的每行含有k+1列。（2）置首行首列为_closure(S)，为方便叙述设为状态T。（3）从T开始，对每个字符a，求两个运算 move(T,a)（为叙述方便将结果 记为B)_closure(B)（为叙述方便将结果记为C)（4）检查该行所有的状态子集C，将未出现在第一列者填
7、入到后面空行的第一列。（5）重复(3)(4)直到第一列中状态子集不再扩大为止(在第i+1列上的所有状态子集均已在第一列上出现)。（6）将该状态转换矩阵中所有状态子集重新命名，得到状态转换矩阵，其所示的是与给定的NFA等价的DFA（未化简的DFA）。注意 DFA M的初态为该表第一行第一列的状态。DFA M的终态为含有原NFA N的终态的状态子集。,13,-closure(0)=0,1,2,4,7=A,初态,练习：NFADFA要求：书写格式如下表,3,8,6,1,2,4,7,0,1,2,4,7,B,5,6,1,2,4,7,B,5,9,6,1,2,4,7,A,B,C,D,move(A,a)=3,8
8、,-closure(3,8)=3,8,6,1,2,4,7,move(B,a)=3,8,-closure(3,8),终态,C,move(A,b)=5,move(B,b)=5,9,-closure(5)=5,6,1,2,4,7,-closure(5,9)=5,9,6,1,2,4,7,D,move(E,b)=5,B,B,E,B,C,move(D,b)=5,10,move(C,a)=3,8,move(D,a)=3,8,move(E,a)=3,8,-closure(3,8),-closure(3,8),-closure(5,10)=5,10,6,1,2,4,7,-closure(3,8),-closur
9、e(5),move(C,b)=5,C,-closure(5),5,10,6,1,2,4,7,E,注意：表中每一表项，需要明确写出move和-closure的值,14,B,D,C,E,A,DFA M,b,a,最后画出DFA的转换图,15,1、首先把状态集S分成终态集和非终态集,形成初始划分：=Z，KZ；2、对中每个子集进行如下变换：设含有m个子集,=I1,I2,Im,则对每一个Ii和每一个a：考察：Iia=f(Ii，a)，如Iia中的状态分别落于中P个不同的子集，则：Ii将被P个更小的状态子集Ii1,Ii2,Iip 所细分。令细分后所得的状态集合为new；3、重复步骤2直至所含的子集数不再增加为
10、止，即new=;4、对中的每个子集Ii，从中任选一个状态作为代表，确定新自动机的初态、终态集和转换函数。若某子集包含原有的初态，则此代表状态即为最小化后M的初态；若某子集包含原有的终态，则此代表状态即为最小化后M的终态。,3、DFA的最小化算法:-划分法,16,练习：,结果：=S,B,A,C,D,E,F最小化的DFA如右图：,S,B，A,S,B,解：答题格式如下：,a,b,b,:S,A,B，C,D,E,F,不可拆分,17,把转换图的概念拓广，每条弧上可以用一个正规式标记。第一步:改造M，使其只有一个初态和终态。在M的转换图上加进x、y两个结。从x用弧连接到M的所有初态结点，从M的所有终态结点用
11、弧连接到y，从而构成一个新的NFA M，L(M)=L(M)。第二步:逐步消结。消去NFA M中的状态结点，直至剩下x、y为止。在消结的过程中，逐步用正规式标记弧。消结的过程是直观的，只需反复使用下面的替换规则。第三步:x至y弧线上的标记便是上的r，它就是M上所接受的正规式。,4、FA 正规式r（消结法）,18,替换规则,19,1,3,1,3,|,1,(|)()*,3,练习：,结果：(|)()*,重点理解消除状态2后产生的符号串,第五章 LL(1)分析法提取左公因子：一般：A1|2|n|r1|rm 改写：AA|r1|rm A1|2|n若1，2 n仍有公共左因子，则再次提取，直到无公共左因子为止。
12、消除直接左递归 AA1|A2|Am|1|2|n 消除左递归改写为右递归：A1A|2A|nA A1A|2A|mA|,21,要求无环路A+A 和 无-产生式。算法步骤如下：1.把非终结符按某一顺序排序为A1，A2，An。2.for(i=1；i=n；i+)/处理全部非终结符 3化简由（2）所得到的文法。,消除间接左递归 代入法 P89,for(j=1；j=i-l；j+)if(Aj1|2|k，AiAj)把AiAj改写成 Ai1|2|k；消除关于Ai-产生式的直接左递归；,例如A3A1b则改写A3，即：左部非终结符下标右部时改写,22,解：解题过程按如下步骤书写：1)非终结符号排序为S，Q，R2)对S：
13、Q的序号2大于S的序号1，不处理；对Q：R的序号3大于Q的序号2，不处理；对R：S的序号1小于R的序号3，所以改写RSa；用(1)的右部取代S得到：RQca|ca|a，记为(4)；此时，(4)式中Q的序号2小于R的序号3，所以改写RQca。用QRb|b的右部取代Q，得到RRbca|bca|ca|a，记为(5)式；(5)式中出现直接左递归，消除直接左递归R(bca|ca|a)R RbcaR|3)最终文法为：SQc|c QRb|b R(bca|ca|a)R RbcaR|,练习：对下面文法消除左递归：Gs：(1)SQc|c(2)RSa|a(3)QRb|b,自己完成练习 提取左公因子和消除左递归。注意
14、：解题过程按上页的例子写。,(1)AaABe|a BBb|d(2)SAS|b ASA|a,要判别一个上下文无关文法是否是LL(1)文法分为六步：,（1）消除文法的左递归和左公因子。（2）求能推出的非终结符集。（3）计算每个非终结符A的FIRST集。（4）计算每个非终结符A的FOLLOW集。（5）计算每个产生式A的SELLECT集。（6）按LL(1)文法的定义判别。如果没有产生式第（2）和（4）步可以省略。,1求出能推出的非终结符,首先建立一个以文法的非终结符个数为上界的一维数组，其数组元素为非终结符，对应每一个非终结符有一个标志位，用来记录能否推出。其值有三种情况“未定”、“是”、“否”。用一
15、个数组X 来表示这些状态。计算出能推导出的非终结符的步骤如下：（1）将数组X 中对应的每一个非终结符的标记记为“未定”。（2）扫描文法中的产生式。1)删除所有右部含有终结符的产生式。若这使得以某一非终结符为左部的所有产生式都被删除，则将数组中对应的非终结符的标记值改为“否”，说明该非终结符不能推出。2)若某一非终结符的某一个产生式右部为，则将数组中对应该非终结符的标志置为“是”，并从文法中删除该非终结符的所有的产生式。（3）扫描产生式右部的每一个符号。1)若所扫描到的非终结符号在数组中对应的标志是“是”，则删去该非终结符，若这使产生式右部为空，则对产生式左部的非终结符在数组中对应的标志改为“是
16、”，并删除该非终结符为左部的所有的产生式。2)若所扫描到的非终结符号在数组中对应的标志是“否”，则删除该产生式。若这使得产生式左部非终结符的有关产生式都被删除，则把在数组中该非终结符对应的标志改成“否”。（4）重复（3），直到扫描完一遍文法的产生式，数组中的非终结符对应的特征再没有改变为止。,练习：求出能推出的非终结符SAB SbC A Ab BBaDCAD Cb DaSDc,第一次扫描,是,是,否,第二次扫描,是,否,结果：,是,是,是,是,否,否,27,定义 令GS=(VT，VN，S，P)，则 P76FIRST()=a|*a，aVT，、V*若*，则FIRST()对每一文法符号X，计算FIR
17、ST(X)过程如下：(1)若XVT，则 FIRST(X)=X；(2)（直接收取）若XVN，且有产生式Xa，aVT，则把a加入到 FIRST(X)中；若XVN，且有产生式X，则把加到 FIRST(X)中；(3)（反复传送）若XVN，有产生式XY1Y2Yn，Y1,Yi都是非终结符，且对于任何j，1ji-1，FIRST(Yj)都含有，则把所有FIRST(Yj)中的非元素都加到FIRST(X)中；FIRST(Yi)的元素加入到FIRST(X)特别地，若所有FIRST(Yj,j=1,2,n)均含有，则把和FIRST(Yj)中的所有非元素都加到FIRST(X)中.(4)反复使用(2)-(3)，直到FIRS
18、T(X)不再增大为止。,2、FIRST集（难点）终结首符集P80FIRST集的求法（从左向右看）,例GS:SAB|bC Ab|BaD|CAD|b DaS|c 求出每个非终结符的FIRST集,FIRST集,1、已求出能推出的非终结符集T为A,B,S2、求出FIRST集,b,b,a,b,a，c,a,a,c,A,B,C,D,S,（敛）,演草部分：FIRST(S)=(FIRST(A)-)(FIRST(B)-)bFIRST(A)=b FIRST(B)=aFIRST(C)=(FIRST(A)-)FIRST(D)b FIRST(B)=ac,29,计算过程如下：P 82(a)设S为开始符号，则#FOLLOW(
19、S)(b)若有产生式A B，*则FIRST()加至FOLLOW(B)(c)若*(即FIRST()）(可理解为A B)则FIRST()-和FOLLOW(A)加至FOLLOW(B),FOLLOW集求法(从右向左看齐）,练习：GS：SAB|bC Ab|BaD|CAD|b DaS|c求非终结符的FOLLOW集,准备工作：已经求出推出的非终结符，FIRST集,#,#,#,a，#,#,FOLLOW集,，c,结论：FOLLOW(S)=#FOLLOW(A)=a,c,#FOLLOW(B)=#FOLLOW(C)=#FOLLOW(D)=#,FOLLOW(A)=FIRST(B)-FOLLOW(S)FIRST(D),F
20、OLLOW(S)=#FOLLOW(D),D,C,B,A,S,FOLLOW(B)=FOLLOW(S),FOLLOW(C)=FOLLOW(S),FOLLOW(D)=FOLLOW(B)FOLLOW(C),演草部分：,31,4、判断是否是LL（1）文法产生式的可选集SELECT P78,A 的可选集SELECT*若右部串，则SELECT(A)=FIRST()*若右部串，则SELECT(A)=FIRST()-FOLLOW(A),分析表是一个二维数组MA，b，其中A是非终结符号，b是终结符号或是符号#。1)对文法G的每个产生式A执行第2步；2)对每个终结符号bSELECT(A)，把A加至MA，b中；MA，
21、b内容为一条关于A的产生式。其中：b 为Vt或#。3)把所有无定义的MA，b标上错误标记或用空白表示。,结论：当分析表中每一项无冲突时，为LL(1)文法。,练习：判断文法是否LL(1)文法，写出原因,SELECT(F(E)=(,SELECT(ETE)=（，i,SELECT(E+TE)=+,SELECT(E)=),#,SELECT(TFT)=(，i,SELECT(T*FT)=*,SELECT(T)=+,),#,SELECT(Fi)=i,+TE,TE,TE,FT,FT,*FT,(E),i,因为上面的分析表中每一项没有冲突，所以，该文法是LL（1）文法。,33,XVN,#S进栈，当前输入符送a,上托
22、栈顶符号放入X,若产生式为XX1X2Xn按逆序即XnX2X1入栈,出错,X=#,XVT,X=a,MX,a是产生式吗,出错,X=a,读入下一个符号,结束,是,是,是,是,否,否,否,否,否,是,3.LL(1)分析程序的控制程序,初始格局：(#S，输入串#),终止格局：(#，#),图中符号说明如下：“#”句子括号即输入串的括号“S”文法的开始符号“X”存放当前栈顶符号的工作单元a存放当前输入符号a的工作单元,1,#E,2,3,TF,4,ETE,TFT,i,Fi,i匹配,5,T,6,#E,7,8,ET+,E+TE,+匹配,#ET,9,TF,TFT,Fi,10,#ET,i匹配,11,i,12,#E,T
23、*FT,*匹配,13,14,15,16,#ETF,Fi,#ET,i匹配,#E,#ET,T,E,17,#,接受,对输入串i+i*i#进行分析,#,ET,i+i*i#,i+i*i#,i+i*i#,i+i*i#,+i*i#,+i*i#,+i*i#,i*i#,i*i#,i*i#,*i#,*i#,i#,i#,#,#,#,#E,#ET,#ET,#,#E,#ET,TF*,i,注意：红色部分为易出错部分,练习,以作业题为主，练习完整的过程1、能推出的非终结符集。2、求非终结符的FIRST、FOLLOW集。3、构造分析表。4、判断是否LL（1）文法。5、若是LL(1)文法，则写出句子的分析过程。,第六章 算符优
24、先文法1、会写表达式的逆波兰式,练习：求下述表达式的逆波兰式：,(a+b/d)*e,a,b,d,/,+,e,*,注,根据逆波兰式特点：,运算对象顺序不变；,运算符紧跟运算对象之后。,可直接写出：,练习以下公式的逆波兰式a+(b-c)*d+e/fa*b/ce*da+(-b),38,FIRSTVT计算如下：P111初值：若有产生式Aa或ABa 则aFIRSTVT(A)迭代：若aFIRSTVT(B)且有产生式AB 则aFIRSTVT(A)LASTVT计算如下：P111初值：若有产生式Aa或AaB 则aLASTVT(A)迭代：若aLASTVT(B)且有产生式AB 则aLASTVT(A),根据定义直观计
25、算FIRSTVT集、LASTVT集,2.会构造算符优先分析表,39,例如：求下面文法的每个非终结符的FIRSTVT和LASTVT。准备工作：增加E#E#E#E#EE+TETTT*FTFFPFFPP(E)Pi,#,(,i,#,i,),+,*,*,(,i,(,i,(,i,+,*,*,i,),i,),i,),40,构造优先表的算法：P114准备工作：对文法开始符号S，增加S#S#for(每个产生式AX1X2Xn)for(i=1;iXi+1;,41,(0)E#E#(1)EE+T(2)E T(3)TT*F(4)T F(5)FPF(6)F P(7)P(E)(8)P i,(1)LASTVT(E)+,(0)L
26、ASTVT(E)#,(1)+FIRSTVT(T),(3)*FIRSTVT(F),(7)(FIRSTVT(E),(5)FIRSTVT(F),(3)LASTVT(T)*,(5)LASTVT(P),(7)LASTVT(E),(0)#FIRSTVT(E),练习,P122 第4题1、求FIRSTVT和LASTVT集2、求分析表,第七章 LR分析法,证明文法是SLR(1)文法。1、求出LR(0)的DFA。2、对于有冲突的状态，写出利用FOLLOW集的计算，可以解决冲突，从而证明该文法是SLR（1）文法。（计算归约项非终结符的FOLLOW，与可移进终结符比较）；3、写出 SLR（1）分析表。4、会求LR（1
27、）的DFA的初始状态（LR(1)项目集规范族的I0）,练习：P162 例题2,1、写出LR(0)的DFA2、找出DFA中冲突项，写出冲突项的解决方案，归约和归约冲突、归约和移进冲突FOLLOW集3、冲突解决，写出改进的SLR(1)分析表.,扩充如何判断一个文法是哪种LR文法P166第6题,方法2：1、先构造LR(1)的DFA和分析表；2、若有冲突，则不是LR(1)文法，结束。3、无冲突，合并同心集，4、合并同心集，无冲突，则为LALR(1)文法；5、合并同心集，有冲突，则为LR(1)文法；6、若是LALR(1)文法，构造分析表，看一行中归约的状态；若有归约，则把该行都填上归约，若无冲突，则为L
28、R(0)文法；若有冲突，则求FOLLOW集，能否解决，能解决，是SLR(1)文法，否则LALR(1)文法。,P150 判断下面文法是哪种类型的LR文法？(0)SS(1)SL=R(2)S R(3)L*R(4)L i(5)R L解：(1)构造LR(1)的DFA,(2)构造LALR(1)的分析表,(3)解决冲突，得到如下分析表,因为FOLLOW(R)=#,=，在I2中，FOLLOW(R)=，所以I2的“=”的冲突没解决，所以该文法不是SLR(1)文法，是LALR(1)文法 P150,第8章 语法制导翻译,练习：为文法：S L.L|LL L B|BB 0|1 9给出一个语法制导定义，要求输出S的十进制的值。解：设属性val记录S、L、B的值。属性len记录L的位数。Print函数输出S的十进制的值S L1.L2 S.val=L1.val+L2.val/10L2.len;print(S.val)S L S.val=L.val;print(S.val)L L1 B L.val=L1.val*10+B.val;L.len=L1.len+1;L B L.val=B.val L.len=1B 0 B.val=0;B 1 B.val=1;,第11章 代码优化,把程序划分为基本块，并作出程序流图。基本块的划分，关键找入口语句。流图的画法,
