资源描述：
《编译原理总复习-习题与试题教学内容.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、编译原理总复习-习题与试题关于考试题目类型：简答题(25分)、填空题(25分)、计算题(50分)内容分布(大概)：概述与词法分析(30分)、语法分析(40分)、语法制导翻译与运行环境(30分)考试范围：1－5章讲过的内容侧重考察：基本概念与基本方法的掌握易犯的错误不认真审题（对题目的要求理解错误：意思理解错、难题想容易、容易题想难。关键问题是基本概念不清楚）所答非所问(例如：没有要求LL分析却将文法改为LL的)画蛇添足(例如：仅问有无冲突却将分析表先构造出来)偷工减料(例如：有若干问，仅回答部分或问
2、题仅答一半)警示千万不要作弊！命运掌握在自己的手中！2实际试题举例一、简答题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
3、((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
4、RTT→DR
5、εR→dR
6、εD→a
7、bd则FIRST(S)=，FIRST(D)=，FIRST(T)=，FIRST(R)=
8、。2.2语法分析、语义分析、代码优化、目标代码生成、符号表管理和出错处理2.3r和s表示的正规集2.4a*(b
9、ba)*2.9FIRST(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）解：
10、含有至少两个连续b的a、b串，例如bb、bbb等。r=(a
11、b)*bb(a
12、b)*。直接用状态转换矩阵构造：初态：{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不可区分）abAABBACCCC三、计算题（3.4）3.4（15分）有文法G和G的语法制导翻译如下：E→E1*T
13、{E.place=newtemp;emit(*,E1.place,T.place,E.place;}
14、T{E.place=T.place;}T→T1+F{T.place=newtemp;emit(+,T1.place,F.place,T.place;}
15、F{T.place=F.place;}F→(E){F.place=E.place;}
16、id{F.place=id.name;}(a)（4分）求句型(T+F)*id的短语、直接短语以及句柄；(b)（4分）根据语法制导翻译写出句子a*b+c*d的中间代码
17、；(c)（3分）若a=3，b=5，c=7，d=8，请给出中间代码计算结果；(d)（4分）将文法G简化为：E→E*T
18、T，T→T+F
19、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：部分习题解答9习题2.4写出下述语言的正规式描述（1）由偶数个0和
20、奇数个1构成的所有01串（2）所有不含子串011的01串（3）每个a后面至少紧随两个b的ab串（4）C的形如/*…*/的注释。其中…代表不含*/的字符串思路：分析题意，从最简单的例子考虑，然后找出统一规律（1）的解题步骤：1.最简单的符合要求的串：1、010（还有100、001、111等）2.所有01均为偶数的串：A=((00
21、11)
22、(01
23、10)(00
24、11)*(10
25、01))*3.符合要求的所有串：A1A、A0A1A0A（为什么没有后三个？）结果：A1A
26、A0A
