习题与试题课件.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是终态） a b {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 得： a b A A B B A C C D C D D C 最小化DFA得：（C和D不可区分） a b A A B B A C C C C * 三、计算题（3.4） 3.4（15分）有文法G和G的语法制导翻译如下： E→E1*T { E.place=newtemp; emit(*,E1.place