201306 Language Interpreter and Function Composition 学习笔记 - xiaoxianfaye/Learning GitHub Wiki

201306 Language, Interpreter and Function Composition 学习笔记

Language, Interpreter and Function Composition

The Way to be a Master Programmer

语言、解释器和函数组合。 在编程领域，如果想成为一个好的程序员是你的追求，这个课程就是一个努力的方向。

1 Theory

1.1 The way you think about programming

对于编程这个事情，你是怎么看的？你认为编程是个什么样的事情？

学一门编程语言，对于这门编程语言也不知道好坏，可能是Basic、C、C++、Java、GO等。学会了一门语言，然后用它解决问题。这个问题可能非常复杂，但是我把它做出来了。有没有想过，你是怎么编程序的？在编程这个过程里，你是如何跟编程语言互动的？你如何理解语言？你把语言当成了什么？你可能做了一件很复杂的事情，先不说在更高的解决问题的层面，先说在编程这个层面，在跟编程语言互动这个层面上，你是怎么考虑编程这件事情？在使用编程语言时，跟编程语言互动时有什么感觉？这是编程里非常重要的一环。我们的能力，一方面是解决问题的能力、建模的能力；另一方面是更基础、更细的能力，在使用编程语言的过程里面，你的所思所想。学员举例，语言用起来不是很顺手。

语言是一组固定的规则。这些规则是语言的设计者创造的。设计者离你很远，你也不清楚TA是谁，你就用。用的时候你会想，这个语言的规则是否适合解决我的问题呢？但可能一闪而过。语言就是这样，语言设计得肯定好的，语言设计得很牛的，TA这样设计肯定有道理，就这样用吧。当然，最终你肯定把程序编出来了，程序本身可能你还觉得很漂亮，里面有这么多组件，每个组件都很漂亮，组件就像一个完美的机械表一样，它的各个部件之间契合得非常优美，但是它是按照固定的规则契合的。机械表能不能变成一个汽车？不可能。要思考这个问题。虽然说组件还是非常优美地组合在一起，但是想想就会发现，这些组合是固定的，它必须按照固定的方式去组合，如果换一种场景或方式就组合不起来了。

1.2 Why should we think about problems from language perspective?

从语言层面思考问题。

1. The quality of the GLUE that most directly determines the power of the system.

无论系统中的每个组件、每个操作多么复杂、功能多么强劲，能够决定一个系统是否威力强大的核心并不是每一个部分，而在于如何把组件组合起来，即粘合剂的粘合方式非常重要。

粘合剂是什么意思？稍微再具体化一下。有一组操作，能不能给每个操作命名，能不能将一个操作的输出作为另一个操作的输入，能不能给一串操作起个名字，能不能对一串操作进行参数化，这个名字是局部的还是全局的，等等这样一些问题。这些问题和操作本身、操作如何实现没关系，考虑的是如何粘合、粘合、粘合。这是非常重要的问题。

可以回想一下，我们在做程序开发时，考虑得更多的是功能分解。用面向对象设计考虑更多的是职责分派、协作起来完成一件事情，如何粘合是没有细致考虑的，并没有考虑上面那些问题。

这才是抽象的本质(更高层面)。系统的部件是一个维度，另一个维度是这些部件的粘合方式。系统的好坏(power)、是否能做很多事情，不在于每个部件能做多少事情，而在于部件的粘合方式。

举个例子，UNIX的管道 vs Windows的工具。UNIX里每个小工具都可以干一件事情，可以任意组合。Windows里的工具很强大，但就是一些固定的集合。

再举个例子，布局管理器的例子。很多固定的布局管理器，把很多部件很精美地合在一起，但是不能变。在布局管理器例子里，每一个部件很简单，但粘合的方式很厉害，可以组合出很多不同的布局。

我们要学如何把部件粘合在一起，只有语言能提供足够灵活的粘合方式。

2. Choosing the right kind of language for the right purpose.

系统很复杂，涉及到很多不同的、不相关的领域，如何解决这个问题呢？设计一个统一框架、统一平台？也能做出来，硬凑在一起完全可能的，但凑完以后的复杂性是无法承受的，逐渐失控。

其实每个领域都有自己的特点，如何设计系统呢？针对系统的每个领域设计一套小语言。例如，用Java编程，访问数据库肯定都用SQL，不会用XML。不那么明显，但肯定是用合适的语言做合适的事情。想想为何这样做？不要从实现层面思考，不就是用SQL访问数据库、用XML描述数据和规则嘛。要上升到更高的层面，明显化而不是隐藏，在不同领域选择合适的工具。往往用了这个思想但是没有意识到。这样做了以后就会发现，再复杂的系统，每一面都是语言来做的，语言之间的融合和组合是非常容易的，就可以对抗复杂性。

3. Thinking explicitly about languages is the best tool for dealing with complexity.

语言跟用语言编的程序有什么区别？如果能够在编程的过程中显式地思考语言会达到一个什么样的结果？

元编程(Meta-programming)，可以在程序里显式地操纵语言本身的结构。Ruby和Python虽然支持，但比较弱。

程序语言和程序语言编的程序有什么区别？其实没有区别。这样的话，就能在每个层次上对语言本身进行扩充、定制、糅合，最终能够更好地应对复杂性。比较困难，但如果掌握这种思维的话，威力是非常大的。

以上是“从语言层面思考问题”的三个要点。

1.3 How should we think about problems from language perspective?

如果从语言层面思考问题，该如何做呢？

1.3.1 Interpreter

The interpreter for a computer language is just another program.

一个语言本身是有语法的，但还有语义，解释器决定了语义。“1+1=3”肯定是符合语法的，语义对不对呢？可能对、也可能不对，取决于解释器。就像看一幅画《少女与老妇》，这样看是这样的，那样看是那样的，脑子里解释得不一样。解释器直接决定了程序的语义、语言的语义。可能会觉得解释器很难，要学编译原理等，确实解释器的水很深，但是在实际工作中，有很多东西不需要学习，是比较简单的，掌握住思想以后，可以做很多东西。

Interpreter不过是另外一个程序。

The view of programming makes difference.

把程序和程序语言分开看，跟把程序和程序语言合在一起看，两者之间的差别。

1.3.2 The interpreter recipe

The Interpreter Recipe

  1. Look at a piece of data.
  2. Decide what kind of data it represents.
  3. Extract the components of the datum and do the right thing with them.

怎么写Interpreter呢？实现一个Interpreter的步骤是很清楚的。 第1步：给一个数据，这里的数据是泛指，并不是1、2、3或者字符串，而是一种表示。 第2步：看表示是什么意思。举个例子，1+2，第1步来个1，这是个数据，这个数据表示1；第2步来个+，这个数据表示加号；第3步来个2。 第3步：把这个东西提炼出来，该干啥就干啥。举个例子，1+2=，先来个1，知道是数字1，把1提炼出来放在一边，又来个+，知道是加号，把+提炼出来放在一边，又来个3，知道是数字3，把3提炼出来放在一边，然后来个=，知道是等号，把前面两个数字加一下返回结果即可。

解释器就是这样工作的，原理很简单。在代码层次上就是switch-case。switch-case不总是烂代码，问题在于它所处的层次。如果在低层次做支撑，可以把上面做得很漂亮；还是说，各个层次都有switch-case。switch-case是一个非常强大的工具，可以做很多事情，问题在于要把它用在正确的地方。

写个解释器，就3步。

1.3.3 The C programming language

举个C语言的例子。

C语言中给你印象最深的库函数是什么？为什么？ printf, i++, open, ...

int printf(const char* format, ...);

这是什么？“const char* format”就是个语言。其他操作，比如i++、open等，都是解决一个特定的问题。但printf解决一个领域的问题。format是什么？或者换一种问法，如果你来实现一个输出的API，你会如何做？printString、printInt、printFloat、printLong ...，无穷无尽，需求天天变。但其实需求没有变，只是我们在看待问题的时候层次不对。如果站在另外一个层次或另外一个角度看的话，就可以得到一个更加优美的方法，而且这个方法是非常纯净、简单、一致的。

printf如何实现？ 用switch-case实现了format语言解释器。

1.4 Essence of Abstraction

抽象的本质(Faye：老师没多讲)。

2 Regular Expression

正则表达式。在做字符串处理时，有很多各种各样的场景。看一个pattern是否在一个string里出现，如果出现，能不能把它提炼出来。

你如何来做这件事情？如何提供API给别人用？别人提供的API，一个pattern描述和一个字符串，这是一个高层API。高层接口已给定，如何实现？也可以思考一下，别人为何提供这样的接口？如果不这样定义的话，会是一个多么可怕的场景，可能编一辈子程序也编不完这个需求。

重点是下面(相对于高层API)要做一个引擎，这个引擎的API是什么？基于这个引擎是否很容易实现上面的东西。

考虑3点：原子、组合、抽象。

2.1 Which are primitives and which are combinations?

abc
[abc]
A*
A+
A?
A|B

先解释一下上面几种正则表达式的术语定义：

  • abc：字面的(literal)，完全一模一样匹配的。
  • [abc]：选择1个，a, b or c。
  • A*：0个或多个，zero or more times。
  • A+：1个或多个，one or more times。
  • A?：0个或1个(optional)，once or not at all。
  • A|B：两个中只要1个行就可以了(alternative)，Either A or B。

哪些是原子？哪些是组合？

了解了术语定义以后，API就有了，起个名字。

  • abc：lit
  • [abc]：oneof
  • A*：star或zeroOrMany
  • A+：plus或oneOrMany
  • A?：opt
  • A|B：alt

选好原子，其他的都能从它们推演出来的就是组合。思路就是这样的，问题在于很细节的考虑。

这个问题暂时先放一下，后面就会有答案了。

Two Perspectives 别人设计的语言，我们拿来用就行了。 我设计的语言，给别人用。

Language Designer 我们平时在做设计时有没有这样考虑过问题？这样考虑问题跟原来考虑问题有什么区别？做模块设计做接口，你是如何设计接口的，有没有这样考虑过问题？

我们平时在做设计时是不是这样考虑问题的？ 并不是要做语言的设计者，而是稍微变化一下观点，一点点就够了，就可以做出非常好的设计。就是一个角度的变化、思考问题的层次，多练习。没有什么比语言更好用。不要考虑重用的问题，用任何一个框架解决重用的问题，基本上都是失败的，但用语言就不一样，不考虑重用，但结果非常好。没有什么比语言更好重用的。

2.2 Elements of Language

Elements of Language:

  1. primitives
  2. means of combination
  3. means of abstraction

思考问题的3个层次：哪些是原子的，怎么组合，组合后同样形成一个原子，就是抽象。

本来有3个原子，3个原子组合在一起不知道是什么，这就麻烦了，系统不完备了，东西越来越多，根本无法控制。如果3个原子，任意组合出来跟3个原子没有区别，系统就简单。这个简单并不是说完成的功能少，而是可以完成更多————少即是多，不仅能够完成更多的功能，而且复杂性完全可以掌控。

2.3 APIs

lit, seq, star, alt, oneof, plus, dot, ...

  • lit：就是字面的意思。字面显示“abc”，a是一个原子，b是一个原子，abc跟a就是一个长度的关系。在这个过程中，zero是个特殊的，是否需要有zero。lit表示字面这个字符串要进行匹配。
  • seq：把正则表达式的模式连接起来，表明先后顺序，它是隐含在star、plus中间的。
  • star：0个或多个。
  • alt：A或B。
  • oneof：从字面字符串中取任意1个字符，alt是oneof的加强版(Faye：没想明白为什么，总感觉老师是不是说反了，oneof是alt的加强版，alt处理2个pattern，oneof处理pattern列表)。
  • plus：1个或多个。
  • dot：任意1个字符。

这里只给出了一些名字和含义，并没有给出它们是怎么用的。

举一个lit的例子，考虑如何用lit接口，接口的规格说明是什么，别人怎么用这个接口。

lit接口提供给语言的使用者，TA应该怎么用？

学员1：

'abchhh'.lit('abc') => 'hhh'
'defhhh'.lit('abc') => None

学员2：

lit('abc', 'abchhh') => True | False
star('a*', 'abc') => True, a, bc

从API使用角度，lit和star不完全一致。

学员3：

lit('abc', 'abchhh', pos) => True | False, remain

学员4：

lit('abc', lit('hh', string)) => True | False, remain

这里有一个思考问题的方式，一件一件想，然后再通盘去看。

这里的思考方法就是前面讲过的“The Interpreter Recipe”，它是有步骤的：

  1. Look at a piece of data.
  2. Decide what kind of data it represents.
  3. Extract the components of the datum and do the right thing with them.

看一看这个数据，这个数据是语言里面的一种表示，首先要考虑这个表示是什么，如何去表示这种东西。然后才是这个数据表示的什么意思。再然后是用这个意思干什么事情。这个层次是很清晰的，而我们现在把它搅在一起了，根本不知道在干什么，直接实现出来了。

仔细思考一个语言的话，要把层次分清楚。首先是表示(Notation)，在实现内部如何表示这个东西。lit就生成一个表示，有了这个表示，才能看到才能分辨出这个表示是什么，再然后才能说可以用这个表示干事情。

一个API，例如lit，在解释器里怎么表示呢，是个什么表示方法。首先生成一个表示，然后去case这个表示，然后去do这个表示。如何表示才能case，然后去do。case是一种实现，但case的东西很重要。这样去思考问题。

这个是原子、那个是组合，这个问题先放一放，不要一上来就考虑这些问题，问题搅在一起会很复杂。第一步，考虑一下lit怎么表示，才能case。API定义完，它处于什么层次，它返回的什么东西。API只返回一个表示行不行。这是考虑问题的方式，一步一步下来以后，问题就比较清楚。

现在写的lit，很多是把事情都干了，看不到表示什么，现在不是要实现这个功能，是要设计一个语言的解释器。

  1. 如何表示Notation。

以lit为例，把问题具体化，想返回一个内部表示(representation)，这个内部表示是什么？

lit('abc') => representation?

思考这个问题，lit如何表示？后面的oneof、star如何表示？先只考虑这一件事情。因为这里的“表示”是很重要的一点。所有的组合也好、组合的层次也好，得首先知道它是什么，才知道它能不能组合、如何组合。这个层次要清楚。现在需要设计一个内部表示方式。这种表示方法能分辨就可以了。我们现在处在解释器、语言的下面，要构造解释器。

注意，这里的'abc'是pattern。设计一个语言的时候不能考虑被匹配的字符串，被匹配的字符串千差万别，pattern是领域的核心。

lit(Pattern) => representation?

要实现一个语言去完成一个功能，有3个步骤。第1步是语言里的语素如何表示；第2步才能case这个语素，能分辨、好分辨；第3步才是对这个语素干什么事情、完成语义。如何表示语素有个判断方法————好不好case。

def interpret(Notation, String):
    case lit:
        do_lit
    case oneof:
        do_oneof
    ...

interpret(lit('a'), 'abc')

不要去考虑把lit一下从头到尾全实现了。首先构造一个Notation，再看Notation是什么，然后干什么。这是一个骨架，先把概念厘清。

这个语言比较简单，把语言内部的抽象表示方法提炼出来。

def lit(Pattern): return (‘lit’, Pattern) // case这些语素，好分辨

可以用更贴近领域的词 def match(Pattern, String): case (‘lit’, Pattern): string.startswith(Pattern) case one of: do_oneof

…

两种思考方式：都是从下往上 功能实现：在功能层面，先考虑架构，还是考虑底层功能块？ 如何更好地表达一种实现，在表达层面从下往上。 或者说：不是从当前使用的实现语言考虑如何做这个功能，而是从目前的功能描述中能否选择一种更好的表达方法把要做什么表达出来，怎么做先不考虑。 不是一个维度，两种不同的设计方法。

《Practice of Programming》 第九章 Notation

def lit(Pattern): //定义 return (‘lit’, Pattern) //定义

def interpret(Notation, String): (component, Data) = extract_component???(Notation) //识别 if component == ‘lit’: //识别 return ???? Data, String //实现 … //实现 interpret(lit(“a”), “abc”) => ??? //解释器的执行

在“lit”上定义、识别、实现三步都有了。最后还要有解释器的执行。

def lit(Pattern): //定义了一种助记表示方式来表示出语法含义——匹配Pattern的字面 return (‘lit’, Pattern) //tuple、’lit’放在tuple第一个元素

def interpret(Notation, String): (component, Data) = extract_component (Notation) if component == ‘lit’: return ???? Data, String else: raise ValueError(“No such notation %s” % Notation)

def extract_component(Notation): return (Notation[0], Notation[1]) //如果只考虑lit的话这里直接返回Notation也可以

interpret(lit(“a”), “abc”) => ??? 应该是剩下的字符串集合 因为有的pattern可能会返回多个匹配结果，因此interpret函数应该返回原字符串中去掉多个匹配结果后，生成的剩余字符串集合。

Faye’s Code：

def lit(pattern): return ('lit', pattern)

def interpret(notation, s): (component, data) = extract_component(notation) if component == 'lit': return [s[len(data):]] if s.startswith(data) else [] else: raise ValueError('No such notation %s' % notation)

def extract_component(notation): return (notation[0], notation[1])

def test(): assert interpret(lit('a'), 'abc') == ['bc'] assert interpret(lit('d'), 'abc') == []

if name == 'main': test()

第二步：做两个lit的情况(seq) interpret(seq(lit(“a”), lit(“b”)), “abc”) => ??? interpret(lit(“ab”), “abc”) => ??? 这两者的区别：从实现功能来说，两者是一样的，

戴振卿的写法： interpret(lit(“b”), interpret(lit(“a”), “abc”)) interpret(seq(lit(“a”), lit(“b”)), “abc”) => ??? 这两个的区别：第一种interpret返回剩下的字符串。这两种都能实现功能， 戴振卿的这种写法是一种Pattern——就是一串，提炼出来就是seq。 戴振卿的写法其实是seq的“实现”。

梁丽的笔记： 匹配‘ab’的三种API，有何区别？

  1. interpret(lit(‘ab’), ‘abc’)
  2. interpret (lit(‘b’), interpret(lit(‘a’), ‘abc’))
  3. interpret(seq(lit(‘a’), lit(‘b’)), ‘abc’) 当‘ab‘间加个‘.’时，1）与3）的区别来了。 2）与3）的效果是一样的，但2）是实现，3）是声明

def seq(p1, p2): return (‘seq’, p1, p2)

def interpret(Notation, String): (component, Data1, Data2) = extract_component (Notation) if component == ‘lit’: return ???? Data1, String elif component == ‘seq’: return interpret (Data2, interpret(Data1, String)) else: raise ValueError(“No such notation %s” % Notation)

def extract_component(Notation): if len(Notation) == 2: return (Notation[0], Notation[1], None) elif len(Notation) == 3: return (Notation[0], Notation[1], Notation[2])

interpret(seq(lit(‘a’), lit(‘b’)), ‘abc’) interpret (seq(lit(‘c’), seq(lit(‘a’), lit(‘b’))), ‘abc’)

思考： 之前的一步一步思考步骤！！ interpret(lit(“b”), interpret(lit(“a”, “Dbc”)) 如果没有匹配上如何处理？

邓辉总结： 为啥要从语言设计角度考虑问题？ 提供更好的角度更好地解决问题，应对更多的复杂性，提升我们的能力和看待问题的方法

实现语言的一种重要方法Interpreter，三个步骤。 从另外一个维度去看，解决问题需要哪些语素、语法。 语言的三个要素：Primitive、如何把Primitive组合起来的手段——合子。 原子、组合和抽象。如果把原子组合起来以后能否还具有原子的特性，这是抽象非常重要的概念，只有这样做了，才能控制复杂性，才能对程序的所有变换非常清楚——“少即是多”。

正则表达式的例子展示了：

  1. 如何定义Notation
  2. 如何识别Notation
  3. 如何实现一个语义
  4. 实现了简单的组合

语言、语言的应用 —— 这样分层

Faye’s Code:

def lit(pattern): return ('lit', pattern)

def seq(pattern1, pattern2): return ('seq', pattern1, pattern2)

def interpret(notation, s): (component, data1, data2) = extract_component(notation) if component == 'lit': return [s[len(data1):]] if s.startswith(data1) else [] elif component == 'seq': return set(ry for rx in interpret(data1, s) for ry in interpret(data2, rx)) #return set(reduce(lambda x, acc: x+acc, [interpret(data2, remain) for remain in interpret(data1, s)], [])) else: raise ValueError('No such notation %s' % notation)

def extract_component(notation): l = len(notation) if l == 2: return (notation[0], notation[1], None) elif l == 3: return (notation[0], notation[1], notation[2])

def test(): assert interpret(lit('a'), 'abc') == ['bc'] assert interpret(lit('d'), 'abc') == []

assert interpret(seq(lit('a'), lit('b')), 'abc') == set(['c'])
assert interpret(seq(lit('a'), lit('b')), 'bc') == set([])

if name == 'main': test()

在seq的实现中，使用了set去除重复元素。例如:alt(star(lit(‘a’)),star(lit(‘b’)))，对于待测文本’ab’来说，star(lit(‘a’))的匹配剩余结果为{‘ab’,’b’}, star(lit(‘b’)的匹配剩余结果为{‘ab’}。两个集合的并集为{‘ab’,’b’}，去除了重复的’ab’。 6 2013-06-01(下午) 第三步：dot (语义是任意字符)

Faye’s Code

def lit(pattern): return ('lit', pattern)

def seq(pattern1, pattern2): return ('seq', pattern1, pattern2)

def dot(): return ('dot',) # 注意这里的“,”不能省略，否则extract的时候长度会被判断为3

def interpret(notation, s): (component, data1, data2) = extract_component(notation) if component == 'lit': return [s[len(data1):]] if s.startswith(data1) else [] elif component == 'seq': return set(ry for rx in interpret(data1, s) for ry in interpret(data2, rx)) #return set(reduce(lambda x, acc: x+ acc, [interpret(data2, remain) for remain in interpret(data1, s)], [])) elif component == 'dot': return [s[1:]] if len(s) > 0 else [] else: raise ValueError('No such notation %s' % notation)

def extract_component(notation): l = len(notation) if l == 3: return (notation[0], notation[1], notation[2]) elif l == 2: return (notation[0], notation[1], None) elif l == 1: return (notation[0], None, None)

def test(): assert interpret(lit('a'), 'abc') == ['bc'] assert interpret(lit('d'), 'abc') == []

assert interpret(seq(lit('a'), lit('b')), 'abc') == set(['c'])
assert interpret(seq(lit('a'), lit('b')), 'bc') == set([])

assert interpret(dot(), 'ab') == ['b']
assert interpret(dot(), 'a') == ['']
assert interpret(dot(), '') == []

if name == 'main': test()

第四步：alt (二选一)

当第一个匹配有结果后，第二个还匹配吗？如果alt在中间呢？

Faye’s Code def lit(pattern): return ('lit', pattern)

def seq(pattern1, pattern2): return ('seq', pattern1, pattern2)

def dot(): return ('dot',)

def alt(pattern1, pattern2): return ('alt', pattern1, pattern2)

def interpret(notation, s): (component, data1, data2) = extract_component(notation) if component == 'lit': return [s[len(data1):]] if s.startswith(data1) else [] elif component == 'seq': return set(ry for rx in interpret(data1, s) for ry in interpret(data2, rx)) #return set(reduce(lambda x, acc: x+acc, [interpret(data2, remain) for remain in interpret(data1, s)], [])) elif component == 'dot': return [s[1:]] if len(s) > 0 else [] elif component == 'alt': return interpret(data1, s) + interpret(data2, s) else: raise ValueError('No such notation %s' % notation)

def extract_component(notation): l = len(notation) if l == 3: return (notation[0], notation[1], notation[2]) elif l == 2: return (notation[0], notation[1], None) elif l == 1: return (notation[0], None, None)

def test(): assert interpret(lit('a'), 'abc') == ['bc'] assert interpret(lit('d'), 'abc') == []

assert interpret(seq(lit('a'), lit('b')), 'abc') == set(['c'])
assert interpret(seq(lit('a'), lit('b')), 'bc') == set([])

assert interpret(dot(), 'ab') == ['b']
assert interpret(dot(), 'a') == ['']
assert interpret(dot(), '') == []

assert interpret(alt(lit('a'), lit('b')), 'acd') == ['cd']
assert interpret(alt(lit('a'), lit('b')), 'bcd') == ['cd']
assert interpret(alt(lit('a'), lit('b')), 'cde') == []
assert interpret(alt(lit('a'), lit('b')), 'abcd') == ['bcd']
assert interpret(alt(lit('a'), lit('ab')), 'abcd') == ['bcd', 'cd']
assert interpret(alt(lit('a'), lit('ab')), 'cd') == []

if name == 'main': test()

课堂视频中，是在引入alt时，把interpret返回的剩下字符串改成了剩下字符串的列表。 且seq实现中并未引入set，尚未考虑剩余字符串重复问题。

为保证同步，把程序改成和课堂进度一样，去掉set，孙鸣的测试用例可以通过：

def lit(pattern): return ('lit', pattern)

def seq(pattern1, pattern2): return ('seq', pattern1, pattern2)

def dot(): return ('dot',)

def alt(pattern1, pattern2): return ('alt', pattern1, pattern2)

def interpret(notation, s): (component, data1, data2) = extract_component(notation) if component == 'lit': return [s[len(data1):]] if s.startswith(data1) else [] elif component == 'seq': return [ry for rx in interpret(data1, s) for ry in interpret(data2, rx)] #return reduce(lambda x, acc: x+acc, [interpret(data2, remain) for remain in interpret(data1, s)], []) elif component == 'dot': return [s[1:]] if len(s) > 0 else [] elif component == 'alt': return interpret(data1, s) + interpret(data2, s) else: raise ValueError('No such notation %s' % notation)

def extract_component(notation): l = len(notation) if l == 3: return (notation[0], notation[1], notation[2]) elif l == 2: return (notation[0], notation[1], None) elif l == 1: return (notation[0], None, None)

def test(): assert interpret(lit('a'), 'abc') == ['bc'] assert interpret(lit('d'), 'abc') == []

assert interpret(seq(lit('a'), lit('b')), 'abc') == ['c']
assert interpret(seq(lit('a'), lit('b')), 'bc') == []

assert interpret(dot(), 'ab') == ['b']
assert interpret(dot(), 'a') == ['']
assert interpret(dot(), '') == []

assert interpret(alt(lit('a'), lit('b')), 'acd') == ['cd']
assert interpret(alt(lit('a'), lit('b')), 'bcd') == ['cd']
assert interpret(alt(lit('a'), lit('b')), 'cde') == []
assert interpret(alt(lit('a'), lit('b')), 'abcd') == ['bcd']
assert interpret(alt(lit('a'), lit('ab')), 'abcd') == ['bcd', 'cd']
assert interpret(alt(lit('a'), lit('ab')), 'cd') == []
#sunming alt testcases
assert interpret(alt(lit('b'), lit('a')), 'ab') == ['b']
assert interpret(alt(lit('b'), lit('a')), 'ba') == ['a']
assert interpret(alt(lit('a'), seq(lit('a'), lit('b'))), 'abc') == ['bc', 'c']
assert interpret(alt(lit('b'), lit('a')), 'c') == []

if name == 'main': test()

邓辉点评：选取的数据结构要贴合逻辑， 否则数据结构间需额外转换。

再来看这两种写法的区别： interpret(seq(lit('a'), seq(lit('b'), lit('c'))), "abc") interpret(lit("abc"), "abc")

如果加个’d’： interpret(seq(lit('a'), seq(lit('b'), seq(lit('c'), lit(‘d’)))), "abc") interpret(lit("abcd"), "abc") 没什么大的区别，第一种稍微麻烦些

如果ab中间加个“.”（任意字符）呢？： 差别就大了。

这两种都能实现功能，但一种是有结构、按规则组合起来的，另一种是硬绑定实现的。

为啥一定要startsWith？从哪儿开始匹配？

第五步：opt (0个或1个)

我一开始是这样做的： def opt(pattern): return ('opt', pattern)

def interpret(notation, s): (component, data1, data2) = extract_component(notation) if component == 'lit': return [s[len(data1):]] if s.startswith(data1) else [] elif component == 'seq': return [ry for rx in interpret(data1, s) for ry in interpret(data2, rx)] #return reduce(lambda x, acc: x+acc, [interpret(data2, remain) for remain in interpret(data1, s)], []) elif component == 'dot': return [s[1:]] if len(s) > 0 else [] elif component == 'alt': return interpret(data1, s) + interpret(data2, s) elif component == 'opt': remains = interpret(data1, s) return [s] + remains if len(remains) > 0 else [s] else: raise ValueError('No such notation %s' % notation)

测试代码： assert interpret(opt(lit('c')), 'abc') == ['abc'] assert interpret(opt(lit('a')), 'abc') == ['abc', 'bc']

仔细想一下：opt是一个新的语言结构吗？ 有或者没有？0或1个匹配？alt？

def opt(pattern): return alt(lit(''), pattern)

Faye’s Code

def lit(pattern): return ('lit', pattern)

def seq(pattern1, pattern2): return ('seq', pattern1, pattern2)

def dot(): return ('dot',)

def alt(pattern1, pattern2): return ('alt', pattern1, pattern2)

def opt(pattern): return alt(lit(''), pattern)

def interpret(notation, s): (component, data1, data2) = extract_component(notation) if component == 'lit': return [s[len(data1):]] if s.startswith(data1) else [] elif component == 'seq': return [ry for rx in interpret(data1, s) for ry in interpret(data2, rx)] #return reduce(lambda x, acc: x+acc, [interpret(data2, remain) for remain in interpret(data1, s)], []) elif component == 'dot': return [s[1:]] if len(s) > 0 else [] elif component == 'alt': return interpret(data1, s) + interpret(data2, s) else: raise ValueError('No such notation %s' % notation)

def extract_component(notation): l = len(notation) if l == 3: return (notation[0], notation[1], notation[2]) elif l == 2: return (notation[0], notation[1], None) elif l == 1: return (notation[0], None, None)

def test(): assert interpret(lit('a'), 'abc') == ['bc'] assert interpret(lit('d'), 'abc') == []

assert interpret(seq(lit('a'), lit('b')), 'abc') == ['c']
assert interpret(seq(lit('a'), lit('b')), 'bc') == []

assert interpret(dot(), 'ab') == ['b']
assert interpret(dot(), 'a') == ['']
assert interpret(dot(), '') == []

assert interpret(alt(lit('a'), lit('b')), 'acd') == ['cd']
assert interpret(alt(lit('a'), lit('b')), 'bcd') == ['cd']
assert interpret(alt(lit('a'), lit('b')), 'cde') == []
assert interpret(alt(lit('a'), lit('b')), 'abcd') == ['bcd']
assert interpret(alt(lit('a'), lit('ab')), 'abcd') == ['bcd', 'cd']
assert interpret(alt(lit('a'), lit('ab')), 'cd') == []
#sunming alt testcases
assert interpret(alt(lit('b'), lit('a')), 'ab') == ['b']
assert interpret(alt(lit('b'), lit('a')), 'ba') == ['a']
assert interpret(alt(lit('a'), seq(lit('a'), lit('b'))), 'abc') == ['bc', 'c']
assert interpret(alt(lit('b'), lit('a')), 'c') == []

assert interpret(opt(lit('c')), 'abc') == ['abc']
assert interpret(opt(lit('a')), 'abc') == ['abc', 'bc']

if name == 'main': test()

视频中的过程：

  1. 修改interpret函数 def interpret(notation, s): … elif component == ‘opt’: return [s] + interpret(data1, s) … 修改interpret相当于修改我们的语言。 问题：层次不够、不断地重复规则 opt的含义是0或1。是不是一种特殊的“或”呢？

  2. 不修改interpret函数， opt()函数改为： def opt(pattern): return (‘alt’, lit(‘’), pattern)

比第一次好，但脑子想的和实际写出来的还不一样

  1. 更好的、最终版本 def opt(pattern): return alt(lit(‘’), pattern)

和2相比，更好地表达了特殊的alt，2还是偏实现。

opt只不过是一个alt的调用，只不过这个调用很常见，所以提取一个高层次的pattern。

以上这些都是设计细节，不是实现细节。

只要实现了 opt(lit(‘a’))，opt里面随便填什么pattern都是对的。

第六步：star (0或多个)

def star(pattern): return ('star', pattern)

def interpret(notation, s): (component, data1, data2) = extract_component(notation) if component == 'lit': return [s[len(data1):]] if s.startswith(data1) else [] elif component == 'seq': return [ry for rx in interpret(data1, s) for ry in interpret(data2, rx)] #return reduce(lambda x, acc: x+acc, [interpret(data2, remain) for remain in interpret(data1, s)], []) elif component == 'dot': return [s[1:]] if len(s) > 0 else [] elif component == 'alt': return interpret(data1, s) + interpret(data2, s) elif component == 'star': result = [s] //第0次 remains = interpret(data1, s) //第1次 for remain in remains: result += interpret(notation, remain) return result else: raise ValueError('No such notation %s' % notation)

assert interpret(star(lit('a')), 'abc') == ['abc', 'bc']

邓辉的推导等式： star(P, Str) = [Str] + [star(P, R) for R in P(Str)].flat()

再加一个测试用例： assert interpret(star(lit('')), 'abc') == ['abc']

发现死循环、堆栈溢出！！

再改一下公式的显示，看得更清楚点：

P = lit(‘a’) star(P, Str) = [Str] + [star(P, R) for R in interpret(P, Str)].flat()

如果递归要能结束，规模一定要不断缩小，R一定要比Str小。 但如果P = lit(‘’)，公式就死循环了，所以要加判断条件： P = lit(‘’) star(P, Str) = [Str] + [star(P, R) for R in interpret(P, Str) if R != Str].flat() 也可以理解为：要把结果集中完全等同于s的结果刨除掉

增加递归终止条件： elif component == 'star': result = [s] remains = interpret(data1, s) for remain in remains: if len(remain) < len(s): #remain的规模要不断缩小 result += interpret(notation, remain) return result

测试代码： assert interpret(star(lit('a')), 'abc') == ['abc', 'bc'] assert interpret(star(lit('a')), 'aabc') == ['aabc', 'abc', 'bc'] assert interpret(star(lit('')), 'abc') == ['abc']

Faye’s Code 本阶段完整代码： def lit(pattern): return ('lit', pattern)

def seq(pattern1, pattern2): return ('seq', pattern1, pattern2)

def dot(): return ('dot',)

def alt(pattern1, pattern2): return ('alt', pattern1, pattern2)

def opt(pattern): return alt(lit(''), pattern)

def star(pattern): return ('star', pattern)

def interpret(notation, s): (component, data1, data2) = extract_component(notation) if component == 'lit': return [s[len(data1):]] if s.startswith(data1) else [] elif component == 'seq': return [ry for rx in interpret(data1, s) for ry in interpret(data2, rx)] #return reduce(lambda x, acc: x+acc, [interpret(data2, remain) for remain in interpret(data1, s)], []) elif component == 'dot': return [s[1:]] if len(s) > 0 else [] elif component == 'alt': return interpret(data1, s) + interpret(data2, s) elif component == 'star': result = [s] remains = interpret(data1, s) for remain in remains: if len(remain) < len(s): result += interpret(notation, remain) return result else: raise ValueError('No such notation %s' % notation)

def extract_component(notation): l = len(notation) if l == 3: return (notation[0], notation[1], notation[2]) elif l == 2: return (notation[0], notation[1], None) elif l == 1: return (notation[0], None, None)

def test(): assert interpret(lit('a'), 'abc') == ['bc'] assert interpret(lit('d'), 'abc') == []

assert interpret(seq(lit('a'), lit('b')), 'abc') == ['c']
assert interpret(seq(lit('a'), lit('b')), 'bc') == []

assert interpret(dot(), 'ab') == ['b']
assert interpret(dot(), 'a') == ['']
assert interpret(dot(), '') == []

assert interpret(alt(lit('a'), lit('b')), 'acd') == ['cd']
assert interpret(alt(lit('a'), lit('b')), 'bcd') == ['cd']
assert interpret(alt(lit('a'), lit('b')), 'cde') == []
assert interpret(alt(lit('a'), lit('b')), 'abcd') == ['bcd']
assert interpret(alt(lit('a'), lit('ab')), 'abcd') == ['bcd', 'cd']
assert interpret(alt(lit('a'), lit('ab')), 'cd') == []
#sunming alt testcases
assert interpret(alt(lit('b'), lit('a')), 'ab') == ['b']
assert interpret(alt(lit('b'), lit('a')), 'ba') == ['a']
assert interpret(alt(lit('a'), seq(lit('a'), lit('b'))), 'abc') == ['bc', 'c']
assert interpret(alt(lit('b'), lit('a')), 'c') == []

assert interpret(opt(lit('c')), 'abc') == ['abc']
assert interpret(opt(lit('a')), 'abc') == ['abc', 'bc']

assert interpret(star(lit('a')), 'abc') == ['abc', 'bc']
assert interpret(star(lit('a')), 'aabc') == ['aabc', 'abc', 'bc']
assert interpret(star(lit('')), 'abc') == ['abc']

if name == 'main': test()

邓辉总结：

lit：原子 dot: 原子 alt：组合子 opt：是个抽象：opt = lambda p: alt(lit(‘’), p)，基于组合子产生的更高层面的Pattern star：组合子、粘合的规则：把对于一个原子或组合出的抽象不断的应用 oneof：组合子 def oneof(p): if len(p) <=1: return lit(‘p’) else: return alt(lit(p[0]), oneof(p[1:]))

作为语言设计者，你会发现虽然有很多逻辑可以组合出来，但是通过Profile发现实现很慢或者用得特别多但速度又是瓶颈，可以把one of作为一个原子，这纯属优化！

每一段代码都是一个公式。

讲的东西有用吗？能解决哪些问题？

Interpreter与Compiler的区别： Compiler是优化的Interpreter，Compiler是机器等价于硬件。

star可以做到和seq一样。

钱沛老师： 把三个步骤自动化起来。

自己往下写：

参考梁丽的代码修改一下star的实现：

elif component == 'star': #result = [s] #remains = interpret(data1, s) #for remain in remains: # if len(remain) < len(s): # result += interpret(notation, remain) #return result return reduce(lambda result, remain: result + interpret(notation, remain), list(set(interpret(data1, s)) - set([s])), [s])

第七步：oneof

oneof为alt的受限版，alt的两个参数可以为组合参数（也就是可以由上述grammar组合而成），而oneof只接受字符串，包含的语言集合为只含有一个字符的字符串集合，该字符为oneof参数中的任意一个字符。

Faye’s Code：

组合方式： def oneof(pattern): return lit(pattern) if len(pattern) <= 1 else alt(lit(pattern[0]), oneof(pattern[1:]))

assert interpret(oneof('a'), 'abc') == ['bc'] assert interpret(oneof(''), 'abc') == ['abc'] assert interpret(oneof('abc'), 'abc') == ['bc']

之前邓辉老师讲了，如果oneof用得很多且有性能瓶颈，可以当作原子来实现 原子方式： def oneof(pattern): #return lit(pattern) if len(pattern) <= 1 else alt(lit(pattern[0]), oneof(pattern[1:])) return ('oneof', pattern)

def interpret(notation, s): (component, data1, data2) = extract_component(notation) if component == 'lit': return [s[len(data1):]] if s.startswith(data1) else [] elif component == 'seq': return [ry for rx in interpret(data1, s) for ry in interpret(data2, rx)] #return reduce(lambda x, acc: x+acc, [interpret(data2, remain) for remain in interpret(data1, s)], []) elif component == 'dot': return [s[1:]] if len(s) > 0 else [] elif component == 'alt': return interpret(data1, s) + interpret(data2, s) elif component == 'star': #result = [s] #remains = interpret(data1, s) #for remain in remains: # if len(remain) < len(s): # result += interpret(notation, remain) #return result return reduce(lambda result, remain: result + interpret(notation, remain), list(set(interpret(data1, s)) - set([s])), [s]) elif component == 'oneof': return ([s] if len(data1) == 0 else [s[1:]] if any(s.startswith(x) for x in data1) else []) else: raise ValueError('No such notation %s' % notation)

assert interpret(oneof('a'), 'abc') == ['bc'] assert interpret(oneof(''), 'abc') == ['abc'] assert interpret(oneof('abc'), 'abc') == ['bc'] assert interpret(oneof('d'), 'abc') == []

第八步：plus (至少1个)

def plus(pattern): return seq(pattern, star(pattern))

assert interpret(plus(lit('a')), 'aab') == ['ab', 'b']

plus是组合子。

为了和之前孙鸣在论坛上讲的课程保持一致，再实现一个eol(endofline) eol只能匹配空字符串且只能在字符串末尾 第九步：eol def eol(): return ('eol',)

def interpret(notation, s): ... elif component == 'eol': return [''] if not s else [] ...

assert interpret(seq(lit('a'), eol()), 'a') == [''] assert interpret(seq(lit('a'), eol()), 'ba') == []

到目前为止完整的代码： def lit(pattern): return ('lit', pattern)

def seq(pattern1, pattern2): return ('seq', pattern1, pattern2)

def dot(): return ('dot',)

def alt(pattern1, pattern2): return ('alt', pattern1, pattern2)

def opt(pattern): return alt(lit(''), pattern)

def star(pattern): return ('star', pattern)

def oneof(pattern): #return lit(pattern) if len(pattern) <= 1 else alt(lit(pattern[0]), oneof(pattern[1:])) return ('oneof', pattern)

def plus(pattern): return seq(pattern, star(pattern))

def eol(): return ('eol',)

def interpret(notation, s): (component, data1, data2) = extract_component(notation) if component == 'lit': return [s[len(data1):]] if s.startswith(data1) else [] elif component == 'seq': return [ry for rx in interpret(data1, s) for ry in interpret(data2, rx)] #return reduce(lambda x, acc: x+acc, [interpret(data2, remain) for remain in interpret(data1, s)], []) elif component == 'dot': return [s[1:]] if len(s) > 0 else [] elif component == 'alt': return interpret(data1, s) + interpret(data2, s) elif component == 'star': #result = [s] #remains = interpret(data1, s) #for remain in remains: # if len(remain) < len(s): # result += interpret(notation, remain) #return result return reduce(lambda result, remain: result + interpret(notation, remain), list(set(interpret(data1, s)) - set([s])), [s]) elif component == 'oneof': return ([s] if len(data1) == 0 else [s[1:]] if any(s.startswith(x) for x in data1) else []) elif component == 'eol': return [''] if not s else [] else: raise ValueError('No such notation %s' % notation)

def extract_component(notation): l = len(notation) if l == 3: return (notation[0], notation[1], notation[2]) elif l == 2: return (notation[0], notation[1], None) elif l == 1: return (notation[0], None, None)

def test(): assert interpret(lit('a'), 'abc') == ['bc'] assert interpret(lit('d'), 'abc') == []

assert interpret(seq(lit('a'), lit('b')), 'abc') == ['c']
assert interpret(seq(lit('a'), lit('b')), 'bc') == []

assert interpret(dot(), 'ab') == ['b']
assert interpret(dot(), 'a') == ['']
assert interpret(dot(), '') == []

assert interpret(alt(lit('a'), lit('b')), 'acd') == ['cd']
assert interpret(alt(lit('a'), lit('b')), 'bcd') == ['cd']
assert interpret(alt(lit('a'), lit('b')), 'cde') == []
assert interpret(alt(lit('a'), lit('b')), 'abcd') == ['bcd']
assert interpret(alt(lit('a'), lit('ab')), 'abcd') == ['bcd', 'cd']
assert interpret(alt(lit('a'), lit('ab')), 'cd') == []
#sunming alt testcases
assert interpret(alt(lit('b'), lit('a')), 'ab') == ['b']
assert interpret(alt(lit('b'), lit('a')), 'ba') == ['a']
assert interpret(alt(lit('a'), seq(lit('a'), lit('b'))), 'abc') == ['bc', 'c']
assert interpret(alt(lit('b'), lit('a')), 'c') == []

assert interpret(opt(lit('c')), 'abc') == ['abc']
assert interpret(opt(lit('a')), 'abc') == ['abc', 'bc']

assert interpret(star(lit('a')), 'abc') == ['abc', 'bc']
assert interpret(star(lit('a')), 'aabc') == ['aabc', 'abc', 'bc']
assert interpret(star(lit('')), 'abc') == ['abc']

assert interpret(oneof('a'), 'abc') == ['bc']
assert interpret(oneof(''), 'abc') == ['abc']

assert interpret(oneof('abc'), 'abc') == ['bc'] assert interpret(oneof('d'), 'abc') == []

assert interpret(plus(lit('a')), 'aab') == ['ab', 'b']

assert interpret(seq(lit('a'), eol()), 'a') == ['']
assert interpret(seq(lit('a'), eol()), 'ba') == []

if name == 'main': test()

Interpreter实现了，现在要实现match和search的逻辑。 孙鸣：  match和search的差别在于：match的匹配只能从待测文本的起始开始，而Search则不然。  match先使用了interpret计算了pattern匹配的剩余结果集合，因为要求是最长的匹配结果，所以，要计算出最短的剩余结果长度，然后取出最长的匹配。  search和match不同在于，不仅仅从字符串起始匹配，所以，逐个子字串匹配，直到找到匹配结果。这里使用m is not None判断是因为m为空字串也是匹配成功，例如：search(star(lit('a')),'ba'),所以，不能用if not m判断。  search中range为len+1，是因为能够处理text为空串的情况；例如：search(star(lit('a')),'')

最终的代码： def lit(pattern): return ('lit', pattern)

def seq(pattern1, pattern2): return ('seq', pattern1, pattern2)

def dot(): return ('dot',)

def alt(pattern1, pattern2): return ('alt', pattern1, pattern2)

def opt(pattern): return alt(lit(''), pattern)

def star(pattern): return ('star', pattern)

def oneof(pattern): #return lit(pattern) if len(pattern) <= 1 else alt(lit(pattern[0]), oneof(pattern[1:])) return ('oneof', pattern)

def plus(pattern): return seq(pattern, star(pattern))

def eol(): return ('eol',)

def interpret(notation, s): (component, data1, data2) = extract_component(notation) if component == 'lit': return [s[len(data1):]] if s.startswith(data1) else [] elif component == 'seq': return [ry for rx in interpret(data1, s) for ry in interpret(data2, rx)] #return reduce(lambda x, acc: x+acc, [interpret(data2, remain) for remain in interpret(data1, s)], []) elif component == 'dot': return [s[1:]] if len(s) > 0 else [] elif component == 'alt': return interpret(data1, s) + interpret(data2, s) elif component == 'star': #result = [s] #remains = interpret(data1, s) #for remain in remains: # if len(remain) < len(s): # result += interpret(notation, remain) #return result return reduce(lambda result, remain: result + interpret(notation, remain), list(set(interpret(data1, s)) - set([s])), [s]) elif component == 'oneof': return ([s] if len(data1) == 0 else [s[1:]] if any(s.startswith(x) for x in data1) else []) elif component == 'eol': return [''] if not s else [] else: raise ValueError('No such notation %s' % notation)

def extract_component(notation): l = len(notation) if l == 3: return (notation[0], notation[1], notation[2]) elif l == 2: return (notation[0], notation[1], None) elif l == 1: return (notation[0], None, None)

def match(pattern, s): remains = interpret(pattern, s) if remains: minlen = len(min(remains, key=len)) return s[:(len(s) - minlen)]

def search(pattern, s): for i in range(len(s) + 1): m = match(pattern, s[i:]) if m is not None: return m

def test_interpret(): assert interpret(lit('a'), 'abc') == ['bc'] assert interpret(lit('d'), 'abc') == []

assert interpret(seq(lit('a'), lit('b')), 'abc') == ['c']
assert interpret(seq(lit('a'), lit('b')), 'bc') == []

assert interpret(dot(), 'ab') == ['b']
assert interpret(dot(), 'a') == ['']
assert interpret(dot(), '') == []

assert interpret(alt(lit('a'), lit('b')), 'acd') == ['cd']
assert interpret(alt(lit('a'), lit('b')), 'bcd') == ['cd']
assert interpret(alt(lit('a'), lit('b')), 'cde') == []
assert interpret(alt(lit('a'), lit('b')), 'abcd') == ['bcd']
assert interpret(alt(lit('a'), lit('ab')), 'abcd') == ['bcd', 'cd']
assert interpret(alt(lit('a'), lit('ab')), 'cd') == []
#sunming alt testcases
assert interpret(alt(lit('b'), lit('a')), 'ab') == ['b']
assert interpret(alt(lit('b'), lit('a')), 'ba') == ['a']
assert interpret(alt(lit('a'), seq(lit('a'), lit('b'))), 'abc') == ['bc', 'c']
assert interpret(alt(lit('b'), lit('a')), 'c') == []

assert interpret(opt(lit('c')), 'abc') == ['abc']
assert interpret(opt(lit('a')), 'abc') == ['abc', 'bc']

assert interpret(star(lit('a')), 'abc') == ['abc', 'bc']
assert interpret(star(lit('a')), 'aabc') == ['aabc', 'abc', 'bc']
assert interpret(star(lit('')), 'abc') == ['abc']

assert interpret(oneof('a'), 'abc') == ['bc']
assert interpret(oneof(''), 'abc') == ['abc']

assert interpret(oneof('abc'), 'abc') == ['bc'] assert interpret(oneof('d'), 'abc') == []

assert interpret(plus(lit('a')), 'aab') == ['ab', 'b']

assert interpret(seq(lit('a'), eol()), 'a') == ['']
assert interpret(seq(lit('a'), eol()), 'ba') == []

def test(): assert match(lit('a'), 'abc') == 'a' assert search(lit('a'), 'bac') == 'a' assert search(star(lit('a')), '') == ''

#sunming testcases
a, b, c = lit('a'), lit('b'), lit('c')
abcstars = seq(star(a), seq(star(b), star(c)))
dotstar = star(dot())

assert search(lit('def'), 'abcdefg') == 'def'
assert search(seq(lit('def'), eol()), 'abcdef') == 'def'
assert search(seq(lit('def'), eol()), 'abcdefg') == None
assert search(a, 'not the start') == 'a'
assert match(a, 'not the start') == None
assert search(plus(seq(a, b)), 'abc') == 'ab'
assert match(abcstars, 'aaabbbccccccccdef') == 'aaabbbcccccccc'
assert match(abcstars, 'junk') == ''
assert all(match(seq(abcstars, eol()), s) == s for s in 'abc aaaabbccc aaaabcccc'.split())
assert all(match(seq(abcstars, eol()), s) == None for s in 'cab aaabbcccd aaaa-b-cccc'.split())
r = seq(lit('ab'), seq(dotstar, seq(lit('aca'), seq(dotstar, seq(a, eol())))))
assert all(search(r, s) is not None for s in 'abracadabra abacaa about-acacia-flora'.split())
assert all(match(seq(c, seq(dotstar, b)), s) is not None for s in 'cab cob carob cb carbuncle'.split())
 assert not any(match(seq(c, seq(dot(), b)), s) for s in 'crab cb across scab'.split())

if name == 'main': test_interpret() test()

Compiler版本 regex_compiler.py

孙鸣： 那编译阶段又放在哪里呢？还记得lit、seq等api么？原先这些api都只是简单地接受pattern的定义并将其组成一个数据结构（tuple）以供match_set解析，现在我们把它变成编译函数，让它们返回一个编译对象（函数），这个函数接受text文本参数，对文本应用pattern的规则，返回结果。也就是说在pattern定义时就将操作类型和参数等规则内置在编译对象（函数）中。

所有api的返回不再是简单的数据结构，是一个函数。可以应用于任何文本，接收文本参数，返回该pattern匹配后的剩余结果集！

第一步：lit def lit(ps): return lambda s: [s[len(ps):]] if s.startswith(ps) else []

def match(pattern, s): remains = pattern(s) if remains: minlen = len(min(remains, key=len)) return s[:(len(s) - minlen)]

def search(pattern, s): for i in range(len(s) + 1): m = match(pattern, s[i:]) if m is not None: return m

def test(): assert match(lit('a'), 'abc') == 'a' assert match(lit('ab'), 'abc') == 'ab' assert match(lit('d'), 'abc') == None assert match(lit(''), 'abc') == '' assert search(lit('a'), 'bac') == 'a' assert search(lit('aa'), 'baac') == 'aa' assert search(lit('d'), 'abc') == None assert search(lit(''), 'abc') == ''

if name == 'main': test()

第二步：oneof

def oneof(ps): return lambda s: ([s] if len(ps) == 0 else [s[1:]] if any(s.startswith(x) for x in ps) else [])

def test(): … assert match(oneof('ab'), 'abc') == 'a' assert match(oneof('ab'), 'bac') == 'b' assert match(oneof('d'), 'abc') == None assert match(oneof(''), 'abc') == '' assert search(oneof('ab'), 'abc') == 'a' assert search(oneof('ab'), 'bac') == 'b' assert search(oneof('d'), 'abc') == None assert search(oneof(''), 'abc') == ''

第三步：seq

def seq(pattern1, pattern2): return lambda s: [ry for rx in pattern1(s) for ry in pattern2(rx)] #return lambda s: reduce(lambda x, acc: x + acc, map(pattern2, pattern1(s)), [])

def test(): … assert match(seq(lit('a'), lit('b')), 'abc') == 'ab' assert match(seq(lit('b'), lit('c')), 'abc') == None assert match(seq(lit(''), lit('')), 'abc') == '' assert search(seq(lit('a'), lit('b')), 'abc') == 'ab' assert search(seq(lit('b'), lit('c')), 'abc') == 'bc' assert search(seq(lit(''), lit('')), 'abc') == ''

seq函数的具体实现写了两种方法 :)

第四步：dot def dot(): return lambda s: [s[1:]] if len(s) > 0 else []

def test(): … assert match(dot(), 'a') == 'a' assert match(dot(), 'ab') == 'a' assert match(dot(), '') == None assert search(dot(), 'a') == 'a' assert search(dot(), 'ab') == 'a' assert search(dot(), '') == None

第五步：alt def alt(pattern1, pattern2): return lambda s: pattern1(s) + pattern2(s)

def test(): ... assert search(alt(lit('a'), lit('b')), 'acd') == 'a' assert search(alt(lit('a'), lit('b')), 'bcd') == 'b' assert search(alt(lit('a'), lit('b')), 'cde') == None assert search(alt(lit('a'), lit('b')), 'abcd') == 'a' assert search(alt(lit('a'), lit('ab')), 'abcd') == 'ab' assert search(alt(lit('a'), lit('ab')), 'cd') == None assert search(alt(lit('b'), lit('a')), 'ab') == 'a' assert search(alt(lit('b'), lit('a')), 'ba') == 'b' assert search(alt(lit('a'), seq(lit('a'), lit('b'))), 'abc') == 'ab' assert search(alt(lit('b'), lit('a')), 'c') == None

第六步：opt def opt(pattern): return alt(lit(''), pattern)

def test(): ... assert match(opt(lit('c')), 'abc') == '' assert match(opt(lit('a')), 'abc') == 'a' #according to current search/match algorithm, the result is '', and the result of python re lib is also '' assert search(opt(lit('c')), 'abc') == '' assert search(opt(lit('a')), 'abc') == 'a'

第七步：star def star(pattern): return lambda s: star_recursive(pattern, s)

def star_recursive(pattern, s): result = [s] remains = pattern(s) for remain in remains: if len(remain) < len(s): result += star_recursive(pattern, remain) return result

def test(): ... assert match(star(lit('a')), 'abc') == 'a' assert match(star(lit('a')), 'aabc') == 'aa' assert match(star(lit('')), 'abc') == '' assert search(star(lit('a')), 'abc') == 'a' assert search(star(lit('a')), 'aabc') == 'aa' assert search(star(lit('')), 'abc') == '' #according to current search/match algorithm, the result is '', and the result of python re lib is also '' assert search(star(lit('a')), 'daabc') == ''

star函数用一句话来实现： def star(pattern): return lambda s: [s] + [result for remain in pattern(s) if len(remain) < len(s) for result in star(pattern)(remain)]

python re lib测试结果如下：

m = re.match("c?", "abc") m.group() '' m = re.match("c*", "abc") m.group() ''

第八步：plus def plus(pattern): return seq(pattern, star(pattern))

def test(): ... assert match(plus(lit('a')), 'aab') == 'aa' assert match(plus(lit('')), 'aab') == '' assert search(plus(lit('a')), 'aab') == 'aa' assert search(plus(lit('')), 'aab') == '' assert search(plus(lit('a')), 'baab') == 'aa'

第九步：eol def eol(): return lambda s: [''] if not s else []

def test(): ... assert search(seq(lit('def'), eol()), 'abcdef') == 'def' assert search(seq(lit('def'), eol()), 'abcdefg') == None

跑一下孙鸣的测试用例： #sunming testcases a, b, c = lit('a'), lit('b'), lit('c') abcstars = seq(star(a), seq(star(b), star(c))) dotstar = star(dot())

assert search(lit('def'), 'abcdefg') == 'def'
assert search(seq(lit('def'), eol()), 'abcdef') == 'def'
assert search(seq(lit('def'), eol()), 'abcdefg') == None
assert search(a, 'not the start') == 'a'
assert match(a, 'not the start') == None
assert search(plus(seq(a, b)), 'abc') == 'ab'
assert match(abcstars, 'aaabbbccccccccdef') == 'aaabbbcccccccc'
assert match(abcstars, 'junk') == ''
assert all(match(seq(abcstars, eol()), s) == s for s in 'abc aaaabbccc aaaabcccc'.split())
assert all(match(seq(abcstars, eol()), s) == None for s in 'cab aaabbcccd aaaa-b-cccc'.split())
r = seq(lit('ab'), seq(dotstar, seq(lit('aca'), seq(dotstar, seq(a, eol())))))
assert all(search(r, s) is not None for s in 'abracadabra abacaa about-acacia-flora'.split())
assert all(match(seq(c, seq(dotstar, b)), s) is not None for s in 'cab cob carob cb carbuncle'.split())

assert not any(match(seq(c, seq(dot(), b)), s) for s in 'crab cb across scab'.split())

完整代码： def lit(ps): return lambda s: [s[len(ps):]] if s.startswith(ps) else []

def oneof(ps): return lambda s: ([s] if len(ps) == 0 else [s[1:]] if any(s.startswith(x) for x in ps) else [])

def seq(pattern1, pattern2): #return lambda s: [ry for rx in pattern1(s) for ry in pattern2(rx)] return lambda s: reduce(lambda x, acc: x + acc, map(pattern2, pattern1(s)), [])

def dot(): return lambda s: [s[1:]] if len(s) > 0 else []

def alt(pattern1, pattern2): return lambda s: pattern1(s) + pattern2(s)

def opt(pattern): return alt(lit(''), pattern)

def star(pattern): #return lambda s: star_recursive(pattern, s) return lambda s: [s] + [result for remain in pattern(s) if len(remain) < len(s) for result in star(pattern)(remain)]

#def star_recursive(pattern, s):

result = [s]

remains = pattern(s)

for remain in remains:

if len(remain) < len(s):

result += star_recursive(pattern, remain)

return result

def plus(pattern): return seq(pattern, star(pattern))

def eol(): return lambda s: [''] if not s else []

def match(pattern, s): remains = pattern(s) if remains: minlen = len(min(remains, key=len)) return s[:(len(s) - minlen)]

def search(pattern, s): for i in range(len(s) + 1): m = match(pattern, s[i:]) if m is not None: return m

def test(): assert match(lit('a'), 'abc') == 'a' assert match(lit('ab'), 'abc') == 'ab' assert match(lit('d'), 'abc') == None assert match(lit(''), 'abc') == '' assert search(lit('a'), 'bac') == 'a' assert search(lit('aa'), 'baac') == 'aa' assert search(lit('d'), 'abc') == None assert search(lit(''), 'abc') == ''

assert match(oneof('ab'), 'abc') == 'a'
assert match(oneof('ab'), 'bac') == 'b'
assert match(oneof('d'), 'abc') == None
assert match(oneof(''), 'abc') == ''
assert search(oneof('ab'), 'abc') == 'a'
assert search(oneof('ab'), 'bac') == 'b'
assert search(oneof('d'), 'abc') == None
assert search(oneof(''), 'abc') == ''

assert match(seq(lit('a'), lit('b')), 'abc') == 'ab'
assert match(seq(lit('b'), lit('c')), 'abc') == None
assert match(seq(lit(''), lit('')), 'abc') == ''
assert search(seq(lit('a'), lit('b')), 'abc') == 'ab'
assert search(seq(lit('b'), lit('c')), 'abc') == 'bc'
assert search(seq(lit(''), lit('')), 'abc') == ''

assert match(dot(), 'a') == 'a'
assert match(dot(), 'ab') == 'a'
assert match(dot(), '') == None
assert search(dot(), 'a') == 'a'
assert search(dot(), 'ab') == 'a'
assert search(dot(), '') == None

assert match(alt(lit('a'), lit('b')), 'acd') == 'a'
assert match(alt(lit('a'), lit('b')), 'bcd') == 'b'
assert match(alt(lit('a'), lit('b')), 'cde') == None
assert match(alt(lit('a'), lit('b')), 'abcd') == 'a'
assert match(alt(lit('a'), lit('ab')), 'abcd') == 'ab'
assert match(alt(lit('a'), lit('ab')), 'cd') == None
assert match(alt(lit('b'), lit('a')), 'ab') == 'a'
assert match(alt(lit('b'), lit('a')), 'ba') == 'b'
assert match(alt(lit('a'), seq(lit('a'), lit('b'))), 'abc') == 'ab'
assert match(alt(lit('b'), lit('a')), 'c') == None

assert search(alt(lit('a'), lit('b')), 'acd') == 'a'
assert search(alt(lit('a'), lit('b')), 'bcd') == 'b'
assert search(alt(lit('a'), lit('b')), 'cde') == None
assert search(alt(lit('a'), lit('b')), 'abcd') == 'a'
assert search(alt(lit('a'), lit('ab')), 'abcd') == 'ab'
assert search(alt(lit('a'), lit('ab')), 'cd') == None
assert search(alt(lit('b'), lit('a')), 'ab') == 'a'
assert search(alt(lit('b'), lit('a')), 'ba') == 'b'
assert search(alt(lit('a'), seq(lit('a'), lit('b'))), 'abc') == 'ab'
assert search(alt(lit('b'), lit('a')), 'c') == None

assert match(opt(lit('c')), 'abc') == ''
assert match(opt(lit('a')), 'abc') == 'a'
#according to current search/match algorithm, the result is '', and the result of python re lib is also ''
assert search(opt(lit('c')), 'abc') == ''
assert search(opt(lit('a')), 'abc') == 'a'

assert match(star(lit('a')), 'abc') == 'a'
assert match(star(lit('a')), 'aabc') == 'aa'
assert match(star(lit('')), 'abc') == ''
assert search(star(lit('a')), 'abc') == 'a'
assert search(star(lit('a')), 'aabc') == 'aa'
assert search(star(lit('')), 'abc') == ''
#according to current search/match algorithm, the result is '', and the result of python re lib is also ''
assert search(star(lit('a')), 'daabc') == ''

assert match(plus(lit('a')), 'aab') == 'aa'
assert match(plus(lit('')), 'aab') == ''
assert search(plus(lit('a')), 'aab') == 'aa'
assert search(plus(lit('')), 'aab') == ''
assert search(plus(lit('a')), 'baab') == 'aa'

assert search(seq(lit('def'), eol()), 'abcdef') == 'def'
assert search(seq(lit('def'), eol()), 'abcdefg') == None

#sunming testcases
a, b, c = lit('a'), lit('b'), lit('c')
abcstars = seq(star(a), seq(star(b), star(c)))
dotstar = star(dot())

assert search(lit('def'), 'abcdefg') == 'def'
assert search(seq(lit('def'), eol()), 'abcdef') == 'def'
assert search(seq(lit('def'), eol()), 'abcdefg') == None
assert search(a, 'not the start') == 'a'
assert match(a, 'not the start') == None
assert search(plus(seq(a, b)), 'abc') == 'ab'
assert match(abcstars, 'aaabbbccccccccdef') == 'aaabbbcccccccc'
assert match(abcstars, 'junk') == ''
assert all(match(seq(abcstars, eol()), s) == s for s in 'abc aaaabbccc aaaabcccc'.split())
assert all(match(seq(abcstars, eol()), s) == None for s in 'cab aaabbcccd aaaa-b-cccc'.split())
r = seq(lit('ab'), seq(dotstar, seq(lit('aca'), seq(dotstar, seq(a, eol())))))
assert all(search(r, s) is not None for s in 'abracadabra abacaa about-acacia-flora'.split())
assert all(match(seq(c, seq(dotstar, b)), s) is not None for s in 'cab cob carob cb carbuncle'.split())
 assert not any(match(seq(c, seq(dot(), b)), s) for s in 'crab cb across scab'.split())

if name == 'main': test()