您的位置:考研教育网>  > 考试大纲 > 考研专业课 正文

东南大学1999年研究生入学考试编译原理试题

   2007-01-19 14:37 【 】【我要纠错

  试题名称:编译原理

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

  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、执行循环中代码外提,强度减弱优化和基本块内删除公共子表达式优化,最后画出包含优化后的中间代码的程序流图。

    注:数组A:array[1……10,1……10] of int;按行存放,每个下标变量占1字编址,首地址为addrA.

◇ 编辑推荐
·2016年考研调剂信息汇总(更新中)
·2016年考研国家线
·2017考研网上辅导招生简章
 考研教育网官方微信

微信公众账号cnedu_cn

 网上辅导课程特色
  • 即报即学
  • 名师团队
  • 反复看课
  • 在线答疑
  • 移动教学
  • 讲义下载
  • 课后练习
  • 模拟测试
 24小时报名咨询
考研网上辅导课程 精品班 实验班
学费 购买 学费 购买
公共课 政 治 1500元 购买 3500元 购买
英 语 1500元 购买 3500元 购买
数 学 1500元 购买 3500元 购买
专业课 考研名师编写,网校独创考研管理类、法律类、教育等专业课电子书正在热卖!