2002年编译原理部分(50分)

一 写出a+b*c/(a-b)-b*(-c+a)的后缀式.。(4 ))

 

二 正规式（a | b）a（a | b）*a表示的语言是什么？求出接受该正规集的状态最少的确定有限自动机。(8分)

 

三 请写出不能被5整除的非零开头的正整数集的文法。(6分)

 

四 对下列文法G      G: S→SPa | P

                        P-y→ PQb | Q

                        Q→S | d

    试完成下列各题：

    1该文法是(a)右线性文法   (b) LL（1）文法   (c) 2型文法

             (d)算符优先文法  (e)递归文法

 

           （多选题5分，漏选、错选均扣分）

    2文法G是不是SLR文法。请构造SLR分析表证实之。(6分)

 

五 写出句子if i>2 then a[i, j]：=x+2 else

                    while（i<j） do x：=a[j, i]＋1

   的三地址语句或四元式序列。（8分）

 

六 program test;

   var i，j：integer；

   procedure example (x, y：integer)；

   begin y：=y**2；x：=x-y；y：=y-x  end；

    begin a：=3；b：=4：call example (a, b)；

          wr i to (a)；write (b)

    end；

    其中：参数传递方式为call-by-reference,则a, b输出何值。**为乘幂运

          算。（5分）

 

七 三地址语句序列如下图：

   1请划分基本块，构造程序流图；

   2 请求出必经结点集，回边和由回边组成的循环。(8分）

                ①i：=i+l

                ②if i=j goto④

                ③a:=a+l

                ④ if i>a goto⑧

                ⑤a:=a*2

                ⑥if j>a goto①

                ⑦goto⑩

                ⑧a: =a/2

                ⑨if j>a goto④

                ⑩goto⑧