博客

【编译原理】龙书第三章作业答案

练习3.1.1：根据3.1.2节中的讨论，将下面的C++程序划分成正确的词素序列。哪些词素应该有相关联的词法值？应该具有什么值？

答案：

左列为词素，右列为值，划分如下：

练习3.1.2：像HTML或XML之类的标记语言不同于传统的程序设计语言，它们要么包含有很多标点符号（标记），如HTML，要么使用由用户自定义的标记集合，如XML。而且标记还可以带有参数。请指出如何把如下的HTML文档划分为适当的词素序列。哪些词素应该有相关联的词法值？应该具有什么值？

答案：

其中，常量的值为所存在内存单元中的值；符号没有对应的值；关键字的值为它们本身。

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

答案：

1）以a开头和结尾的零个或多个a或b组成的串的组合。

2）零个或多个a或b组成的串的组合。

3）结尾倒数第三个是a的零个或多个a或b组成的串的组合。

4）由三个b和零个或多个a组成的串的组合。

5）偶数个a或b组成的串的组合。

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

答案：


1）设σ=[b-df-hj-np-tv-z]，也就是除了所有元音以外的小写字母串。所以该题语言的正则定义是：σ* a(σ|a)*e(σ|e)*i(σ|i)*o(σ|o)*u(σ|u) *

2）a * b * … z *

3）由于串中字符串只可能是以下两种情况：

（i）除了 * / 以外的所有字符；

（ii）“ * /”。考虑用或符号 ” | ” 来描述上述情况。

为了使其描述更多合法字符，再将它描述为闭包 ” * ”。再结合首尾分别规定为：”/ * ”和 ” * /”，所以正则表达式如下（注：” / ” 前和 ” * ” 前必须加多一个 “ \ ”）：

\ / \ * ((^\ * \ / )|(“ * /”)) * \ * \ /

9）(b*a * )|(b * a * ba * )

练习3.3.11: UNIX的shell命令sh在文件名表达式中使用图3-9中的运算符来描述文件名的集合。例如，文件名表达式*.o和所有以.0结束的文件名匹配;sort1.?和所有形如sort1.c的文件名匹配，其中c可以是任何字符。试问如何使用只包含并、连接和闭包运算符的正则表达式来表示sh文件名表达式?

答案：

首先设name为所有可以做文件名的字符，前缀一定为可做文件名的字符，然后可以为?*\的字面字符，点号“.”之后也是一样的：

[name\ * \ ?? ’\’].[ name \ * \ ??’\’]

练习3.4.1: 给出识别练习3.3.2中各个正则表达式所描述的语言的状态转换图

答案：


1）



2）



3）该小题较复杂，为了确保思路清晰，首先作出如下所示的NFA图像：



其次将这个NFA进一步转换得到状态转移图（也是某种意义上的DFA）：



4）为了确保思路清晰，首先作出如下所示的NFA图像：



其次将这个NFA进一步转换得到状态转移图（也是某种意义上的DFA）：



5）这个字符串可以看作是(aa|bb) * 和（（ab|ba）(aa|bb) * （ab|ba）(aa|bb)* ）*两个闭包连接而成的而在画第二个大闭包的各个组成部分的时候，最后一部分(aa|bb) * 与第一部分的闭包完全相同，所以可以转换到第一部分从而形成闭包，具体状态转移图如下所示：

练习3.4.2࿱