计划-20090520

虽然最近工作比较忙，但是还是想把算法再捡一捡。
1.算法
USACO 做题(每周至少三道)
2.编译器的学习
继续读spidermonkey的代码
继续读Engineering a Compiler
外加英语听力，感觉好忙呀。

使用os.walk要当心

今天用python写了一段脚本，作用是遍历目录查找里面文件的内容。
遍历目录的代码使用了os.walk，大致如下：

def all_files(path):
for root, dirs, files in os.walk(path, topdown=False):
    for name in files:
        yield os.path.join(root, name)

调用的时候传入一个路径的参数，根据路径返回目录下的文件。

print list(all_file("c:/test"))

但是实际执行的时候，test目录下总是有些文件取不到。
改成u"c:/test"就都能取到了。
查看了一下os.walk的代码，os.walk做的就是调用listdir，在对子目录进行递归调用。

try:
    # Note that listdir and error are globals in this module due
    # to earlier import-*.
    names = listdir(top)
except error, err:
    if onerror is not None:
        onerror(err)
    return

dirs, nondirs = [], []
for name in names:
    if isdir(join(top, name)):
        dirs.append(name)
    else:
        nondirs.append(name)

if topdown:
    yield top, dirs, nondirs
for name in dirs:
    path = join(top, name)
    if followlinks or not islink(path):
        for x in walk(path, topdown, onerror, followlinks):
            yield x
if not topdown:
    yield top, dirs, nondirs

经过调试，问题这里的listdir上。
再查看到listdir的代码(posixmodule.c)

static PyObject *
posix_listdir(PyObject *self, PyObject *args)
{
/* XXX Should redo this putting the (now four) versions of opendir
   in separate files instead of having them all here... */
#if defined(MS_WINDOWS) && !defined(HAVE_OPENDIR)

PyObject *d, *v;
HANDLE hFindFile;
BOOL result;
WIN32_FIND_DATA FileData;
char namebuf[MAX_PATH+5]; /* Overallocate for \\*.*\0 */
char *bufptr = namebuf;
Py_ssize_t len = sizeof(namebuf)-5; /* only claim to have space for MAX_PATH */

#ifdef Py_WIN_WIDE_FILENAMES
/* If on wide-character-capable OS see if argument
   is Unicode and if so use wide API.  */
if (unicode_file_names()) {
 PyObject *po;
 if (PyArg_ParseTuple(args, "U:listdir", &po)) {
  ......
}
#endif

if (!PyArg_ParseTuple(args, "et#:listdir",
                      Py_FileSystemDefaultEncoding, &bufptr, &len))
 return NULL;
if (len > 0) {
 char ch = namebuf[len-1];
 if (ch != SEP && ch != ALTSEP && ch != ':')
  namebuf[len++] = '/';
}
strcpy(namebuf + len, "*.*");

if ((d = PyList_New(0)) == NULL)
 return NULL;

hFindFile = FindFirstFile(namebuf, &FileData);
......
#endif /* which OS */
}  /* end of posix_listdir */

上面代码是我删减过的，去掉了根据不同操作系统的预处理，只留下windows相关的。
这里根据传递的路径是字符串还是unicode，执行不同的分支。
如果传递的是字符串，则从26行开始执行。
首先对传入的路径进行处理。
如果路径不是以\\结尾的，则追加上/，然后再追加上*.*
所以如果传递的是c:/test，处理之后就变成了c:/test/*.*。
看起来没有毛病，但是对于有些字符集(例如shift_jis)，处理\\以外，有些字符也是以\\结尾的。
比如说在shift_jis
>>> '表'
'\x95\\'
所以如果以'表'结尾的目录经过处理不会变成
'表/*.*' 而是'表*.*'
这时取到的不是这个目录里面的内容，而是目录本身!!!
listdir正常返回，只是取到结果不对。
这个结果返回给os.walk，所以得到的结果也不对。

结论：
使用os.walk时，一定要用unicode。

关于treetop的一点备忘

treetop是一个PEG的解释器。

1. PEG跟CFG不同，我觉得主要有两点不同
(1)它比CFG使用要简单，速度可能更快。
另外, 它的token扫描和语法放到一起也是一个优势．
(2)匹配时依赖顺序
A/B不会等于B/A,这一点需要注意.
绝大多数的语法都可以用PEG来解析，
我开始使用的时候，出错的时候，总是怀疑是不是有些语法无法用PEG来解析，
但是最后都是我写的rule的顺序有问题, 所以请相信PEG :).

2. 使用的注意要点
(1)treetop没有可以匹配大小写混在的方法，一个解决的方法就是写成下面的形式。

rule select_keyword
 [Ss] [Ee] [Ll] [Ee] [Cc] [Tt]
end

(2)左循环
PEG的算法决定了不能很好的处理左循环，所以需要我们手动的把它拆开．

(3)顺序
如果/之间的表达式都可以匹配，
要把大的顺序放到前面，然后是小的．

(4)匹配关键字，而不是以关键字开始的

rule end_keyword
'end' !(!' ' .)
end

(5)匹配标识符

rule identifier
 (!keyword name) / (keyword name)
end
rule name
 [a-zA-Z]+
end

Ubuntu下访问blogspot

网上看到访问被封杀的blogspot的方法。

1. 修改/etc/hosts文件
加入
72.14.219.190 mocibb.blogspot.com

2.新建proxy.pac， 设置为firefox的自动加载脚本。

function FindProxyForURL(url,host){
   if(dnsDomainIs(host, ".blogspot.com")){
       return "PROXY 72.14.219.190:80";
   }
}

参考：
1.http://my.opera.com/fermi/blog/2007-03-22-how-to-visit-the-banned-blogspot

在Ubuntu上安装python

今天在机器上安装了python， 把步骤总结一下。

Ubuntu6.10默认就已经安装python了， 版本是2.4。
注意不要卸载默认的2.4，因为有些包可能依赖指定版本的python。

1. 解压缩source安装
>$mkdir ~/python
>$cp Python-2.5.tgz ~/python
>$tar -zxvf Python-2.5.tgz

解压之后会创建目录~/python/Python-2.5
2. 编译安装
编译python需要libc6-dev
>$apt-get install libc6-dev
>$cd ~/python/Python-2.5
>$./configure
>$make
>$make install
默认的安装目录是/usr/local，可以通过./configure --prefix=安装目录， 来指定。