PDF《第4章 词法分析》

《编译原理》课后习题答案

第四章 第4章词法分析 第1题构造下列正规式相应的 DFA.

(1) 1(0|1) *101 (2) 1(1010*|1(010)*1)*0 (3) a((a|b)*|ab*a)*b (4) b((ab)*|bb)*ab 答案: (1) 先构造 NFA: 用子集法将 NFA 确定化 .

0 1 X . A A A AB AB AC AB AC A ABY ABY AC AB 除X,A 外,重新命名其他状态,令AB 为B、AC 为C、ABY 为D,因为 D 含有 Y(NFA 的终态),所以 D 为终态. .

0 1 X . A A A B B C B C A D D C B DFA 的状态图:: 盛威网(www.snwei.com)专业的计算机学习网站

1 《编译原理》课后习题答案

第四章 (2)先构造 NFA: X A

1 B ε

1 C

0 D

1 E

0 ε F

1 G

0 H

1 I

0 J

1 K L ε ε

0 Y ε ε ε ε 用子集法将 NFA 确定化 ε

0 1 X X T0=X A A ABFL T1= ABFL Y CG Y Y CG CGJ T2= Y T3= CGJ DH K DH DH K ABFKL T4= DH EI EI ABEFIL T5= ABFKL Y CG T6= ABEFIL EJY CG EJY ABEFGJLY T7= ABEFGJLY EHY CGK EHY ABEFHLY CGK ABCFGJKL T8= ABEFHLY EY CGI EY ABEFLY CGI CGJI T9= ABCFGJKL DHY CGK DHY DHY T10= ABEFLY EY CG T11= CGJI DHJ K DHJ DHJ T12= DHY EI T13= DHJ EIK EIK ABEFIKL T14= ABEFIKL EJY CG 盛威网(www.snwei.com)专业的计算机学习网站

2 《编译原理》课后习题答案

第四章 将T

0、T

1、T

2、T

3、T

4、T

5、T

6、T

7、T

8、T

9、T

10、T

11、T

12、T

13、T14重新命名,分别用

0、

1、

2、

3、

4、

5、

6、

7、

8、

9、

10、

11、

12、

13、14 表示.因为

2、

7、

8、

10、12 中含有Y, 所以它们都为终态.

0 1

0 1

1 2

3 2

3 4

5 4

6 5

2 3

6 7

3 7

8 9

8 10

11 9

12 9

10 10

3 11

13 5

12 6

13 14

14 7

3 0

1 0

12 1

2 7

8 10

3 4

5 6

9 11

13 14

1 1

0 1

0 1

0 1

1 0

1 1

0 1

0 1

1 0

0 1

0 1 盛威网(www.snwei.com)专业的计算机学习网站

3 《编译原理》课后习题答案

第四章 (3) 先构造 NFA: 先构造 NFA: X A a B ε a,b ε D a E a F C ε Y ε ε b ε b 用子集法将 NFA 确定化 ε a b X X T0=X A A ABCD T1=ABCD BE BY BE ABCDE BY ABCDY T2=ABCDE BEF BEY BEF ABCDEF BEY ABCDEY T3=ABCDY BE BY T4=ABCDEF BEF BEY T5=ABCDEY BEF BEY 将T

0、T

1、T

2、T

3、T

4、T5重新命名,分别用

0、

1、

2、

3、

4、5 表示.因为

3、5 中含有Y, 所以它们都为终态. a b

0 1

1 2

3 2

4 5

3 2

3 4

4 5

5 4

5 0 a b

1 3

2 a

5 4 a b a b a b a b 盛威网(www.snwei.com)专业的计算机学习网站

4 《编译原理》课后习题答案

第四章 (4) 先构造 NFA: X A b B ε a F b G b H E ε Y a ε C D b ε I b ε ε ε ε 用子集法将 NFA 确定化: ε a b X X T0=X A A ABDEF T1=ABDEF CI G CI CI G G T2=CI DY DY ABDEFY T3=G H H ABEFH T4=ABDEFY CI G T5=ABEFH CI G 将T

0、T

1、T

2、T

3、T

4、T5重新命名,分别用

0、

1、

2、

3、

4、5 表示.因为

4 中含有Y, 所以它为终态. a b

0 1

1 2

3 2

4 3

5 4

2 3

5 2

3 DFA 的状态图: 盛威网(www.snwei.com)专业的计算机学习网站

5 《编译原理》课后习题答案

第四章

0 b b

1 2 a

4 5

3 b b a b a b 盛威网(www.snwei.com)专业的计算机学习网站

6 《编译原理》课后习题答案

第四章 第2题 已知 NFA= ( {x,y,z} ,{0,1},M,{x},{z}) , 其中: M(x,0)={z}, M(y,0)={x,y}, ,M(z,0)={x,z}, M(x,1)={x},M(y,1)=φ,M(z,1)={y},构造相应的 DFA. 答案: 先构造其矩阵

0 1 x z x y x,y z x,z y 用子集法将 NFA 确定化:

0 1 x z x z xz y xz xz xy y xy xy xyz x xyz xyz xy 将x、z、xz、y、xy、xyz 重新命名,分别用 A、B、C、D、E、F 表示.因为 B、C、F 中含有 z,所以它为终态.