编译原理试题+答案.docx

编译原理试题+答案.docx

《编译原理试题+答案.docx》由会员分享，可在线阅读，更多相关《编译原理试题+答案.docx（13页珍藏版）》请在冰点文库上搜索。

编译原理试题+答案

编译原理试卷三

窗体顶端

一、选择

1.下面说法正确的是：

A一个正规文法也一定是二型文法

B一个二型文法也一定能有一个等价的正规文法

2.文法G[A]：

A→bA→ABB→AbB→a是（　　）：

A二型文法

B正规文法

3.下面说法正确的是（　　）：

Alex是一个词法分析器

Byacc是一个语法分析器的生成器

4.一个LR

（1）文法合并同心集后,如果不是LALR

（1）文法必定存在（　　）：

A移进--归约冲突

B归约--归约冲突

5.7．5PL/0语言编译程序使用递归子程序法进行语法分析，他的文法必须满足（　　）：

ALL

（1）文法

BSLR

（1）文法窗体底端

二、问答题

问答第1题

（6分）试对repeatx:

=buntilb>aor（b

应回填的值

回填的次序

真链头E.true=

（1）

x:

=b

真出口链（　）

（2）

ifb>agoto

（　）

（　）

真出口链（　）

（3）

goto

（　）

（　）

（4）

ifb

（　）

（　）

假链头E.false=

（5）

goto

（　）

（　）

假出口链（　）

（6）

ifb=dgoto

（　）

（　）

（7）

goto

（　）

（　）

（8）

...

问答第2题

（10分）某语言的拓广文法G′为：

　　（0）S′→S

（1）S→Db|B

（2）D→d|ε

　　（3）B→Ba|ε

证明G不是LR（0）文法而是SLR

（1）文法，请给出SLR

（1）分析表。

问答第3题

（5分）给出文法G[S]的LR

（1）项目集规范族中I0项目集的全体项目。

　　G[S]为：

S→S;V|V

　　　　　　V→VaA|A

　　　　　　A→b（S）|ε

I0:

问答第4题

（5分）文法G[M]及其LR分析表如下，请给出对串dada#的分析过程。

　　G[M]:

1）S→VdB　　　　2）V→e

　　　　　3）V→ε　　　　4）B→a

　　　　　5）B→Bda　　　6）B→ε

状态

ACTION

GOTO

d

e

a

#

S

B

V

0

r3

S3

1

2

1

acc

2

S4

3

r2

4

r6

S5

r6

6

5

r4

r4

6

S7

r1

7

S8

8

r5

r5

问答第5题

（7分）

（1）给出下列PL/0示意程序中当程序执行到D过程调用A过程后（即执行A过程体时）的栈式存储分配布局和用Display显示表时A过程最新活动记录的内容。

（2）说明Display表和全局Display的作用。

PL/0示意程序为：

　　　varx;

　　procedureA;

　　　vard;

　　　begin（*A*）

　　　　write（x）;

　　　end（*A*）;

　　procedureB;

　　　constn=7;

　　　vare,g;

　　　procedureD;

　　　　varj,k;

　　　　begin（*D*）

　　　　　read（j,k）;

　　　　　x:

=x+j*n;

　　　　　callA;

　　　　end;（*D*）

　　　begin（*B*）

　　　　callD;

　　　end;（*B*）

　　begin（*main*）

　　　read（x）;

　　　callB;

　　end.（*main*）

问答第6题

（5分）给出问答第5题PL/0示意程序编译到D过程体时TABLE表的内容。

其中TABLE表的格式可为下表。

TABLE表的格式

name

kind

level

val

adr

size

问答第7题

（6分）按指定类型给出下列语言的文法。

（1）L1={candbm|n≥0,m>0}用正规文法。

（2）L2={0na1nbmcm|n>0，m≥0}用二型文法。

问答第8题

（5分）文法G[S]为：

　　S→SdT|T

　　T→T

　　G→（S）|a

试给出句型（SdG）

问答第9题

（5分）给出与正规式R＝（aba）*（（ba）*|b）b等价的NFA。

问答第10题

（6分）将下图的NFA确定化为DFA。

问答第11题

（5分）将文法G[S]改写为等价的G'[S]，使G'[S]不含左递归和左公共因子。

　　G[S]：

S→[A

　　　　　A→B]|AS

　　　　　B→aB|a

问答第12题

（10分）判断下面文法是否为LL

（1）文法，若是，请构造相应的LL

（1）分析表。

　　S→aD

　　D→STe|ε

　　T→bM

　　M→bH

　　H→M|ε

参考答案

一、选择题答案

选择第1题

A

选择第2题

A

选择第3题

B

选择第4题

B

选择第5题

A

二、问答题答案

问答第1题

解：

应回填的值

回填的次序

真链头E.true=6

（1）

x:

=b

（2）

ifb>agoto

（8）

（6）

真出口链（6,2）

（3）

goto

（4）

（1）

（4）

ifb

（6）

（2）

假链头E.false=7

（5）

goto

（1）

（4）

假出口链（7,5）

（6）

ifb=dgoto

（8）

（5）

（7）

goto

（1）

（3）

（8）

...

问答第2题

解：

拓广文法G'，增加产生式S'→S

在项目集I0中：

有移进项目D→·d

归约项目D→·和B→·

存在移进-归约和归约-归约冲突，所以G不是LR（0）文法。

若产生式排序为：

（0）S'→S

（1）S→Db

（2）S→B

（3）D→d

（4）D→ε

（5）B→Ba

（6）B→ε

G′的LR（0）项目集族及识别活前缀的DFA如下图：

识别G′活前缀的DFA

由产生式知：

Follow（S）={#}

Follow（D）={b}

Follow（B）={a,#}

在I0中:

Follow（D）∩{d}={b}∩{d}=

Follow（B）∩{d}={a,#}∩{d}=

Follow（D）∩Follow（B）={b}∩{a,#}=

在I3中:

Follow（S）∩{a}={#}∩{a}=

所以在I0，I3中的移进-归约和归约-归约冲突可以由Follow集解决,所以G是SLR

（1）文法,

构造的SLR

（1）分析表如下表。

SLR

（1）分析表

状态

ACTION

GOTO

b

d

a

#

S

D

B

0

r4

S4

r6

r6

1

2

3

1

acc

2

S5

3

S6

r2

4

r3

5

r1

6

r5

r5

问答第3题

解：

:

I0:

问答第4题

解：

对串dada#的分析过程如下表

对输入串dada#的分析过程

步骤

状态栈

文法符号栈

剩余输入符号

动作

1

2

3

4

5

6

7

8

9

0

02

024

0245

0246

02467

024678

0246

01

#

#V

#Vd

#Vda

#VdB

#VdBd

#VdBda

#VdB

#S

dada#

dada#

ada#

da#

da#

a#

#

#

#

用V→ε归约

移进

移进

用B→a归约

移进

移进

用B→Bda归约

用S→VdB归约

接受

问答第5题

解：

（1）PL/0示意程序中当程序执行到D过程调用A过程后（即执行A过程体时）的栈式存储分配布局和用Display显示表时栈中过程最新活动记录的内容如下图。

栈式存储分配布局和栈中过程最新活动记录的内容

（2）Display表和全局Display的作用是：

　　·Display表的作用是对嵌套过程语言实现对非局部变量的引用而设置的，它依次存放着包围它的外过程的最新活动记录的基地址SP值，由于，嵌套层次为i+1过程中的非局部变量可能在i，i-1，…，0层，所以，对非局部变量的引用是通过它的Display表元素d[i]，d[i-1]，…，d[0]而获得包围它的外过程的最新活动记录的基地址SP值，再加上变量在该过程（第i层）的偏移量。

如若非局部变量a是在第i层，那么引用a时，首先从当前栈顶过程的Display表中元素d[i]中取出存放的第i层最新活动记录基地址sp值，然后加上a所在过程（第i层）的偏移量，就得到a的存放地址。

　　·全局Display是存放本过程Display表的起始地址，其作用是把Display地址作为连接数据之一，如过程P1调用过程P2时，这时先从P1的全局Display找到P1的Display表起始地址，然后从P1的Display表中自底向上地抄录I2个单元（I2为P2的层数）再添上进入P2后新建立的P2的sp值，就构成了P2的Display表。

问答第6题

解：

问答第5题PL/0示意程序编译到D过程体时TABLE表的内容如下表。

TABLE表的内容

name

kind

level

val

adr

size

main

x

A

B

n

e

g

D

j

k

procedure

variable

procedure

procedure

constant

variable

variable

procedure

variable

variable

.

0

0

0

.

1

1

1

2

2

.

.

.

.

7

0

dx

过程A的入口

过程B的入口（待填）

.

dx

dx+1

过程D的入口

dx

dx+1

4

.

4

（待填5）

.

.

.

5

由于A和B是并列过程，当编译到B过程时A过程体已经编译结束，A所定义的标识符不会再被使用，所以由B过程定义的标识符覆盖。

问答第7题

（1）解：

描述L1语言的正规文法如下：

　　S→cA

　　A→aA|B

　　B→dD

　　D→bD|ε

（2）解：

描述L2语言的二型文法如下：

　　S→AB

　　A→0A1|0a1

　　B→bBc|ε

问答第8题

解：

句型（SdG）

　　短语：

（SdG）

　　简单（直接）短语：

G、a

　　句柄：

G

　　最左素短语：

SdG

问答第9题

解：

与正规式R＝（aba）*（（ba）*|b）b等价的NFA如下图：

问答第10题

解：

用子集法确定化如下表

I

Ia

Ib

状态

{X,0,1,3}

{0,1,3}..

{2,3,Y}..

{1,3}....

{2,Y}....

{Y}......

{0,1,3}

{0,1,3}

{1,3}..

.....

{1,3}..

.....

{2,3,Y}

{2,3,Y}

{Y}....

{2,Y}..

{Y}....

....

X

1

2

3

4

Y

确定化后如下图

问答第11题

解：

文法G[S]改写为等价的不含左递归和左公共因子的G'[S]为：

　　S→[A

　　A→B]A′

　　A′→SA′|ε

　　B→aB′

　　B′→B|ε

问答第12题

解：

文法的FIRST集和FOLLOW集

非终结符

FIRST集

FOLLOW集

S

{a}.....

{#，b}

D

{a，ε}

{#，b}

T

{b}.....

{e}....

M

{b}.....

{e}....

H

{b，ε}

{e}....

由于select（D→STe）∩select（D→ε）={a}∩{#，b}=

select（H→M）∩select（H→ε）={b}∩{e}=

所以该文法是LL

（1）文法，LL

（1）分析表如下表。

LL

（1）分析表

a

e

b

#

S

→aD.

D

→STe

→ε

→ε

T

→bM

M

→bH

H

→ε

→M.

表中不含多重入口也可说明文法是LL

（1）的。