编译原理习题CH3-3

3.3.1 语言的词法形式与字符集

1. C语言

  • 输入字母表： 包括ASCII字符：字母（a-z、A-Z）、数字（0-9）、空格、标点符号（例如：+、-、*、/、;、=、(、)、{、}）等。
  • 数字常量： 十进制（123）、八进制（0123）、十六进制（0x1A）、浮点数（1.23、4.56e7）。
  • 标识符： 以字母或下划线（_）开头，可以包含字母、数字或下划线（例如：myVar、_tmp）。

2. C++语言

  • 输入字母表： 与C语言相似，但还包括C++特有的符号，如::、->、<=>（航天器操作符）等。
  • 数字常量： 同C语言（十进制、八进制、十六进制、浮点数）。
  • 标识符： 同C语言，但C++支持命名空间中的标识符（例如：std::vector）。

3. C#语言

  • 输入字母表： 与C++相似，但还包括C#特有的符号，如=>（Lambda操作符）、::（命名空间解析符）、@（逐字字符串）。
  • 数字常量： 同C/C++（十进制、八进制、十六进制、浮点数）。
  • 标识符： 同C/C++，但支持Unicode字符作为标识符（例如：变量、student123）。

4. Fortran语言

  • 输入字母表： 主要包括字母（A-Z）、数字（0-9）、一些标点符号（例如：+、-、*、/、=、,、.）以及Fortran特有的关键字如DO、END、IF等。
  • 数字常量： 十进制（123.45）、科学计数法（1.23E+4）、整数、复数。
  • 标识符： 必须以字母开头，可以包含字母、数字和下划线（例如：var1、temp_2）。

5. Java语言

  • 输入字母表： 与C/C++相似，但增加了Java特有的关键字（例如：class、extends、super、new）。
  • 数字常量： 十进制、十六进制（0x1F）、浮点数（1.23、3.14e-2）。
  • 标识符： 同C语言，但Java允许标识符使用更广泛的字符集（例如：HelloWorld）。

6. Lisp语言

  • 输入字母表： 包括字母（a-z、A-Z）、数字（0-9）、圆括号()以及Lisp特有的符号，如+、-、*、/。
  • 数字常量： 十进制整数和浮点数。
  • 标识符： 可以包含字母、数字和符号，但必须以字母开头。Lisp对标识符大小写不敏感，因此foo和FOO是相同的。

7. SQL语言

  • 输入字母表： 包括标准的字母数字字符和用于SQL查询的标点符号，如SELECT、FROM、WHERE、=、*、+、-、;、()等。
  • 数字常量： 整数值（例如：100、1.23）、浮点数。
  • 标识符： 通常是字母数字和下划线，有些数据库支持区分大小写的标识符（例如：user_name、UserName）。

3.3.2 正则表达式描述

我们来描述以下正则表达式所表示的语言：

  1. a(a|b)\*a
    • 语言描述： 由a和b组成的字符串，且字符串以a开始和结束。
    • 示例：aa、aba、abba。
  2. ((ε|a)b\*)\*
    • 语言描述： 由a和b组成的字符串。
    • 这个表达式表示任何数量的a后跟任意数量的b（包括没有b）。因此，生成了任何组合的a和b。
    • 示例：a、b、ab、ba、aaa、bb。
  3. (a|b)\*a(a|b)(a|b)
    • 语言描述： 由a和b组成的字符串，且倒数第三个字符是a。
    • 示例：baaa、bba、aab。
  4. a\*ba\*ba\*ba\*
    • 语言描述： 由a和b组成的字符串，且该字符串仅包含三个b。
    • 示例：bb、abbab、aabb。
  5. !!(aa|bb)\*((ab|ba)(aa|bb)\*(ab|ba)(aa|bb)\*)\*
    • 语言描述： 由a和b组成的字符串，且包含偶数个a和b。
    • 示例：ab、baab、ababab。

3.3.3 前缀、后缀、子串计数

  1. 前缀（字符串长度为n的前缀）：前缀是字符串的任意前缀。
    • 总数：n + 1（包括空字符串作为前缀）。
  2. 后缀（字符串长度为n的后缀）：后缀是字符串的任意后缀。
    • 总数：n + 1（包括空字符串作为后缀）。
  3. 真前缀（字符串长度为n的真前缀）：真前缀不包括字符串本身。
    • 总数：n（不包括字符串本身作为前缀）。
  4. 子串（字符串长度为n的子串）：子串是字符串中的任意连续部分。
    • 总数：C(n+1, 2) + 1，其中C(n, 2)是选择两个索引的组合数，+1是为了计算空字符串。
  5. 子序列（字符串长度为n的子序列）：子序列是通过删除某些（或没有）字符而不改变字符顺序形成的任意序列。
    • 总数：Σ(i=0, n) C(n, i)，其中C(n, i)表示二项式系数。

3.3.4 正则表达式的大小写不敏感性

对于一个大小写不敏感的语言，例如SQL，关键词“select”可以用不同的大小写书写。为了表达这一点，我们可以使用正则表达式，使其匹配不同大小写的组合。

例如，“select”在SQL中可以是：

  • select
  • SELECT
  • Select
  • sElEcT

正则表达式如下：

select -> [Ss][Ee][Ll][Ee][Cc][Tt]

这里的[Ss]表示匹配S或s，[Ee]表示匹配E或e，以此类推。通过这种方式，我们可以实现大小写不敏感的匹配。

3.3.5 正则定义问题

  1. 所有包含五个元音字母按顺序排列的小写字母字符串：
    • 定义：want -> other* a (other|a)* e (other|e)* i (other|i)* o (other|o)* u (other|u)*
    • 解释：want表示一个字符串，包含从a到u的五个元音字母，并且字母之间可以有其他小写字母。other表示除了元音字母以外的任意小写字母。
  2. 所有字母按字典顺序递增排列的小写字母字符串：
    • 定义：a* b* ... z*
    • 解释：每个字母的出现顺序是从a到z的升序排列，因此字符串中的字母按字典顺序排列。
  3. 注释（由/\*和\*/包围的字符串），不允许有\*/，除非它在双引号内：
    • 定义：\/\*([^*"]*|".*"|\*+[^/])*\*\/
    • 解释：这个正则表达式匹配以/*开头、*/结尾的注释内容。它通过排除*/中的特殊情况，避免了误匹配。
  4. 所有不包含重复数字的数字字符串（提示：可以先从少量数字如{0, 1, 2}开始）：
    • 定义：want -> 0|A?0?1(A0?1|01)*A?0?|A0?
    • 解释：这定义了一个不包含重复数字的数字字符串。A表示没有重复数字的子集，确保每个数字在字符串中出现一次。
  5. 包含三种棋子移动的表达式（例如：p-k4或kbp*qn）：
    • 定义：want -> (FE*G|(aa)*b)(E|FE*G)
    • 解释：这定义了符合棋步规则的字符串，其中F和G分别代表棋子的不同移动方式。
  6. 所有不包含子串abb的a和b组成的字符串：
    • 定义：b*(a+b?)*
    • 解释：这个正则表达式表示一个没有abb子串的字符串，允许字符串中只有a和b，并且不包含abb。
  7. 所有不包含子序列abb的a和b组成的字符串：
    • 定义：b* | b*a+ | b*a+ba*
    • 解释：这个正则表达式定义了一个没有abb子序列的字符串，包含a和b的任意组合。

3.3.6 编写字符类

  1. 前十个字母（直到“j”），无论大小写：
    • 定义：[A-Ja-j]
    • 解释：这个字符类匹配从A到J的字母以及从a到j的字母。[A-J]匹配大写字母A到J，[a-j]匹配小写字母a到j。
  2. 所有小写辅音字母：
    • 定义：[bcdfghjklmnpqrstvwxzy]
    • 解释：这个字符类匹配所有的小写辅音字母，排除了元音字母a、e、i、o、u。
  3. 十六进制数的数字（选择大写或小写表示10到15的数字）：
    • 定义：[0-9a-f]
    • 解释：这个字符类匹配数字0到9以及小写字母a到f，表示十六进制数的数字（选择小写字母表示a到f，大写字母表示也是一样的）。
  4. 合法英语句子的结尾字符（例如：逗号、感叹号等）：
    • 定义：[.?!]
    • 解释：这个字符类匹配句子末尾的标点符号，如句号（.）、问号（?）、感叹号（!）。

3.3.7 操作符字符的转义

某些字符在正则表达式中具有特殊意义，例如 \、"、.、^、$、[、]、*、+、?、{、}、|、/ 等。如果要匹配这些字符本身而非它们的特殊功能，需要对其进行转义。

例如，正则表达式中的 * 通常是一个量词，表示重复前面的模式，而如果要匹配字符 * 本身，则需要将其转义。

对于问题要求的字符串 \，我们可以通过以下方式编写正则表达式来匹配：

  • 定义：\"\\
  • 解释：
    • \" 用来匹配反斜杠字符 \。
    • \\ 用来匹配反斜杠字符 \，因为反斜杠本身是转义字符，所以需要两个反斜杠来表示一个字面上的反斜杠。

这两个转义字符一起表示了匹配一个反斜杠 \ 字符。

3.3.9 正则表达式中的重复操作符

问题：r{m,n}表示匹配从m到n次的模式r。例如，a{1,5}匹配1到5个字母a。证明，对于包含此类重复操作符的每个正则表达式，都有一个等价的正则表达式，没有重复操作符。

解答：

对于r{m,n}，可以将其展开为多个具体的重复模式：

  • r{m,n}等价于：
    • r重复m次：r(r...r)（共m次）
    • r重复m+1次：r(r...r)（共m+1次）
    • … 一直到r重复n次：r(r...r)（共n次）

因此，r{m,n}可以展开为：

1
r.(m).r | r.(m+1).r | ... | r.(n).r

也就是说，我们可以通过显式列出每个重复次数的形式，来构造一个没有重复操作符的等价表达式。

例如，a{1, 5}可以展开为：

1
a | aa | aaa | aaaa | aaaaa

这样，r{m, n}可以通过将其转换为多个简单的模式（没有重复操作符）来表示。

3.3.10 ^和$操作符的意义

问题：^匹配行的左端，匹配不包含小写元音字母的完整行。

如何判断^的含义？
是否总是可以将使用^和$操作符的正则表达式替换为一个等价的、不使用这两个操作符的表达式？

解答：

  1. 判断^的含义：
    • 如果^出现在方括号[]中的第一个位置，它表示补充字符类，即匹配不包含给定字符集合的字符。
      • 例如：^[^aeiou]*$表示匹配不包含小写元音的完整行。
    • 如果^没有出现在方括号中，而是位于正则表达式的开始位置，则它表示行的左端，即匹配行的起始部分。
    • 同理，$用于匹配行的右端，即行的结束部分。
  2. 是否可以去除^和$：
    • 不能总是替换正则表达式中的^和用于匹配行的开始和结束，无法通过其他方式完全替代。
    • 例如，^abc$表示匹配整行恰好是abc，如果去掉^和$，我们就无法保证字符串的开始和结束位置。
    • 然而，在某些情况下，可以通过使用其他手段（例如，匹配开始和结束的特定字符）来模拟类似的功能，但这依赖于具体情况。

总结：

  • ^如果出现在方括号[]中的第一个位置，它表示补充字符类，否则它表示匹配行的左端。
  • ^和$并不能总是被等效的表达式所替代，特别是当涉及行的开始和结束时，去掉这两个操作符可能导致不匹配的结果。