1999年编译原理部分（共50分）

一 写出在∑={a, b}上，不是a开头的，以as结尾的字符串集合的正规表达式，并构造与之等价的状态最少的DFA     (9分)

 

二  给出文法GI：        S→aSb | P

                         P→bPc | bQc

                         Q→Qa | a

     1它是chomsky哪一型文法。

     2.它生成的语言是什么？

     3它是不是算符优先文法？请构造算符优先关系表证实之。

     4请证实所有(a)左递归文法(b)有公共左因子的文法均不是LL（1)文法。

     5文法G1消除左递归，提取公共左因子后是不是LL (1)文法？请证实。（共15分）

 

三  给出文法G2:  S→SaS | SbS | cSd | eS | f

    1请证实这是一个二义文法。

    2给出什么样的约束条件，可构造出无冲突的LR分析表？请证实你的论点。（共8分）

 

四  给出右列代码序列：                 (1)a:=b-c

    1.请划分基本块并构造流图           (2) d: =a+4

    2.假定各基本块出口之后的          （3 e: =a-b

      活跃变量均为a, c、f，             (4)f=c+e

      循环中可用作固定分配的          （5 b:=b+c

      寄存器为R0, RI，则将            （6 c:=b-f

      R0, R1固定分配给循环中           (7) if b<c goto（10）

      哪二个变量可使执行代            （8 b:=b-c

      价省得最多？（共10分）         （9 f :=b+f

                                      （10 ）a:=a-f

 

五．下列基本块内代码：                （11）if a =c goto（3）

            t1：=3*A                   (12)  halt

            t2：=2*C

            t3：=tl+t2

            t4：二t3+5

            t5：=2*C

            t6：=3*A

            t7：=t6+t5

            t8：=t7-1

            t9：＝t4-t8

        1 请用dag进行局部优化

        2 基本块出口时t9恒为6，是否有进一步优化的方法，可获得此结果？（共8分）