编译原理模拟题合集.docx

编译原理模拟题合集.docx

《编译原理模拟题合集.docx》由会员分享，可在线阅读，更多相关《编译原理模拟题合集.docx（16页珍藏版）》请在冰点文库上搜索。

编译原理模拟题合集

编译原理

一、填空题（20分）

1.1编译程序的工作过程可划分为词法分析、语法分析、语义分析、中间代码生成、代码优化、目标代码生成等阶段，一般在语义分析阶段对表达式中运算对象的类型进行检查。

1.2递归下降法和预测分析法是自上而下的语法分析方法。

1.3常用的存储分配策略有静态存储分配和动态存储分配，其中，动态存储分配策略包括栈分配和堆分配。

1.4移进、归约是自下而上或LR分析中的典型操作。

1.5对于数组M[1..6,1..8]，如果每个元素占k个存储单元，且起始地址为a，则以行为主序存放时元素M[4,4]的地址是__a+27*k__，以列为主序存放时元素M[4,4]的地址是_a+21k__。

1.1LR

（1）分析法中，L的含义是自左至右扫描输入串，R的含义是最右推导的逆。

1.2源程序经过编译后产生的程序称为目标程序。

1.3词法分析的输出由单词种别和单词的值两部分组成。

1.4文法G：

S→AB,A→aA|ε,B→bBc|bc描述的语言L（G）=｛ambkck|m>=1,k>=0｝。

1.5允许用户随意地动态申请与释放内存空间应采用_堆_存储分配技术。

1.6一个文法产生的_句子的全体_称为该文法的语言。

1.7语义错误可分为静态语义错误和动态语义错误，“运算符与运算对象的类型不一致”属于_静态语义_错误，“无穷递归”属于_动态语义_错误。

1.1出错处理和符号表管理是编译程序各阶段都涉及到的工作。

1.2用LR方法实现语法分析时，典型的操作有__移进__、___归约__、接受和报错。

1.3一个上下文无关文法（N，T，P，S）的四个组成部分是终结符集合N、非终结符集合T、产生式集合和开始符号。

1.4已知数组M[1..5,1..8]以行为主序存放，如果每个元素占4个存储单元，且起始地址为a，则元素M[4,7]的地址是__a+120__。

数组元素的地址计算公式由两部分组成，一部分是不变部分，它在__编译__时确定；另一部分是可变部分，它在__运行__时确定。

1.5表达式（a+b）*c-d的逆波兰（后缀）表达式为__ab+c*d-__。

二、单选题（20分）

2.1词法分析器不能D。

A.识别出数值常量B.过滤源程序中的注释

C.扫描源程序并识别记号D.发现括号不匹配

2.2给定文法A→bA|ca，C是该文法的句子。

A.bbaB.cabC.bcaD.cba

2.3一个句型中的最左B称为该句型的句柄。

A.短语B.直接短语C.非终结符号D.终结符号

2.4已知文法G[S]:

S→A1A→A1|S0|0。

与G等价的正规式是C。

A.0（0|1）*B.1*|0*1C.0（1|10）*1D.1（10|01）*0

2.5源程序是句子的集合，B可以较好地反映句子的结构。

A.线性表　B.树C.完全图　D.堆栈

2.6与逆波兰式ab+c*d+对应的中缀表达式是B。

A.a+b+c*dB.（a+b）*c+dC.（a+b）*（c+d）D.a+b*c+d

2.7识别上下文无关语言的自动机是A。

A.下推自动机B.NFAC.DFAD.图灵机

2.8B是与规范归约（最左归约）互逆的一个过程。

A.最左推导　B.最右推导C.词法分析　D.语义分析

2.9文法G产生的A的全体是该文法描述的语言，

A.句子　B.短语C.终结符　D.非终结符

2.10在表达式x:

=y+1中，A作为左值出现（其中，“:

=”表示赋值）。

A.x　B.yC.1　D.y+1

2.1编译程序是对___D___。

A.汇编语言的翻译B.高级语言的解释执行

C.机器语言的执行D.高级语言的翻译

2.2编译过程中C阶段不是必需的。

A.语法分析B.语义分析C.代码优化D.目标代码生成

2.3为数组声明a:

array[1..4,0..3]中a分配的存储空间的首地址为base_a，且每个数组元素占据一个存储单元。

若以行为主存放，数组元素a[3,1]在存储空间中相对base_a的偏移量是B。

A.8B.9C.10D.11

2.4识别正则语言的自动机是B。

A.下推自动机B.有限自动机C.线性界限自动机D.图灵机

2.5表达式“a+b*（c-d）”的后缀式为B。

A.ab+cd-*B.abcd-*+C.ab+*cd-D.abcd*+-

2.6一个文法产生的语言是指D。

A.从开始符号出发推导的所有符号串的集合　

B.所有终结符和非终结符形成的集合

C.所有短语构成的集合

D.该文法产生的句子的集合

2.7函数（或过程）调用时，A。

A.值调用方式下将实参的右值传递给形参，引用调用方式下将实参的左值传递给形参

B.值调用方式下将实参的左值传递给形参，引用调用方式下将实参的右值传递给形参

C.值调用方式下将形参的右值传递给实参，引用调用方式下将形参的左值传递给实参

D.值调用方式下将形参的左值传递给实参，引用调用方式下将形参的右值传递给实参

2.8用来描述控制进入和离开活动方式的树结构被称为C。

A.语法树B.分析树C.活动树D.嵌套关系树

2.9不含子串100的所有0、1符号串的正规式是A。

A.0*（1|10）*B.1*|0*1C.0（01|10）*1D.1（10|01）*0

2.10B是与规范归约（最左归约）互逆的一个过程。

A.最左推导　B.最右推导C.词法分析　D.语义分析

2.1生成中间代码所依据的是_____C_____。

A.语法规则B.词法规则C.语义规则D.等价变换规则

2.2一个句型中的最左____B____称为该句型的句柄。

A.短语B.直接短语C.非终结符号D.终结符号

2.3给定文法A→bA|cc，____D____是该文法的句子。

A.ccbcB.bcbcC.cbcbD.bbcc

2.4程序设计语言中大多数的语法现象可用Chomsky的____C____文法表示。

A.0型（短语结构文法）B.1型（上下文有关文法）

C.2型（上下文无关文法）D.3型（正规文法）

2.5有限状态自动机可以识别的语言为____D____。

A.上下文有关语言B.上下文无关语言

C.短语文法定义的语言D.正规文法定义的语言

2.6有文法G：

S→AA,A→Aa|a。

G不是LL

（1）文法的理由是____C_____。

A.FIRST（S）∩FIRST（A）≠

B.FIRST（A）∩FOLLOW（A）≠

C.FIRST（Aa）∩FIRST（a）≠

D.都不是

2.7表达式的类型检查工作在______C_____阶段进行。

A.语法分析B.词法分析C.语义分析D.优化

2.8编译器分析源程序时遇到的错误可分为语法错误和语义错误两类，____A_____。

A.表达式中括号不匹配是语法错误，运算对象与运算符号不匹配是语义错误

B.表达式中括号不匹配是语义错误，运算对象与运算符号不匹配是语法错误

C.表达式中括号不匹配和运算对象与运算符号不匹配都是语法错误

D.表达式中括号不匹配和运算对象与运算符号不匹配都是语义错误

2.9已知某高级语言源程序A经编译后得到机器C上的目标程序B，则A。

A.对B进行反编译，不能还原出源程序A

B.对B进行反汇编，不能得到与源程序A等价的汇编程序代码

C.对B进行反编译，得到的是源程序A的变量声明和算法流程

D.对A和B进行交叉编译，可以产生在机器C上运行的动态链接库

2.10集合

D。

A.可用正规式“

”表示

B.不能用正规式表示，但可用非确定的有限自动机识别

C.可用正规式“

”表示

D.不能用正规式表示，但可用上下文无关文法表示

三、简答题（30分）

3.1（5分）请分别写出传值调用、引用调用方式下，下面代码的输出结果。

programmain（input,output）

proceduref（a,b）

begin

a:

=b-a;

b:

=a*b+1;

end;

begin

x:

=5;y:

=10;

f（y,x）;

print（x,y）;

end.

传值调用方式：

510

引用调用方式：

-24-5

3.2（10分）请计算下面文法G（E）中各非终结符的FIRST和FOLLOW集合。

请说明该文法为什么不是LL

（1）文法。

G（E）：

E→E*T|TT→T-F|FF→（E）|id

FIRST（F）=FIRST（T）=FIRST（E）={（,id}

FOLLOW（E）={#,*,）}FOLLOW（T）={-,*,#,）}FOLLOW（F）={-,*,#,）}

3.3（10分）下图所示的分析树用到了某个上下文无关文法的所有产生式。

（a）给出该文法的所有非终结符号集合N和终结符号集合T。

（b）给出该文法的产生式集合。

N={S,A,B}

T={a,b,c,d}

S→aAcB|BdA→AaB|cB→bScA|b|ε

3.4（5分）某程序执行到某一时刻时控制栈中的内容如下所示（其中M是主程序，P、Q、R、S均是过程），给出所有在生存期的活动的调用关系（提示：

若A调用B，则记为A→B）。

M→P→R→Q→S→S

3.1（10分）对下述C++程序，（a）指出各参数的传递方式；（b）给出程序的执行结果。

voidf（inta,int&b,int&c）{c=c+10;b=a*b+c;}

voidmain（）

{intx=10,y=25,z=0,t=0;

z=x+y*10;

f（x+y,x,z）;cout<<"1：

"<

t=x+y;

f（t,x,z）;cout<<"2：

"<

}

（a）参数a采用传值方式，参数b和c采用传引用方式

（b）1：

6202：

400180

3.2（10分）请简要说明进行自上而下的语法分析时，文法中为什么不能有左递归和公共左因子。

进行自上而下的语法分析时，若存在左递归，则可能在分析某些句子时陷入死循环；若存在公共左因子，则可能因为虚假匹配导致需要回溯，从而降低分析效率。

3.3（10分）举例说明下述文法G是二义的。

有哪些方法可以消除文法的二义性。

G：

S→aA|BbA→bA|εB→a

以句子“ab“为例，其分析树可有如下两种形式：

即句子“ab”存在不同的最左推导S=>aA=>abA=>ab和S=>Bb=>ab，因此文法G是二义的。

消除文法二义性的方法主要有两种：

一是改写文法为非二义的：

二是规定优先级和结合性，限制分析的每一步仅有唯一选择。

3.1请列举三种常用的中间代码？

采用中间代码有什么好处？

常用的中间代码：

三地址码，后缀式，DAG图

<1>中间代码的特点是与具体机器（指令系统）无关；

<2>采用中间代码可以明确区分前端与后端；便于优化和移植。

3.2对下述C/C++程序，（a）指出调用函数testfunc时各参数的传递方式；（b）给出程序的执行结果。

voidtestfunc（int&a,int&b,intc）{a=b-c;c=c+10;b=a*b+c;}

intmain（）

{intx=1,y=2,z=3;

testfunc（y,x,z）;

cout<<"x="<

return0;

}

调用函数testfunc时，y和x与a和b间传引用，z和c间传值

x=11y=-2z=3

3.3简述拉链与回填技术的基本思想。

拉链与回填技术的基本思想：

在转移地址未确定时，将所有转向相同地址的三地址码拉链；当转移地址确定后，沿所拉的链将确定的地址回填到每个三地址码中。

从而达到一遍分析确定所有转移地址的目的。

四、综合题（40分）

4.1（15分）设有正规式r=1（0|1）*1，试给出：

（a）（5分）识别该正规集的NFA；

（b）（10分）识别该正规集的DFA（要有计算过程）；

（a）NFA如下图所示

（b）s0={A}

ε_闭包（s0）=s0初态

ε_闭包（smove（s0,1））={B}记为s1

ε_闭包（smove（s1,0））={B}=s1

ε_闭包（smove（s1,1））={B,C}记为s2，终态

ε_闭包（smove（s2,0））={B}=s1

ε_闭包（smove（s2,1））={B,C}=s2

DFA如下图所示

4.2（15分）设有上下文无关无法G及其语法制导翻译如下（注：

G中终结符id仅由单个英文字母组成，如a,b等）：

E→E1*T{E.place=newtemp;emit（*,E1.place,T.place,E.place;}

|T{E.place=T.place;}

T→T1-F{T.place=newtemp;emit（-,T1.place,F.place,T.place;}

|F{T.place=F.place;}

F→（E）{F.place=E.place;}

|id{F.place=id.name;}

（a）（4分）画出句子a-b*c的分析树；

（b）（3分）写出当a=1、b=2、c=3时的计算结果；（*表示算术乘、-表示算术减）

（c）（8分）将文法G简化为：

E→E*T|T，T→T-F|F，F→id，给出其识别活前缀的DFA，该DFA的项目集中有冲突吗？

若有，是哪种类型的冲突。

（a）

（b）-3

（c）拓广文法，增加产生式：

S→E，识别活前缀的DFA如下图所示

存在移进－归约冲突

4.3（10分）阅读以下程序代码

if（y>0andx>0）

while（x>y）dox=x-y

elsey=1

（a）（4分）请画出其代码结构图（流程图）；

（b）（6分）给出其三地址码序列。

（a）

（b）

101ify>0goto103

102goto104

103ifx>0goto105

104goto110

105ifx>ygoto107

106goto111

107t1=x–y

108x=t1

109goto105

110y=1

4.1（15分）设有正规式r=（a|ba）*，试：

（a）（5分）用自然语言简要叙述该自动机所识别的语言的特点，列举三个它可识别的串。

（b）（10分）构造识别该正规集的NFA和DFA（要有计算过程）。

（a）正规式r=（a|ba）*所表示语言的特点是b不能连续出现，即只要出现字符b，则其后必然出现至少一个a。

（b）识别正规式r=（a|ba）*所表示语言的NFA如下图所示：

ε_闭包（{0}）={0,3}记为A

ε_闭包（smove（A,a））={1,3,0}记为B

ε_闭包（smove（A,b））={2}记为C

ε_闭包（smove（B,a））={0,1,3}=B

ε_闭包（smove（B,b））={2}=C

ε_闭包（smove（C,a））={3,0}记为D

ε_闭包（smove（C,b））={}

ε_闭包（smove（D,a））={1,3,0}=B

ε_闭包（smove（D,b））={2}=C

DFA如下图所示

图中状态A，B，D是等价的，因此最小化DFA如下图所示：

4.2（15分）对于文法

S→SaA|bA

A→Ac|d|ε

（a）（4分）计算非终结符S和A的FIRST集和FOLLOW集；

（b）（6分）构造识别该文法活前缀的DFA；

（c）（5分）该文法是否为LR（0）文法？

为什么？

是否为SLR

（1）文法，为什么？

（a）FIRST（S）={b}FIRST（A）={d,ε}

FOLLOW（S）={a,#}FOLLOW（A）={a,c,#}

（b）识别该文法活前缀的DFA如下图所示

（c）该文法不是LR（0）文法，存在移进－归约冲突；是SLR

（1），冲突可解决。

4.3（10分）给出语句while（x<0）doif（x

=y+z的中间代码序列。

101ifx<0goto103

102goto108

103ifx

104goto101

105t1=y+z

106x=t1

107goto101

4.1（10分）有NFAN如下图所示。

<1>求出N的最小DFAD；<2>给出N所识别语言的正规式r。

<1>确定化：

{1}记为A，初态

smove（A,a）={2}记为B

smove（B,a）={3，4}记为C，终态

smove（B,b）={2}

smove（C,a）={2}

如下图所示：

它已经是最小DFA。

<2>r=a（b|aa）*a，它所描述的语言是由a开始和结尾的、偶数个a组成的a、b串。

4.2（10分）设有文法G[S]：

S→aBc|bAB,A→aAb|b,B→b|ε。

<1>计算非终结符S、A、B的FIRST和FOLLOW集合；

<2>该文法能否推导出baabbb，若能，写出其分析树，否则说明原因。

<1>FIRST（B）={b,ε}FIRST（A）={a,b}FIRST（S）={a,b}

FOLLOW（S）={#}FOLLOW（A）={b}FOLLOW（B）={c,#}

<2>可以推导出baabbb

4.3（10分）有上下文无关无法G[V]和语法制导翻译如下：

（1）V→id{var_no:

=var_no+1;}

（2）|id（E）{arr_no:

=arr_no+1;}

（3）E→E+V{exp_no:

=exp_no+1;}

（4）|V{exp_no:

=exp_no+1;}

（a）给出识别该文法活前缀的DFA；

（b）若语义变量var_no、arr_no和exp_no的初值均为1，请给出分析句子id（id+id（id））之后它们各自的值；

（a）识别该文法活前缀的DFA如下图所示

（b）句子id（id+id（id））分析树

var_no=2arr_no=2exp_no=3