《编译程序总复习例题》由会员分享，可在线阅读，更多相关《编译程序总复习例题（23页珍藏版）》请在金锄头文库上搜索。
1、编译程序总复习编译程序总复习例题例题1. 1. 编译程序的功能和组织结构编译程序的功能和组织结构2. 2. 编译和解释程序编译和解释程序3. 3. 正则表达式正则表达式 NFA DFA DFA NFA DFA DFA 最小化最小化 句型句型推导的语法树推导的语法树短语短语简单短语简单短语 句柄句柄6.6.文法文法语言语言句子句子7.7.语法分析语法分析自顶向下和自底向上自顶向下和自底向上（LLLL法、法、 LRLR法）法） 8.8.语法制导翻译语法制导翻译 9.9.中间代码中间代码 10.10.中间代码优化中间代码优化 11.11.目标代码目标代码1 . 编译程序的功能和组织结构表 处 理词
2、法 分 析源 程 序目 标 程 序错 误 处 理语 法 分 析语 义 分 析目 标 代 码 生 成前前 端端后 端中 间 代 码 优 化中 间 代 码 生 成2. 编译和解释程序目标程序源 程 序编 译 程 序初始数据计 算 结 果源程序解 释 程 序初始数据计 算 结 果功能工作结果实现技术上解释解释 程序程序源程序的一源程序的一 个个执执执执行行系系统统统统源程序的源程序的 执执执执行行结结结结果果执执执执行中行中间间间间代代码码码码编译编译 程序程序源程序的一源程序的一 个个转换转换转换转换 系系统统统统源程序的源程序的 目目标标标标代代码码码码把把中中间间间间代代码转码转码转码转 换换
3、换换成目成目标标标标程序程序解释程序和编译程序的区别解释程序和编译程序的根本区别根本区别： 是否生成目标代码3. 正则表达式设文法GA: A B B X | BA X Xa | Xb | a | b 试求出文法GA产生的语言对应 的正则式。3. 设文法GA: AB B X | BA X Xa | Xb | a | b 试求出文法GA产生的语言对应的正则式 。解解: : ( (a|b)(a|b)* (a|b)(a|b)*)*a|b)(a|b)* (a|b)(a|b)*)*4. 4.请构造与正则式请构造与正则式R=(a*b)*R=(a*b)*baba(a|b)* (a|b)* 等价的状态最少的等价
4、的状态最少的DFADFA（确定有限自确定有限自 动机）。动机）。解：解： (1) (1) NFANFA (2) NFA DFA(2) NFA DFA (3) DFA (3) DFA 最小化最小化5.5.有文法有文法GEGE：E ET|E+T|E-TT|E+T|E-TT TF|T*F|T/FF|T*F|T/FF Fi/(E)i/(E)请判断请判断( (E+T)*i+FE+T)*i+F是是G G的一句型的一句型 吗？吗？ 如果是，请画出它的推导的语法如果是，请画出它的推导的语法 树。树。 并写出语法树的短语、简单短语并写出语法树的短语、简单短语 、句柄。、句柄。有文法有文法GEGE：E ET|E+
5、T|E-TT|E+T|E-TT TF|T*F|T/FF|T*F|T/FF Fi/(E)i/(E)( (E+T)*i+FE+T)*i+F是是G G的一句型的一句型) )E E( (+ +E ET TE E+ +E ET TT TF FF F* *T Ti iF F每棵子树的每棵子树的 叶组成叶组成短语短语 ( (E+T)*i+FE+T)*i+F (E+T)*I(E+T)*I (E+T)(E+T) E+TE+Ti iF F每棵简单子每棵简单子 树的叶组成树的叶组成 简单短语简单短语 E+T E+T i iF F最左简单子树的叶组成最左简单子树的叶组成句柄句柄 E+TE+T6.6.（1 1）设有文法
6、）设有文法GS=(b,S,B,S, GS=(b,S,B,S, S b|S b|bBbB,B,BbSbS), ,该文法所描述的该文法所描述的 语言语言是是_。（2 2）已知语言）已知语言L=L=a an nbbbbn n|n 1|n 1，则则 _文法文法可以产生语言可以产生语言L L。（3 3）设有文法设有文法GIGI： II1 | I0 | II1 | I0 | Ic Ic | a | b | c | a | b | c 该文法的该文法的句子句子有有 _ab0 ab0 a0c01 a0c01 aaa aaa bc10bc106.6. （1 1）设有文法）设有文法GS=(b,S,B,S, S G
7、S=(b,S,B,S, S b|b|bBbB,B,BbSbS),),该文法所描述的语言是该文法所描述的语言是L L（GS=bGS=b2i+12i+1|i 0|i 0 （2 2）已知语言已知语言L=L=a an nbbbbn n|n 1|n 1，则则Z Z aAbaAbA A aAbaAb | b | b上述文法可以产生语言上述文法可以产生语言L L。 （3 3）设有文法设有文法GIGI：II1 | I0 | II1 | I0 | Ic Ic | a | b | c | a | b | c 该文法的该文法的句子句子有有 。ab0 ab0 a0c01 a0c01 aaa aaa bc10bc107
8、. 7. 设有文法设有文法GSGS： SESE EEAaAa | | bB bB AAcAcA|d|d BBcBcB|d|d 构造其构造其LR(0)LR(0)分析表并利用分析分析表并利用分析 表判断表判断acccdacccd是否为文法是否为文法GSGS的句的句 子。子。 7. 7. 设有文法设有文法GSGS： SESE EEAaAa | | bB bB AAcAcA|d|d BBcBcB|d|d 构造其构造其LR(0)LR(0)分析表并利用分析表判断分析表并利用分析表判断acccdacccd是否为是否为 文法文法GSGS的句子。的句子。 解解： （1 1）识别活前缀的自动机）识别活前缀的自动机
9、 （2 2）LRLR分析表分析表 （3 3）LRLR分析过程分析过程即即判断判断 acccdacccd是否为文法是否为文法GSGS的句子的句子8 .8 .在一个移入在一个移入- -规约的分析中采用规约的分析中采用 以下的语法制导的翻译模式，在按以下的语法制导的翻译模式，在按 一产生式规约时，立即执行括号中一产生式规约时，立即执行括号中 的动作。的动作。 A A aB print “0” A A c print “” B Ab print “2” 当分析器的输入为aacbb时，打印 的字符串是什么？分析器分析器输 入为aacbb， 打印的字符打印的字符 为为 1202012020b bB Bc
10、cA AA Aa aB BA Aa ab bA A aB print “0” A A c print “” B Ab print “2”9. 9. （1 1）表达式）表达式a*b-c-d$e$f-g-h*Ia*b-c-d$e$f-g-h*I中中 ，运算符的优先级，运算符的优先级由高到低由高到低依次依次 为为- -、* *、$ $，且均，且均右结合右结合，且相应，且相应 的后缀式为的后缀式为_。 （2 2）表达式）表达式- -a+b*c+d+(e*f)/d*ea+b*c+d+(e*f)/d*e, , 如果运算符的优先级如果运算符的优先级由高到低由高到低依依 次为次为- -、+ +、* *、/ /
11、，且均，且均左结合左结合，则，则 其后缀式为其后缀式为_。9. 9. （1 1）表达式）表达式a*b-c-d$e$f-g-h*Ia*b-c-d$e$f-g-h*I中，运算符的中，运算符的 优先级由高到低依次为优先级由高到低依次为- -、* *、$ $，且相应的后，且相应的后缀式为缀式为abcdabcd - - * - - *efghefgh - -I*$ - -I*$。（2 2）表达式表达式- -a+b*c+d+(e*f)/d*ea+b*c+d+(e*f)/d*e，如果运如果运 算符的优先级由高到低依次为算符的优先级由高到低依次为- -、+ +、* *、/ /，且，且 均左结合，则其后缀式为均
12、左结合，则其后缀式为a-b+a-b+cdcd+ +efef*+*de*/*+*de*/。10.10.试写出算术表达式试写出算术表达式a+b*c-(c*b+a-e)/(b*c+d)a+b*c-(c*b+a-e)/(b*c+d)优化后的四元式序列。优化后的四元式序列。11.11.目标代码目标代码写出下列表达式的目标代码写出下列表达式的目标代码 T := C*T := C*（A+BA+B）+ +（A+BA+B） C := A+BC := A+B A :=A :=（C*DC*D）+ +（E-FE-F） 写出下列表达式的目标代写出下列表达式的目标代 码码 T T := := C*C*（A+BA+B）+
13、+（A+BA+B ） C := A+BC := A+B A :=A :=（C*DC*D）+ +（E-FE-F） 解答：解答： LOADLOADA,R1A,R1 ADDADDB,R1B,R1 LOAD LOAD C,R2C,R2 MULT MULT R1,R2R1,R2 ADD ADD R1,R2R1,R2 STORE STORE G,R2G,R2LOADLOADE,R2E,R2 SUB SUB F,R2F,R2 STORESTOREC,R1C,R1 MULT MULT D,R1D,R1 ADD ADD R2,R1R2,R1 STORE STORE A,R2A,R2编译器设计方案编译器设计方案
14、C C 惯用的词法惯用的词法 C C 语言的语言的Tiny Machine Tiny Machine 运行时环境运行时环境 C C 的语法和语义的语法和语义 使用使用C C 和和T M T M 的编程设计的编程设计 C C 的程序例子的程序例子 这里定义了一个编程语言称作这里定义了一个编程语言称作C C M i n u s M i n u s ( (或简称或简称为为C C ) )，这是一种适合编译器设计方案这是一种适合编译器设计方案 的语言，它比的语言，它比T I N Y T I N Y 语言更复杂，包括函数和语言更复杂，包括函数和 数组。本质上它数组。本质上它是是C C 的一个子集，但省去了一的一个子集，但省去了一 些重要的部分，因此得名。些重要的部分，因此得名。 语言惯用的词法语言惯用的词法( (包括语言标记的包括语言标记的 描述描述) ) 每个语言构造的每个语言构造的B N F B N F 描述描述 相关语义的英语描述相关语义的英语描述 C C 的两个示例程序的两个示例程序 C C 的一个的一个Tiny Machine Tiny Machine 运行时运行时 环境环境 C C
