1700436339
UNIX传奇:历史与回忆 4.6 正则表达式
1700436340
1700436341
前文写到“正则表达式”时,没有详细解释。正则表达式是一种用于指定文本模式的符号。它可以是单词,如expression;可以是短语,如regular expression;也可以是更复杂的文本。实际上,正则表达式就是一种描述文本模式的小型语言。单词或短语本身就是正则表达式,它在文本中代表自己,正则表达式识别器会找到它出现的每处地方。
1700436342
1700436343
正则表达式还可以通过赋予某些字符特殊含义来指定更复杂的模式,这些字符称为元字符(metacharacter)。例如,在使用grep时,元字符“.”匹配任意单个字符,而元字符“*”匹配前一个字符的任意数量的重复,因此模式“.*”匹配括号中的任意字符序列。
1700436344
1700436345
Unix对正则表达式的“痴恋”由来已久,正则表达式遍布于文本编辑器、grep及其衍生工具以及许多其他语言和工具中。正则表达式略加变形之后,也被用于文件名模式,如前文提到的匹配一组文件名的shell“通配符”。
1700436346
1700436347
肯·汤普森在Multics以及稍后GE 635(我第一次遇到正则表达式的地方)上的QED编辑器中采用了正则表达式。肯发明了一种非常快的算法,能够快速处理复杂的表达式。该算法还获得了专利。QED的功能足够强大,原则上可以只用编辑器命令编写任何程序(尽管没有哪个正常人会这样做)。我甚至写过一篇关于QED编程的教程,这事在很大程度上是白费力气,但从那以后我就开始写这类文档了。
1700436348
1700436349
对于大多数任务而言,QED都过于强悍了。肯和丹尼斯是Unix ed文本编辑器的原作者,后来又有几个人加以修改(甚至包括我)。ed比QED简单得多,但它也支持正则表达式。grep源自ed,所以它的正则表达式用法和ed中的一样。
1700436350
1700436351
文件名通配符使用正则表达式的变体风格。虽然通配符由shell解释,但由于PDP-7上的主存储器非常有限,所以最早的实现方式是由shell调用名为glob(代表“global”,意为“全局”)的独立程序。从模式中生成文件名扩展列表的操作被称为“globbing”。glob这个名字如今在Python等几种编程语言的库中仍然存在。
1700436352
1700436353
阿尔·阿霍对Unix的早期贡献之一是扩展了grep,让它能支持更丰富的正则表达式,例如可以搜索像this|that这样的替代模式。阿尔把这个程序称为egrep,表示“extended grep”(意为“扩展grep”)。
1700436354
1700436355
关于egrep,值得多说几句。它是理论结合实践的范例,也体现了 1127中心成员之间的典型互动,正是这些结合与互动成就了如此之好的软件。这个故事来自道格·麦基尔罗伊:
1700436356
1700436357
“在与霍普克罗夫特(Hopcroft)[10]及厄尔曼(Ullman)[11]合著的《计算机算法的设计与分析》(The Design and Analysis of Computer Algorithms)一书中,阿尔·阿霍为某个算法写了个例程,那正是egrep的第一个实现。我立即在一个日历程序里用上了。该程序使用自动生成的巨大正则表达式来识别五花八门的日期模式,如today、tomorrow、until the next business day等。
1700436358
1700436359
“令阿尔懊恼的是,识别器得花30秒左右的时间才能编译出来,运行起来反倒疾如闪电。
1700436360
1700436361
“他提出了一套绝妙的策略,即在需要用到时,才生成识别器,而不是预先全部生成。因此,虽然存在指数量级的状态,但每次只构造极少部分。这带来了巨大的变化:在实践中,无论处理多么复杂的模式,egrep总是跑得很快。egrep技术卓越,但除非你知道标准方法的性能有多差,否则就会视若无睹。”
1700436362
1700436363
这是个常见的Unix故事:来自真实用户的真实问题,对相关理论的深入了解,有效的工程使理论在实践中很好地发挥作用,以及不断改进。这一切都得益于团队中广泛的专业知识、开放的环境和尝试新想法的文化。
1700436364
1700436365
1700436366
1700436367
1700436369
UNIX传奇:历史与回忆 4.7 C语言
1700436370
1700436371
新编程语言一直是Unix的重要组成部分。
1700436372
1700436373
Multics尝试用高级语言PL/I来编写操作系统,这是其一大贡献。IBM于1964年创建PL/I,意图融合Fortran、COBOL和ALGOL的全部优点。结果PL/I成了第二系统效应的范例。对大多数程序员来说,这种语言太庞大、太复杂,难以编译,而且在Multics上能工作的编译器也没能按时交付。道格·麦基尔罗伊和道格·伊斯特伍德(Doug Eastwood)临时救急,创造了在Multics上使用的PL/I简化子集,称为EPL(“Early PL/I”,早期PL/I),但EPL仍然是一种复杂的语言。
1700436374
1700436375
BCPL(Basic Combined Programming Language,基本组合编程语言)是另一种用于系统级编程的语言。它由剑桥大学教授马丁·理查兹(Martin Richards)设计。理查兹1967年访问麻省理工学院时为它写了编译器。BCPL比PL/I的任何分支版本都简单得多,很适合编写操作系统代码。贝尔实验室Multics开发组成员们非常熟悉BCPL。
1700436376
1700436377
贝尔实验室退出Multics项目后,肯·汤普森认为,“没有Fortran,计算机就不完整”,于是他着手为PDP-7编写Fortran编译器。事实证明这太艰难了,因为PDP-7 Unix只有4K个18位字长(8 KB)的主存储器供编译器等用户程序使用。
1700436378
1700436379
肯不断重新设计,最终打造出满足PDP-7条件限制的语言。这种语言更接近于BCPL而不是Fortran,肯叫它B语言。1993年,丹尼斯·里奇在“The Development of the C Language”(C语言的开发)中阐述道:
1700436380
1700436381
“可以将B语言看作没有类型的C语言。更准确地说,它是压缩到8 KB内存中、再经汤普森的大脑过滤的BCPL。它的名字看上去比较像是BCPL的缩写。不过也有另一种说法,认为它来源于与B语言毫无相关的Bon语言,一种由汤普森在Multics时期创造的语言。Bon语言则要么是以他的妻子邦妮的名字命名,要么是(根据其手册中引用的一段百科全书)以某个宗教的名字命名。”
1700436382
1700436383
到目前为止,我们故事中的计算机都以字为操作单位,而不是以字节为操作单位。也就是说,它们的操作针对明显大于单个字节的块状信息。IBM 7090和类似的计算机,如GE系列,天然只能以36位(大约4字节)的块为单位来操纵信息;PDP-7的块单位是18位(大约2字节)。面向字的计算机在单独或按顺序处理字节时很笨拙:程序员必须使用库函数或通过特别的编程技巧来访问装在较大块中的单个字节。
1700436384
1700436385
相比之下,PDP-11以字节为操作单位:它主存储器的基本单位是8位字节,而不是早期计算机的18位或36位字长。它也可以处理较大块的信息,如16位和32位整数以及16位地址。
1700436386
1700436387
B语言很适合PDP-7这样以字为操作单位的计算机,但不适合PDP-11这样以字节为操作单位的计算机,所以,PDP-11到货后,丹尼斯开始针对新的架构对B语言进行增强,并为其编写编译器。新的语言被称为“NB”,即“New B”(意为“新B语言”),最后发展成了C语言。
[
上一页 ]
[ :1.700436338e+09 ]
[
下一页 ]