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