编译原理题库——简答题Word文档下载推荐.doc

编译原理题库——简答题Word文档下载推荐.doc

《编译原理题库——简答题Word文档下载推荐.doc》由会员分享，可在线阅读，更多相关《编译原理题库——简答题Word文档下载推荐.doc（206页珍藏版）》请在冰点文库上搜索。

T′→,ST′|ε

提取公共左因子：

S→（T）|aS′

S′→+S|ε

T′→,ST′|ε

3答：

wab+cde10-/+8+*+

4答：

该语句的四元式序列如下（其中E1、E2和E3分别对应A＜C∧B＜D、A≥1和A≤D，并且关系运算符优先级高）：

100（j<

A,C,102）

101（j,_,_,113）

102（j<

B,D,104）

103（j,_,_,113）

104（j=,A,1,106）

105（j,_,_,108）

106（+,C,1,C）

107（j,_,_,112）

108（j≤,A,D,110）

109（j,_,_,112）

110（+,A,2,A）

111（j,_,_,108）

112（j,_,_,100）

113

5答：

证明：

　　由文法G[S]：

S→aSb|Sb|b，对句子aabbbb对应的两棵语法树为：

因此，文法G[S]为二义文法。

编译原理B

1.什么是句子？

什么是语言?

2.写一文法，使其语言是偶正整数的集合,要求：

（1）允许0打头；

（2）不允许0打头。

3.已知文法G[E]为：

E→T|E+T|E-T

T→F|T*F|T/F

F→（E）|i

①该文法的开始符号（识别符号）是什么？

②请给出该文法的终结符号集合VT和非终结符号集合VN。

③找出句型T+T*F+i的所有短语、简单短语和句柄。

4.构造正规式相应的NFA:

1（0|1）*101。

5.写出表达式（a＋b*c）/（a＋b）－d的逆波兰表示和三元式序列。

B卷答案

（1）设G是一个给定的文法，S是文法的开始符号，如果Sx（其中x∈VT*）,则称x是文法的一个句子。

（2）设G[S]是给定文法，则由文法G所定义的语言L（G）可描述为：

L（G）＝{x│Sx,x∈VT*}。

（1）G[S]=（{S,P,D,N},{0,1,2,…,9},P,S）

P:

S->

PD|D

P->

NP|N

D->

0|2|4|6|8

N->

0|1|2|3|4|5|6|7|8|9

（2）G[S]=（{S,P,R,D,N,Q},{0,1,2,…,9},P,S）

PD|P0|D

NR|N

R->

QR|Q

2|4|6|8

1|2|3|4|5|6|7|8|9

Q->

0|1|2|3|4|5|6|7|8|9

3解：

①该文法的开始符号（识别符号）是E。

②该文法的终结符号集合VT={+、-、*、/、（、）、i}。

非终结符号集合VN={E、T、F}。

③句型T+T*F+I的短语为i、T*F、第一个T、T+T*F+i;

简单短语为i、T*F、第一个T;

句柄为第一个T。

4解：

1（0|1）*101对应的NFA为

5解：

逆波兰表示：

　　　　　abc*＋ab＋/d－　　　　　　　　　

三元式序列：

　　　　　①（*，b，c）　　　　　②（＋，a，①）　　　　　③（＋，a，b）　　　　　④（/，②，③）　　　　　⑤（－，④，d）

编译原理C

1．（10分）对下列错误信息，请指出可能是编译的哪个阶段（词法分析、语法分析、语义分析、代码生成）报告的。

（1）else没有匹配的if

（2）数组下标越界

（3）使用的函数没有定义

（4）在数中出现非数字字符

（5）函数调用时实参与形参类型不一致。

2．（15分）构造一个DFA，它接收Σ={0,1}上所有满足如下条件的字符串：

每个1都有0直接跟在右边。

并给出该语言的正规式

3．（10分）为下面的语言设计文法：

（1）{ambn,其中m³

n}

（2）{w|wÎ

{a,b}*，w的长度为奇数}

证明E+T*（id）是文法的一个句型，指出该句型的所有短语、直接短语和句柄。

5．（15分）给定文法：

E→E+T|E-T|T

T→T*F|T/F|F

F→（E）|id

C卷答案

1答案：

（每小题2分）

（1）语法分析

（2）语法分析

（3）语义分析

（4）词法分析

（5）语义分析

2答案：

按题意相应的正规表达式是（0*10）*0*，或0*（0|10）*0*，构造相应的DFA。

3答案：

（每小题10分）

（1）考虑在先产生同样数目的a,b，然后再生成多余的a。

以下是一种解法：

S→aSb|aS|ε

（2）A→aB|bB

B→aA|bA|ε

5证明E+T*（id）是文法的一个句型，指出该句型的所有短语、直接短语和句柄。

答：

，

短语：

id，（id），T*（id），E+T*（id）。

直接短语：

id。

句柄是id。

编译原理D卷

3、何谓“标识符”，何谓“名字”，两者的区别是什么？

4、令＋、*和↑代表加、乘和乘幂，按如下的非标准优先级和结合性质的约定，计算1＋1*2↑*1↑2的值：

（1）、优先顺序（从高至低）为＋、*和↑，同级优先采用左结合。

（2）、优先顺序为↑、＋、*，同级优先采用右结合。

6、令文法G6为N→D∣ND，D→0∣1∣2∣3∣4∣5∣6∣7∣8∣9

（1）、G6的语言L（G6）是什么？

（2）、给出句子0127、34和568的最左推导和最右推导。

7、写一个文法，使其语言是奇数集，且每个奇数不以0开头。

8、令文法为E→T∣E+T∣E-T

T→F∣T*F∣T/F

F→（E）∣i

（1）给出i+i*i、i*（i+i）的最左推导和最右推导；

给出i+i+i、i+i*i和i-i-i的语法树。

9、证明下面的文法是二义的：

S→iSeS∣iS∣i

11、给出下面语言的相应文法：

L1={anbnci∣n≥1，i≥0}，

L2={aibncn∣n≥1，i≥0}

L3={anbnambm∣n，m≥0}

L4={1n0m1m0n∣n，m≥0}

标识符是高级语言中定义的字符串，一般是以英文字母（包括大小写字母）或下划线开头的，由数字、字母和下划线组成的一定长度的字符串，它只是一个标志，没有其他含义。

名字是用标识符表示的，但名字不仅仅是一个字符串，它还具有属性和值。

（1）、1＋1*2↑*1↑2=2*2↑*1↑2=4↑*1↑2=4↑↑2=

（2）、1＋1*2↑*1↑2=

6解：

（1）、L（G6）是由0到9这10个数字组成的字符串。

（2）、句子0127、34和568的最左推导：

N=>

ND=>

NDD=>

NDDD=>

DDDD=>

0DDD=>

01DD=>

012D=>

0127

DD=>

3D=>

34

DDD=>

5DD=>

56D=>

568

句子0127、34和568的最右推导：

N=>

N7=>

ND7=>

N27=>

ND27=>

N127=>

D127=>

N4=>

D4=>

N8=>

ND8=>

N68=>

D68=>

7解：

G（S）：

A→2∣4∣6∣8∣D

B→A∣0

C→CB∣A

D→1∣3∣5∣7∣9

S→CD∣D

8解：

（1）最左推导为：

E=>

E+T=>

T+T=>

F+T=>

i+T=>

i+T*F=>

i+F*F=>

i+i*F=>

i+i*i

T=>

T*F=>

F*F=>

i*F=>

i*（E）=>

i*（E+T）=>

i*（T+T）

=>

i*（F+T）=>

i*（i+T）=>

i*（i+F）=>

i*（i+i）

最右推导为：

E+T=>

E+T*F=>

E+T*i=>

E+F*i=>

E+i*i=>

T+i*i=>

F+i*i=>

F*（E）=>

F*（E+T）=>

F*（E+F）=>

F*（E+i）

F*（T+i）=>

F*（F+i）=>

F*（i+i）=>

（2）语法树：

T

E

+

F

i

*

-

9解：

考虑句子iiiei，存在如下两个最右推导：

S=>

iSeS=>

iSei=>

iiSei=>

iiiei

iS=>

iiSeS=>

由此该文法是二义的。

11解：

L1的文法：

S→AC；

A→aAb∣ab；

C→cC∣ε

L2的文法：

S→AB；

A→aA∣ε；

B→bBc∣bc

L3的文法：

A→aAb∣ε；

B→aBb∣ε

L4的文法：

S→1S0∣A；

A→0A1∣ε；

编译原理E卷

1、令A、B和C是任意正规式，证明以下关系成立：

A∣A=A

（A*）*=A*

A*=ε∣AA*

（AB）*A=A（BA）*

（A∣B）*=（A*B*）*=（A*∣B*）*

A=b∣aA当且仅当A=a*b

2、构造下列正规式相应的DFA

1（0∣1）*101

1（1010*∣1（010）*1）*0

0*10*10*10*

（00∣11）*（（01∣10）（00∣11）*（01∣10）（00∣11）*）*

3、给出下面正规表达式：

（1）以01结尾的二进制数串；

（2）能被5整除的十进制整数；

包含奇数个1或奇数个0的二进制数串；

4、对下面情况给出DFA及正规表达式：

（1）{0，1}上不含子串010的所有串。

5、将图3.18的（a）和（b）分别确定化和最小化。

1

a，b

a

（a）

2

b

（b）

5

4

3

6、构造一个DFA，它接受∑={0，1}上所有满足如下条件的字符串：

每个1都有0直接跟在右边。

、

7、给定右线性文法G：

S→0S∣1S∣1A∣0B

A→1C∣1

B→0C∣0

C→0C∣1C∣0∣1

求出一个与G等价的左线性文法。

文法G对应的状态转换图如下所示：

S

Z

0，1

B

C

A

E卷答案

1证明：

（1）、A∣A=A

L（A∣A）=L（A）∪L（A）=L（A），所以有A∣A=A。

（2）、（A*）*=A*

（3）、A*=ε∣AA*

通过证明两个正规式所表示的语言相同来证明两个正规式相等。

L（ε∣AA*）=L（ε）∪L（A）L（A*）=L（ε）∪L（A）（L（A））*

=L（ε）∪L（A）（（L（A））0∪（L（A））1∪（L（A））2∪（L（A））3∪…）

=L（ε）∪（L（A））1∪（L（A））2∪（L（A））3∪（L（A））4∪…

=（L（A））*=L（A*）

即：

L（ε∣AA*）=L（A*），所以有：

A*=ε∣AA*

（4）、（AB）*A=A（BA）*

利用正规式的分配率和结合律直接推导。

（AB）*A=（（AB）0∣（AB）1∣（AB）2∣（AB）3∣…）A

=εA∣（AB）1A∣（AB）2A∣（AB）3A∣…

=Aε∣A（BA）1∣A（BA）2∣A（BA）3∣…

=A（ε∣（BA）1∣（BA）2∣（BA）3∣…）

=A（BA）*

（AB）*A=A（BA）*

（5）、（A∣B）*=（A*B*）*=（A*∣B*）*

证明:

先证（A∣B）*=（A*B*）*

因为L（A）L（A）*L（B）*,L（B）L（A）*L（B）*

故:

L（A）∪L（B）L（A）*L（B）*

于是由本题第二小题结论可知（L（A）∪L（B））*（L（A）*L（B）*）*①

又L（A）L（A）∪L（B）,L（B）L（A）∪L（B）

L（A）*（L（A）∪L（B））*

L（B）*（L（A）∪L（B））*

因此有:

L（A）*L（B）*（L（A）∪L（B））*（L（A）∪L（B））*=（（L（A）∪L（B））*）2

故（L（A）*L（B）*）*（（L（A）∪L（B））*）*

由本题第二小题得:

（（L（A）∪L（B））*）*=（L（A）∪L（B））*

故得:

（L（A）*L（B）*）*（L（A）∪L（B））*②

则由①②得:

（L（A）∪L（B））*=（L（A）*L（B）*）*

由于L（（A*B*））*=（L（A*B*））*=（L（A*）L（B*））*=（L（A）*L（B）*）*

即有（L（A）∪L（B））*=L（（A*B*））*③

而（A|B）*对应的语言为（L（A）∪L（B））*,且（A*B*）*对应的语言为L（（A*B*））*

则根据③得（A|B）*=（A*B*）*

再证:

（A*|B*）*=（A*B*）*

因为:

A,B是任意正规式,由以上结论得:

（A*|B*）*=（（A*）*（B*）*）*

又由本题第二小题目的结论可得：

（A*）*=A*，（B*）*=B*

因此，（A*|B*）*=（A*B*）*

综合上述两种结论，最后得：

（A∣B）*=（A*B*）*=（A*∣B*）*

2解：

（1）、1（0∣1）*101

第一步：

根据正规式构造NFA，先引入初始状态X和终止状态Y：

X

1（0∣1）*101

Y

再对该转换图进行分解，得到分解后的NFA如下图：

X

ε

第二步：

对NFA进行确定化，获得状态转换矩阵：

状态

{X}

Ø

{1，2，3}

{2，3}

{2，3，4}

{2，3，5}

{2，3，4，Y}

根据转换矩阵获得相应的DFA：

第三步：

化简该DFA，获得最简的DFA即为所求。

首先根据是否终止状态将所有状态分为两个集合{0，1，2，3，4}和{5}，这里集合{5}已经不可划分，只需考虑集合{0，1，2，3，4}。

{0，1，2，3，4}0={2，4，-}，{0，1，2