2001年编译原理部分

1  请写出∑={a, b}上的第三个字符为b的a, b字符串集的正规式以及识别该正规式的状态最少的DFA（10分）。

 

2  对右列文法及相应的翻译方案，              P→aPb｛print“1”｝

   完成下列各题：                            P→Q｛print“2”｝

   (1)它生成的语言是什么？（2分）           Q→cQd｛print“3”｝

   (2)这是Chomsky哪一型文法？（1分）      Q→cRd｛print“4”｝

   (3)这文法是否是SLR文法，请              R→Ra｛print“5”｝

     构造分析表证实之。(7分)                R→a｛print“6”｝

   (4)这文法是否是算符优先文法，请

      证实之(5分）

   (5)这文法经消除左递归，提取左因子后

      是否是LL(1)文法，请证实之(5分）

   (6)输入串acccaaadddb经翻译后的输出串是什么？(3分)

 

3  对下列中间代码，完成下列各题：(8分)

  （1）x：=y+z    (2)z:=4*t     (3)y:=y+t          (4) s:=y+x

   (5)t:=t-s        (6)x:=x+z    (7)if s<t goto（10）   (8) z:=s+t

   (9)t: -z-t     （10）y: -y+z  （11）if x=y goto (3)  （12) halt

    （1）请划分基本块，构造流图，求出循环；

     (2)若基本块出口之后的活跃变量均为xt y, zY循环中可用作固定分配的寄存器为R0和R1，则该分配给哪两个变量，为什么？

 

4  基木块内的代码如下图所示：

    (1) A:=2     (2) B:=C*D     (3) E:=C/D

    (4)F:=B+E  （5）G: =A+F    (6)H:=A*2

    (7)I:=C*D   （8）J:=H*I    （9) I:=H+F

    请用dag表示完成局部优化，写出优化后的代码；

若基本块出口之后仅I活跃，则优化后的代码是什么？(7分)