读书记录之《计算的本质》

之前读龙书,读到自动机的时候就完全渐渐就不知所云了。后来试着看看其他类似的书,比如虎书、鲸书,最后统统都放弃了。

最近看了《计算的本质》,感觉看着还不错,简单的解释了龙书里的部分概念,还有一部分SICP的内容。

这本书主体分两部分,第一部分主要是基础的语法语义分析和自动机、下推自动机和图灵机;第二部分是一些图灵等价的机器,比如labmda、SKI、IOTA之类演算,同时还有些机器极限和抽象的讨论。

从小步语义、大步语义开始,一直到语法分析,计算的本质到底是什么?

继续阅读

探索Ruby正则表达式算法(译)

来源:Exploring Ruby’s Regular Expression Algorithm(2012)

ps. 业余翻译的,求轻拍。有什么问题可以直接指出。

大家都熟悉正则表达式,它是开发者的“瑞士军刀”。不管你想查找哪种信息,解析哪些字符串,总有一种正则表达式适合你。事实上,你可能用过很久的ruby所使用的正则表达式了——正则表达式已经被集成到几乎所有主要的语言中好多年了:Perl、javascript、PHP、Java等等。ruby支持是在90年代中期,而正则表达式是在60年代中期发明的,早了30年。

但是正则表达式是怎样工作的呢?如果你对正则表达式引擎后面的计算机原理感兴趣的话,可以读一下这三篇Russ Cox写的极棒的文章:

在这里我不打算重复Russ的内容。但是我准备在第二篇文章中快速的解释一下ruby所使用的“无递归的回溯实现”, 这意味着它可能也会像perl正则表达式一下慢吞吞。就是说,这意味着Ruby并没有使用目前最主流的正则表达式实现方法——Thompson NFA,也就是Russ第一篇文章中所描述的。

今天我们细看一下Oniguruma,也就是Ruby所使用的正则表达式引擎。我们使用一些插图来表现一些简单的正则示例,以此来弄清楚在使用正则的时候是Ruby内部是如何工作的——它比你想象的要复杂多了。

继续阅读