编译原理习题两则（龙书，写出语言的正则定义）

3.3.5.3

注释，即 /* 和 */ 之间的串，且串中没有不在双引号（"）中的 */。

注：假设双引号是匹配的。

---

思路：从空串开始写，写出整体框架后，通过分类讨论的方法不断进行扩充构造。

---

很容易想到整体结构为：

comment_begin content_without_end comment_end
1

且显然：

comment_begin -> /\*
comment_end -> \*/
1
2

下面需要通过分类讨论的方法构造出 content_without_end。首先，由于其中的内容是自由的，所以它肯定是一个形如闭包的正则表达式（(...)*）。然后，容易想到内容里可以有被引号括起来的任意字符。因此我们定义：

quoted -> "[^"]*"
1

对于 content_without_end 的闭包中的其他情况，肯定是不在引号内的，所以一定不能出现 */，还需要注意不要因为闭包出现 */。下面继续分类讨论：

• 如果没有 * 出现在闭包中，是不会有问题的。所以可以认为闭包的形式形如：

  (quoted | [^*"] | ...)*
  1

  [^*"] 还排除了双引号，是因为我们假设了双引号是匹配的，所以双引号已经在 quoted 中被处理了。

• 如果 * 出现在了闭包中，后面是不能紧挨 / 的，所以首先想到写成：

  \*[^/"]
  1

  （* 一定不能结尾，否则 \* 和 [^*"] 会构成 */，所以考虑这种情况时，后面一定接一个字符是合理的）

  但这么写会阻止连续的星号存在，所以修正为：

  \*+[^/\*"]
  1

  但这还阻止了 * 后面紧跟双引号的情况，所以修正为：

  \*+([^/\*"] | quoted)
  1

综上，闭包的形式为：

(quoted | [^*"] | \*+([^/\*"] | quoted))*
1

最后，由于以上思路认为 * 一定不能结尾，所以 content_without_end 的后面还需要补充任意多的 * 来修正整个字符串结尾是 ******/ 的情况。

(quoted | [^*"] | \*+([^/\*"] | quoted))*\**
1

综上，答案为：

/\*(quoted | [^*"] | \*+([^/\*"] | quoted))*\*+/
1

受 VS Code 支持的正则表达式为：

/\*(?:"[^"]*"|[^\*"]|\*+(?:[^/\*"]|"[^"]*"))*\*+/
1

样例文本：

/* test "/* test */" */  */
1

3.3.5.6

所有由偶数个 a 和奇数个 b 构成的串。

---

思路：容易想到拿走一个 b（因为有奇数个 b，所以一定存在），则剩下的串有偶数个 a 和偶数个 b。但拿走中间的字符无法保证两端串的结构，所以我们拿走开头的字符。枚举开头的字符即可。

---

首先注意到，3.3.2.5 给出了偶数个 a、偶数个 b 的正则表达式：

eaeb -> (aa|bb)*((ab|ba)(aa|bb)*(ab|ba)(aa|bb)*)*
1

它用到了两两分组的思路，可以注意下。两两分组后，每一组只有可能是 aa, ab, ba, bb。但它还用到了整个字符串一定是偶数个字符的性质。

• 以 b 开头时，显然是 b eaeb。

• 以 a 开头时，用类似的思路改变奇偶性，有：

  a(aa|bb)*(ab|ba) eaeb
  1

把这两种情况并起来即可。

受 VS Code 支持的正则表达式为：

(?:a(?:aa|bb)*(?:ab|ba)(?:ab|bb)*(?:(?:ab|ba)(?:aa|bb)*(?:ab|ba)(?:aa|bb)*)*)|(?:b(?:ab|bb)*(?:(?:ab|ba)(?:aa|bb)*(?:ab|ba)(?:aa|bb)*)*)
1