资源描述：
《编译原理总复习-习题与试题.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、习题与试题认真复习，重点是掌握基本概念。基本概念掌握了，相当一部分试题的解就有了习题与试题的目的区别：习题的目的是通过反复的练习理解、掌握所学知识，会有不少繁、难、大量步骤的题；试题的目的是考察对本课程综合掌握的情况，特点是短时间内覆盖大量内容。太繁琐步骤或太难等需要耗费大量时间的题是不可能出的自己要会辨别什么是主要的什么是次要的，抓什么丢什么。“基本概念要严谨（清楚），基本方法要灵活”总之一句话，学习方法的掌握是个人努力的结果，单纯靠别人教是学不会的如果是我复习词法分析基本概念：正规式：正规表达式
2、。正规集：正规表达式所表示的集合。有限自动机(一个五元数组)：确定的有限自动机(DFA)和非确定的有限自动机(NFA)。词法分析器的构造：1)单词符号分类；2)单词输出的形式常见计算题类型：已知集合求正规式、DFA；已知正规式求DFA、集合；已知FA求正规式、集合；FA的确定化、最小化。语法分析基本概念：上下文无关文法、语言、下推自动机，LL分析与LR分析；一些必要的定义、公式、算法的核心思想等；常见的计算题类型：（自己思考）基本解题方法与技巧等。3.语法制导翻译（略）4.运行环境（略）（哪些最重要
3、？）关于考试题目类型：简答题(25分)、填空题(25分)、计算题(50分)内容分布(大概)：概述与词法分析(30分)、语法分析(40分)、语法制导翻译与运行环境(30分)考试范围：1－5章讲过的内容侧重考察：基本概念与基本方法的掌握易犯的错误不认真审题（对题目的要求理解错误：意思理解错、难题想容易、容易题想难。关键问题是基本概念不清楚）所答非所问(例如：没有要求LL分析却将文法改为LL的)画蛇添足(例如：仅问有无冲突却将分析表先构造出来)偷工减料(例如：有若干问，仅回答部分或问题仅答一半)警示千万不
4、要作弊！命运掌握在自己的手中！3实际试题举例一、简答题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(
5、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
6、RTT→DR
7、εR→dR
8、εD→a
9、bd则FIRST(S)=，FIRST(D)=，FIRST(T)=，FIRST(R)=。2.2语法分析、语义
10、分析、代码优化、目标代码生成、符号表管理和出错处理2.3r和s表示的正规集2.4a*(b
11、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）解：含有至少两个连续b的a
12、、b串，例如bb、bbb等。r=(a
13、b)*bb(a
14、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{E.place=ne
15、wtemp;emit(*,E1.place,T.place,E.place;}
16、T{E.place=T.place;}T→T1+F{T.place=newtemp;emit(+,T1.place,F.place,T.place;}
17、F{T.place=F.place;}F→(E){F.place=E.place;}
18、id{F.place=id.name;}(a)（4分）求句型(T+F)*id的短语、直接短语以及句柄；(b)（4分）根据语法制导翻译写出句子a*b+c*d
