Permalink
Switch branches/tags
Nothing to show
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
269 lines (174 sloc) 7.89 KB

3.3 节的练习

3.3.1

对于下列各个语言

  • C
  • C++
  • C#
  • Fortran
  • Java
  • Lisp
  • SQL

查询语言使用手册以确定:

  1. 形成各语言的输入字母表的字符集分别是什么(不包括哪些只能出现在字符串或注释中的字符)?
  2. 各语言的数字常量的语法形式是什么?
  3. 各语言的标识符的词法形式是什么?

3.3.2

试描述下列正则表达式定义的语言:

  1. a(a|b)*a
  2. ((ε|a)b*)*
  3. (a|b)*a(a|b)(a|b)
  4. a*ba*ba*ba*
  5. !! (aa|bb)*((ab|ba)(aa|bb)*(ab|ba)(aa|bb)*)*

解答

  1. 由 a 开头并结尾的由 a 和 b 构成的字符串。
  2. 由 a 和 b 构成的字符串。
  3. 倒数第 3 位为 a 的由 a 和 b 构成的字符串。
  4. 仅含 3 个 b 的由 a 和 b 构成的字符串。
  5. 含有偶数个 a 和偶数个 b 的由 a 和 b 构成的字符串。

3.3.3

试说明在一个长度为 n 的字符串内,有多少

  1. 前缀
  2. 后缀
  3. 真前缀
  4. ! 子串
  5. ! 子序列

解答

  1. n + 1
  2. n + 1
  3. n - 1
  4. C(n+1,2)
  5. Σ(i=0,n) C(n, i)

3.3.4

很多语言都是大小写敏感的,因此这些语言的关键字只能有一种写法,描述这些关键字词素的正则表达式就很简单。但是,像 SQL 这样呃语言是大小写不敏感的。请描述出如何用正则表达式来表达大小写不敏感的语言中的关键字。给出描述 SQL 语言中的关键字 "select" 的表达式,以说明你的思想。

解答

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

3.3.5

! 试写出下列语言的正则定义

  1. 包含5个元音的所有小写字母串,这些串中的元音按顺序出现
  2. 所有由按词典递增序列的小写字母组成的串
  3. 注释,由 /* 和 */ 之间的串,且串中没有不在双引号中的 */
  4. !! 所有不重复的数位组成的串 (即允许 101 这样的串,但不允许 110 这样的串)
  5. !! 所有由偶数个 a 和奇数个 b 构成的串
  6. 以非正式的方法表示的国际象棋的步法的集合,如 p - k4 或者 kbp x qn
  7. !! 所有由 a 和 b 组成且不含子串 abb 的串
  8. 所有由 a 和 b 组成且不含子序列 abb 的串

解答

1、

want -> other* a (other|a)* e (other|e)* i (other|i)* o (other|o)* u (other|u)*
other -> [bcdfghjklmnpqrstvwxyz]

2、

a* b* ... z*

3、

\/\*([^*"]*|".*"|\*+[^/])*\*\/

/* 和 */ 间出现内容,是三种不同情况的闭包(随意组合出的任意长度的串):

  1. [^*"]*:除了 * 和 " 之外所有的符号任意长度的串。
  2. ".*":两个引号括起来的串,其内允许任何符号。
  3. \*+[^/]:出现 * 的情况,其后跟一个不是 / 的符号。

该表达式也匹配 /**/ 的情况。

需要注意的是,该表达式暗含以下约束:

  • 不能包含不成对的引号
  • 没有考虑单引号的情况(某些语言中单引号也表字符串)

4、

want -> 0|A?0?1(A0?1|01)*A?0?|A0?
A -> 0?2(02)*

解答过程:

step1. 转换图

转换图

step2. GNFA

GNFA

step3. 去掉节点 0,并简化

去掉节点 0,并简化

step4. 去掉节点 2,并简化

去掉节点 2,并简化

step5. 去掉节点 1,并简化

去掉节点 1,并简化

5、

want -> (FE*G|(aa)*b)(E|FE*G)
E -> b(aa)*b
F -> a(aa)*b
G -> b(aa)*ab|a
F -> ba(aa)*b

解答过程:

step1. 转换图

转换图

step2. GNFA

GNFA

step3. 去掉节点 A,并简化

去掉节点 A,并简化

step4. 去掉节点 D,并简化

去掉节点 D,并简化

step5. 去掉节点 C,并简化

去掉节点 C,并简化

8、

b*(a+b?)*

9、

b* | b*a+ | b*a+ba*

3.3.6

为下列字符集合写出对应的字符类

  1. 英文字母的前10个数字(a~j),包括大写和小写
  2. 所有小写的辅音字母的集合
  3. 十六进制中的数位
  4. 可以出现在一个合法的英文句子后面的字符集

解答

  1. [A-Ja-j]
  2. [bcdfghjklmnpqrstvwxzy]
  3. [0-9a-f]
  4. [.?!]

3.3.7

请注意这些正则表达式中的些列字符都具有特殊的含义:

\ " . ^ $ [ ] * + ? { } | /

如果想要使得这些特殊字符在一个串中表示他们资深,就必须取消他们的特殊含义,我们可以将他们放在一个长度大于等于1且加上双引号的串中就可以取消特殊含义。如,正则表达式 "**" 和字符串 ** 匹配。我们也可以在一个运算符前面加一个反斜线,得到这个字符的字面含义。那么正则表达式 ** 也和串 ** 匹配。请写出一个和字符串 "\ 匹配的正则表达式。

解答

\"\\

3.3.8

在 Lex 中,补集字符类代表该字符类中列出的字符之外的所有字符。我们将 ^ 放在开头来表示一个补集字符类。除非 ^ 在该字符类中列出,否则这个字符不在被取补的字符类中。因此 [^A-Za-z] 匹配所有不是大小写字母的字符,[^^] 匹配除 ^ 之外的任何字符。试证明,对于每个带有补集字符类的正则表达式,都存在一个等价的不含补集字符类的正则表达式。

3.3.9 !

试证明:对于每一种包含 r{m, n} 这种形式的表达式,都存在一个等价的不包含重复运算符的正则表达式

解答

r{m,n} 等价于 r.(m个).r | r.(m+1个).r | ... | r.(n个).r

3.3.10 !

^ 可表示一行的开始,也可表示取补。

  1. 怎样判断它到底表示哪个意思?
  2. 是否总是能将一个包括 ^ 和 $ 的正则表达式替换为一个等价的不包含这些运算符的正则表达式?

解答

  1. 如果 ^ 位于中括号中,且为第一个字符,即取补,否则就代表行首。

3.3.11 !

UNIX 的 shell 命令 sh 在文件名表达式中使用下表的运算符来描述文件名的集合。试问如何使用只包含并、连接和闭包运算符的正则表达式来表示 sh 文件名表达式?

表达式 匹配 例子
's' 串s的字面值 '\'
\c 字符c的字面值 \'
* 任何串 *.o
? 任何字符 sort1.?
[s] s中的任何字符 sort1.[cso]

3.3.12 !

SQL 语言支持一种不成熟的模式描述方式,其中有两个具有特殊含义的字符;下划线(_) 表示任意字符, 百分号(%) 表示包含0个或多个字符的串。此外,程序员还可以将任意一个字符定义为转义字符。假设我们已经知道哪个是转义字符,说明如何将任意 SQL 模式表示为一个正则表达式。