编译原理1、3章作业答案

第一章

习题1.6.3：对于图1-14中的块结构代码，假设使用常见的声明的静态作用域规则，给出其中12个声明中的每一个的作用域？ { int w, x ,y ,z; /*块B1 */ { int x, z; /*块B2 */ { int w, x; } /*块B3 */ } { int w, x; /*块B4 */ { int y, z;} /*块B5 */ } } 答： 声 明 块 变 作 用 域 量 W X Y Z B1 B2 B3 B4 B5 B1-B3-B4 / B3 B4 / B1-B2-B4 B2-B3 B3 B4 / B1-B5 / / / B5 B1-B2-B5 B2 / / B5

习题1.6.4：下面C代码的打印结果是什么？ #define a (x+1) Int x=2; Void b(){ x=a;printf(“%d\\n”,x);} Void b(){ x=1;printf(“%d\\n”,a);} Void main(){b();c();} 答：输出结果是 3 2

调用函数b()时，a=x+1此处x为全局变量值2，故输出为3 调用函数c()时，x局部定义为1，此处a=x+1为2，故输出为2

第三章

习题3.3.2：试描述下列正则表达式定义的语言：

(1)a(a|b)*a:以a开头和以a结束的中间由任意个a或b组成的串的集合

(2)((?|a)b*)*:由0个和多个b组成的串以及由0个或多个以a开头由任意个b组成的实例所组成的串的集合 (3)(a|b)*a(a|b)(a|b)：由a或b构成的长度至少为3的且倒数第三个字符为a的串的集合 (4)a*ba*ba*ba*：由a、b构成的b的个数为3的串的集合

习题3.3.5：试写出下列语言的正则定义：

(1)包含5个元音的所有小写字母串，这些串中的元音按顺序出现

：a[bcd]?e[fgh]? i[jklmn]?o[pqrst]?u[vwxyz]? (2)所有由按字典递增排序的小写字母组成的串 ：a*b*c*d*…z*

(3)注释，即/*和*/之间的串，且串中没有不在双引号(＂)中的*/ ：[/*]([a-zA-Z]|(＂*/＂))?[*/]

习题3.4.1：给出识别练习3.3.2中各个正则表达式所描述的语言的状态转换图 (1) a(a|b)?a

(3)(a|b)? a(a|b)(a|b)

习题3.7.3使用算法3.23和3.20将下列正则表达式转换成DFA (1)(a|b)?

由(a|b)?生成相应的NFA，如下图所示

由上面的NFA生成相应的DFA

1) 标记集合A，A是?-closure(1)，即A={1,2,3,5,8}

2) 标记集合B，B是?-closure（move(A,a)）={1,2,3,4,5,7,8} 3) 标记集合C，C是?-closure（move(A,b)）={1,2,3,5,6,7,8}

得到一个只含有三个状态的DFA，其中A是接受状态,其状态转换图如下

(2)(a?|b?)?

由(a?|b?)?得到相应的NFA如下图所示

由上述NFA得到相应的DFA如下

1)标记集合A，A是?-closure(0)，即A={0,1,2,3,4,5}

2)可以得到 ?-closure（move(A,a)）={0,1,2,3,4,5}=A，?-closure（move(A,b)）={0,1,2,3,4,5}=A，故该DFA中应只有一个状态A，得到一个一状态的DFA，其状态转换图如下

本文来源：https://www.bwwdw.com/article/n84t.html