编译原理复习题目集答案.docx

编译原理复习题目集答案.docx

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

编译原理复习题目集答案

第4章词法分析

重点内容：

正规式转化为DFA

a、正规式->NFA

b、NFA->DFA（子集法）

c、DFA化简（分割法）

题目1：

课件例题：

a、为R=（a|b）*（aa|bb）（a|b）*构造NFA

b、从NFA构造DFA的算法

c、化简

题目2：

4.7例1：

构造正规式相应的DFA：

1（0|1）*101

按照以下三步：

（1）由正规表达式构造转换系统（NFA）

（2）由转换系统（NFA）构造确定的有穷自动机DFA

（3）DFA的最小化

答：

（1）构造与1（0|1）*101等价的NFA

（2）将NFA转换成DFA：

采用子集法，即DFA的每个状态对应NFA的一个状态集合：

0

1

X

A

A

A

AB

AB

AC

AB

AC

A

ABY

ABY

AC

AB

除X，A外，重新命名其他状态：

0

1

X

A

A

A

B

B

C

B

C

A

D

D

C

B

1、将M的状态分成非终态和终态集{X,A,B,C}和{D}。

2、寻找子集中不等价状态{X,A,B,C}=>{X}，{A,B}{C}=>{X}{A}{B}{C}，无需合并。

最后生成DFA：

题目3：

自习、书本练习4.7，参考答案见《z4书本练习4.7.doc》

已知文法G[S]：

S→aA|bQA→aA|bB|bB→bD|aQQ→aQ|bD|bE→aB|bFF→bD|aE|b

1、构由于不可到达，去除E、F相关的多余产生式

2、由新的G[S]构造NFA如下

3、NFA的转换表：

a

b

S

A

Q

A

A

B,Z

B,Z

Q

D

Q

Q

D,Z

D

A

B

D,Z

A

D

B

Q

D

4、子集法重命名状态：

（上标0：

初态，*：

终态）

a

b

00

1

3

1

1

2

2*

3

4

3

3

5

4

1

6

5*

1

4

6

3

4

5、使用分割法化简以上DFAG：

5.1令G={（0,1,3,4,6）,（2,5）}//分别为非终态和终态集

5.2由{0,1,3,4,6}a={1,3}，{0,1,3,4,6}b={3,2,5,6,4}

将{0,1,3,4,6}划分为{0,4,6}{1,3}，得G={（0,4,6）,（1,3）,（2,5）}

5.3由{0,4,6}b={3,6,4}，将之划分为{0},{4,6}，得G={（0）,（4,6）,（1,3）,（2,5）}

5.4观察后，G中状态不可再分，为最小化DFA。

6、分别用0，4，1，2代表各状态，DFA状态转换图如下：

造相应的最小的DFA

第5章自顶向下的语法分析

重点内容：

LL

（1）文法

a、去除左递归

b、LL

（1）文法的判定（first、follow、select集）

c、预测分析表

d、使用栈和预测分析表对输入串的分析

题目1：

课件例题：

消除左递归+判定+分析

算术表达式文法G 

E→E+T│T

T→T*F│F

F→（E）│I

d、分析输入串i+i*i#

（1）消除G的左递归得到文法G‘

E→TE'

E'→+TE'│ε

T→FT'

T'→*FT'│ε

F→（E）│i

（2）求出每个产生式的select集,G’是LL

（1）文法

SELECT（E→TE'）={（,i}SELECT（E'→+TE'）={+}

SELECT（E'→ε）={）,#}SELECT（T→FT'）={（,i}

SELECT（T'→*FT'）={*}SELECT（T'→ε）={+,）,#}

SELECT（F→（E））={（}SELECT（F→i）={i}

（3）依照选择集合把产生式填入分析表

注：

表中空白处为出错

题目2：

作业、习题5.1：

消除左递归+判定+分析

G[S]:

S->a|^|（T）T->T,S|S

d、分析输入串（a,a）#

文法G[S]:

S->a|^|（T），T->T,S|S

（1）给出对（a,（a,a））的最左推导

（2）改写文法，去除左递归

（3）判断新文法是否LL1文法，如是，给出其预测分析表

（4）给出输入串（a,a）#的分析过程，判断其是否文法G的句子。

答：

（1）对（a,（a,a））的最左推导为：

S=>（T）

=>（T,S）

=>（S,S）

=>（a,S）

=>（a,（T））

=>（a,（T,S））

=>（a,（S,S））

=>（a,（a,S））

=>（a,（a,a））

（2）改写文法为：

0）S→a1）S→ʌ2）S→（T）3）T→SN4）N→,SN5）N→ε

非终结符

FIRST集

FOLLOW集

S

{a,ʌ,（}

{#,,,）}

T

{a,ʌ,（}

{）}

N

{,,ε}

{）}

对左部为N的产生式可知：

FIRST（→,SN）={,}

FIRST（→ε）={ε}

FOLLOW（N）={）}

由于SELECT（N→,SN）∩SELECT（N→ε）={,}∩{）}=ᴓ

所以文法是LL

（1）的。

（3）预测分析表：

a

ʌ

（

）

#

S

→a

→ʌ

→（T）

T

→SN

→SN

→SN

N

→ε

→,SN

可由预测分析表中，无多重入口判定文法是LL

（1）的。

（4）对输入串（a,a）#的分析过程为：

栈

当前输入符

剩余输入符

所用产生式

#S

#）T（

#）T

#）NS

#）Na

#）N

#）NS,

#）NS

#）Na

#）N

#）

#

（

（

a

a

a

a

a

）

）

#

a,a）#

a,a）#

a）#

a）#

a）#

a）#

a）#

）#

）#

#

#

S→（T）

T→SN

S→a

N→,SN

S→a

N→ε

可见输入串（a,a）#是文法的句子。

题目3：

复习、书本5.6例1：

判定+分析

G[S]：

S→aH，H→aMd|d，M→Ab|ε，A→aM|e

d、分析输入串aaabd#

（1）判断G[S]是否为LL

（1）文法；若是，构造其预测分析表；

Select（H→aMd）={a},Select（H→d）={d}；

Select（M→Ab）={a,e},Select（M→ε）={d,b}；

Select（A→aM）={a},Select（A→e）={e}

相同左部产生式的select集的交集均为空，所以G[S]是LL

（1）文法。

预测分析表：

（2）分析aaabd#是否G[S]的句子。

使用栈和预测分析表对输入串的分析：

第6章自底向上的语法分析

重点内容：

算符优先文法

a、非终结符的firstvt集和lastvt集的计算

b、算符优先关系表

c、使用栈和算符优先关系表对输入串的归约

题目1：

课件例题：

文法：

E→E+T|T

T→T×F|F

F→（E）|I

c、算符优先归约输入串i+i#

（1）求各非终结符的FIRSTVT集与LASTVT集

（2）计算算符优先关系表并说明此文法是否算符优先文法

（3）给出输入串i+i#的算符优先分析过程

（1）FIRSTVT-LASTVT表：

非终结符

FIRSTVT

LASTVT

E

+×i（

+×）i

T

xi（

×）i

F

i（

）i

（2）算符优先关系表：

+

x

（

）

i

#

+

>

<

<

>

<

>

x

>

>

<

>

<

>

（

<

<

<

=

<

）

>

>

>

>

i

>

>

>

>

#

<

<

<

<

=

优先关系表中无多重定义，此文法是算符优先文法

（3）对输入串i+i#的算符优先分析过程为：

题目2：

作业、习题6.1、复习：

文法G[S]:

S->a|^|（T）T->T,S|S

c、算符优先归约输入串（a,a）#

文法G[S]:

S->a|^|（T），T->T,S|S

（1）计算G[S]的FIRSTVT、LASTVT

（2）改造算符优先关系表并说明G[S]是否算符优先文法

（3）给出输入串（a,a）#的算符优先分析过程，判断其是否文法G的句子。

答：

文法展开为：

S→a

S→ʌ

S→（T）

T→T,S

T→S

（1）FIRSTVT-LASTVT表：

非终结符

FIRSTVT

LASTVT

S

a^（

a^）

T

a^（

a^）

（2）算符优先关系表：

a

^

（

）

#

a

>

>

>

^

>

>

>

（

<

<

<

=

<

）

>

>

>

<

<

<

>

>

#

<

<

<

=

表中无多重入口，所以是算符优先（OPG）文法。

（3）对输入串（a,a）#的算符优先分析过程为：

栈

当前输入字符

剩余输入串

动作

#

#（

#（a

#（N

#（N,

#（N,a

#（N,N

#（N

#（N）

#N

（

a

a

）

）

）

#

#

a,a）#

a）#

a）#

a）#

）#

#

#

#

Movein

Movein

Reduce:

S→a

Movein

Movein

Reduce:

S→a

Reduce:

T→T,S

Movein

Reduce:

S→（T）

可见输入串（a,a）#是文法的句子。

题目3：

自习、书本练习6.4，参考答案见《z6书本练习6.4.doc》

已知文法G[S]：

SS;GSGGG（T）GHHaH（S）TT+STS

c、算符优先归约输入串a;（a+a）#

（1）构造算符优先关系表

FIRSTVT（S）={;}∪FIRSTVT（G）={;,a,（}

FIRSTVT（G）={（}∪FIRSTVT（H）={a,（}

FIRSTCT（H）={a,（}

FIRSTVT（T）={+}∪FIRSTVT（S）={+,;,a,（}

LASTVT（S）={;}∪LASTVT（G）={;,a,）}

LASTVT（G）={）}∪LASTVT（H）={a,）}

LASTVT（H）={a,}}

LASTVT（T）={+}∪LASTVT（S）={+,;,a,}}

即：

FIRSTVT

LASTVT

S

;,a,（

;,a,）

G

a,（

a,）

H

a,（

a,）

T

+,;,a,（

+,;,a,）

由SàS;G

LASTVT（S）>;

;

由GàG（T…

LASTVT（G）>（

（

由Gà…T）

LASTVT（T）>）

由Gà…（T）

（=）

由TàT+S

LASTVT（T）>+

+

由Hà（S）

（

LASTVT（S）>）

（=）

由S->#S#

#

LASTVT（S）>#

#=#

;

（

）

a

+

#

;

>

<

>

<

>

>

（

<

<

＝

<

<

）

>

>

>

>

>

a

>

>

>

>

>

+

<

<

>

<

>

#

<

<

<

＝

由优先关系表中所有符号对的关系唯一，可判定文法G[S]是算符优先文法。

（2）分析a;（a＋a）//SS;G|GGG（T）|HHa|（S）TT+S|S

分析栈

优先关系

当前字符

剩余输入串

动作

1

#

<

a

;（a＋a）#

移进

2

#a

>

;

（a＋a）#

归约Ha

3

#H

<

;

（a＋a）#

移进

4

#H;

<

（

a+a）#

移进

5

#H;（

<

a

+a）#

移进

6

#H;（a

>

+

a）#

归约Ha

7

#H;（H

<

+

a）#

移进

8

#H;（H+

<

a

）#

移进

9

#H;（H+a

>

）

#

归约Ha

10

#H;（H+H

>

）

#

归约TT+S

11

#H;（T

=

）

#

移进

12

#H;（T）

>

#

归约H（S）

13

#H;H

>

#

归约SS;G

14

#S

=

#

接受