PPT《习题与试题》

习题与试题 认真复习,重点是掌握基本概念.

基本概念掌握了,相当一部分试题的解就有了习题与试题的目的区别:习题的目的是通过反复的练习理解、掌握所学知识,会有不少繁、难、大量步骤的题;

试题的目的是考察对本课程综合掌握的情况,特点是短时间内覆盖大量内容.太繁琐步骤或太难等需要耗费大量时间的题是不可能出的自己要会辨别什么是主要的什么是次要的,抓什么丢什么. 基本概念要严谨(清楚),基本方法要灵活 总之一句话,学习方法的掌握是个人努力的结果,单纯靠别人教是学不会的 如果是我复习 词法分析基本概念:正规式、正规集、有限自动机,词法分析器的构造常见计算题类型:已知集合求正规式、DFA;

已知正规式求DFA、集合;

已知FA求正规式、集合;

FA的确定化、最小化.语法分析基本概念:上下文无关文法、语言、下推自动机,LL分析与LR分析;

一些必要的定义、公式、算法的核心思想等;

常见的计算题类型:(自己思考)基本解题方法与技巧等.3. 语法制导翻译(略)4. 运行环境(略)(哪些最重要?) 关于考试 题目类型:简答题(25分)、填空题(25分)、计算题(50分)内容分布(大概):概述与词法分析(30分)、语法分析(40分)、语法制导翻译与运行环境(30分) 考试范围:1-5章讲过的内容侧重考察:基本概念与基本方法的掌握 易犯的错误不认真审题(对题目的要求理解错误:意思理解错、难题想容易、容易题想难.关键问题是基本概念不清楚)所答非所问(例如:没有要求LL分析却将文法改为LL的)画蛇添足(例如:仅问有无冲突却将分析表先构造出来)偷工减料(例如:有若干问,仅回答部分或问题仅答一半) 警示千万不要作弊!命运掌握在自己的手中! 实际试题举例

一、简答题 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)(ba)(b...a)(ba),它恰好是L(a(ba)*),即L((ab)*a)= L(a(ba)*). 也可以用归纳法证明(提示:以ab重复0次、1次作为归纳基础,假设ab重复n次成立,证明ab重复n+1次也成立).

二、填空题(30分) 2.2(6分)编译程序的基本组成有:词法分析、中间代码生成、和.2.3(1分)正规式r和s等价说明 相同.2.4(2分)不含子串baa的所有a、b符号串的正规式是 .2.9(4分) 已知文法G定义如下:S→eT|RT T→DR|ε R→dR|ε D→a|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,ε} .

三、计算题(3.3) 3.3(13分)已知一个NFA如图. (a)(4分) 用自然语言简要叙述该自动机所识别的语言 的特点,列举两个它可识别的串. (b)(3分)写出与该自动机等价的正规式r. (c)(6分)用子集法构造识别r的最小DFA. (3.3)解: 含有至少两个连续b的a、b串,例如bb、bbb等.r=(a|b)*bb(a|b)*.直接用状态转换矩阵构造:初态:{0}子集法得:(2是终态) {0,1,2} {0,2} {0,2} {0,1,2} {0,2} {0,1,2} {0,1,2} {0} {0,1} {0,1} {0} {0} b a 令: {0}=A,{0,1}=B,{0,1,2}=C,{0,2}=D得: C D D C D C C A B B A A b a 最小化DFA得:(C和D不可区分) C C C C A B B A A b a

三、计算题(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. (3.4)解: 短语:(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: 部分习题解答 习题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又应该如何构造? (4)C的形如/*…*/ 的注释.其中…代表不含*/的字符串 思路:注释中若遇到*:若后边是/则结束注释否则仍然是注释步骤:1. 注释串是空;

2. 考虑没有*的注释;

3. 考虑含*的注释结果:(4) (2)所有不含子串011的01串:1*(01|0)*(3)每个a后面至少紧随两个b的ab串:(b|abb)* 习题2.9 用自然语言给出下述正规式所描述的语言,并构造他们的最小DFA:10*1(0|1)*011(0|1)* 说明:所谓用自然语言描述就是解释字符串的性质,一般情况下是已经有了形式化描述.解:10*1:首尾是1中间有零或若干个0的01串.(0|1)*011(0|1)* :至少含一个011的01串.注意:绝对不允许用正规式表示,因为正规式是已知条件 习题2.10 有一NFA的状态转换矩阵下表,其中S为初态,D为终态 S B C D A A B C C D A B B C A A A,B,C D C,D A,B S ε c b a 求出它的最小DFA用正规式描述DFA所接受的语言 问题:根据DFA写出对应的正规式,通常的考虑和步骤是什么? 再重复一遍: 正规式、DFA是从两个不同的侧面表示一个集合(即正规集).所以,根本的方法是把正规集作为桥梁,先分析清楚DFA识别出的是一个什么集合,然后再设计此集合的正规式.反之亦然. 习题2.10(2)的解 该DFA从初态到终态有三条路径:b|c|a(a|c)*b,而且是这三条路径的至少一次重复,故正规式为:(b|c|a(a|c)*b)+ 习题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 习题 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的分析树和剪句柄的过程解:作为练习,本题的每一步都是必要的.相对来说分析表的构造并不重要.(具体步骤有时间板书) 构造SLR(1)分析表的方法: 1.可移进项直接从D........