编译程序总复习例题.ppt

1、编译程序总复习例题,1. 编译程序的功能和组织结构 2. 编译和解释程序 3. 正则表达式 NFA DFA DFA 最小化 句型推导的语法树短语简单短语句柄,6.文法语言句子 7.语法分析自顶向下和自底向上 （LL法、 LR法） 8.语法制导翻译 9.中间代码 10.中间代码优化 11.目标代码,1 . 编译程序的功能和组织结构,表 处 理,词 法 分 析,源 程 序,目 标 程 序,错 误 处 理,语 法 分 析,语 义 分 析,目 标 代 码 生 成,前 端,后 端,中 间 代 码 优 化,中 间 代 码 生 成,2. 编译和解释程序,目标程序,源 程 序,编 译 程 序,初始数据,计 算

2、 结 果,解释程序和编译程序的区别,解释程序和编译程序的根本区别： 是否生成目标代码,3. 正则表达式,设文法GA: A B B X | BA X Xa | Xb | a | b 试求出文法GA产生的语言对应的正则式。,3. 设文法GA:ABB X | BAX Xa | Xb | a | b试求出文法GA产生的语言对应的正则式。,解: (a|b)(a|b)* (a|b)(a|b)*)*,4.请构造与正则式R=(a*b)*ba(a|b)* 等价的状态最少的DFA（确定有限自动机）。,解： (1) NFA (2) NFA DFA (3) DFA 最小化,5.有文法GE：ET|E+T|E-T TF|

3、T*F|T/F Fi/(E),请判断(E+T)*i+F是G的一句型吗？ 如果是，请画出它的推导的语法树。 并写出语法树的短语、简单短语、句柄。,有文法GE： ET|E+T|E-T TF|T*F|T/F Fi/(E),(E+T)*i+F是G的一句型,),E,(,+,E,T,E,+,E,T,T,F,F,*,T,i,F,每棵子树的叶组成短语 (E+T)*i+F (E+T)*I (E+T) E+T i F,每棵简单子树的叶组成简单短语 E+T i F,最左简单子树的叶组成句柄 E+T,6.（1）设有文法GS=(b,S,B,S, S b|bB,BbS),该文法所描述的语言是_。（2）已知语言L=anbb

4、n|n 1，则_文法可以产生语言L。（3）设有文法GI：II1 | I0 | Ic | a | b | c 该文法的句子有_ ab0 a0c01 aaa bc10,6.（1）设有文法GS=(b,S,B,S, S b|bB,BbS),该文法所描述的语言是 L（GS=b2i+1|i 0 （2）已知语言L=anbbn|n 1，则 Z aAb A aAb | b 上述文法可以产生语言L。 （3）设有文法GI： II1 | I0 | Ic | a | b | c 该文法的句子有 。 ab0 a0c01 aaa bc10,7. 设有文法GS：SEEAa | bBAcA|dBcB|d构造其LR(0)分析表并

5、利用分析表判断acccd是否为文法GS的句子。,7. 设有文法GS：SEEAa | bBAcA|dBcB|d构造其LR(0)分析表并利用分析表判断acccd是否为文法GS的句子。,解： （1）识别活前缀的自动机 （2）LR分析表 （3）LR分析过程即判断acccd是否为文法GS的句子,8 .在一个移入-规约的分析中采用以下的语法制导的翻译模式，在按一产生式规约时，立即执行括号中的动作。A aB print “0”A c print “”B Ab print “2”当分析器的输入为aacbb时，打印的字符串是什么？,分析器输入为aacbb，打印的字符为 12020,b,B,c,A,A,a,B,A

6、,a,b,A aB print “0”A c print “”B Ab print “2”,9. （1）表达式a*b-c-d$e$f-g-h*I中，运算符的优先级由高到低依次为-、*、$，且均右结合，且相应的后缀式为_。（2）表达式-a+b*c+d+(e*f)/d*e,如果运算符的优先级由高到低依次为-、+、*、/，且均左结合，则其后缀式为_。,9. （1）表达式a*b-c-d$e$f-g-h*I中，运算符的优先级由高到低依次为-、*、$，且相应的后缀式为abcd - - *efgh - -I*$。 （2）表达式-a+b*c+d+(e*f)/d*e，如果运算符的优先级由高到低依次为-、+、*、

7、/，且均左结合，则其后缀式为 a-b+cd+ef*+*de*/。,10.试写出算术表达式a+b*c-(c*b+a-e)/(b*c+d)优化后的四元式序列。,11.目标代码,写出下列表达式的目标代码 T := C*（A+B）+（A+B） C := A+B A :=（C*D）+（E-F）,写出下列表达式的目标代码 T := C*（A+B）+（A+B） C := A+B A :=（C*D）+（E-F） 解答： LOADA,R1 ADDB,R1 LOAD C,R2 MULT R1,R2 ADD R1,R2 STORE G,R2,LOADE,R2 SUB F,R2 STOREC,R1 MULT D,R1 ADD R2,R1 STORE A,R2,编译器设计方案, C 惯用的词法 C 语言的Tiny Machine 运行时环境 C 的语法和语义 使用C 和T M 的编程设计 C 的程序例子 这里定义了一个编程语言称作C M i n u s (或简称为C )，这是一种适合编译器设计方案的语言，它比T I N Y 语言更复杂，包括函数和数组。本质上它是C