《编译原理》作业和试题讲解课件.ppt

编译原理作业与试题讲解;2.4 写出下述语言的正规式描述;2.4 写出下述语言的正规式描述;2.4 写出下述语言的正规式描述;2.4 写出下述语言的正规式描述;2.4 写出下述语言的正规式描述;2.4 写出下述语言的正规式描述;2.4 写出下述语言的正规式描述;2.9 用自然语言给出下述正规式所描述的语言，并构造 它们的最小DFA10*1 (0|1)*011(0|1)*;2.10;2.10;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 - S’ S’ - 0S1SS’ | 1S0SS’ | ε 即是S - 0S1S | 1S0S | ε 这些文法都等价;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;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进行分析（以格局变化的方式） （5）根据（4）的分析给出-id+id*id的分析树和剪句柄的过程 ;构造SLR（1）分析表的方法：;3.19 假设所讨论的文法是非二义的，说明为什么在规范归约中，非终结符绝不会出现在句柄的右边。 解：（解题思路：用反证的方法，假设在规范归约中句柄右边有非终结符，则推出矛盾） 假设在规范归约中有句型“...α...A...”，其中α是句柄，A非终结符。 根据规范归约定义，A必定是由句型中相对于A的短语归约而来。而A的短语在α右边（即先归约了右边的短语），与规范归约矛盾。 得证。 请进一步思考：为什么假设文法是非二义的？;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. 把自己当作计算机，按照参数传递的实现方式“运行”一遍程序，得出结果； 2. 找台机子把程序敲进去试试（辅助手段） 表达式a+b如何可以作为复写-恢复的实参？ 解决方案：忽略返回值问题（因为复写-恢复一般要求形参要有左值） 考试中不会有这样很困惑的问题！;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 …… end D; begin …… end A;;（4）若一个可能的程序运行控制流是 A-C-E-F-B,试给出每次调用和返回时的控制栈中各活动记录的可确定内容和显示表的变化； （5）分别给出C调用E的调用序列和从E返回的返回序列。 解： （4）若一个可能的程序运行控??流是 A-C-E-F-B，给出控制栈中的内容和控制链与访问链的指向。 静态嵌套结构、活动栈、以及控制链与访问链