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