试题编号 :553

试题名称 :编译原理

一 :已知正规文法中的左线性文法

G1:S→Sa|Sb|c

试构造无ε产生式的等价右线性文法 ,并构造相应的确定有限自动机DFA,画出状态转换图即可.

二 :已知正规文法(X为开始符号)

G2: X→0Y|1Z|0

Y→0X|1Y|1

Z→1X

1.该文法产生语言是什么?请用正规式表示.

2.构造最简的确定有限自动机DFA,并画出状态转换图.

三 :已知上下文无关文法(E为开始符号)

G3: E→ET+|T

T→TF*|F

F→E|i

1.消除文法左递归,并给出改写后的文法产生式;

2.给出文法改写以后的各非终结符X的First(X)与Follow(X)集合,并由此判定它是否是LL(1)文法(按下表填).

V(N) │ First(X) │ Follow(X)

────┼──────┼───────

X 　│　　　　　　│

...　│　　　　　　│

　　　　│　　　　　　│

四 :已知表达式文法(已拓广)

G4: E'→E

E→E+E|i

1.试构造文法G4的LR(0)项目集规范族;

2.若'+'服从右结合率,请给出LR分析表.

五 :已知文法(Z为开始符号)

G5: Z→bMb

M→(Ma)|a

1.试构造算符优先分析表(即填下表);

　 │　 a │　b │　( │ ) │　# │

──┼──┼──┼──┼──┼──┼

a │　　│　　│　　│　　│　　│

──┼──┼──┼──┼──┼──┼

b │　　│　　│　　│　　│　　│

──┼──┼──┼──┼──┼──┼

( │　　│　　│　　│　　│　　│

──┼──┼──┼──┼──┼──┼

) │　　│　　│　　│　　│　　│

──┼──┼──┼──┼──┼──┼

# │　　│　　│　　│　　│　　│

──┼──┼──┼──┼──┼──┼

2.若某相邻的终结符a,b间存在a<=b两种关系,那么在进行算符优先分析做归约动作时,在寻找栈顶的素短语符号串时要察看它与哪个产生式右部的符号串匹配.

例如栈顶串 ...aAbα(a,b∈VT,A∈(VA∪ε),a<=b,α∈V*)为已知可归约,而现有产生式X→aAbα,则取素短语aAbα,若只有产生式Y→Abα,那么就取Abα进行归约.试按此规定的算法给出语句b((aa)a)b的算符优先分析过程.

六 :翻译成中间代码.

1.将如下程序段翻译成后缀式(逆波兰式),填在一维数组POST[i]中,设i初值=1.

t:=15;

b:=20;

while t<>b do

if t>b then t:=t-b

else b:=b-t;

2.翻译布尔表达式成转移四元式序列,并指出待填真假链序号.

(a>b+1) and not (c+2<d) or f(x)

注 :f(x)为布尔函数.

七 :有如下一个计算m*2^n的C语言程序,试给出运行时整个栈或数据区的结构.数据区的活动记录结构如图所示.

┌──────┐┌─────┐

│ 函数 f返回值││返回结果值│

├──────┤├─────┤

│ 局部变量区 ││局部变量区│

├──────┤├─────┤

│ 全程变量区 ││形参单元区│

├──────┤├─────┤

│ 主程序 main ││ 返回地址 │

│ 　数据区 　│├─────┤

└──────┘│ 基 SP │

├─────┤

│函数数据区│

└─────┘

int m;

f(n)

int n;

{ int c;

if (n==0) c=m;

else c=f(n-1)*2;

return (c);

}

main()

{ int n=2;

m=5;

printf("%d/n",f(n));

}

八 :已知如下程序段

a:=1;

while a<=10 do

begin

if a<>b then

A[a,b]:=A[a,b]+2;

a:=a+1;

end;

1.按语法制导生成四元式中间代码序列;

2.将中间代码序列划分成基本块,画出程序流图,并指出循环结点集;

3.执行循环中代码外提,强度减弱优化和基本块内删除公共子表达式优化,最后画出包含优化后的中间代码的程序流图.