《编译原理》作业与试题讲解.ppt

1,编译原理作业与试题讲解,黄冈师范学院计科院基础理论教研室张瑞红,2,2.4写出下述语言的正规式描述,（1）由偶数个0和奇数个1构成的所有01串采用算法解决：首先构造出识别偶数个0和奇数个1的自动机，然后使用自动机到正则表达式的算法求解。具体步骤参考自动机理论、语言和计算导论。,(00+01(11)*10)*(1+01(11)*0)(0(11)*0)*(1+0(11)*10)*(00+01(11)*10)*(1+01(11)*0)(0(11)*0)*,JFLAP,注：JFLAP中的“或”用“+”表示,3,2.4写出下述语言的正规式描述,（1）由偶数个0和奇数个1构成的所有01串另一种思路：先写出偶数个0和偶数个1的正则表达式A，在此基础上，使用A、0、1构造出偶数个0和奇数个1的正则表达式。A=(00+11)+(10+01)(00+11)*(10+01)*,A1A+A0A1A0A,4,2.4写出下述语言的正规式描述,（1）由偶数个0和奇数个1构成的所有01串另一种思路：先写出偶数个0和偶数个1的正则表达式A，在此基础上，使用A、0、1构造出偶数个0和奇数个1的正则表达式。A=(00+11)+(10+01)(00+11)*(10+01)*,1A+0A(10+01)A,若是1开头，则再加偶0和偶1即得结果;若是0开头，则讨论0A后可跟：跟00、11，则等价于0A；跟01、10，则是0A(01+10)，已是偶0奇1，则再加偶0和偶1即得结果,5,2.4写出下述语言的正规式描述,（2）所有不含子串011的01串思路一：3种状态：只接收了1，接收了0，接收了01思路二：接收011的RE-DFA-不接收011的DFA-RE,接收011的DFA,不接收011的DFA,x,6,2.4写出下述语言的正规式描述,（2）所有不含子串011的01串,注：JFLAP中的“”用“”表示,7,2.4写出下述语言的正规式描述,（3）每个a后面至少紧随两个b的ab串思路：abb应该为一个整体，和b进行组合，串的形式如下bbbbbabbabbbbbbabbbbbbb.(b*|abb)*(b|abb)*,8,2.4写出下述语言的正规式描述,（4）C的形如/*/的注释。其中代表不含*/的字符串思路：接收*/的DFA-不接收*/的DFA-RE接收*/的DFA中有3个状态：没有接收*；接收了*；接收了*/,(*|*/)*/*(*|*/)*/,x,9,2.9用自然语言给出下述正规式所描述的语言，并构造它们的最小DFA10*1(0|1)*011(0|1)*,所谓用自然语言描述：即解释字符串的性质练习目的：锻炼思维推理能力归纳：由特殊到一般的推理，如根据要求写正规式演绎：由一般到特殊的推理，如根据正规式生成字符串解：10*1：首尾是1中间有零或若干个0的01串(0|1)*011(0|1)*：至少含一个011的01串,10,2.10,有一NFA的状态转换矩阵下表，其中S为初态，D为终态,求出它的最小DFA用正规式描述DFA所接受的语言,问题：根据DFA写出对应的正规式，通常的考虑和步骤是什么？,正规式、DFA是从两个不同的侧面表示一个集合(即正规集)。所以，根本的方法是把正规集作为桥梁，先分析清楚DFA识别出的是一个什么集合，然后再设计此集合的正规式。(当然也可以采用机械化的算法来实现，不过结果往往很复杂，难以理解),11,2.10,该DFA从初态到终态有三条路径：b|c|a(a|c)*b，而且是这三条路径的至少一次重复，故正规式为：(b|c|a(a|c)*b)+,12,3.6设字母表=0,1，设计下列语言的文法。对于正规语言，可用正规式表示。（2）0和1个数相等的字符串；（3）0和1个数不相等的字符串；（2）（3）均不能用正规式表示，为什么？（鸽巢原理反证）（2）思路：S包含0、1个数相等，0、1相等的最小项是、01、10，则给它们加上S，则0、1个数仍相等S-S0S1S|S1S0S|消除直接左递归S-SS-0S1SS|1S0SS|即是S-0S1S|1S0S|这些文法都等价,13,3.6设字母表=0,1，设计下列语言的文法。对于正规语言，可用正规式表示。（2）0和1个数相等的字符串；（3）0和1个数不相等的字符串；（3）思路：将0、1个数相等的字符串加上若干个0或1即可S-0S1S|1S0S|加0：A-0A1A|1A0A|0A|加1：B-0B1B|1B0B|1B|S-A|B?不能推导出，结果应该为S-A0A|B1B,14,3.17对于文法G3.4和它所产生的句子-id+id*id和-(id+id)*idEE+T|TTT*F|F(G3.4)F(E)|-F|id（1）构造基于LR(0)项目集的识别活前缀的DFA（2）指出DFA中所有含有冲突的项目集，并说明这些冲突可以用SLR(1)方法解决；（3）构造文法G3.4的SLR(1)分析表（4）用分析表对句子-id+id*id和-(id+id)*id进行分析（以格局变化的方式）（5）根据（4）的分析给出-id+id*id的分析树和剪句柄的过程,15,构造SLR（1）分析表的方法：,1可移进项直接从DFA上看：actionI,a:=sjgotoI,A:=k2可归约项分两步走：若在I状态中有A.，首先计算：FOLLOW(A),然后填写：actionI,b:=Ri其中：bFOLLOW(A)且A是第i个产生式。,16,3.19假设所讨论的文法是非二义的，说明为什么在规范归约中，非终结符绝不会出现在句柄的右边。解：（解题思路：用反证的方法，假设在规范归约中句柄右边有非终结符，则推出矛盾）假设在规范归约中有句型“.A.”，其中是句柄，A非终结符。根据规范归约定义，A必定是由句型中相对于A的短语归约而来。而A的短语在右边（即先归约了右边的短语），与规范归约矛盾。得证。请进一步思考：为什么假设文法是非二义的？,17,4.4假定下述程序分别采用值调用，引用调用，复写-恢复和换名调用，请给出它们的打印结果。programmain(inputoutput);procedurep(x,y,z);beginy:=y+1;z:=z+xend;begina:=2;b:=3;p(a+b,a,a);printaend;两种解题的思路：1.把自己当作计算机，按照参数传递的实现方式“运行”一遍程序，得出结果；2.找台机子把程序敲进去试试（辅助手段）表达式a+b如何可以作为复写-恢复的实参？解决方案：忽略返回值问题（因为复写-恢复一般要求形参要有左值）考试中不会有这样很困惑的问题！,18,procedureAisprocedureBisProcedureDisx:character;beginendD;beginendB;procedureCisx:integer;procedureEisy:integer;beginendE;procedureFisy:float;beginendF;beginendD;beginendA;,5.5有一过程A如下所示。采用静态作用域、最近嵌套原则，设A是第0层的过程。,19,（4）若一个可能的程序运行控制流是A-C-E-F-B,试给出每次调用和返回时的控制栈中各活动记录的可确定内容和显示表的变化；（5）分别给出C调用E的调用序列和从E返回的返回序列。解：（4）若一个可能的程序运行控制流是A-C-E-F-B，给出控制栈中的内容和控制链与访问链的指向。静态嵌套结构、活动栈、以及控制链与访问链：,20,试题举例一、简答题,1.1（2分）有哪些方法可以去除文法的二义性。1.2（2分）写出-(a+b)*c)+d的后缀式。1.5（4分）试证明正规式(ab)*a与a(ba)*是等价的。,1.1（1）改写文法（2）规定文法符号的优先级和结合性1.2ab+c*d+（或ab+c*-d+）1.5证明：考虑L(ab)*a)中的任意一个串ababab.aba，由串连接的结合性可得：a(ba)(ba)(b.a)(ba)，它恰好是L(a(ba)*)，即L(ab)*a)=L(a(ba)*)。也可以用归纳法证明（提示：以ab重复0次、1次作为归纳基础，假设ab重复n次成立，证明ab重复n+1次也成立）。,21,二、填空题,2.2（6分）编译程序的基本组成有：词法分析、中间代码生成、和。2.3（1分）正规式r和s等价说明相同。2.4（2分）不含子串baa的所有a、b符号串的正规式是。2.9（4分）已知文法G定义如下：SeT|RTTDR|RdR|Da|bd则FIRST(S)=，FIRST(D)=，FIRST(T)=，FIRST(R)=。,2.2语法分析、语义分析、代码优化、目标代码生成、符号表管理和出错处理2.3r和s表示的正规集2.4a*(b|ba)*2.9FIRST(S)=e，d，a，b，FIRST(D)=a，b，FIRST(T)=，a，b，FIRST(R)=d，。,22,三、计算题（3.3）,3.3（13分）已知一个NFA如图。(a)(4分)用自然语言简要叙述该自动机所识别的语言的特点，列举两个它可识别的串。(b)（3分）写出与该自动机等价的正规式r。(c)（6分）用子集法构造识别r的最小DFA。,