1、编译原理复习纲要2017.5文法和语言文法和语言符号和符号串符号和符号串文法的类型文法的类型文法和语言的文法和语言的形式化定义形式化定义句型分析句型分析语法树语法树文法和语言的二义性文法和语言的二义性上下文无关文法上下文无关文法文法的定义文法的定义推导的定义推导的定义语言的定义语言的定义第三章第三章字母表和符号串字母表和符号串符号串的运算符号串的运算集合的闭包运算集合的闭包运算第三章：1、已知文法，为句子建立语法树，写出最左推导和最右推导。注意：推导用 表示概念：最左推导：在推导的任何一步，都是对当前句型的最左边的非终结符进行替换。最右推导：在推导的任何一步，都是对当前句型的最右边的非终结符进
2、行替换。2、指出句子/句型的短语、直接短语和句柄。 概念：v短语子树的末端结点从左到右排列形成的符号串是相对于子树根的短语。v直接短语简单子树(只有父子两代)的末端结点从左到右排列形成的符号串是相对于简单子树的直接短语。v句柄最左的简单子树的末端结点从左到右排列形成的符号串。v注意，相同的字符按顺序加下标来区别。 T+T F+T a+T*F E+T E a+F*F a+a*F a+a*a练习：练习：EE+T T TT*F F 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
3、F+a*a a+a*a最左推导最左推导最右推导最右推导EE+TT+TF+T a+Ta+T*F a+F*Fa+a*F a+a*aEE+TE+T*FE+T*a E+F*aE+a*a T+a*aF+a*aa+a*a a+T +E a+a*a练习：对表达式文法练习：对表达式文法GE，求句子，求句子a+a*a的全部短的全部短语，直接短语，句柄。语，直接短语，句柄。方法：画出该句型或句子的语法树即可求得。方法：画出该句型或句子的语法树即可求得。注意注意:符号串中有多个符号串中有多个a所以，要加下标区分所以，要加下标区分a，句子变为句子变为a1+a2*a3短语短语： a1 a2 a3 a2*a3 a1+a2
4、*a3 直接短语直接短语： a1 a2 a3句柄句柄：a1EE+TTFa1T*FFa2a3注意：短语中容易漏掉注意：短语中容易漏掉a1+a2*a3n3、根据要求构造文法、根据要求构造文法方法：根据语言中符号串的特征写文法，方法：根据语言中符号串的特征写文法，练习：为只包含数字、练习：为只包含数字、 , 的表达式，例如的表达式，例如 9 2 5等构等构造一个文法，使得造一个文法，使得 和和 运算满足右结合，运算满足右结合， 的运算优先的运算优先级高于级高于 。q提示：参考：算数表达式的文法提示：参考：算数表达式的文法qE E+T |T T T*F |F F F 0|1|2 |.9q通过构造一个算
5、术表达式的语法树去理解结合性通过构造一个算术表达式的语法树去理解结合性和运算和运算优先性优先性与与语法树的层次，进而思考左、右递归产生式与语法树的层次，进而思考左、右递归产生式与运算符的结合性的关系。运算符的结合性的关系。n答案：答案：nE T E |TnT F T |FnF 0|1|2 |.9词法分析词法分析自动构造工具自动构造工具正规集正规集正规式正规式有穷自动机（有穷自动机（NFA DFA)正规文法正规文法第四章第四章 知识结构知识结构第四章1、用自然语言给出正规式所描述的语言。、用自然语言给出正规式所描述的语言。问题：问题：看得懂，但是不太会用自然语言较好的表达。看得懂，但是不太会用自
6、然语言较好的表达。说明：说明：所谓用自然语言描述就是解释字符串的性质，一般情况下所谓用自然语言描述就是解释字符串的性质，一般情况下是已经有了形式化描述。是已经有了形式化描述。如：如： 10*1：首尾是：首尾是1中间有零或若干个中间有零或若干个0的的01串。串。 (0|1)*011(0|1)* ：至少含一个：至少含一个011的的01串。串。注意：绝对不允许用正规式形式表示，因为正规式已经给出。注意：绝对不允许用正规式形式表示，因为正规式已经给出。2、给出自然语言对应的正规式。、给出自然语言对应的正规式。 如：如：a后跟随大于等于后跟随大于等于0个个b的所有符号串。的所有符号串。问题：问题：拿到这
7、类题该怎样思考，然后去解决？拿到这类题该怎样思考，然后去解决？思路：思路：分析题意，从最简单的例子考虑，然后找出统一规律。分析题意，从最简单的例子考虑，然后找出统一规律。1） a,ab,abb,abbb2）正规式：）正规式：ab *练习：练习：1、正规集、正规集: a后跟随大于等于后跟随大于等于0个个b的所有符号串的所有符号串 正规式：正规式：ab* 2、正规集正规集: 所有含有两个相继所有含有两个相继a或或b的符号串的符号串 正规式：正规式：(a b)*(aa bb)(a b)*3、正规集、正规集: 空串和任何长度为偶数的空串和任何长度为偶数的a,b符号串符号串 正规式：正规式：(aa ba
8、 ab bb)* 4、正规集、正规集: 任何以任何以abb结尾的结尾的a,b符号串符号串 正规式：正规式：(a b)*abb 自动机基础自动机基础 简单有限自动机的构造简单有限自动机的构造给定一右线性文法，构造有限自动机给定一右线性文法，构造有限自动机FAFA右线性文法右线性文法FAaVTa AVN A是一个状态是一个状态识别符号识别符号S初态初态新增终态新增终态ZAaB Aa ABtAZt注意：注意：1、新增终态、新增终态Z2、形如、形如 A 的产生式的产生式 AZ 例例GS: SaA SbB S AaB AbA BaS BbA B ZBAa abbabSSaASbBS AaBAbABaSB
9、bAB 2 2 有限自动机的有限自动机的确定化确定化。（子集法）。（子集法）对给定的对给定的NFA N构造一张表，表的构成如下：构造一张表，表的构成如下：（1）设字母表）设字母表= a1, ak ，表的每行含有，表的每行含有k+1列。列。（2）置首行首列为）置首行首列为_closure(S)，为方便叙述设为状态，为方便叙述设为状态T。（3）从）从T开始，对每个字符开始，对每个字符a，求两个运算，求两个运算 move(T,a)（为叙述方便将结果（为叙述方便将结果 记为记为B) _closure(B) （为叙述方便将结果记为（为叙述方便将结果记为C)（4）检查该行所有的状态子集）检查该行所有的状态
10、子集C，将未出现在第一列者填入到后面空行将未出现在第一列者填入到后面空行的第一列。的第一列。（5）重复）重复(3)(4)直到第一列中状态子集不再扩大为止直到第一列中状态子集不再扩大为止(在第在第i+1列上的所列上的所有状态子集均已在第一列上出现有状态子集均已在第一列上出现)。（6）将该状态转换矩阵中所有状态子集重新命名，）将该状态转换矩阵中所有状态子集重新命名， 得到状态转换矩阵，其所示的是与给定的得到状态转换矩阵，其所示的是与给定的NFA等价的等价的DFA （未化简的（未化简的DFA）。）。 注意注意 DFA M的初态为该表第一行第一列的状态。的初态为该表第一行第一列的状态。 DFA M的终
11、态为含有原的终态为含有原NFA N的终态的状态子集的终态的状态子集 。 -closure(0)=0,1,2,4,7=A初态初态练习：练习：NFADFA要求：书写格式如下表要求：书写格式如下表stateab3,8,6,1,2,4,70,1,2,4,7B5,6,1,2,4,7B5,9,6,1,2,4,7ABCDmove(A,a)=3,8-closure(3,8)= 3,8,6,1,2,4,7move(B,a)=3,8-closure(3,8)终态终态Cmove(A,b)=5move(B,b)=5,9-closure(5) =5,6,1,2,4,7-closure(5,9)= 5,9,6,1,2,4
12、,7Dmove(E,b)=5BBEBCmove(D,b)=5,10move(C,a)=3,8move(D,a)=3,8move(E,a)=3,8-closure(3,8)-closure(3,8)-closure(5,10)=5,10,6,1,2,4,7-closure(3,8)-closure(5)move(C,b)=5C-closure(5)5,10,6,1,2,4,7E注意：表中每一表项，需要明确注意：表中每一表项，需要明确写出写出move和和-closure的值的值BDCEbbbbAaaabaa最后画出最后画出DFA的转换图的转换图1、首先把状态集、首先把状态集S分成终态集和非终态集分
13、成终态集和非终态集, 形成初始划分：形成初始划分： = Z，KZ；2、对、对中每个子集进行如下变换：中每个子集进行如下变换：设含有设含有m个子集个子集,=I1,I2,Im,则对每一个则对每一个Ii和每一个和每一个a：考察：考察：Iia=f(Ii，a)，如，如Iia中的状态分别落于中的状态分别落于中中P个不同的子集，则：个不同的子集，则：Ii将被将被P个更小的状态子集个更小的状态子集Ii1,Ii2,Iip 所细分。所细分。 令细分后所得的状态集合为令细分后所得的状态集合为new；3、重复步骤、重复步骤2直至所含的子集数不再增加为止，即直至所含的子集数不再增加为止，即new=;4、对、对中的每个子
14、集中的每个子集Ii，从中任选一个状态作为代表，确定新自动机的初，从中任选一个状态作为代表，确定新自动机的初态、终态集和转换函数。态、终态集和转换函数。 若某子集包含原有的初态，则此代表状态即为最小化后若某子集包含原有的初态，则此代表状态即为最小化后M的初态；的初态； 若某子集包含原有的终态，则此代表状态即为最小化后若某子集包含原有的终态，则此代表状态即为最小化后M的终态。的终态。3、DFA的最小化算法的最小化算法:-划分法划分法 练习：练习：结果：结果：=S,B,A,C,D,E,F最小化的最小化的DFA如右图：如右图：CDBAEFSbaaaaaabbbbbbaaS,B，A bS,B 解：答题格
15、式如下：解：答题格式如下：DabBASaabb:S,A,B ， C,D,E,F不可拆分不可拆分把转换图的概念拓广，每条弧上可以用一个正规式标记。把转换图的概念拓广，每条弧上可以用一个正规式标记。第一步第一步 : 改造改造M，使其只有一个初态和终态。，使其只有一个初态和终态。v在在M的转换图上加进的转换图上加进x、y两个结。从两个结。从x用用 弧连接到弧连接到M的所有的所有初态结点，从初态结点，从M的所有终态结点用的所有终态结点用 弧连接到弧连接到y，从而构成一，从而构成一个新的个新的NFA M，L(M)=L(M)。v第二步第二步 : 逐步消结。逐步消结。v消去消去NFA M中的状态结点，直至剩
16、下中的状态结点，直至剩下x、y为止。在消结的为止。在消结的过程中，逐步用正规式标记弧。消结的过程是直观的，只需过程中，逐步用正规式标记弧。消结的过程是直观的，只需反复使用下面的替换规则。反复使用下面的替换规则。v第三步第三步 : x至至y弧线上的标记便是弧线上的标记便是上的上的r，它就是，它就是M上所接受的上所接受的正规式。正规式。4、FA 正规式正规式r （消结法）消结法）abcR2R1abcR2R1R3acR1R2acR1 R2acR1R2*R3替换规则替换规则ac R1R21313|1(|)()(|)()* * 0 4 4 00 34 练习：练习：结果：结果：(|)()*123 重点理解
17、消除状态重点理解消除状态2后产生的符号串后产生的符号串第五章第五章 LL(1)分析法分析法提取左公因子：提取左公因子：一般：一般：A1|2|n|r1|rm 改写：改写：A A|r1 |rm A 1| 2 | n若若 1， 2 n仍有公共左因子，则再次提取，直到仍有公共左因子，则再次提取，直到无公共左因子为止。无公共左因子为止。消除直接左递归消除直接左递归 AA 1|A 2|A m| 1| 2| n 消除左递归改写为右递归：消除左递归改写为右递归： A 1A| 2A| nA A 1A| 2A| mA|21要求无环路A+A 和 无-产生式。 算法步骤如下：1.把非终结符按某一顺序排序为A1，A2，
18、An 。2.for(i=1；i=n；i+)/处理全部非终结符 3化简由（2）所得到的文法。 消除间接左递归 代入法 P89 for(j=1；j右部时改写22解：解：解题过程按如下步骤书写：解题过程按如下步骤书写：1)非终结符号排序为非终结符号排序为S，Q，R2)对对S：Q的序号的序号2大于大于S的序号的序号1，不处理；，不处理； 对对Q：R的序号的序号3大于大于Q的序号的序号2，不处理；，不处理； 对对R：S的序号的序号1小于小于R的序号的序号3，所以改写，所以改写RSa； 用用(1)的右部取代的右部取代S得到：得到：RQca|ca|a，记为，记为(4)； 此时，此时，(4)式中式中Q的序号的
19、序号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 自己完成练习自己完成练习 提取左公因子和消除左递归。提取左公因子和消除左递归。 注意：解题过程按上页的例子
20、写。注意：解题过程按上页的例子写。n(1)AaABe|a BBb|dn (2) SAS|b ASA|a要判别一个上下文无关文法是否是LL(1)文法分为六步：n（1）消除文法的左递归和左公因子。n（2）求能推出的非终结符集。n（3）计算每个非终结符A的FIRST集。n（4）计算每个非终结符A的FOLLOW集。n（5）计算每个产生式A的SELLECT集。n（6）按LL(1)文法的定义判别。n如果没有产生式n第（2）和（4）步可以省略。1求出能推出的非终结符n首先建立一个以文法的非终结符个数为上界的一维数组，其数组元素为非首先建立一个以文法的非终结符个数为上界的一维数组，其数组元素为非终结符，对应每
21、一个非终结符有一个标志位，用来记录能否推出终结符，对应每一个非终结符有一个标志位，用来记录能否推出 。其值。其值有三种情况有三种情况“未定未定”、“是是”、“否否”。 用一个数组用一个数组X X 来表示这些状态。来表示这些状态。n计算出能推导出计算出能推导出 的非终结符的步骤如下：的非终结符的步骤如下：n（1 1）将数组）将数组X X 中对应的每一个非终结符的标记记为中对应的每一个非终结符的标记记为“未定未定”。n（2 2）扫描文法中的产生式。）扫描文法中的产生式。q1)1)删除所有右部含有终结符的产生式。若这使得以某一非终结符为左部删除所有右部含有终结符的产生式。若这使得以某一非终结符为左部
22、的所有产生式都被删除，则将数组中对应的非终结符的标记值改为的所有产生式都被删除，则将数组中对应的非终结符的标记值改为“否否”，说明该非终结符不能推出，说明该非终结符不能推出 。q2)2)若某一非终结符的某一个产生式右部为若某一非终结符的某一个产生式右部为 ，则将数组中对应该非终结符，则将数组中对应该非终结符的标志置为的标志置为“是是”，并从文法中删除该非终结符的所有的产生式。，并从文法中删除该非终结符的所有的产生式。（3 3）扫描产生式右部的每一个符号。）扫描产生式右部的每一个符号。q1)1)若所扫描到的非终结符号在数组中对应的标志是若所扫描到的非终结符号在数组中对应的标志是“是是”，则删去该
23、非，则删去该非终结符，若这使产生式右部为空，则对产生式左部的非终结符在数组中终结符，若这使产生式右部为空，则对产生式左部的非终结符在数组中对应的标志改为对应的标志改为“是是”，并删除该非终结符为左部的所有的产生式。，并删除该非终结符为左部的所有的产生式。q2)2)若所扫描到的非终结符号在数组中对应的标志是若所扫描到的非终结符号在数组中对应的标志是“否否”，则删除该产，则删除该产生式。若这使得产生式左部非终结符的有关产生式都被删除，则把在数生式。若这使得产生式左部非终结符的有关产生式都被删除，则把在数组中该非终结符对应的标志改成组中该非终结符对应的标志改成“否否”。n（4 4）重复（）重复（3
24、3），），直到扫描完一遍文法的产生式，数组中的非终结符对应直到扫描完一遍文法的产生式，数组中的非终结符对应的特征再没有改变为止。的特征再没有改变为止。非终结符非终结符SABCD 求出能推出求出能推出 的非终结符的非终结符初值初值未定未定未定未定未定未定未定未定未定未定第一次扫描第一次扫描是是是是否否第二次扫描第二次扫描是是否否非终结符SABCD 结果：是是是是是是是是否否否否定义 令GS=(VT，VN，S，P)，则 P76FIRST()= |*，aVT ，、V*n若 *，则FIRST()n对每一文法符号X，计算FIRST(X)过程如下：-(1)若XVT ，则 FIRST(X)=X；-(2) （
25、直接收取）p若XVN，且有产生式Xa，aVT，则把a加入到 FIRST(X)中；p若XVN，且有产生式X，则把加到 FIRST(X)中；q(3)（反复传送）p若XVN，有产生式XY1Y2Yn，Y1,Yi都是非终结符，且对于任何j，1ji-1，FIRST(Yj)都含有，则把所有FIRST(Yj)中的非元素都加到FIRST(X)中；FIRST(Yi)的元素加入到FIRST(X)p特别地，若所有FIRST(Yj,j=1,2,n)均含有，则把和FIRST(Yj)中的所有非元素都加到FIRST(X)中. q(4)反复使用(2)-(3)，直到FIRST(X)不再增大为止。、FIRST集（难点） 终结首符集
26、P80例例GS: SAB|bC Ab| BaD| CAD|b DaS|c 求出每个非终结符的求出每个非终结符的FIRST集集FIRST集集1、已求出能推出、已求出能推出的非终结符集的非终结符集T为为A,B,S2、求出、求出FIRST集集,b, b, aba，c ,a,a, cABCDS （敛）（敛）演草部分： FIRST(S)=(FIRST(A) -) ( FIRST(B)-) bFIRST(A)=b FIRST(B)=aFIRST(C)=(FIRST(A) -) FIRST(D) b FIRST(B)=ac计算过程如下：P 82n(a)设S为开始符号，则#FOLLOW(S)n(b)若有产生式
27、A B， * 则FIRST() 加至FOLLOW(B)n(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(
28、A)=FIRST(B)-FOLLOW(S)FIRST(D)FOLLOW(S)=#FOLLOW(D)DCBASFOLLOW(B)=FOLLOW(S)FOLLOW(C)=FOLLOW(S)FOLLOW(D)=FOLLOW(B) FOLLOW(C) 演草部分：演草部分： 4、判断是否是LL（1）文法产生式的可选集SELECT P78A 的可选集SELECT *若右部串 ，则SELECT(A )= FIRST() *若右部串 ，则SELECT(A )= FIRST()- FOLLOW(A)分析表是一个二维数组MA，b，其中A是非终结符号，b是终结符号或是符号#。 1)对文法G的每个产生式A执行第2步；
29、 2)对每个终结符号bSELECT(A)， 把A加至中； MA，b内容为一条关于A的产生式。 其中：b 为Vt或#。 3)把所有无定义的MA，b标上错误标记或用空白表示。 结论：结论：当分析表中每一项无冲突时，为当分析表中每一项无冲突时，为LL(1)文法。文法。练习：判断文法是否练习：判断文法是否LL(1)文法，文法，写出原因写出原因SELECT(F(E)=( SELECT(ETE)=（，（，i SELECT()=+SELECT()=),# SELECT(TFT)= (，iSELECT()=* SELECT()=+,),#SELECT(Fi)=i i+*()#EETTF+TETETEFTFT*
30、FT(E)i因为上面的分析表中每一项没有冲突，所以，该文法是因为上面的分析表中每一项没有冲突，所以，该文法是LL（1）文）文法。法。XVVN N#S进栈，当前输入符送进栈，当前输入符送a上托栈顶符号放入上托栈顶符号放入X若产生式为若产生式为XX1X2Xn按逆按逆序即序即XnX2X1入栈入栈 出错出错X=#XVTX=aX=aMX,a是是产生式吗产生式吗出出错错X=aX=a读入读入下一下一个符个符号号结束结束是是是是是是是是否否否否否否否否否否是是3.LL(1)3.LL(1)分析程序分析程序的控制程序的控制程序初始格局：初始格局：(#S，输入串，输入串#)终止格局：终止格局：(#(#，# #) )
31、图中符号说明如下：“#”句子括号即输入串的括号“S”文法的开始符号“X”存放当前栈顶符号的工作单元a存放当前输入符号a的工作单元1#E23 TF4ETEETETFTTFT iFiFii i匹配匹配5 T T6#E78 ET+E E+TE+TE+ +匹配匹配#ET9 TFTFTTFTFiFi10#ETi i匹配匹配11 i12#E T T* *FTFT* *匹配匹配13141516#ETFFiFi#ETi i匹配匹配#E#ETT TE E17#接受接受对输入串对输入串i+i*i#进行分析进行分析# ETi+i*i#i+i*i#i+i*i#i+i*i# +i*i# +i*i# +i*i# i*i#
32、 i*i# i*i#*i#* i#i#i#E#ET#ET# #E#ET TF* i +TETETEFTFT*FT(E)i+TETETEFTFT*FT(E)i注意：红色部分为注意：红色部分为易出错部分易出错部分练习n以作业题为主，练习完整的过以作业题为主，练习完整的过程程n1、能推出、能推出的非终结符集。的非终结符集。n2、求非终结符的、求非终结符的FIRST、FOLLOW集。集。n3、构造分析表。、构造分析表。n4、判断是否、判断是否LL（1）文法。）文法。n5、若是、若是LL(1)文法，则写出句文法，则写出句子的分析过程。子的分析过程。VN推出?FIRSTFOLLOWVNab 步骤分析栈剩余
33、输入串推导所用产生式或匹配VN推出?FIRSTFOLLOWVN步骤分析栈剩余输入串推导所用产生式或匹配第六章 算符优先文法1 1、会写、会写表达式表达式的的逆波兰式逆波兰式练习练习：求下述表达式的逆波兰式：求下述表达式的逆波兰式：(a+b/d)(a+b/d)* *e , e , a a b b d d / / + +e e* *注注根据逆波兰式特点：根据逆波兰式特点： 运算对象顺序不变；运算对象顺序不变； 运算符紧跟运算对象之后。运算符紧跟运算对象之后。 可直接写出：可直接写出：练习以下公式的逆波兰式练习以下公式的逆波兰式a+(b-c)a+(b-c)* *d+e/fd+e/fa a* *b/c
34、eb/ce* *d da+(-b)a+(-b)FIRSTVT计算如下：计算如下：P111p初值：若有产生式初值：若有产生式Aa或或ABa 则则a FIRSTVT(A)p迭代：若迭代：若a FIRSTVT(B)且有产生式且有产生式AB 则则a FIRSTVT(A)LASTVT计算如下：计算如下：P111p初值：若有产生式初值：若有产生式Aa或或AaB 则则a LASTVT(A)p迭代：若迭代：若a LASTVT(B)且有产生式且有产生式AB 则则a LASTVT(A)根据定义直观计算根据定义直观计算FIRSTVT集、集、LASTVT集集2. 会构造算符优先分析表会构造算符优先分析表例如：求下面文
35、法的每个非终结符的例如：求下面文法的每个非终结符的FIRSTVT和和LASTVT。准备工作：准备工作：增加增加E#E#E#E#EE+TETTT*FTFFP FFPP(E)PiFIRSTVTLASTVTE E T F P #(, i#i, )+* * (,i (,i(,i+* * i, ) i, )i, )构造优先表的算法：构造优先表的算法：P114准备工作：准备工作：对文法开始符号对文法开始符号S，增加，增加S#S#for(每个产生式每个产生式AX1X2Xn) for(i=1;i=n-1;i+) if(Xi和和Xi+1均为终结符均为终结符) 置置Xi Xi+1 ； if(in-2且且Xi和和X
36、i+2均为终结符均为终结符,但但Xi+1 为为 非终结符非终结符) 置置Xi Xi+2 ；if(Xi为终结符为终结符,Xi+1为非终结符为非终结符) for(FIRSTVT(Xi+1)中的每个中的每个b)置置XiXi+1;A abA aQbA aBA Bb(0)E#E# (1)EE+T (2)E T (3)TT*F (4)T F (5)FP F (6) F P (7)P(E) (8)P i (1)LASTVT(E) + (0)LASTVT(E)(1)+ FIRSTVT(T)(3)* FIRSTVT(F)(7)( FIRSTVT(E) (0)# FIRSTVT(E)练习nP122 第4题n1、求
37、FIRSTVT和LASTVT集n2、求分析表VNFIRSTVTLASTVTabcabc第七章 LR分析法n证明文法是SLR(1)文法。n1、求出LR(0)的DFA。n2、对于有冲突的状态，写出利用FOLLOW集的计算，可以解决冲突，从而证明该文法是SLR（1）文法。（计算计算归约项非终结符的归约项非终结符的FOLLOW，与可移进终结符比较，与可移进终结符比较）；）； n3、写出 SLR（1）分析表。n4、会求LR（1）的DFA的初始状态（LR(1)项目集规范族的I0）练习：P162 例题2n1、写出LR(0)的DFAn2、找出DFA中冲突项，写出冲突项的解决方案，n 归约和归约冲突、归约和移进
38、冲突qFOLLOW集n3、冲突解决，写出改进的SLR(1)分析表.扩充扩充如何判断一个文法是哪种如何判断一个文法是哪种LR文法文法P166第第6题题方法方法2：n1、先构造、先构造LR(1)的的DFA和分析表；和分析表；q2、若有冲突，则不是、若有冲突，则不是LR(1)文法，结束。文法，结束。q3、无冲突，合并同心集，、无冲突，合并同心集，n4、合并同心集，无冲突，则为、合并同心集，无冲突，则为LALR(1)文法；文法；n5、合并同心集，有冲突，则为、合并同心集，有冲突，则为LR(1)文法；文法；q6、若是、若是LALR(1)文法，构造分析表，看一行中归约的状态；文法，构造分析表，看一行中归约
39、的状态；n若有归约，则把该行都填上归约，若有归约，则把该行都填上归约，q若无冲突，则为若无冲突，则为LR(0)文法；文法；q若有冲突，则求若有冲突，则求FOLLOW集，能否解决，集，能否解决，能解决，是能解决，是SLR(1)文法，否则文法，否则LALR(1)文文法法。I0:S S,# S L=R,# S R,# L *R,=/#L i,=/# R L,# I1:SS ,#sI9:SL=R ,#RI6:S L= R,# R L,# L *R,# L i,# =I2:S L =R,# R L,# LI3:SR ,#RI5:Li ,=/#iiI12:Li ,#iiI13:L*R ,#RLI10:RL
40、 ,#LI7:L*R ,=/#RI8:RL ,=/#LI4: L *R,=/# R L,=/#L i,=/# L *R,=/#*I11:L * R,# R L,# L *R,# L i,# *P150 判断下面文法是哪种类型的判断下面文法是哪种类型的LR文法？文法？(0) SS (1)SL=R (2)S R (3)L *R (4)L i(5)R L解：解：(1)构造构造LR(1)的的DFA=*i#SLR0S4S51231acc2S6r53r24S4S5875r4r46S4S5897r3r38r5r59r1(2)构造构造LALR(1)的分析表的分析表=*i#SLR0S4S51231acc2S6r
41、53r24S4S5875r4r46S4S5897r3r38r5r59r1(3)解决冲突，得到如下分析表解决冲突，得到如下分析表FOLLOW集集S #S #L =,#R #,=S6/r5r5r5r5因为因为FOLLOW(R)=#,=，在在I2中，中， FOLLOW(R) =，所以，所以I2的的“=”的冲突没解决，的冲突没解决，所以该文法不是所以该文法不是SLR(1)文法，是文法，是LALR(1)文法文法 P150r4r4r4r4r3r3r3r3r5r5r5r5第8章 语法制导翻译练习：练习：为文法：为文法：S L.L | LL L B | BB 0 | 1 9给出一个语法制导定义给出一个语法制导
42、定义，要求，要求输出输出S的十进制的值。的十进制的值。n解：解：设属性设属性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章 代码优化n把程序划分为基本块，并作出程序流图。 q基本块的划分，关键找入口语句。q流图的画法
