西安电子科技大学编译原理总复习-习题与试题-2010.ppt

《编译原理》复习 西安电子科技大学 软件工程研究所 刘 坚 课程内容 第一章 引言 1 语言的翻译 2 编译器的基本组成 3 编译器的分析－综合模式 第二章 词法分析 1 记号、模式与单词 3 记号的识别－有限自动机（FA） 4 从正规式到词法分析器 第三章 语法分析 1 程序设计语言与文法 2 有关推导的基本概念 3 自上而下分析 3 自上而下分析（续） 4 自下而上分析 4 自下而上分析（续1） 4 自下而上分析（续2） 第四章 语法制导翻译生成中间代码 1 语法制导翻译的基本概念 2 基本设计方法 3 中间代码 4 符号表的组织 5 声明语句的翻译 6 可执行语句的翻译 结 束（2010年5月25日） 试题与习题 关于考试 实际试题举例一、简答题 二、填空题（30分） 三、计算题（1） 解： 三、计算题（2） 解： 部分习题解答 习题2.4 （4） C的形如/*…*/ 的注释。其中…代表不含*/的字符串 习题2.9 习题2.10 习题2.10（2）的解 习题3.7 习题3.14 习题3.11+3.18 习题3.11+3.18（续） To know how to do something well is to enjoy it.战略上藐视敌人，战术上重视敌人。 The trees that are slow to grow bear the best fruit. 习题 3.17 习题 3.17（解） 构造SLR（1）分析表的方法： 习题3.6 习题3.22 习题 4.4 习题4.9 n维数组元素的地址计算 n维数组元素的地址计算（续1） 习题4.10 2（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。 (a) 短语：(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： 写出下述语言的正规式描述 （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又应该如何构造？ 思路：注释中若遇到*：若后边是/则结束注释否则仍然是注释 步骤： 1. 注释串是空； 2. 考虑没有*的注释； 3. 考虑含*的注释 结果：(4) /* ([^*]|*[^/])* */ （2） 所有不含子串011的01串：1*(01|0)* （3） 每个a后面至少紧随两个b的ab串：(b|abb)* 用自然语言给出下述正规式所描述的语言，并构造他们的最小DFA：10*1 (0|1)*011(0|1)* 说明：所谓用自然语言描述就是解释字符串的性质，一般情况下是已经有了形式化描述。 解： 10*1：首尾是1中间有零或若干个0的01串。 (0|1)*011(0|1)* ：至少含一个011的01串。 注意： *是0或若干次的重复；+是至少一次的重复 绝对不允许用正规式表示，因为正规式是已知条件 DFA（略）(0|1)*011(0|1)* 的DFA构造与考试题中