习题与试题

文库专用1习题与试题•认真复习，重点是掌握基本概念。基本概念掌握了，相当一部分试题的解就有了•习题与试题的目的区别：习题的目的是通过反复的练习理解、掌握所学知识，会有不少繁、难、大量步骤的题；试题的目的是考察对本课程综合掌握的情况，特点是短时间内覆盖大量内容。太繁琐步骤或太难等需要耗费大量时间的题是不可能出的•自己要会辨别什么是主要的什么是次要的，抓什么丢什么。“基本概念要严谨（清楚），基本方法要灵活”•总之一句话，学习方法的掌握是个人努力的结果，单纯靠别人教是学不会的文库专用2如果是我复习1.词法分析•基本概念：正规式、正规集、有限自动机，词法分析器的构造•常见计算题类型：已知集合求正规式、DFA；已知正规式求DFA、集合；已知FA求正规式、集合；FA的确定化、最小化。2.语法分析•基本概念：上下文无关文法、语言、下推自动机，LL分析与LR分析；•一些必要的定义、公式、算法的核心思想等；•常见的计算题类型：（自己思考）•基本解题方法与技巧等。3.语法制导翻译（略）4.运行环境（略）（哪些最重要？）文库专用3关于考试•题目类型：简答题(25分)、填空题(25分)、计算题(50分)•内容分布(大概)：概述与词法分析(30分)、语法分析(40分)、语法制导翻译与运行环境(30分)•考试范围：1－5章讲过的内容•侧重考察：基本概念与基本方法的掌握易犯的错误1.不认真审题（对题目的要求理解错误：意思理解错、难题想容易、容易题想难。关键问题是基本概念不清楚）2.所答非所问(例如：没有要求LL分析却将文法改为LL的)3.画蛇添足(例如：仅问有无冲突却将分析表先构造出来)4.偷工减料(例如：有若干问，仅回答部分或问题仅答一半)警示千万不要作弊！命运掌握在自己的手中！文库专用4实际试题举例一、简答题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次也成立）。文库专用5二、填空题（30分）2.2（6分）编译程序的基本组成有：词法分析、、、中间代码生成、、、和。2.3（1分）正规式r和s等价说明相同。2.4（2分）不含子串baa的所有a、b符号串的正规式是。2.9（4分）已知文法G定义如下：S→eT|RTT→DR|εR→dR|εD→a|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，ε}。文库专用6三、计算题（3.3）3.3（13分）已知一个NFA如图。(a)(4分)用自然语言简要叙述该自动机所识别的语言的特点，列举两个它可识别的串。(b)（3分）写出与该自动机等价的正规式r。(c)（6分）用子集法构造识别r的最小DFA。012bba,ba,b文库专用7（3.3）解：1.含有至少两个连续b的a、b串，例如bb、bbb等。2.r=(a|b)*bb(a|b)*。3.直接用状态转换矩阵构造：初态：{0}子集法得：（2是终态）ab{0}{0}{0,1}{0,1}{0}{0,1,2}{0,1,2}{0,2}{0,1,2}{0,2}{0,2}{0,1,2}令：{0}=A，{0,1}=B，{0,1,2}=C，{0,2}=D得：abAABBACCDCDDC最小化DFA得：（C和D不可区分）abAABBACCCCABCbbaaa,b文库专用8三、计算题（3.4）3.4（15分）有文法G和G的语法制导翻译如下：E→E1*T{E.place=newtemp;emit(*,E1.place,T.place,E.place;}|T{E.place=T.place;}T→T1+F{T.place=newtemp;emit(+,T1.place,F.place,T.place;}|F{T.place=F.place;}F→(E){F.place=E.place;}|id{F.place=id.name;}(a)（4分）求句型(T+F)*id的短语、直接短语以及句柄；(b)（4分）根据语法制导翻译写出句子a*b+c*d的中间代码；(c)（3分）若a=3，b=5，c=7，d=8，请给出中间代码计算结果；(d)（4分）将文法G简化为：E→E*T|T，T→T+F|F，F→id。给出它的识别活前缀的DFA。文库专用9（3.4）解：(a)短语：(T+F)*id、(T+F)、T+F、id直接短语：T+F、id句柄：T+F(b)a*b+c*d的中间代码：(1)(+,b,c,t1)(2)(*,a,t1,t2)(3)(*,t2,d,t3)(c)计算结果：t3=288(d)识别活前缀的DFA：E’→.EE→.E*TE→.TT→.T+FT→.FF→.idE’→E.E→E.*TE→T.T→T.+FT→F.F→id.E→E*.TT→.T+FT→.FF→.idT→T+.FF→.idE→E*T.T→T.+FFETFid*++TididI0I1I2I3I4I5I6I7T→T+F.I8F文库专用10部分习题解答文库专用11习题2.4写出下述语言的正规式描述（1）由偶数个0和奇数个1构成的所有01串（2）所有不含子串011的01串（3）每个a后面至少紧随两个b的ab串（4）C的形如/*…*/的注释。其中…代表不含*/的字符串思路：分析题意，从最简单的例子考虑，然后找出统一规律（1）的解题步骤：1.最简单的符合要求的串：1、010（还有100、001、111等）2.所有01均为偶数的串：A=((00|11)|(01|10)(00|11)*(10|01))*3.符合要求的所有串：A1A、A0A1A0A（为什么没有后三个？）结果：A1A|A0A1A0A思考：识别它的DFA又应该如何构造？文库专用12（4）C的形如/*…*/的注释。其中…代表不含*/的字符串思路：注释中若遇到*：若后边是/则结束注释否则仍然是注释步骤：1.注释串是空；2.考虑没有*的注释；3.考虑含*的注释结果：(4)/*([^*]|*[^/])**/（2）所有不含子串011的01串：1*(01|0)*（3）每个a后面至少紧随两个b的ab串：(b|abb)*文库专用13习题2.9用自然语言给出下述正规式所描述的语言，并构造他们的最小DFA：10*1(0|1)*011(0|1)*说明：所谓用自然语言描述就是解释字符串的性质，一般情况下是已经有了形式化描述。解：10*1：首尾是1中间有零或若干个0的01串。(0|1)*011(0|1)*：至少含一个011的01串。注意：绝对不允许用正规式表示，因为正规式是已知条件文库专用14习题2.10有一NFA的状态转换矩阵下表，其中S为初态，D为终态abcεSA,BC,DDA,B,CAACBBADCCBAADCBS1.求出它的最小DFA2.用正规式描述DFA所接受的语言问题：根据DFA写出对应的正规式，通常的考虑和步骤是什么？再重复一遍：正规式、DFA是从两个不同的侧面表示一个集合(即正规集)。所以，根本的方法是把正规集作为桥梁，先分析清楚DFA识别出的是一个什么集合，然后再设计此集合的正规式。反之亦然。文库专用15习题2.10（2）的解20a1b,cb,ca,cab该DFA从初态到终态有三条路径：b|c|a(a|c)*b，而且是这三条路径的至少一次重复，故正规式为：(b|c|a(a|c)*b)+文库专用16习题3.7设计一文法G，使得L(G)={ω|ω是不以0开始的正奇数}思路：首先根据集合的描述设计几个句子，然后从句子中找出规律（或共性），把它们的性质用产生式表示出来。解：正规式：个位：[13579]个位以上：[0-9]*最高位：[1-9]三段连起来：[1-9][0-9]*[13579]两种情况：[1-9][0-9]*[13579]|[13579]产生式：S→ACB|BA→1|2|3|4|5|6|7|8|9B→1|3|5|7|9C→ε|0C|AC文库专用17习题3.17对于文法G3.4和它所产生的句子-id+id*id和-(id+id)*idE→E+T|TT→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的分析树和剪句柄的过程解：作为练习，本题的每一步都是必要的。相对来说分析表的构造并不重要。（具体步骤有时间板书）文库专用18构造SLR（1）分析表的方法：1．可移进项直接从DFA上看：action[I,a]:=sjgoto[I,A]:=k2．可归约项分两步走：若在I状态中有[A→α.]，首先计算：FOLLOW(A),然后填写：action[I,b]:=Ri其中：b∈FOLLOW(A)且A→α是第i个产生式。IJKaA文库专用19习题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如何作为引用调用和复写-恢复的实参？解决方案：忽略返回值问题。其实这一思想可以推广到任何不支持某种方式的情况（放心，考试中不会有这种很困惑的问题）具体结果（略）文库专用20习题5.5procedureAisprocedureBisProcedureDisx:character;begin……endD;begin……endB;procedureCisx:integer;procedureEisy:integer;begin……endE;procedureFisy:float;begin……endF;begin……endD;begin……endA;有一过程A如下所示。采用静态作用域、最近嵌套原则，设A是第0层的过程。文库专用21习题5.5（续）（4）若一个可能的程序运行控制流是A-C-E-F-B,试给出每次调用和返回时的控制栈中各活动记录的可确定内容和显示表的变化；（5）分别给出C调用E的调用序列和从E返回的返回序列。说明：（4）（5）是学生希望讲解的题目解：（4）若一个可能的程序运行控制流是A-C-E-F-B，给出控制栈中的内容和控制链与访问链的指向。静态嵌套结构、活动栈、以及控制链与访问链：ABCDEFACEFB文库专用22Toknowhowtodosomethingwellistoenjoyit.战略上藐视敌人，战术上重视敌人。Thetreesthatareslowtogrowbearthebestfruit.认真复习、迎接考试（结束2007年6月19日）文库专用23附件1：教材与习题答案中的错误教材23页：例2.7上边两行：将“M[si,sj]”改为“M[si,ch]”将“...是从状态si到状态sj的边上的标记ch(或ε)。”改为“...是