编译程序总复习-例题

编译程序总复习——例题1.编译程序的功能和组织结构2.编译和解释程序3.正则表达式NFA→DFA→DFA最小化句型→推导的语法树→短语→简单短语→句柄6.文法←→语言←→句子7.语法分析——自顶向下和自底向上（LL法、LR法）8.语法制导翻译9.中间代码10.中间代码优化11.目标代码1.编译程序的功能和组织结构表处理词法分析源程序目标程序错误处理语法分析语义分析目标代码生成前端后端中间代码优化中间代码生成2.编译和解释程序目标程序源程序编译程序初始数据计算结果源程序解释程序初始数据计算结果功能工作结果实现技术上解释程序源程序的一个执行系统源程序的执行结果执行中间代码编译程序源程序的一个转换系统源程序的目标代码把中间代码转换成目标程序解释程序和编译程序的区别解释程序和编译程序的根本区别：是否生成目标代码3.正则表达式设文法G[A]:A→[BB→X]|BAX→Xa|Xb|a|b试求出文法G[A]产生的语言对应的正则式。3.设文法G[A]:

A→[B

B→X]|BA

X→Xa|Xb|a|b

试求出文法G[A]产生的语言对应的正则式。解:

[(a|b)(a|b)*]([(a|b)(a|b)*])*4.请构造与正则式R=(a*b)*ba(a|b)*等价的状态最少的DFA（确定有限自动机）。解：(1)NFA(2)NFA→DFA(3)DFA最小化5.有文法G[E]：ET|E+T|E-T

TF|T*F|T/F

Fi/(E)请判断(E+T)*i+F是G的一句型吗？如果是，请画出它的推导的语法树。并写出语法树的短语、简单短语、句柄。有文法G[E]：ET|E+T|E-TTF|T*F|T/FFi/(E)(E+T)*i+F是G的一句型)E(+ETE+ETTFF*TiF每棵子树的叶组成短语(E+T)*i+F(E+T)*I(E+T)E+TiF每棵简单子树的叶组成简单短语E+TiF最左简单子树的叶组成句柄

E+T6.（1）设有文法G[S]=({b},{S,B},S,{S→b|bB,B→bS}),该文法所描述的语言是_________。

（2）已知语言L={anbbn|n≥1}，则_______文法可以产生语言L。

（3）设有文法G[I]：

I→I1|I0|Ic|a|b|c该文法的句子有________

①ab0②a0c01③aaa④bc106.

（1）设有文法G[S]=({b},{S,B},S,{S→b|bB,B→bS}),该文法所描述的语言是

L（G[S]={b2i+1|i≥0}

（2）已知语言L={anbbn|n≥1}，则

Z→aAb

A→aAb|b

上述文法可以产生语言L。（3）设有文法G[I]：

I→I1|I0|Ic|a|b|c该文法的句子有②③④。

①ab0②a0c01③aaa④bc107.

设有文法G[S]：

S→E

E→Aa|bB

A→cA|d

B→cB|d

构造其LR(0)分析表并利用分析表判断acccd是否为文法G[S]的句子。

7.

设有文法G[S]：

S→E

E→Aa|bB

A→cA|d

B→cB|d

构造其LR(0)分析表并利用分析表判断acccd是否为文法G[S]的句子。

解：（1）识别活前缀的自动机（2）LR分析表（3）LR分析过程——即判断acccd是否为文法G[S]的句子8.在一个移入-规约的分析中采用以下的语法制导的翻译模式，在按一产生式规约时，立即执行括号中的动作。

A→aB{print“0”}

A→c{print“”}

B

→Ab{print“2”}

当分析器的输入为aacbb时，打印的字符串是什么？分析器输入为aacbb，打印的字符为12020bBcAAaBAab⑤④③②①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，如果运算符的优先级由高到低依次为-、+、*、/，且均左结合，则其后缀式为

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+BA:=（C*D）+（E-F）

写出下列表达式的目标代码T:=C*（A+B）+（A+B）C:=A+BA:=（C*D）+（E-F）解答：LOAD A,R1ADD B,R1LOAD C,R2MULT R1,R2ADD R1,R2STORE G,R2LOAD E,R2SUB F,R2STORE C,R1MULT D,R1ADD R2,R1STORE A,R2编译器设计方案•C－惯用的词法•C－语言的TinyMachine运行时环境•C－的语法和语义•使用C－和TM的编程设计•C－的程序例子这里定义了一个编程语言称作C－Minus(或简称为C－)，这是一种适合编译器设计方案的语言，它比TIN