LL(1)文法分析

自顶向下

自顶向下是一种从开始符号推导出输入符号所对应的语法的过程,举个例子:

上面便是个从开始符号S出发,推导出aabb语法情况的过程,可以通过这个信息产生语法树。

那么如何推导呢?下面是通过一个栈来做的穷举推导过程,这种推导是需要回溯的:

上面的例子里面,出栈一个非终结符的时候,便从这个终结符的几个产生式里找一个做尝试,如果此路不通,就回退到尝试的路口,然后换一个产生式继续努力,直到找到一条看起来可以走下去的路继续重复以上的步骤(如果所有产生式都不能走通,就判断为语法有问题)。

可以想象,如果从A开始就选错了产生式,然后B尝试了所有产生式都没走通,那么回溯的层次就不仅仅是B自己一层了。这就好像一条路有X个岔路,然后每个岔路又有各自Y个岔路,而每个子岔路下面仍然有可能有Z个岔路,而目的地是X5Y2Z8,这种做法好像赌博碰运气一样,看天吃饭。有没有其他好的方法呢?

继续阅读

探索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内部是如何工作的——它比你想象的要复杂多了。

继续阅读

mail core2编译脚本执行失败的问题

今天编译mail core2的时候发现curl一直下不回文件,导致编译失败,错误如下:

应该是curl下载失败了。

自己手动执行了一下curl命令,或许是我的curl版本有问题,下回来的文件大小为0。

用curl -I 拿回来的头Content-Length并没有什么问题,状态码也是200。

或许是网络问题,或许是curl的bug,curl版本 7.43.0。

既然没查出原因,就先绕条路,把curl下载改为wget(mac需要额外安装,使用brew就可以),把mailcore2项目scripts/include.sh目录下的build-dep.sh(约325行):

替换为

再编译,就通过了。

至于curl无法通过的原因,待查。

两个PHP代码片段

最近有同事碰到两个问题:

这段代码输出什么?

这段呢?

第一个代码输出true,原因在于in_array使用了==的逻辑(如果第三个参数为true则为===的逻辑),不知道这样是否合理。源码中php将字符串转成了数字,转不了则返回0。(以上测试版本为5.5.30和7.0.0)

第二个代码输出:

因为第一次使用了引用,引用计数不释放,引用的地址是数组中c的地址。第二次循环对$m赋值的时候,不停的修改了$m指向的地址,数组中的地址也就发生了变化。赋值的源码位在于zend_execute.c/zend_assign_to_variable方法中。

红黑树

红黑树是一种很常用的自平衡二叉树。之前写过二叉搜索树,我们知道二叉搜索树查找速度是由树的高度决定的,但是因为二叉搜索树对树的平衡没什么限制,如果所有节点都在一个叉上,就变成了链表了。红黑树作为二叉搜索树的同时,用以下五个性质保证了树的平衡:

  1. 节点是红色或黑色。
  2. 根是黑色。
  3. 所有叶子都是黑色(叶子是NIL节点)。
  4. 每个红色节点必须有两个黑色的子节点。(从每个叶子到根的所有路径上不能有两个连续的红色节点。)
  5. 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。

因为这些性质,一棵红黑树尽量保持每个路径上节点数差距不大,从来保证了树的查找速度。

红黑树

红黑树是一颗二叉搜索树,其查找方法自然也就是二叉搜索树的查找方法。因为给二叉搜索树节点涂了颜色,树上面的修改操作(如插入、删除)会影响红黑树的某些性质,恢复其性质需要需要O(log n) 次操作。

继续阅读

二叉查找树

二叉查找树英语Binary Search Tree),也称二叉搜索树、有序二叉树(英语:ordered binary tree),排序二叉树(英语:sorted binary tree)。二叉查找树是基础性数据结构,用于构建更为抽象的数据结构,如集合multiset关联数组等。

二叉查找树是指一棵空树或者具有下列性质的二叉树

  1. 若任意节点的左子树不空,则左子树上所有结点的值均小于它的根结点的值;
  2. 若任意节点的右子树不空,则右子树上所有结点的值均大于它的根结点的值;
  3. 任意节点的左、右子树也分别为二叉查找树。
  4. 没有键值相等的节点(英语:no duplicate nodes)。

注:维基百科和百度百科上性质【1】和【2】不同,描述中的一个性质会存在键值相等的情况,考虑到性质【4】,是不应该存在这个相等情况的。

注:以上定义摘自维基百科(微幅修改)。

二叉查找树相比于其他数据结构的优势在于查找、插入的时间复杂度较低,等于树高,期望为O(log n),最坏为O(n)。

二叉查找树

两个高度相同的二叉查找树

上面的两个二叉查找树树高是一样的,但是查找是速度是相同的。

下面介绍二叉查找树的一些操作:

继续阅读

PHP访问类私有元素

从PHP5开始,我们通过反射类来访问私有方法:

继续阅读

linux内核同步方法-原子操作

转自:edsionte's TechBlog

原子操作

原子操作用于执行轻量级、仅执行一次的操作,比如修改计数器,某些条件下的增加值或设置位等。原子操作指的是指令以原子的方式执行。之所以用原子来修饰这种操作方式是因为它们均不可再分。也就是说,原子操作要么一次性执行完毕,要么就不执行,这些操作的执行过程是不可被打断的。原子操作的具体实现取决于体系架构,以下代码如无特别声明,均来自linux/arch/x86/include/asm/atomic.h中

内核中提供了两组原子操作的接口:原子整形操作和原子位操作。前者是一组对整形数据的操作,后者则是针对单独的位操作。通过上面的叙述我们可以知道,这写操作接口完成的动作都是原子的。

继续阅读

python生成时间分割的日志

日常写应用写日志是再常见不过的事情,用python的时候发现python自带一个日志模块还挺好用的,不仅支持常见的日志分隔方案,还支持输出到各种位置(比如文件、SMTP、内存)。

网上有大量的logging模块使用教程(可以见后面的参考),这里仅说说按照时间分割的方案。

logging模块按照时间分隔可以使用TimedRotatingFileHandler,logging模块提供三个基本的handler:StreamHandlerFileHandlerNullHandler,其他的handler放在logging.handlers里面,所以需要使用TimedRotatingFileHandler则需要import logging.handlers

logging分割日志用先往默认的文件(test.log)里打,等到分割条件的时候,把之前打的那部分日志转移到对应的分割文件里(上例中就是test.log.20141016.18),这样的好处就是每次最新的都在test.log中,不过你想统一后缀(比如test.2014101618.log)似乎有点困难了,而且应该会有额外的开销。

这里仅仅是简单解释了一下logging的时间分割文件方法,不是一个十分基础和详细的文章,如果您需要更详细的内容还请看下面的参考文章。

参考:

python logging使用方法(官方)
python logging模块文档(官方文档)
python logging TimedRotatingFileHandler(官方文档)
使用python的logging模块
python标准日志模块logging及日志系统设计
python logging现学现用 – TimedRotatingFileHandler使用方法