• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

Python把C语言打得满地找牙

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

好吧,我承认我又标题党了,不该把Python拉出来和C比,我绝无轻视C语言的意思。我想说的只是,在解决某些问题是,比起用C,用Python真是太舒服了。

《Beautiful Code》开篇第一章是由大神Brian Kernighan讲解另一位半神半程序员Rob Pike设计的C语言“正则”表达式引擎(“正则“二字打引号的原因下面会说明)。不能不说短短几十行代码是让人叹为观止的大师杰作。 具体好在哪里我也不重复了,如果我都能对这段代码头头是道,那也不劳Kernighan亲自出场赞不绝口了。总之,他说:I was amazed by how compact and elegant this code was... 我觉得,既然Kernighan都如此赞赏,论“compat and elegant”,这一定是C语言的最高境界了。估计这也是程序设计的最高境界了吧?一段时间里,我深信不疑,直到有一天,我看见了这个Regular expression engine in 14 lines of Python。再次惊叹。

首先,整理一下这段代码,实际上,原帖中的代码还不够精简,因为它用3行实现了一个Python标准库中已有的函数。取消这三行,改为用import引入库函数,得到的代码如下:

from itertools import chain as iconcat

def nil(s): yield s

def seq(l, r):
    
return lambda s: (sr for sl in l(s) for sr in r(sl))

def alt(l, r):
    
return lambda s: iconcat(l(s), r(s))

def star(e):
    
return lambda s: iconcat(nil(s), seq(e, star(e))(s))

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

def char(c):
    
def match(s):
        
if s and s[0] == c: yield s[1:]
    
return match

就代码量来看,和《Beautiful Code》中的C“正则”引擎相差不大,但此Python实现的正则引擎在功能和简单性上都有无可比拟的优势,在分析这个正则引擎如何使用,顺带说明其工作原理后,再来看它的好处。

使用这个正则引擎时首先用char, nil, sq, alt, star, plus这几个函数构造出一个正则表达式,用BNF记号表示,格式是这样的:

exp -> char(c) |
       nil |
       seq(exp, exp) |             
       alt(exp, exp) |
       star(exp) |
       plus(exp)

其语义为:

exp->char(c) 表示匹配以字母c开头的字符串;

exp->nil 表示匹配一个空字符串;

exp->seq(exp1, exp2)表示如果exp1匹配s1,exp2匹配s2,则exp匹配由s1和s2连接成的字符串;

exp->alt(exp1, exp2)表示字符串s必须匹配exp1或exp2中的一个;

exp->star(exp1)匹配空字符串,或由一个或多个匹配exp1的子字符串连接成的字符串;

exp->plus(exp1)匹配由一个或多个匹配exp1的子字符串连接成的字符串。

总之不论格式还是语义它都和教科书上的正则表达式完全一致。例如,正则表达式e=c(a|d)*r用这个正则引擎表到出来就是:

e = seq(char('c'),

                seq(plus(alt(char('a'), char('d'))),

                        char('r'))

现在是使用的问题了。构造出来的正则表达式的Python类型是函数,此函数接受一个参数,即被匹配的字符串。调用此函数得到的结果是一个集合,其中每一个元素为一个字符串,对应一个正则表达式和目标字符串的匹配,而这个字符串的内容就是目标字符串中剩下的无法匹配的部分。也就是说,如果正则表达式可以和目标字符串匹配,则返回的集合不为空,反之则得到一个空集合,因此,我们可以用:

if e(str):

来判断正则表达式e是否和字符串str匹配。

要理解这个正则引擎的工作原理,只要抓住前述的一点“调用此函数得到的结果是一个集合,其中每一个元素为一个字符串,对应一个正则表达式和目标字符串的匹配,而这个字符串的内容就是目标字符串中剩下的无法匹配的部分“。实际上nil, char, seq, alt, plus中的每一个都符合此定义。这也是此Python正则引擎设计的好处之一:简单明了,易于理解,易于实现,易于确保正确。要写出《Beautiful Code》中的正则引擎是相当难的。我承认,以我的水平,即使Rob Pike把他的设计告诉我让我写代码,我也无法正确的写出。循环、指针还有边界条件,实在太容易出错了,这样的代码,非出自大师之手不可。而Python版的正则引擎就不一样,简单清晰的语义,很好的模块性,即使让我来写也可一次写对。

虽然代码量相当,但是此Python 在功能上大大强过C版。首先,C版并不是一个真正的正则引擎。它无法表达“匹配exp1或匹配exp2”,这大大的限制它的实用性,而Python版是教科书式的标准正则引擎。其次,C版不能表达(abc)*这样的表达式,即其Kleene closure中的内容只能是一个字母,而Python版Kleene closure中可以是任何表达式。这就是为什么开头“正则”二字要加引号。

此Python版代码的可组合性也比C版好。如果要在原有的基础上添加功能,Python版的用户只需要添加新的函数,而C版则要修改已有函数,难易程度不可同日耳语。比如注意到Python版没有“匹配任意字符”的功能,我们只需添加两行代码即可实现此功能:

def any(s):
    yield s[1:]

不仅实现简单,而且因为不改动已有代码,测试也容易。

为什么在实现一个简单的正则引擎这个任务上,Python比C版顺手许多呢。看看Python版中用到的C所不具备的语言特性:generator function, generator expression, 高阶函数,string slicing。string slicing不仅仅是一个简单的产生子字符串的表达式,支撑其易用性是Python的自动内存管理。


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
《c程序设计语言》读书笔记--多个空格变为一个空格发布时间:2022-07-18
下一篇:
转载C#中使用结构来传递多个参数发布时间:2022-07-18
热门推荐
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap