习题与试题 认真复习，重点是掌握基本概念。基本概念掌握了，相当一部分试题的解就有了

Presentation on theme: "习题与试题 认真复习，重点是掌握基本概念。基本概念掌握了，相当一部分试题的解就有了"— Presentation transcript:

1 习题与试题 认真复习，重点是掌握基本概念。基本概念掌握了，相当一部分试题的解就有了
习题与试题的目的区别：习题的目的是通过反复的练习理解、掌握所学知识，会有不少繁、难、大量步骤的题；试题的目的是考察对本课程综合掌握的情况，特点是短时间内覆盖大量内容。太繁琐步骤或太难等需要耗费大量时间的题是不可能出的 自己要会辨别什么是主要的什么是次要的，抓什么丢什么。“基本概念要严谨（清楚），基本方法要灵活” 总之一句话，学习方法的掌握是个人努力的结果，单纯靠别人教是学不会的

2 如果是我复习 词法分析 基本概念：正规式、正规集、有限自动机，词法分析器的构造
常见计算题类型：已知集合求正规式、DFA；已知正规式求DFA、集合；已知FA求正规式、集合；FA的确定化、最小化。 语法分析 基本概念：上下文无关文法、语言、下推自动机，LL分析与LR分析； 一些必要的定义、公式、算法的核心思想等； 常见的计算题类型：（自己思考） 基本解题方法与技巧等。 3. 语法制导翻译（略）4. 运行环境（略）（哪些最重要？）

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

4 实际试题举例 一、简答题 1.1（2分）有哪些方法可以去除文法的二义性。 1.2（2分）写出 -((a+b)*c)+d 的后缀式。
1.5（4分）试证明正规式(ab)*a与a(ba)*是等价的。 1.1 （1）改写文法 （2）规定文法符号的优先级和结合性 1.2 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.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，ε} 。

6 三、计算题（3.3） 3.3（13分）已知一个NFA如图。 (a)(4分) 用自然语言简要叙述该自动机所识别的语言
的特点，列举两个它可识别的串。 (b)（3分）写出与该自动机等价的正规式r。 (c)（6分）用子集法构造识别r的最小DFA。

7 （3.3）解： 含有至少两个连续b的a、b串，例如bb、bbb等。 r=(a|b)*bb(a|b)*。 直接用状态转换矩阵构造：
初态：{0} 子集法得：（2是终态） a b {0} {0,1} {0,1,2} {0,2} 令： {0}=A，{0,1}=B，{0,1,2}=C，{0,2}=D 得： a b A B C D 最小化DFA得：（C和D不可区分） a b A B C

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）解： 短语：(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：

10 部分习题解答

11 习题2.4 写出下述语言的正规式描述 （1） 由偶数个0和奇数个1构成的所有01串 （2） 所有不含子串011的01串
（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为终态 求出它的最小DFA 用正规式描述DFA所接受的语言
b c ε S A,B C,D D A,B,C A C B 求出它的最小DFA 用正规式描述DFA所接受的语言 问题：根据DFA写出对应的正规式，通常的考虑和步骤是什么？ 再重复一遍： 正规式、DFA是从两个不同的侧面表示一个集合(即正规集)。所以，根本的方法是把正规集作为桥梁，先分析清楚DFA识别出的是一个什么集合，然后再设计此集合的正规式。反之亦然。

15 习题2.10（2）的解 该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|B A→1|2|3|4|5|6|7|8|9 B→1|3|5|7|9 C→ε|0C|AC

17 习题 3.17 对于文法G3.4和它所产生的句子-id+id*id 和 -(id+id)*id E → E+T|T
T → 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]:=sj goto[I,A]:=k 2．可归约项分两步走：若在I状态中有[A→α.]， 首先计算：FOLLOW(A), 然后填写：action[I,b]:=Ri 其中：b∈FOLLOW(A)且A→α是第i个产生式。

19 习题 4.4 假定下述程序分别采用值调用，引用调用，复写-恢复和换名调用，请给出它们的打印结果。
program main(input output); procedure p(x,y,z); begin y:=y+1; z:=z+x end; begin a:=2; b:=3; p(a+b, a, a); print a end; 两种解题的思路： 1. 把自己当作计算机，按照参数传递的实现方式“运行”一遍程序，得出结果； 2. 找台机子把程序敲进去试试（辅助手段） 困惑的是：表达式a+b如何作为引用调用和复写-恢复的实参？ 解决方案：忽略返回值问题。其实这一思想可以推广到任何不支持某种方式的情况（放心，考试中不会有这种很困惑的问题） 具体结果（略）

20 习题5.5 有一过程A如下所示。采用静态作用域、最近嵌套原则，设A是第0层的过程。 procedure A is
procedure B is Procedure D is x : character; begin …… end D; begin …… end B; procedure C is x : integer; procedure E is y: integer; begin …… end E; procedure F is y: float ; begin …… end F; begin …… end D; begin …… end A;

21 习题5.5（续） （4）若一个可能的程序运行控制流是 A-C-E-F-B,试给出每次调用和返回时的控制栈中各活动记录的可确定内容和显示表的变化； （5）分别给出C调用E的调用序列和从E返回的返回序列。 说明：（4）（5）是学生希望讲解的题目 解： （4）若一个可能的程序运行控制流是 A-C-E-F-B，给出控制栈中的内容和控制链与访问链的指向。 静态嵌套结构、活动栈、以及控制链与访问链：

22 To know how to do something well is to enjoy it
To know how to do something well is to enjoy it. 战略上藐视敌人，战术上重视敌人。 The trees that are slow to grow bear the best fruit. 认真复习、迎接考试 （结 束 2007年6月19日）

23 附件1：教材与习题答案中的错误 教材 23页：例2.7上边两行：将“M[si,sj]”改为“M[si,ch]”
附件1：教材与习题答案中的错误 教材 23页：例2.7上边两行：将“M[si,sj]”改为“M[si,ch]” 将“...是从状态si到状态sj的边上的标记ch(或ε)。”改为“...是从状态si经ch(或ε)到达的下一状态sj。” 24页：倒11行：将“M[si,sj]”改为“M[si,ch]” 25页：图2.7最后一行状态“000”应改为“012” 34页：算法2.6方法④2、3行：将“从si出发”改为“从si'出发”，将“称为D的初态”改为“称为D'的初态” 45页：10行：将“N是仅出现”改为“仅N是可以出现” 70页：例3.23：将FOLLOW集合中的“＄”改为“＃” 75页：到4行：将“文法G3.13”改为“文法G3.12” 81页：图3.22：将I0中的“T→.-F”改为“F→.-F”

24 教材 习题解答 附件1：教材与习题答案中的错误（续1）
100页：图4.2：将A.code=(3)“(x,:=,(2))”改为“(:=,x,(2))” 129页：例4.17的中间代码：将“t3:=+r t4”改为“t3:=C +r t4” 133页：例4.18的中间代码：将“t5:=t3*t4”改为“t5:=t3*4”，将“V7”改为“V5” 134页：图4.16：将“V5、V6、V7”分别改为“V6、V7、V5” 136页：4.7.3上边一行：将“ptr^.data/=x”改为“ptr^.data=x” 138页：例4.20：将代码序列中的“L1”改为“L2”， “L2”改为“L1” 144页：例4.23上边一行：将“mklist”改为“mkchain” 习题解答 4页：2.4(1)：A1A|A0A1A0可以简化为A(1|010)A 32页：缺少3.19(1)的解答 32页：到2行：将两处“I10”均改为“I11”，将“I12”改为“I13”

25 二班同学提出的问题及相应解答 习题3.6 设字母表Σ={0,1},设计下述语言的文法。对于正规语言， 可用正规式表示。
（1）每个0后面至少跟随一个1的字符串 （2）0和1个数相等的字符串 （3）0和1个数不相等的字符串 （4）不以011作为子串的字符串 解：（1）(01|1)* （2）S→0S1S|1S0S|ε （3）S→A0A|B1B A→0A1A|1A0A|0A|ε B→0B1B|1B0B|1B|ε （4）1*(0|01)*

26 习题3.22 构造SLR(1)分析表的算法3.9基于的假设是LR(0)项目集中可能有
可以简化（无需计算FOLLOW集合），得到的是LR(0)分析表。试 修改算法3.9成为构造LR(0)分析表的算法。 1.if DFA中有不能解决的移进/归约和归约/归约冲突 then error; else for 每个状态转移Dtran[i,x]=j loop if x∈T then action[i,x]:=Sj; else goto[i,x]:=j; end if; end loop; for 状态i的每个可归约项A→α. loop if S'→ S. then action[i, #]:=acc; else for 每个a∈FOLLOW(A) loop action[i,a]:=Rk; end loop; 状态i： A→α. x B→β. 每个终结符a

27 习题4.9 设整型数组声明的形式为int A[d1,d2,…,d3]，并且假设每个整型 数占据4个字节。
（1）试导出以列为主存储时计算c和v的递推公式； （2）*设计数组声明的语法制导翻译（包括语法和语义），以使得 在对数组声明从左到右分析的同时，正确填写符号表和内情向量的 所有信息。 解： （1） n=1时，addr(A[i1])=a+(i1-1)*4 n=2时，addr(A[i1,i2])=a+(i2-1)*d1*4+(i1-1)*4 addr(A[i1,i2,…,in])=???

28 n维数组元素的地址计算 addr(A[i1，i2，...，in]) =a+((in-1)*dn-1*dn-2*...*d1+(in-1-1)*dn-2*dn-3*...*d (i1-1))*w =a-(dn-1*dn-2*...*d1+dn-2*dn-3*...*d1+...+d1+1)*w +(in*dn-1*dn-2*...*d1+in-1*dn-2*dn-3*...*d1+...+i2*d1+i1)*w =a–c*w+v*w 其中： c=dn-1*dn-2*dn-3…*d1+dn-2*dn-3*dn-4…*d1+*dn-3*dn-4*dn-5…*d1…+d1+1 =(dn-1+1)*dn-2*...*d1+dn-3*dn-4...*d1+...+d1+1 =((dn-1+1)*dn-2+1)*dn-3*dn-4...*d1+...+d1+1 ...... =(...((dn-1+1)*dn-2+1)*dn )*d1+1 同理： v = (...((in*dn-1+in-1)*dn-2+in-2)*dn-3...+i2)*d1+i1

29 n维数组元素的地址计算（续1） c=(...((dn-1+1)*dn-2+1)*dn )*d1+1 v=(...((in*dn-1+in-1)*dn-2+in-2)*dn-3...+i2)*d1+i1 a[i,j]:=x A V := E N [ EL x , a ] i j 修改文法以适应递推公式的同步计算： A → V := E (1) V → id (2) | N [ EL ] (3) N → id (4) EL→ E (5) | E , EL (6) E → E + E (7) | ( E ) (8) | V (9) 令： v0 = in 则： v1 = in*dn-1+in-1 = v0*dn-1+in-1 v2 = (v0*dn-1+in-1)*dn-2+in-2 = v1*dn-2+in-2 ...... 于是有： v0 = in vj = vj-1*dn-j+in-j (j=1，2，..., n-1) 同理可得： c0 = 1 cj = cj-1*dn-j+1 (j=1，2，..., n-1) （2）要适合LR分析，应该将文法改成右递归的。

30 习题4.10 教材中的语法制导翻译将表达式E→id1<id2翻译成一对三地址码 if id1<id2 goto – goto –
这样性质的三地址码序列。 解： 与原来翻译方案的根本区别在于：表达式为真时并不生成三地址码，因此表达式的真出口默认为下一条三地址码。 如果真出口不是下一条三地址码，则仍需要生成两条goto语句。