• 1 Problem
• 2 Showcase & Discuss
• 3 Analysis
  • 3.1 Acceptance Tests of search
  • 3.2 Acceptance Tests of match
• 4 Design
  • 4.1 List of Obvious Concepts
  • 4.2 How Does Regular Expression Engine Work?
    • 4.2.1 search
    • 4.2.2 match
  • 4.3 Core Concepts
• 5 Implementation

1 Problem

正则表达式可以认为是一种领域特定语言(DSL)。正则表达式语言可以用字符串表示。例如："a*b*c*"，描述了一种语言，该语言包含了这样的字符串：任意数目的a，后面跟着任意数目的b，后面跟着任意数目的c。所以，这个语言包含："a"、"ab"、"abc"、"b"、"" ...。在这里，"a*b*c*"就是语法，而描述的字符串集合就是语言。对于正则表达式来说，语法就是对一种语言的描述，语言就是符合这个语法的字符串集合。

使用字符串来表示正则表达式的语法，虽说方便，但是却不易操作。语法表达式会变得越来越长，需要一种更易组合的方式来描述。可以定义一套API来描述语法。

需求一 不使用编程语言自身提供的正则表达式库，自己实现一套基于如下语法定义的正则表达式库。

语法	API	语言示例
字串字面值	lit(s)	lit("abc")定义的语言只包含："abc"
seq	seq(p1, p2)	seq(lit("a"), lit("b"))定义的语言只包含："ab"
. (any character)	dot()	dot()定义的语言包含任意一个字符
$ (end of line)	eol()	eol只能在字符串末尾，eol()定义的语言只包含：""
| (二选一)	alt(p1, p2)	alt(lit("a"), lit("b"))定义的语言包含："a"、"b"
?	opt(p)	opt(lit("a"))定义的语言包含：""、"a"
*	star(p)	star(lit("a"))定义的语言包含：""、"a"、"aa"、...
[]	oneof(s)	oneof只接受字符串，oneof("abc")定义的语言包含："a"、"b"、"c"
+	plus(p)	plus(lit("a"))定义的语言包含："a"、"aa"、...

需求二 基于上述API，实现search接口。search接受两个参数，一个是pattern，一个是待搜索文本，返回待搜索文本中最早匹配pattern的结果字符串。如果在同一个位置有多种匹配，返回最长的那个匹配(即"贪婪"匹配)。如果没有找到合适的匹配，返回空。

示例(仅为示意，非接口形态)：

r = search(lit("def"), "abcdef")
r = "def"

需求三 基于上述API，实现match接口。match接受两个参数，一个是pattern，一个是待匹配文本。match和search的区别在于：match只能从文本的起始开始匹配，且为贪婪匹配。比如字符串"abcdef"，如果pattern是lit("def")，search返回"def"，而match则返回空。

示例(仅为示意，非接口形态)：

r = match(lit("abc"), "abcdef")
r = "abc"

2 Showcase & Discuss

请学员展示自己之前的设计思路和实现方式，大家可以互相点评、讨论。以学员为主，讲师为辅。

3 Analysis

分析：定义清楚问题是什么。

可以通过思考编写验收测试(Acceptance Testing)用例，来定义清楚问题是什么。

3.1 Acceptance Tests of search

"a" == search(lit("a"), "abc")
"a" == search(lit("a"), "bac")
null == search(lit("a"), "bcd")

"def" == search(lit("def"), "def fun")
"def" == search(lit("def"), "abc def")

def_eol = seq(lit("def"), eol())
"def" == search(def_eol, "abcdef")
null == search(def_eol, "abcdefg")

"" == search(star(lit("a")), "")

"ab" == search(plus(seq(lit("a"), lit("b"))), "abc")
"ab" == search(plus(seq(lit("a"), lit("b"))), "dabc")

dot_star = star(dot())
ab_dot_star_aca_dot_star_a_eol = seq(lit("ab"), seq(dot_star, seq(lit("aca"), seq(dot_star, seq(lit("a"), eol())))))
"abracadabra" == search(ab_dot_star_aca_dot_star_a_eol, "abracadabra")
"abacaa" == search(ab_dot_star_aca_dot_star_a_eol, "abacaa")
"about-acacia-flora" == search(ab_dot_star_aca_dot_star_a_eol, "about-acacia-flora")

3.2 Acceptance Tests of match

"a" == match(lit("a"), "abc")
null == match(lit("a"), "bac")
null == match(lit("a"), "bcd")

"def" == match(lit("def"), "def fun")
null == match(lit("def"), "abc def")

def_eol = seq(lit("def"), eol())
"def" == match(def_eol, "def")
null == match(def_eol, "defg")

"" == match(star(lit("a")), "")

"ab" == match(plus(seq(lit("a"), lit("b"))), "abc")
null == match(plus(seq(lit("a"), lit("b"))), "dabc")

a_star_b_star_c_star = seq(star(lit("a")), seq(star(lit("b")), star(lit("c"))))
"aaabbbcccccccc" == match(a_star_b_star_c_star, "aaabbbccccccccdef")
"" == match(a_star_b_star_c_star, "junk")

a_star_b_star_c_star_eol = seq(a_star_b_star_c_star, eol())
"abc" == match(a_star_b_star_c_star_eol, "abc")
"aaaabbccc" == match(a_star_b_star_c_star_eol, "aaaabbccc")
"aaaabcccc" == match(a_star_b_star_c_star_eol, "aaaabcccc")
null == match(a_star_b_star_c_star_eol, "cab")
null == match(a_star_b_star_c_star_eol, "aaabbcccd")
null == match(a_star_b_star_c_star_eol, "aaaa-b-cccc")

dot_star = star(dot())
c_dot_star_b = seq(lit("c"), seq(dot_star, lit("b")))
"cab" == match(c_dot_star_b, "cab")
"cob" == match(c_dot_star_b, "cob")
"carob" == match(c_dot_star_b, "carob")
"cb" == match(c_dot_star_b, "cb")
"carb" == match(c_dot_star_b, "carbuncle")

c_dot_b = seq(lit("c"), seq(dot(), lit("b")))
null == match(c_dot_b, "crab")
null == match(c_dot_b, "cb")
null == match(c_dot_b, "across")
null == match(c_dot_b, "scab")

4 Design

设计：问题分析清楚以后，提出解决问题的逻辑框架。

4.1 List of Obvious Concepts

概念清单：

• pattern：模式
• text：待测文本
• result：结果

这些概念显而易见然而并没有什么用，对设计没有任何实质的意义和帮助。

4.2 How Does Regular Expression Engine Work?

在构造与问题领域根本需求相匹配的计算模型时，最重要的一点就是要想清楚系统是如何计算的，而不是直接从问题描述中找出肤浅的概念和算法。所以，我们有必要仔细分析一下正则表达式引擎应该如何工作。

4.2.1 search

先思考一下正则表达式引擎在search场景下是如何工作的。

举个例子：pattern为"cde"，text为"abcde"。

第1步：从text的起始字符"a"开始，用pattern "cde"测试text的剩余部分"abcde"是否匹配，不匹配。 第2步：到text的字符"b"，用pattern "cde"测试text的剩余部分"bcde"是否匹配，不匹配。 第3步：到text的字符"c"，用pattern "cde"测试text的剩余部分"cde"是否匹配，匹配，最终结果为"cde"。

用一句话来说就是，在search场景下，正则表达式引擎从text的起始字符开始，逐个字符，用pattern测试text的剩余部分是否匹配。

注意，这句话中的“用pattern测试text的剩余部分是否匹配”其实就是match。

4.2.2 match

接下来，思考一下正则表达式引擎在match场景下是如何工作的。根据需求，重点思考贪婪匹配。

举个例子：pattern为"a*ab"，用API描述为：seq(star(lit("a")), lit("ab"))，text为"aaab"。

如果star(lit("a"))是贪婪匹配，匹配结果是"aaa"，text的剩余部分为"b"，lit("ab")无法匹配，整个匹配就失败了。

但事实上，seq(star(lit("a")), lit("ab"))是完全可以匹配"aaab"的。如果star(lit("a"))的匹配结果是"aa"，text的剩余部分为"ab"，lit("ab")就可以匹配"ab"了。

这里的关键在于：star(lit("a"))具有多种匹配可能性，它匹配"aaab"的结果是一个集合{"", "a", "aa", "aaa"}，而不是一个单一的结果。接下来要用lit("ab")遍历匹配这个集合，直到遍历到"aa"时，lit("ab")可以匹配剩余文本"ab"，才匹配成功，得到匹配结果"aaab"。

这样一来，我们需要记录下star(lit("a"))的部分匹配结果(partial result)，即集合{"", "a", "aa", "aaa"}，针对集合中的每个文本，用text去除该文本得到剩余文本，从而得到剩余文本集合{"aaab", "aab", "ab", "b"}。再用lit("ab")遍历匹配这个剩余文本集合，得到它的部分匹配结果，也是一个集合，只不过集合中只有一个元素，即{"ab"}。lit("ab")的部分匹配结果"ab"对应star(lit("a"))的部分匹配结果是"aa"。最后还需要将这两个部分匹配结果拼接起来得到最终的匹配结果"aaab"。

有点棘手！不妨换个方向思考这个问题。

不用可能的匹配结果集合、而直接用剩余文本集合来表示部分匹配结果。匹配到最后得得到最终的剩余文本集合以后，因为需要贪婪匹配，所以要在最终的剩余文本集合中找到长度最短的剩余文本，再用text去除这个剩余文本，从而得到最长的匹配结果，即最终的匹配结果。

还是上面的例子，star(lit("a"))匹配"aaab"的剩余文本集合为{"aaab", "aab", "ab", "b"}，再用lit("ab")遍历匹配这个剩余文本集合，注意针对剩余文本集合中的每个剩余文本，lit("ab")的匹配结果还是一个集合，所以得到的是一个嵌套的剩余文本集合{{}, {}, {""}, {}}，拉平(flatten)后，得到lit("ab")自己的剩余文本集合为{""}，这个集合只有一个元素""，长度最短的也是它，再用"aaab"去除这个元素""，得到最终的匹配结果"aaab"。

再举个稍微复杂一点的例子，pattern为"a*b+"，用API描述为：seq(star(lit("a")), plus(lit("b")))，text为"aaabbc"。

star(lit("a"))匹配"aaabbc"的剩余文本集合为{"aaabbc", "aabbc", "abbc", "bbc"}，再用plus(lit("b"))遍历匹配这个剩余文本集合。同理，针对剩余文本集合中的每个剩余文本，plus(lit("b"))匹配的结果还是一个集合{{}, {}, {}, {"bc", "c"}}，拉平后，得到plus(lit("b"))的剩余文本集合为{"bc", "c"}，这个集合中长度最短的元素是"c"，用"aaabbc"去除"c"，得到最长的匹配结果也是最终的匹配结果"aaabb"。

4.3 Core Concepts

思考到这里，我们发现，我们需要一个工具，它接受pattern和text，返回匹配后的剩余文本集合(remaining texts)，剩余文本集合中的每个元素都是text去除该pattern可能匹配的字符串后剩余的文本。做一下抽象，给这个工具起个名字：partial_match。它才是计算的本质，也是本计算模型的核心概念。

partial_match(star(lit("a")), "aaab") => {"aaab", "aab", "ab", "b"}

5 Implementation

实现：选择实现技术把逻辑框架的软件模型实现出来。