文档库

最新最全的文档下载
当前位置:文档库 > 2014《编译原理》期末复习资料(完整版)

2014《编译原理》期末复习资料(完整版)

1.给出语言{a n b n a m b m | n,m≥0}的一个上下文无关文法。(6分)

解:G[S]:S—>AB

A—>aAb |ε

B—>aBb |ε

2.给出语言{1 n 0 m 1 m0 n | n,m≥0}的一个上下文无关文法。

解: G[S]:S—>1S0 | A

A—>0A1 |ε

3.P48 第6题(5)、(6).画语法树

6、已知文法G:

<表达式>::=<项>|<表达式>+<项>

<项>::=<因子>|<项>*<因子>

<因子>::=(<表达式>)|i

(5)i+(i+i) (6)i+i*i

解:(5)语法树:(6)语法树:

2014《编译原理》期末复习资料(完整版)

2014《编译原理》期末复习资料(完整版)

4.P48第13题直接短语等

13、一个上下文无关文法生成句子abbaa的推导树如下:

2014《编译原理》期末复习资料(完整版)

(3)求直接短语

解:直接短语有:a ε b

P102例题6.1及其分析.( 后加画语法树)

例6.1 设文法G[S]为:

(1)S—>aAcBe

(2)A—>b

(3)A—>Ab

(4)B—>d

对输入串abbcde#进行分析,检查该符号串是否是G[S]的句子。

2014《编译原理》期末复习资料(完整版)

2014《编译原理》期末复习资料(完整版)

一、计算分析题(60%)

1、正规式→ NFA→ DFA→最简DFA

P72第1题(1)、(4);

第一题1、构造下列正规式相应的DFA.

(1)1(0|1)*101

解:先构造NFA

2014《编译原理》期末复习资料(完整版)

2014《编译原理》期末复习资料(完整版)

除S,A外,重新命名其他状态,令AB为B、AC为C、ABZ为D,因为D含有Z(NFA的终态),所以

2014《编译原理》期末复习资料(完整版)

2014《编译原理》期末复习资料(完整版)

(4) b((ab)*|bb)*ab

解:先构造NFA

2014《编译原理》期末复习资料(完整版)

得到DFA如下所示:

2014《编译原理》期末复习资料(完整版)

P72第4题(a)

4、把下图确定化和最小化

2014《编译原理》期末复习资料(完整版)

解:确定化:

2014《编译原理》期末复习资料(完整版)

、{1},其中A为初态,A,B为终态,因此有:

2014《编译原理》期末复习资料(完整版)

最小化::

初始分划得终态组{A,B},非终态组{C}

Π0:{A,B},{C},对终态组进行审查,判断A和B是等价的,故这是最后的划分。重新命名,以A、C

2014《编译原理》期末复习资料(完整版)

即DFA最小化如下:

2014《编译原理》期末复习资料(完整版)

第7题

7、给文法G[S]:

S→aA|bQ

A→aA|bB|b

B→bD|aQ

Q→aQ|bD|b

D→bB|aA

E→aB|bF

F→bD|aE|b

构造相应的最小的DFA。

解:先构造NFA:

2014《编译原理》期末复习资料(完整版)

2014《编译原理》期末复习资料(完整版)

将S、A、BZ、B、Q、DZ、D重新命名,分别用0、1、2、3、4、5、6表示。因为2、5中含有Z,所以

2014《编译原理》期末复习资料(完整版)

2014《编译原理》期末复习资料(完整版)

Π0:{2,5},{0,1,3,4,6}

对{0,1,3,4,6}进行审查: {1,4}输入b到达{2,5},而{0,3,6}输入b到达{3,4,6},故得到新分划{1,4},{0,3,6}

Π1:{2,5},{1,4},{0,3,6}

对{0,3,6}进行审查: {0}经过b到达{2},{3,6}经过b到达{3,6},故得到新分划{0},{3,6}

Π3:得到最后划分{0},{1,4},{2,5},{3,6}

重新命名,以A,B,C,D分别代替{0},{1,4},{2,5},{3,6},其中A为始态,C为终态,可得到最小DFA 如下:

2014《编译原理》期末复习资料(完整版)

2、自顶向下方法

(一)设文法G(E):

E→ E + T|T

T→ T * F|F

F→ i | ( E )

(1) 判断是否为LL(1)文法.

(2) 构造文法的预测分析表.

解:详见P93-96例题。

(1)由于文法中含有左递归,所以必须先消除左递归,使文法变为:

E→T E`

E`→+TE`|ε

T→FT`

T`→*FT`|ε

F→ i| ( E )

FIRST集合如下:

FIRST(E)={(,i}

FIRST(E`)={+,ε}

FIRST(T)={(,i}

FIRST(T`)={*,ε}

FIRST(F)={(,i}

FOLLOW集合如下:

FOLLOW(E)={),#}

FOLLOW(E`)={),#}

FOLLOW(T)={+,),#}

FOLLOW(T`)={+,),#}

FOLLOW(F)={+,*,),#}

各产生式的SELECT集合如下:

SELECT(E→T E`)={(,i}

SELECT(E`→+TE`)={+}

SELECT(E`→|ε)={),#}

SELECT(T→FT`)={(,i}

SELECT(T`→*FT`)={*}

SELECT(T`→|ε)={+,),#}

SELECT(F→ i)={i }

SELECT(F→ ( E ))={(}

由上可知有相同左部产生式的SELECT集合的交集为空,故文法是LL(1)文法。

(2)构造文法的预测分析表如下:

2014《编译原理》期末复习资料(完整版)

(二) P101 6.(4) 改写下面文法为LL(1)文法,井对每个LL(1)文法构造相应的预测分析表。

2014《编译原理》期末复习资料(完整版)

解:

2014《编译原理》期末复习资料(完整版)

2014《编译原理》期末复习资料(完整版)

3、自底向上方法

已知文法G(E):

[0] S'→ E

[1] E→ E + T[2] E→ T

[3] T→ T * F[4] T→ F

[5] F→ ( E ) [6] F→ i

(1) 证明该文法是SLR(1)文法.

(2) 若已给出下面的SLR(1)分析表,试分析句子(i + ( * i ))#输入串出错的位置。

2014《编译原理》期末复习资料(完整版)

3、解:(1):

先分析LR(0)项目:

2014《编译原理》期末复习资料(完整版)

由上可见:

2014《编译原理》期末复习资料(完整版)

I1 ,I2 ,I9存在移进—归约冲突. 分析FOLLOW集:

因为:对I1 FOLLOW(S’)={ # }∩{ + }= ф

对I2FOLLOW(E)={ +,#, ) }∩{* }= ф

对I9FOLLOW(E)={ +,#, ) }∩{* }= ф

所以是SLR(1)文法。

(2):

2014《编译原理》期末复习资料(完整版)

4、(一) 给出语句 if a+b > b+c*d then while x*y>3 do x:=x-a*b else while b+c*d>10 do b:=b-(x*y+5) 相应的三地址代码.

2014《编译原理》期末复习资料(完整版)

(二) While a>0 ∨b<0do

Begin

X:=X+1;

if a>0 then a:=a-1

else b:=b+1 End;

翻译成四元式序列. (10分)

解:

(1) (j>,a,0,5)

(2) (j,_,_,3)

(3) (j<,b,0,5)

(4) (j,_,_,15)

(5) (+,x,1,T1)

(6) (:= ,T1,_,x)

(7) (j>,a,0,9)

(8) (j,_,_,12)

(9) (-,a,1,T2)

(10) (:= ,T2,_,a)

(11) (j,_,_,1)

(12) (+,b,1,T3)

(13) (:= ,T3,_,b)

(14) (j,_,_,1)

(15)

5、(一)设有基本块(10分)

T1:=2

T2:=10∕T1

T3:=S-R

T4:=S+R

A:=T2 * T4

B:=A

T5:=S+R

T6:=T3 * T5

B:=T6

(1) 画出DAG图;

(2) 假设基本块出口时只有A,B还被引用,请写出优化后的四元序列。

5(一)、解:(1)DAG:

2014《编译原理》期末复习资料(完整版)

(3分)

(2) 优化后的四元式

T3:=S-R

T4:=S+R

A:=5*T4

B:=T3+T4

(二) P255-257 DAG图

例试构造以下基本块G的DAG

(1)T0:=3.14

(2)T1:=2* T0

(3)T2:=R+r

(4)A:=T1 * T2

(5)B:=A

(6)T3:=2* T0

(7)T4:=R+r

(8)T5:=T3 * T4

(9)T6:=R-r

(10)B:=T5 *T6

(11)if B<=10 goto (1)

(1) 画出DAG图;

(2) 假设基本块出口时只有A,B还被引用,请写出优化后的四元序列。

解:(1)DAG图如下:

2014《编译原理》期末复习资料(完整版)

(2)四元序列如下:○1 T2:=R+r

○2 T6:=R-r

○3 A:=6.28* T2 ○4 B:=A*T6

四、

1.1

先给出NFA图:

2014《编译原理》期末复习资料(完整版)

画状态转换表:

2014《编译原理》期末复习资料(完整版)

得DFA如下图:

2014《编译原理》期末复习资料(完整版)

1.4

2014《编译原理》期末复习资料(完整版)

2014《编译原理》期末复习资料(完整版)

P72

第4题(a )

2014《编译原理》期末复习资料(完整版)

2014《编译原理》期末复习资料(完整版)