西安交通大学1995编译原理考研试题.docx

西安交通大学1995编译原理考研试题.docx

《西安交通大学1995编译原理考研试题.docx》由会员分享，可在线阅读，更多相关《西安交通大学1995编译原理考研试题.docx（10页珍藏版）》请在冰点文库上搜索。

西安交通大学1995编译原理考研试题

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

1．右列三个文法中，为SLR

（1）文法的   G1：

P→PaP|b

 （A）仅GI（B）仅G2        G2：

P→bPb|cPc|b|c

（C）仅G3（D）G2和G3       G3：

P→bPb|bPc|d

2．右列文法的句型  S→aTb|，T→RaR/aSb/aTb/,b 

R→R/S|S      

 的最左素短语为

（A）aTb    （B）aSb  （C）S    （D）R/    （E），    （4分）

3.表达式a*b-c-d＄e＄f-g-h*i中，运算符的优先级由高到低依次为一、*、＄，且

 均为右结合，则相应的后缀式为

（A）ab*c-d-e＄fg-h-I﹡＄    （B）＄﹡a-b-cd＄e*-f-ghi

（C）bcd--a*efgh—i*$$    （D）abed--*efgh-i*$$

（E）ab*c-d-e＄fg-h-i＄  

4.  programtest（input，output）      

begin｛main｝

vari，J：

integer；              

i:

=2;j:

=3;

CAL（i,j）;

writeln（j:

1）

end｛main}

procedureCAL（x,y:

integer）；      

begin

y=y**2;  

x:

=x-y;  

y:

=y-x

end;{CAL}

  假定程序在语法上是正确的，采用哪一种参数传递方式使程序打印16。

  （A）callbyreference  （B）callbyname  （C）callbyvalue

  （D）前述三种中的二种（E）都不是（**为乘幂运算）    （5分）

5.生成L=amb1cmanbn|1≥2，m≥l，n≥0｝这种语言的文法是什么？

它是chomsky的哪一型文法？

  （5分）

6.请构造与正规式R=（a*b*ba（a|b）*等价的状态最少的DFA。

（10分）

7.下列文法

（1）是不是LL

（1）文法  

（2）是不是SLR

（1）文法。

请证实。

（10分）

（1）S→Pa|Pb|c  

（2）P→Pd|Se|f   E→EiT|T

8.请证实右列文法是个二义文法。

（4分） 

T→T+F|iF|FF→E＊|（

9.设AS为文法的综合属性集，AI为产生式  语义规则

继承属性集，则右列语法制导定义中    P→xQR  Q.b:

=R.d

（A）AS={Q.a,R..c,R.e} R.c:

=1AI={Q.b,R.d,R.f}  R.e:

=Q.a

（B）AS=IQ.a,Q.b｝P→yQR Q.b:

=R.FAI={R.c，R.d，R.e，R.f} R.c:

=Q.a

（C）AS={Q.b，R.c,R.f}R.e:

=2AI={Q.a,R.d,R.e}Q→a Q.a:

=3

（D）AS={Q.a,R.d,R.f} R→v    R.d:

=R.c  R.f:

=R.e

AI=｛Q.b,R.c,R.e｝

（E）AS=笼{Q.b,R.d,R.e}    AI={Q.a,R.c,R.f}    （4分）

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

一．试求与下图NFA等价的化简了的DFA。

（8分）

二．已知（P|Q）*=（P*|Q*）*=（P*Q*）*  求证：

[（P|Q）*|Q*]*P*Q*=（P*Q*）+（4分）

三．文法G1：

P→PaP|PbP|Cp|dRe|f

  1.证明文法G1是二义文法    （2分）

  2.如果要为文法G1构造无冲突的LR分析表，应提出什么样的约束条件？

试证实你的命题。

（6分）

四．生成非0开头的正偶数集的文法是什么？

（6分）

以下选择题允许多种选择：

五．文法G2:

    S→LaR|R

            L→bR|c

            R→L

  是（A）LR（0）文法（B）SLR

（1）文法  （C）LR

（1）文法

    （D）LALR（0）文法（E）都不是  （5分）

六．第5题文法G2是（A）算符文法（B）算符优先文法

              （C）LL

（1）文法  （D）递归文法  （E）右线性文法  （6分）

七．八．（交大的试卷没有画出图，故略）

九．如果优先次序依次为一＋＊＄（乘幂），且均为右结合，则

  2+3-2十2X2X1＄2＄3-3-2+1

  1．的后缀式为

      （A）23+2-2+2*1*23＄3-2-1＋＄

      （B232-2++21**2332--*1+＄＄

      （C）23+2-2+21**23＄＄32--l+

      （D23+2-22*1*23-2-1＄＄

      （E）32-22++21**2＄3＄3-2-1＋      （3分）

  2.它的值为

（A）10252（B）108+1  （C）108  （D）9  （E）106  （2分）

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

一。

请构造与正规式R=（a*|b*）b（ba）*等价的状态最少的DFA。

二。

表达式-a+b*c+d+（e*f）/d*e，如果优先级由高到低依次为一、＋、＊、／，且均为左结合，请写出其后缀式。

三。

文法G及相应的翻译方案列于下：

S→bTc  {print“1”}

S→a  ｛print“2”｝

T→R  ｛print“3”｝

R→R/S  {print“4”}

R→s    {print“5”}

[1]1.文法G属于Chomsky哪一型文法？

[2]2.符号串bR/bTc/bSc/ac是不是该文法的一个句型，请证实。

[6]3.若是句型，写出该句型的所有短语、素短语，以及句柄。

[5]4.文法G是不是算符优先文法，请证实。

[5]5.文法G经消除左递归后得到的等价文法G’是不是LL

（1）文法，请予证实。

[7]6.文法G是不是SLR

（1）文法，请予证实。

[5]7.对于题2的输入符号串，该翻译方案的输出是什么？

[5]四。

数组VARA:

array[1..5,-3..6]ofinteger;按列存放，其首址100,每个整数占4个字节，内存按字节编址，则数组元素A[4，3]的地址是什么？

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

一生成语言L={a1bmc1anbn|1≥0,rn≥1,n≥2}的文法是什么？

它是chomsky哪一型文法？

（5分）

二文法G1：

P→aPQR|abR

RQ→QR

bQ→bb

bR→bc

cR→cc

它是chomsky哪一型文法？

请证实aaabbbccc是Gl的一个句子（5分）

三文法G2：

P→aPb|Q

Q→bQc|bSc

S→Sa|a

  1请构造它的SLR分析表，以说明它是不是SLR文法？

（7分）

  2在消除左递归、提取公共左因子后可得等价文法G2'，它是不是LL

（1）文法（6分）

四求与正规式R=（a|b）*a|（a|b）*a（b）a）*等价的minDFA。

（8分）

五文法G3及相应翻译方案为：

  P→bQb  {print“1”}

             Q→cR  {print“2”}

             Q→a    {print“3”}

             R→Qad  {print“4”｝

  1该文法是不是算符优先文法，请构造算符优先关系表证实之。

（5分）

  2输入串为bcccaadadadb时，该翻译方案的输出是什么？

（4分）

六三维数组a[2:

5,-2:

2,5:

7]首址为100,每个数组元素占4个存储单元，求数组元

  素a（3，1，6）的地址。

（5分）

七右列程序段若以B表示循环体       i:

=1：

 A表示初始化.I-．／          whilei≤ndo

 B表示增量              begin

 C表示测试              sun=sun+a；

                   i=i+l；

                   end

请用正规表达式表示这个程序段可能的执行序列（5分）                                                      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）ifb

    哪二个变量可使执行代      （8）b:

=b-c

    价省得最多？

（共10分）     （9）f:

=b+f

                  （10）a:

=a-f

（11）ifa=cgoto（3）

（12）  halt

五．下列基本块内代码：

        t1：

=3*A            

        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分）

2000年编译原理部分

一给出文法G:

    S→SaA|A

         A→AbB|B

         B→cSd|e

  1证实AacAbCBaAdbed是文法G的一个句型（4分）

  2请写出该句型所有短语、素短语，以及句柄（7分）

  3为该文法每个产生式写相应的翻译子程序，使上述句型经该翻译方案翻译后，

  输出131042521430（4分）

  4文法G是不是SLR文法？

请构造分析表证实之。

（10分）

二文法G’：

    S→aSPQ|abQ

            QP→PQ

            bP→bb

            bQ→bc

            cQ→cc

    1它是chomsky哪一型文法？

（1分）

    2它生成的语言是什么？

（4分）

三写出不能被5整除的偶数集的文法（6分）

四语句WhileA

=F[i,j]elsex:

=x+l经翻译后的三地址语句或四元式序列是什么？

（7分）

  设三地址语句或四元式序列自100开始存放，数组F的内情向量（描述符）自300开始，数组首地址500,每个数组元索占四字节。

五对下列流图：

1求各结点必经结点集            

2求回边

3求由回边构成的循环（共7分

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分）

五写出句子

ifi>2thena[i,j]：

=x+2else

while（i

=a[j,i]＋1

的三地址语句或四元式序列。

（8分）

六programtest;

  vari，j：

integer；

  procedureexample（x,y：

integer）；

  beginy：

=y**2；

x：

=x-y；

y：

=y-x  

end；

  begin

a：

=3；

b：

=4：

callexample（a,b）；

 writo（a）；

write（b）

end；

其中：

参数传递方式为call-by-reference,则a,b输出何值。

**为乘幂运算。

（5分）

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

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

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

（8分）

          ①i：

=i+l

          ②ifi=jgoto④

          ③a:

=a+l

          ④ifi>agoto⑧

          ⑤a:

=a*2

          ⑥ifj>agoto①

          ⑦goto⑩

          ⑧a:

=a/2

          ⑨ifj>agoto④

          ⑩goto⑧