编译原理第15章习题课答案解析课件.ppt

1、2、一个典型的编译系统通常由有哪些部分组成？、一个典型的编译系统通常由有哪些部分组成？各部分的主要功能是什么？各部分的主要功能是什么？1编译系统编译系统编译程序编译程序语法分析语法分析语义分析与中间代码生成语义分析与中间代码生成优化优化目标代码生成目标代码生成运行系统运行系统词法分析词法分析 语法分析语法分析()：在词法分析的基础上将单词序列分解成各类语法在词法分析的基础上将单词序列分解成各类语法短语，如短语，如“程序程序”，“语句语句”，“表达式表达式”等等。等等。语义分析语义分析()：语义分析是在语法分析程序确定出语法短语后，审语义分析是在语法分析程序确定出语法短语后，审查有无语义错误，并

2、为代码生成阶段收集类型信息。查有无语义错误，并为代码生成阶段收集类型信息。1 词法分析词法分析()：从左到右一个字符一个字符的读入源程序，对从左到右一个字符一个字符的读入源程序，对构成源程序的字符串进行扫描和分解，从而识别出构成源程序的字符串进行扫描和分解，从而识别出一个个单词（也称单词符号或简称符号）。一个个单词（也称单词符号或简称符号）。1 代码优化代码优化()：为了使生成的目标代码更为高效，可以对产生的中为了使生成的目标代码更为高效，可以对产生的中间代码进行变换或进行改造，这就是代码的优化。间代码进行变换或进行改造，这就是代码的优化。代码生成代码生成()：目标代码生成是编译器的最后一个阶

3、段。在生成目目标代码生成是编译器的最后一个阶段。在生成目标代码时要考虑以下几个问题：计算机的系统结构、指标代码时要考虑以下几个问题：计算机的系统结构、指令系统、寄存器的分配以及内存的组织等。令系统、寄存器的分配以及内存的组织等。中间代码生成中间代码生成()：完成语法分析和语义处理工作后，编译程序将源程完成语法分析和语义处理工作后，编译程序将源程序变成一种内部表示形式，这种内部表示形式叫做中间序变成一种内部表示形式，这种内部表示形式叫做中间语言或称中间代码，它是一种结构简单、含义明确的记语言或称中间代码，它是一种结构简单、含义明确的记号系统。号系统。21.写出写出C语言和语言的输入字母表。语言和

4、语言的输入字母表。C语言：语言：09数字，大小写英文字母，键盘上可见的字符数字，大小写英文字母，键盘上可见的字符语言：可以包括的所有字符。语言：可以包括的所有字符。6.文法文法G6为为:N D 0|1|2|3|4|5|6|7|8|9 （1）G6的语言是什么的语言是什么?G6的语言是：的语言是：09的数字组成的任意非空串的数字组成的任意非空串L(G6)=0,1,2,3,4,5,6,7,8,9+（2）给出句子）给出句子0127、34和和568的最左和最右推导。的最左和最右推导。7、写一文法，使其语言是奇数集。写一文法，使其语言是奇数集。要求：不以要求：不以0打头。打头。复杂的情况复杂的情况:分三部

5、分分三部分末尾：以末尾：以1|3|5|7|9结尾结尾(一位一位):):D 1|3|5|7|9开头：除了开头：除了0的任意数字的任意数字中间部分：空或者任意数字串中间部分：空或者任意数字串 D1|3|5|7|9 C A0所以题目要求的文法所以题目要求的文法GNGN可以写成：可以写成：N BCD|DD 1|3|5|7|9B 2|4|6|8|DC CA|A 0|BB2|4|6|89、证明文法、证明文法:S|i 是二义的。是二义的。二义性的含义二义性的含义:如果文法存在某个句子对应两棵以上如果文法存在某个句子对应两棵以上不同的语法树，或者两种以上不同的最不同的语法树，或者两种以上不同的最左左/右推导，

6、则称这个文法是二义的。右推导，则称这个文法是二义的。首先：找到此文法对应的一个句子首先：找到此文法对应的一个句子 其次：构造与之对应的两棵语法树其次：构造与之对应的两棵语法树S i S e S i S i i S i S i S e S i i结论：因为该文法存在句子对应两棵结论：因为该文法存在句子对应两棵 不同的语法树，因而该文法是二义的。不同的语法树，因而该文法是二义的。11、给出下面语言的相应文法、给出下面语言的相应文法L1=n10 G1(S):S A B从从n，i的不同取值来把的不同取值来把L1分成两部分：分成两部分：A|前半部分是前半部分是 ：后半部分是后半部分是 c i：B|所以整

7、个文法所以整个文法G1S可以写为：可以写为：L2=n10G2(S):S A BL3=0G3(S):S A BL4=1n 0m 1m 0 0可以看成是两部分：可以看成是两部分：剩下两边的部分就是：剩下两边的部分就是：S 1S0中间部分是中间部分是 0m 1m：A 0A1|所以所以G4S可以写为：可以写为：S 1S0|A A 0A1|A37.构造下列正规式相应的。构造下列正规式相应的。步骤步骤:.根据正规式画出对应的状态转换图根据正规式画出对应的状态转换图;.根据状态转换图画出对应的状态转换矩阵根据状态转换图画出对应的状态转换矩阵;.根据状态转换矩阵得到重命名后的状态转换矩阵根据状态转换矩阵得到重

8、命名后的状态转换矩阵;.根据重命名后的状态转换矩阵得出最后的根据重命名后的状态转换矩阵得出最后的.问题：将状态转换图与混淆。问题：将状态转换图与混淆。1(0|1)*101.状态转换图状态转换图 abadb1(0|1)*101a1(0|1)*101dcef101101ggg.状态转换矩阵状态转换矩阵II0I1a1abdcef10101gII0I1ab,c,db,c,dc,dc,d,ec,dc,dc,d,ec,d,ec,d,fc,d,ec,d,fc,dc,d,e,gc,d,e,gc,d,fc,d,e.重命名后的状态转换矩阵重命名后的状态转换矩阵S01A(始态始态)BBCDCCDDEDECF(终态终

9、态)F(终态终态)EDAB10C1D010E10101F1(1010*|1(010)*1)*0abdc10e0101fghi01110jklmn.状态转换图状态转换图.状态转换矩阵状态转换矩阵.重命名后的状态转换矩阵重命名后的状态转换矩阵8、给出下面正规表达式、给出下面正规表达式（1）以）以01结尾的二进制数串。结尾的二进制数串。(0|1)*01（2）能被）能被5整除的十进制数。整除的十进制数。0|5(0|5)|(1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)*（4）英文字母组成的所有符号串，要求符号串中的）英文字母组成的所有符号串，要求符号串中的 字母按字典序

10、排列。字母按字典序排列。(A|a)*(B|b)*(C|c)*(Z|z)*（3）包含奇數個）包含奇數個1或奇數個或奇數個0的二進制串的二進制串0*1(0|10*1)*|1*0(0|10*1)*（5）沒有重複出現的數字的數字符號串的全體）沒有重複出現的數字的數字符號串的全體令令 0,1,2.9R0129記為記為 i(0,1,2.,9)P（0,1,2.,9)表示表示0,1,2.,9的全排列的全排列019019 P(0,1,2.,9)8、给出下面正规表达式、给出下面正规表达式（6）最多有一個重複出現的數字的數字符號串的全體）最多有一個重複出現的數字的數字符號串的全體i 019 i(0,1,2.,9)0

11、19 P(0,1,2.,9)（7）不包含字串的由）不包含字串的由a和和b組成的符號串的全體組成的符號串的全體b*(a*|()*)*9、对下面情况给出及正规表达式：、对下面情况给出及正规表达式：（1）0,1上的含有子串上的含有子串010的所有串。的所有串。正规式：正规式：(0|1)*010(0|1)*做法同第做法同第7题。题。（2）0,1上不含子串上不含子串010的所有串。的所有串。正规式：正规式：1*(0|11*1)*1*0*1*(0|11)*(0|1)1*(0|11)*1*12、将图、将图3.18的的(a)和和(b)分别确定化和最少化。分别确定化和最少化。(a)aaa,b10.状态转换矩阵状

12、态转换矩阵00,1110,10,110.重命名后的状态转换矩阵重命名后的状态转换矩阵012211200a2baba.最小化最小化0=(0,1,2)10,110,12因此，不能再分因此，不能再分02baa023145aaaabbbbbbaa(b)这道题实质上已经是确定化了的，所以我们只需最小化这道题实质上已经是确定化了的，所以我们只需最小化：2，3，4，5 0，1 2，3，4，50，1，3，5 分属两区，所以分为分属两区，所以分为2，4 3，5 0，11 0，12，4 所以所以 0，1等价等价2，40，1 2，43，5 所以所以2，4等价等价 3，53，5 3，52，4 所以所以3，5等价等价所

13、以分为所以分为 0，1 2，4 3，5 023aabbba14、构造一个，它接受、构造一个，它接受=0,1上所有满足如下上所有满足如下 条件的字符串：每个条件的字符串：每个1都有都有0直接跟在右边。直接跟在右边。思路：先写出满足条件的正规式，由正规式构造思路：先写出满足条件的正规式，由正规式构造 ，再把确定化和最小化。，再把确定化和最小化。满足条件的正规式：满足条件的正规式：(0|10)*0110yx(0|10)*xy12100 xy12100确定化：确定化：给状态编号：给状态编号：02101100最小化：最小化：0,10,1，220,10=1 0,11=20,10=1 0,11=220=02

14、0=0，21=21=2 2或或0,10,1所以所以0,10,1不可分，用狀態不可分，用狀態0 0代表它們代表它們0210015、给定右线性文法、给定右线性文法G：求一个与：求一个与G等价的左线性文法。等价的左线性文法。S 0S|1S|1A|0BA 1C|1B 0C|0C 0C|1C|0|1SABCZ001110001101GZ:Z Z0101B A0|0A B1|1确定化、最小化后的为：确定化、最小化后的为：SB0A110Z010,1补充：构造一右线性文法，使它与如下文法等价：补充：构造一右线性文法，使它与如下文法等价：S A U T B 并根据所得右线性文法，构造出相应的状态转换图。并根据所

15、得右线性文法，构造出相应的状态转换图。思路：思路：先写出原文法所描述的语言先写出原文法所描述的语言 L(G)=1GS:S B C aSaCbcBbcT44.1、考虑下面文法、考虑下面文法G1：S a|（T）T T，S|S（1）消去）消去G1的左递归；的左递归；S a|（T）T T ，S T|（2）经改写后的文法是否是）经改写后的文法是否是(1)文法，给出预测分析表。文法，给出预测分析表。经改写后的文法满足经改写后的文法满足3个条件，所以是个条件，所以是(1)的的预测分析表构造算法预测分析表构造算法:1.对文法中的每个产生式对文法中的每个产生式A 执行第二步和第三步执行第二步和第三步;(S)=a

16、,(T)=a,(T)=,(S)=),(T)=)(T)=)a（，）#S T T S aS S(T)T T T T T 预测分析表构造算法预测分析表构造算法:1.对文法中的每个产生式对文法中的每个产生式A 执行第二步和第三步执行第二步和第三步;2.对每个终结符对每个终结符a(),把把A a加到加到M中中;S a;S;S(T);T;T T FTRST（a）=aFIRST（）=FIRST（T）=（FIRST（ST）=a，（，（FIRST（，（，ST）=，FIRST（）=a（，）#S T T S aS S(T)T T T T 3.若若(),则对于任何则对于任何b(A)把把A 加至加至M中中(T)(T)=

17、)T 递归子程序：递归子程序：S;a (;);T;T;T;T;,;:是输入串指针所指的符号是输入串指针所指的符号:是把调至下一个输入符号是把调至下一个输入符号:是出错诊察程序是出错诊察程序补充题：有文法：补充题：有文法：E E|T T|F（E）|i A+|-M*|/（1）求、集，判断是否是（）求、集，判断是否是（1）文法？）文法？（2）若是构造（）若是构造（1）分析表？）分析表？（3）简述（）简述（1）分析器的工作原理。）分析器的工作原理。4.2：有文法：有文法：E E|T T T|F F*F|P(E)（1）求、集，判断是否是（）求、集，判断是否是（1）文法？）文法？（2）若是构造（）若是构造

18、（1）分析表？）分析表？（3）简述（）简述（1）分析器的工作原理。）分析器的工作原理。E E|T T|F（E）|iA+|-M*|/(M)=*，/(A)=+，-(F)=(，i(T)=*，/，(T)=(，i)(E)=+，-，(E)=(，i(E)=#，)(E)=#，)(T)=+，-，#，)(T)=+，-，#，)(F)=*，/，+，-，#，)(A)=(，i(M)=(，iEE TE E TE E E ATEE ATE E E TT FT T FT T T-T T MFTT MFT T T FF i F（E）A A +A -M M *M /i+-*/（）#P81.2.对文法对文法G:E E T T F F

19、*F|P(E)1)(E)=(T)(F)(P)=(,(E)=+,(T)(T)=(,(F)=*,(E)=#,)(E)(E)=#,)(T)(E)(E)=,)(T)(T)=,)(F)(T)(T)=(,)F)(F)=(,)(P)(F)(F)=*,(,)2)考虑下列产生式:()()=+=()(E)=+#,)=(T)()=(,=(T)(T)=(,+,)=(*F)()=*=(*F)(F)=*(,)=(E)(a)(b)()=所以,该文法式(1)文法.3)預測分析表：4)程序程序 E;(a b T;E E;+;E )#T;(a b F;T T;(a b T *F;(a b P;F F;*;F P;a b (;E;

20、);n4.3下面文法中，那些是下面文法中，那些是(1)文法的，說明理由文法的，說明理由n构造不带回溯的自上而下分析的文法条件构造不带回溯的自上而下分析的文法条件n 1.文法不含左递归，文法不含左递归，n 2.对于文法中每一个非终结符对于文法中每一个非终结符A的各个产生式的候的各个产生式的候选首符集两两不相交。即，若选首符集两两不相交。即，若A 1|2|nn 则则 (i)(j)(ij)n 3.对文法中的每个非终结符对文法中的每个非终结符A，若它存在某个候选，若它存在某个候选首符集包含首符集包含，则，则(A)(A)=n 如果一个文法如果一个文法G满足以上条件，则称该文法满足以上条件，则称该文法G为

21、为(1)文法。文法。SA B 是，满足三个条件SA B 对于A不满足条件3SA B A、B都不满足条件3SB C d满足条件3解題思路：構造文法的預測分析表，通常應當按下列步驟進行：1.消除文法的左遞歸（包括所有直接左遞歸和間接左遞歸）2.對消除左遞歸后的文法，提取公因子 3.對經過上述改造后的文法，計算它的每個非終結符的集合和集合；4.根據集合和集合構造預測分析表：第1步對文法G的每個產生式A執行第1步和第3步；第2步對每個終結符a(),把A加至M中；第3步若(),則對任何b(A),把A加至M中；第4步把所有無定義的M標上“出錯標誌”4.4對下面的文法：()()|(1)構造(1)分析表(2)

22、給出對句子-()分析過程 4.4對下面的文法：()()|(1)構造(1)分析表(2)給出對句子-()分析過程 4.4對下面的文法：()()|(1)構造(1)分析表(2)給出對句子-()分析過程(2)給出對句子-()分析過程(2)給出對句子-()分析過程(2)給出對句子-()分析過程(2)給出對句子-()分析過程51、令文法、令文法G1为：为：E|T TT*F|F F(E)|i 证明证明*F是它的一个句型，指出这个句型的所有是它的一个句型，指出这个句型的所有短语、直接短语和句柄。短语、直接短语和句柄。EE+TT*FT*F是句型是句型*F相对于相对于T的短语的短语*F句型句型*F相对于相对于E的短

23、语的短语T*F是句型是句型*F相对于相对于T的直接短语的直接短语T*F是句柄是句柄2、考虑下面的表格结构文法、考虑下面的表格结构文法G2：Sa|(T)T|S（1）给出）给出(a,()和和(),(a)的最左和最右推导。的最左和最右推导。(a,()的最左推导：的最左推导：S (T)()()()(a,(T)(a,()(a,()(a,()(a,()(),(a)的最左推导：的最左推导：S (T)()()(T)()()()()()()()(),)(),)(),)(),(a)的最右推导：的最右推导：S (T)()()()(T)()()()()()()(),)(),)(),)(a,()的最右推导：的最右推导：

24、S (T)()(T,(T)(T,()(T,()(T,()(T,()(S,()(a,()2）指出）指出(),(a)的规范归约及每一步的句柄。的规范归约及每一步的句柄。S(T)T,Sa(T)ST,ST,S(T)Sa(T)ST,SaSaaSa(),(a)STS(),(a)aSa(),(a)TT,S(T),(a)(T)S(T)(S,(a)STS(T,(a)S(,(a)TT,S根据这个规范规约，给出根据这个规范规约，给出“移进移进归约归约”的过程，的过程，并给出它的语法树的自下而上的构造过程。并给出它的语法树的自下而上的构造过程。符号栈符号栈输入串：输入串：(a ,a ),(a ),a )#S(T)T,

25、Sa(T)ST,ST,S(T)Sa(T)ST,SaSa(aS,TaSS)T,ST(a S T)S)S T,a ST)S归约规则归约规则句柄句柄aSaSTSaSaT,STT,S(T)S(T)STSST,STT,S3、(1)计算练习计算练习2文法文法G2的和。的和。G2：Sa|(T)T|S(S)=a，(T)=，a，(S)=a，)(T)=，a，)S（T）（）.T T，S，FIRSTVT(S).，a,，,，(.T T，S LASTVT(T)，.a ，,，,），,，.S（T）(FIRSTVT(T).(a,(,(,(，.S（T）LASTVT(T).a ),),),，).#a,#,#(,.#.a#,#,）#

26、,.#,)(a#,)(a=.=.1 1、文法是算术文法，且不含、文法是算术文法，且不含产生式。产生式。2 2、由优先关系矩阵可知，任何、由优先关系矩阵可知，任何两个终结符之间的优先关系不多两个终结符之间的优先关系不多于一种。于一种。综上，该文法是算术优先文法。综上，该文法是算术优先文法。.，a（）#，a ()#.输入串输入串(a,()的算符优先过程。的算符优先过程。.(.a.,.(.a.,.a.).).#aS#(S,()#.,.(,(aa)#aS#(S,()#.,(,(a)#.aS#(S,()#.,(,(.)#.(,(#.)#T#(S,(T)#.(T)S#()#.(,.)#.T#(T)#.(.

27、)#.(T)S确认！确认！问题：没有依据最左素短语进行规约问题：没有依据最左素短语进行规约P134-5考虑文法S A1、列出这个文法的所有(0)项目2、构造这个文法的(0)项目集规范族及识别或前缀的3、这个文法是的吗？若是，构造出它的分析表4、这个文法是或(1)的吗解答：1、P134-5考虑文法S A1、列出这个文法的所有(0)项目2、构造这个文法的(0)项目集规范族及识别或前缀的3、这个文法是的吗？若是，构造出它的分析表4、这个文法是或(1)的吗解答：1、确定化：P135-6P135-7证明下面文法是(1)文法，但不是(0)文法SA A B 解：文法GS：0：SA 1：A 2：A 3：B 4

28、：Ba 5：Bp135-8.证明下面的文法是证明下面的文法是(1)的的,但不是但不是(1)的。的。S A B解答解答:(1)首先该文法无左递归存在首先该文法无左递归存在,没有公共左因子。没有公共左因子。其次其次:对于对于S ()=a ()=b ()()=所以该文法是所以该文法是(1)文法。文法。(2)证明该文法不是的。证明该文法不是的。文法的文法的(0)项目集规范族为项目集规范族为:I0=S S S A.B.I1=S S.I2=S I3=S I4=S A.I5=S B.I6=S I7=S I8=S.I9=S.考察考察I0(A)=(B)=(A)(B)=产生规约产生规约-规约冲突。规约冲突。所以该文法不是所以该文法不是(1)文法。文法。P135-9谢谢！