VerbalExpressions

如何弄一个在不同站点做不同事情的 Chromium 扩展

Redis

集群

    先解释一下为什么有这个需求.
    国内似乎有不少所谓的说好听叫资源聚合网站说直白叫盗文章的网站, 虽然鄙博客文章质量很一般, 但也至少被三个不同的网站全文抓取了 (http://outofmemory.cn/ http://www.taocms.org/ http://www.tuicool.com/). 其实流量点击量什么的都不是个事, 我也没打算靠写博客赚钱, 问题是这些网站长得都太残了. (tuicool 还好一点, outofmemory 代码都没用等宽字体你那网站能看! 简直白白浪费这么好个域名) 于是就有了这么个需求: 当访问到这些网站时自动跳转到原博客页面.
    当然了各位读者不必搞这么过河拆桥的需求, 大可写个插件去展开豆瓣页面上的那些短网址什么的.

    简单看一下 Chromium 扩展的结构, 无非就是一个配置文件 (manifest.json) 加上一些 JS 文件, 有必要的话再加上一些 HTML 文件. 这里就说说最简单的, 进入一个网站在页面加载完毕之后执行一个指定 JS 文件中的代码. 那么配置文件要这么写

{
  "name": "ExtensionName",
  "version": "0.1.0",
  "description": "ext descr",
  "browser_action": {
    "default_title": "Extension Title"
  },
  "content_scripts": [
    {
      "matches": ["http://ju.outofmemory.cn/entry/*"],
      "js": ["outofmemory.js"]
    }
  ],
  "manifest_version": 2
}

以上 JSON 中, content_scripts 部分是个数组, 其中每个元素有至少两个属性, matches 表示在 URL 满足什么条件时加载脚本, 而 js 则是加载那些脚本; 如果扩展要用到 jQuery 之类的库, 可以加到此数组最前面.
也就是说, 上面这个例子会在所有 URL 开头为 http://ju.outofmemory.cn/entry/ 的网页上, 调用 outofmemory.js 这个文件. 而这个文件的内容很简单

-function() {
    console.log('Hello world!');
    // window.location = document.getElementsByClassName('copyright')[0].getElementsByTagName('a')[1].href;
}()

    想了一下我还是把代码藏着点, 仍然用业界标准的 Hello world 来开场好了.
    新建一个目录, 把这两个文件保存在此目录下.
    点 Chromium 浏览器菜单 -> 工具 (Tools) -> 扩展程序 (Extensions), 勾选开发者模式 (Developer mode) 下面会刷出来 3 个按钮, 最左边就是加载野生扩展, 在对话框中选中刚才新建的目录, 这样扩展就上线了. 然后挑个页面进去看看控制台吧, 比如 http://ju.outofmemory.cn/entry/81081
    到此代码能执行了, 后面就没什么需要继续说的了, 剩下就是自己抓 DOM 看该怎么搞怎么搞吧.

    附项目地址

Created at 2014-07-18 16:17:45

Permanent Link: /p/523/

Post tags:

Chromium 扩展

VerbalExpressions 与状态机词法分析器

麻将听牌算法 [下篇]

在上篇中分析了听牌可能有关字牌的情形, 具体包括字牌中有一个单张, 而剩下的数牌全能构成面子的单骑醒, 或者字牌中有个对子, 而剩下某数牌含有一个对子的双碰型或一个搭子的边/嵌张听牌. 这篇要讨论字牌全是刻子时的类似情况. 之所以说类似是由于此时数牌只可能有以下两种情况

某一色数牌的牌总数模 3 余 1, 其它两个色都能恰好构成面子
某两色数牌的牌总数摸 3 余 2, 剩下一色能恰好构成面子

体现成代码就是, 需要解决以下两个函数

def _waits_4groups(tiles):
    # 前略
    # 在前面情况不满足时, 调用如下实现
    return (_detect_numeric_suit_with_one_more(tiles) +
            _detect_2_numeric_suits_with_2_more(tiles))

# 找一个花色, 它的数量模 3 余 1
def _detect_numeric_suit_with_one_more(tiles):
    pass

# 找两个花色, 它们各自的牌的数量模 3 都余 2
def _detect_2_numeric_suits_with_2_more(tiles):
    pass

在上一篇代码的支援下, 后一个函数的实现相对容易一些, 如下

Created at 2014-07-16 14:43:49

Permanent Link: /p/522/

Post tags:

作为一个人类经常在打清一色的时候望着手牌不知道听牌没不知道听了哪几张也不知道切哪一张会让听牌数量最大化是一件不愉快的事情, 除了九莲宝灯之类的定式役给背下来好像没别的有效方法. 或者, 写个程序来搞吧.
首先是数据结构, 这里用如下类来描述

Created at 2014-07-02 19:13:02

Permanent Link: /p/521/

Post tags:

    最近看着证明与反驳这本书, 虽然不是什么数学著作, 讨论的也不是改变世界的重要定理, 不过围绕着多面体面棱角个数关系的那个欧拉定理讲得风生水起, 还是挺有意思的.
    书里提到数学研究的一个策略, 对于一个已经证明的定理, 通过想方设法扩张其证明步骤中的条件「边界」, 也许可以把定理从一个特殊形式扩展到普遍形式. 就像写程序库一样, 总希望写出来的东西能尽可能满足各种不同参数下的需求, 虽然在软件行业这么干往往会把自己玩死...
    比如看看费马平方和定理第四步的结论 (请一定看完前四步证明, 后文的内容均是修改此证明)

对于互素的任意整数 a 和 b, a² + b² 的每一个因子也都能表示为两个整数的平方和的形式

这一步虽然内容上有不少平方和, 不过还不是平方和定理实际内容, 只是一步中间引理. 然而即使如此证明看起来也挺费神的.
要扩展这个定理的话, 可以从多个不同角度出发, 对于两个整数平方和成立, 对于三个整数平方和是否成立; 或者, 本文将采取的方式如下

给定正整数 v, u, 对于互素的任意整数 a 和 b, v * a² + u * b² 的每一个因子也都能表示为 v * p² + u * q² 的形式

    然后试着往原来的证明过程中套, 看看会发生什么.

    第一步用到了名字巨长的恒等式, 这个等式说两个平方和的乘积还是一个平方和, 在代数学中有个术语叫封闭性. 比如整数集里面任取两个元素出来进行加减乘运算, 结果还是整数 (除就不一定了), 那么加减乘这三种运算 (三个二元函数) 对于整数集就是封闭的. 类似的, 上述恒等式说明在所有能表示成两个整数平方和的数的集合内, 乘法是封闭的.
    那么这个结论能否运用到形如 v * a² + u * b² 的整数呢? 很快就能验证

(v * a² + u * b²) * (v * c² + u * d²)
  = v² * (ac)² + vu * ((ad)² + (bc)²) + u² * (bd)²
  = v² * (ac)² + u² * (bd)² + 2 * uv * abcd
    + vu * ((ad)² + (bc)²) - 2 * uv * abcd
  = (vac + ubd)² + vu(ad - bc)²

并不是 (v * p² + u * q²) 而是 (p² + vu * q²) 的形式. 真糟糕, 第一步封闭性就阵亡了. 那么今天的内容就到这里, 谢谢大家观看, 我们下期节目再见...
噢等等, 我觉得这个扩张还可以抢救一下, 只要作出一点小牺牲, 把内容收缩一点就好: 令 v, u 之一等于 1, 也就是说变成比如

Created at 2014-05-16 10:42:10

Permanent Link: /p/520/

Post tags:

数学

VerbalExpressions

    说到字符串检索分析替换修改自然会想到正则表达式, 不过这东西实在是一个只写语言. 更改系统中一个一般复杂的正则表达式, 传统的读懂代码然后替换一条语句或者加上一个分支或者参数的模式不管用, 而是直接重写, 就像清理一个塞满的垃圾桶, 方法不是把垃圾一点点挖出来, 而是整个倒掉再铺上新的垃圾袋; 正则表达式有时太复杂了, 一条语句一个调用就顶过一打的循环和分支.
    人们总会想到一些更节省脑细胞的方式来对付字符串, 让机器理解人类的咒语, 于是发明了 VerbalExpressions.
    下面是一个 JS 的例子

var tester = VerEx()
            .startOfLine()
            .then("http")
            .maybe("s")
            .then("://")
            .maybe("www.")
            .anythingBut(" ")
            .endOfLine();

上面这一串等价于 /^(http)(s)?(\:\/\/)(www\.)?([^\ ]*)$/ 这么个正则表达式, 不过书写起来显得科学多了; 如果需要更改逻辑, 也很容易下手到底是什么地方需要增加或者减少一点什么.

基于自动机的词法分析器

这个轮子很有启发性, 于是乎想到以类似的方式构造个词法解析器. 接口上的愿景是类似

var t = Tokenizer();
t.simpleSymbols('+-*/=', 'operator')
 // ...
 .ignore(' ')
 .ignore('\t')
 .ignore('\r')
 // ...
 // 上面都是单独的一个字符, 接下来是循环的模式
 .loop(DIGITS)
 .accept('integer') // 以 0-9 循环的模式, 接受为整数类型

 .startWith(LETTERS)
 .loop(LETTERS + DIGITS)
 .accept('identifier') // 以字母开头, 数字和字母循环的模式, 接受为标识符

 // 接下来是保留字
 .fixed('if')
 .fixed('for')
 // 以及一些超过 1 字符的操作符
 .fixed('==', 'operator')
 .fixed('<=', 'operator')
 // ...
;
var inputString = 'for (i = 0; i < 10; i = i + 1) { if (i % 3 == 0) { print(i); } }';
var tokenArray = t.tokenize(inputString);
console.log(tokenArray);

看起来应该是这么回事. 以这种方式构造出来的东西应该是一个状态机而不是一大波正则表达式形成的集群. 因此首先得构造一个状态数据结构. 作为一个演示就不弄太复杂了, 它看起来类似

Created at 2014-05-06 17:40:39

Permanent Link: /p/519/

Post tags:

就算是 Linux 命令行只要有爱就能剪辑 MAD 了吧

VerbalExpressions

起因当然就是, UP 主以前还没当过 UP 主呢, 这会儿想剪个 MAD 啦.

经过是, 写了个简单脚本用 avconv + mencoder 剪出没有任何特效, 只是纯粹拼接原始片段的视频.

教训是 Linux 从来不缺乏图形界面软件, 只是... 缺乏比对应的命令行软件更优秀的图形界面软件.

这次实践, 基本原理是用 avconv (不要吐槽名字啊, 其实这软件很健全的) 对源视频进行分割, 然后用 mencoder 串联起来, 再配上音乐.

Ubuntu 上安装这些东西以及对应的转码器

apt-get install libav-tools libavcodec-extra-53 mencoder

(Windows 上也有 avconv 和 mencoder 和, 理论上也能这么搞)

直接运用上述工具, 跟一般 Linux 命令行软件一样的问题就是, 参数略复杂, 比如用 mencoder 合并视频

mencoder -ovc copy -o OUTPUT_FILE.mp4 INPUT_FILE INPUT_FILE INPUT_FILE ...

而用 avconv 从一个视频源文件中提取一段内容, 转压成 640x360 分辨率的 MP4 文件, 去掉声音, 要这么干

avconv -ss 00:00:10 -i INPUT_VIDEO_FILE -t 00:00:30 -vf "scale=640:360" -f mp4 -vcodec libx264 -an OUTPUT.mp4

上面 -ss 参数后面是开始时间, -t 参数后是剪出的片段长度. (因为视频流压缩的问题, 这两个时间都可能不精确)

对于制 MAD 来说一次要剪出上百个片段, 这么一个个手打再多的爱最后也是死路一条. 所以得换个方式, 选取一些相对容易的工具; 当然如果没有, 就造一个.

这个轮子构想的出发点是尽量简化对视频剪裁参数的编写. 因为制作 MAD 往往是从多个视频中混合剪出片段, 而且顺序不确定, 所以填写文件名还是太麻烦, 可以这么考虑

将所有源视频放在一个目录下, 文件名前面编号 (如果是同一部动画, 那么就是集数了)

由一个文件给出剪取顺序, 信息包括视频顺序编号, 场景开始时间, 场景长度; 为了让这个文件更容易维护, 也允许文件中有注释

剩下的参数只需要指定输入的音频文件路径和输出的最终文件路径即可

中间弄出来的片段都放临时文件目录好了

基于以上指导思想, 实作如下的 Python 函数

Created at 2014-03-22 22:03:30

Permanent Link: /p/518/

Post tags:

视频剪辑

索引统计与 Python 字典

最近折腾索引引擎以及数据统计方面的工作比较多, 与 Python 字典频繁打交道, 至此整理一份此方面 API 的用法与坑法备案.

索引引擎的基本工作原理便是倒排索引, 即将一个文档所包含的文字反过来映射至文档; 这方面算法并没有太多花样可言, 为了增加效率, 索引数据尽可往内存里面搬, 此法可效王献之习书法之势, 只要把十八台机器内存全部塞满, 那么基本也就功成名就了. 而基本思路举个简单例子, 现在有以下文档 (分词已经完成) 以及其包含的关键词

doc_a: [word_w, word_x, word_y]
doc_b: [word_x, word_z]
doc_c: [word_y]

将其变换为

word_w -> [doc_a]
word_x -> [doc_a, doc_b]
word_y -> [doc_a, doc_c]
word_z -> [doc_b]

写成 Python 代码, 便是

doc_a = {'id': 'a', 'words': ['word_w', 'word_x', 'word_y']}
doc_b = {'id': 'b', 'words': ['word_x', 'word_z']}
doc_c = {'id': 'c', 'words': ['word_y']}

docs = [doc_a, doc_b, doc_c]
indices = dict()

for doc in docs:
    for word in doc['words']:
        if word not in indices:
            indices[word] = []
        indices[word].append(doc['id'])

print indices

不过这里有个小技巧, 就是对于判断当前词是否已经在索引字典里的分支

if word not in indices:
    indices[word] = []

可以被 dict 的 setdefault(key, default=None) 接口替换. 此接口的作用是, 如果 key 在字典里, 那么好说, 拿出对应的值来; 否则, 新建此 key, 且设置默认对应值为 default. 但从设计上来说, 我不明白为何 default 有个默认值 None, 看起来并无多大意义, 如果确要使用此接口, 大体都会自带默认值吧, 如下

for doc in docs:
    for word in doc['words']:
        indices.setdefault(word, []).append(doc['id'])

这样就省掉分支了, 代码看起来少很多.
不过在某些情况下, setdefault 用起来并不顺手: 当 default 值构造很复杂时, 或产生 default 值有副作用时, 以及一个之后会说到的情况; 前两种情况一言以蔽之, 就是 setdefault 不适用于 default 需要惰性求值的场景. 换言之, 为了兼顾这种需求, setdefault 可能会设计成

def setdefault(self, key, default_factory):
    if key not in self:
        self[key] = default_factory()
    return self[key]

倘若真如此, 那么上面的代码应改成

for doc in docs:
    for word in doc['words']:
        indices.setdefault(word, list).append(doc['id'])

Created at 2014-01-01 14:16:40

Permanent Link: /p/517/

Post tags:

Data Structure

简易配置 gunicorn

引子

单纯 gevent 跟 nodejs 一样有个问题是如果服务器有大的同步计算 (比如压缩一张图片什么的) 需求时, 服务器会很卡. 这也不能怪它们, 因为本来它们的长处是 IO 异步化, 同步计算卡住是缺陷特性之一.
然, 或荐~~基独搅受~~ gunicorn 以解此困. 只是其首页上例子意味不明, 各种文档文章都说要编写一些离奇复杂的配置文件, 然后跑个语焉不详的 hello world, 并没能明示重点问题.

正文

嘛, 一番探索之后配了下面一个用例 (Flask)

import time
import flask

app = flask.Flask(__name__)

@app.route('/
')
def root(n):
    time.sleep(2)
    i = n / 2
    while 1 < i:
        if n % i == 0:
            return 'not prime'
        i -= 1
    return 'prime'

if __name__ == '__main__':
    app.run(port=8000)

这个例子里面兼顾了长 IO (用睡眠去模拟) 跟大计算 (算请求的数是不是个素数). 把这货在控制台裸着启动起来, 然后用 apache benchmark 来一发 (如果觉得后面请求参数里那个素数不够大, 可以自行算一个大的替换)

ab -n 500 -c 50 localhost:8000/16785407

当然了, -c 50 这个参数纯是卖萌的, 因为上面这代码自身根本异步不起来. 结果自然是惨不忍睹, 重点两行在测试机上表现如下

Time per request:       131417.472 [ms] (mean)
Time per request:       2628.349 [ms] (mean, across all concurrent requests)

平均单个请求耗时 2.6 秒以上, 其中 2 秒是睡过去的, 剩下 0.6 秒是计算. 也就是说 IO 时间与计算时间大概的比例是 3:1.

安装 gunicorn 可以直接通过 pip 安装, 简单容易, 就不废话了. 下面上 gunicorn 平装版, 把上面的文件保存为 test.py, 在控制台中执行

gunicorn -w 4 test:app

这个是说, 开 4 个进程跑 test 模块下的 app (就是文件里全局定义的 app 变量啦). 现在再开 ab 来一炮 (参数完全相同), 结果是

Time per request:       33150.026 [ms] (mean)
Time per request:       663.001 [ms] (mean, across all concurrent requests)

    从结果上来看差不多就是裸跑的 1/4 了, 因为开了 4 个进程一起搅嘛.

    虽然有 4 个进程睡睡醒醒轮番搞, 但没有异步 IO 的支持, 进程睡着就不干事了. 作为要榨干 worker 进程以及 CPU 使用率的系统管理员来说这可不能忍, 于是继续折腾个 gevent 进去好了, 两者互补, 相得益彰.
    不过用 gunicorn 就不需要在文件最开始打猴子补丁了, gunicorn 有个参数直接让 gevent 嵌入进程

gunicorn -w 4 -k gevent test:app

再来一发 ab, 结果是

Time per request:       9724.214 [ms] (mean)
Time per request:       194.484 [ms] (mean, across all concurrent requests)

嘛, 算是还看得过去的数据了.

补充说明

绑定其它端口

Created at 2013-10-30 16:29:13

Permanent Link: /p/516/

Post tags:

记一些 (没) 有意义的 reduce 用法

在 Python 或 Javascript 等许多语言中都有 reduce 函数. 其中 Python 中 reduce 作为全局函数出现, 而 Javascript 中则是 Array 的成员函数. 大量的用 reduce 来做累加累乘之类的例子就不说了, 这里探讨一个特殊的用例.
前端经常会需要将页面中用户填写的一些内容打包成 JSON 字典, 比如一个注册页面片段








    Submit





document.getElementById('subm').onclick = function() {
    var inputValues = {
        email: document.getElementById('email').value,
        password: document.getElementById('password').value,
        address: document.getElementById('address').value,
        phonenum: document.getElementById('phonenum').value
    };
    /* process inputValues */
};

以后每次这个表单多一项时, 构造 inputValues 时就会多一项, 代码维护会很烦.
如果能这样写的话可能会好一些

var inputValues = {k: document.getElementById(k).value
                   for k in ['email', 'password', 'address', 'phonenum']};

可惜 Javascript 里面没有温暖人心的 dict comprehension... 于是, 就有了下面这种 reduce 替代品 (终于正题了)

var inputValues = ['email', 'password', 'address', 'phonenum'].reduce(
    function(obj, item) {
        obj[item] = document.getElementById(item).value;
        return obj;
    }, {}));

看来 Python 在语法灵活度上的优势已经虐掉 filter, map 函数两条街, 而且 dict comprehension 还能顺带打压一下 reduce, 也难怪 Guido 会挑明了说他不喜欢这些函数. 不过他不喜欢 reduce 主要是这东西太灵活, 一眼看不明白 (能一眼看明白的都直接用 sum 去了). 比如上面这个用例如果没有铺垫, 要理解还得废点草稿纸 (用来提升 bignity 倒是不错). 而下面这个例子也是 (Python)

some_dict = {
    'x': {
        'y': {
            'a': 10
        },
        'z': {
            'b': 20
        },
    },
}
reduce(lambda obj, key: obj.get(key, dict()), ['x', 'y', 'a'], some_dict)

Created at 2013-09-30 12:26:41

Permanent Link: /p/515/

Post tags:

Flask / MongoDB 搭建简易图片服务器

函数式程序设计

前期准备

通过 pip 或 easy_install 安装了 pymongo 之后, 就能通过 Python 调教 mongodb 了.
接着安装个 flask 用来当 web 服务器.
当然 mongo 也是得安装的. 对于 Ubuntu 用户, 特别是使用 Server 12.04 的同学, 安装最新版要略费些周折, 具体说是

sudo apt-key adv --keyserver hkp://keyserver.ubuntu.com:80 --recv 7F0CEB10 echo 'deb http://downloads-distro.mongodb.org/repo/ubuntu-upstart dist 10gen' | sudo tee /etc/apt/sources.list.d/mongodb.list sudo apt-get update sudo apt-get install mongodb-10gen

如果你跟我一样觉得让通过上传文件名的后缀判别用户上传的什么文件完全是捏着山药当小黄瓜一样欺骗自己, 那么最好还准备个 Pillow 库

pip install Pillow

或 (更适合 Windows 用户)

easy_install Pillow

正片

Flask 文件上传

Flask 官网上那个例子居然分了两截让人无从吐槽. 这里先弄个最简单的, 无论什么文件都先弄上来

import flask

app = flask.Flask(__name__)
app.debug = True

@app.route('/upload', methods=['POST'])
def upload():
    f = flask.request.files['uploaded_file']
    print f.read()
    return flask.redirect('/')

@app.route('/')
def index():
    return '''










    '''

if __name__ == '__main__':
    app.run(port=7777)

注: 在 upload 函数中, 使用 flask.request.files[KEY] 获取上传文件对象, KEY 为页面 form 中 input 的 name 值

因为是在后台输出内容, 所以测试最好拿纯文本文件来测.

保存到 mongodb

如果不那么讲究的话, 最快速基本的存储方案里只需要

import pymongo
import bson.binary
from cStringIO import StringIO

app = flask.Flask(__name__)
app.debug = True
db = pymongo.MongoClient('localhost', 27017).test

def save_file(f):
    content = StringIO(f.read())
    db.files.save(dict(
        content=bson.binary.Binary(content.getvalue()),
    ))

@app.route('/upload', methods=['POST'])
def upload():
    f = flask.request.files['uploaded_file']
    save_file(f)
    return flask.redirect('/')

把内容塞进一个 bson.binary.Binary 对象, 再把它扔进 mongodb 就可以了.
现在试试再上传个什么文件, 在 mongo shell 中通过

db.files.find()

就能看到了. 不过 content 这个域几乎肉眼无法分辨出什么东西, 即使是纯文本文件, mongo 也会显示为 Base64 编码.

提供文件访问

Created at 2013-09-07 13:10:57

Permanent Link: /p/514/

Post tags:

PLY 需要安装一份. 可以直接通过 pip 安装

# pip install ply

这东西并非一个扩展的正则表达式工具, 而是一个完备的编译器构造工具, 不过这篇文章只打算讨论其词法分析器构造部分.

基本例子

PLY 很魔法的一点是它使用到了模块内部反射. 也就是说在产生一个词法分析器时, 并不是把词法规则传递给 PLY 的接口, 而是依次将一些指定名字的变量或函数定义在 py 文件中.
下面给出第一个例子, 从文本中抓出十进制数值.

import ply.lex

tokens = (
    'NUMBER',
)

t_NUMBER = r'\d*[.]?\d+'

def t_error(t):
    t.lexer.skip(1)

ply.lex.lex()
ply.lex.input('''
    The Chinese mathematician Zu Chongzhi, around 480 AD, calculated that
        pi ~= 355/113
    (a fraction that goes by the name Milv in Chinese), using Liu Hui's
    algorithm applied to a 12288-sided polygon. With a correct value for its
    seven first decimal digits, this value of 3.141592920... remained the most
    accurate approximation of pi available for the next 800 years.



''')

for token in iter(ply.lex.token, None):
    print token.type, token.value

输出

NUMBER 480 NUMBER 355 NUMBER 113 NUMBER 12288 NUMBER 3.141592920 NUMBER 800

上面的代码有这么一些要点

文件中定义了 tokens 表示可能的词元类型; 在官方例子中, 其中的取值通常以全大写的形式出现
定义词元规则 t_NUMBER, 其名字是 token 变量中的成员 'NUMBER' 加上前缀 t_; 在构造词法分析器时, PLY 会将以 t_ 开头的所有定义收集起来
词元规则 t_NUMBER 的取值是正则表达式, 用来匹配所有的数值
定义 t_error 函数, 如果什么奇怪的东西混进来, 这个函数会被调用; 不过现在只是抓取数值, 无视其它符号, 所以实现只是跳过一个字符 (skip 的参数是字符数量)
调用 ply.lex.lex 构造词法分析器
调用 ply.lex.input 喂一些输入进去
从 ply.lex.token 获得词法分析的结果

利用分词输出

从这个基本例子迈向一个用于简单表达式计算的词法分析器并不困难. 如果按照之前一篇文章里所演示的那个功能 (请将该文章中最后一段代码保存在 expr_eval.py 中以供这次使用), 需要至少以下这些词元类型

二元算符 */^
二元或一元算符 +-
括号
整数

Created at 2013-08-03 20:18:01

Permanent Link: /p/513/

Post tags:

PLY

多国语言环境下 Jinja2 与 strftime 互动异常退治纪要

Tutorial

越俎代庖 - 文件系统权限设置与进程的用户身份

首先提一个问题, 为何用 sudo 执行需要 root 权限的程序时, 输入的是当前用户的口令而不是 root 的?

看一下 sudo 的 manpage, 描述是 "execute a command as another user". 注意并不一定是以 root 身份跑程序, 而是可以用任何其他身份. 这做好事不留名干坏事不怕差评利器真是太方便了. 比如, 偷偷输出某个用户的 SSH RSA 私钥之类的. 在桌面机上很少有人会建多个用户, 那么现在创建一个 (建议接下来的试验都新建用户进行, 避免遗留安全隐患; 另外, 当前用户必须已经被添加到 sudo 白名单中)

$ sudo useradd -m furude
$ sudo passwd furude # 这一步最好设置一个与当前用户不同的口令
$ su - furude
furude $

这样切换到试验用户身份, 然后创建 ssh key, 并确认生成的密钥

$ ssh-keygen
Generating public/private rsa key pair.

Enter file in which to save the key (/home/furude/.ssh/id_rsa): Created directory '/home/furude/.ssh'.
Enter passphrase (empty for no passphrase):
Enter same passphrase again:
Your identification has been saved in /home/furude/.ssh/id_rsa.
Your public key has been saved in /home/furude/.ssh/id_rsa.pub.
The key fingerprint is:
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
The keys randomart image is:
+--[ RSA 2048]----+
| ............... |
+-----------------+
$ ls .ssh
id_rsa	id_rsa.pub

现在另开一个 shell, 以非 furude 身份登入, 执行

$ ls /home/furude/.ssh

会看到错误, 不允许列举该目录. 这是当然了, 要是连密钥都能随便看, 就没什么安全感了.

下面就轮到 sudo 登场了. 还是当前用户身份登入, 执行

$ sudo ls /home/furude/.ssh
id_rsa	id_rsa.pub
$ sudo -u furude ls /home/furude/.ssh
id_rsa	id_rsa.pub
$ sudo -u `whoami` ls /home/furude/.ssh
ls: cannot open directory /home/furude/.ssh/: Permission denied

第一个是以 root 身份执行, root 最大嘛, 所以当然可以毫无压力偷看一切文件或目录了; 接下来 -u furude 参数则是指定以 furude 这个用户身份执行, 自己当然可以看自己的东西了; 最后一个则仍然是以当前用户身份执行, 所以被驳回了.
在上面试验中, 即使以 furude 的身份使用 sudo, 要求输入的口令仍然是当前用户的口令而不是 furude 用户的 (最好新开一个终端试试, 连续使用 sudo 时口令会被缓存下来). 那么, 开头的问题应该是这样的

为何用 sudo 临时以另一用户身份执行程序时, 要求输入的是当前用户的口令, 而不是被指定的那个用户?

Created at 2013-05-12 00:49:33

Permanent Link: /p/512/

Post tags:

文件系统

权限

进程

ASCII Art 字体 Tukasans

Created at 2013-05-12 00:38:41

Permanent Link: /p/511/

Post tags:

ASCII Art

Font

不少语言或者库或多或少都遭遇过乱码问题. 然而这一点在 Python 里面表现得比较另类, 一般来说只要贯彻 UTF-8 到底的思路, 不怎么可能遇到一大波乱码袭来的情况. 只是, 偶尔会直接因为字符串类型设置不对而直接抛运行期异常.
常在河边走, 湿鞋是顺理成章的事情. 这次遇到的情况简报如下

# encoding=utf-8

import jinja2
import datetime

now = datetime.datetime.utcnow()

print jinja2.Template(u'''当前月份 {{ date.strftime('%Y 年 %m 月') }}''').render(date=now)

运行这一段代码, Python 直接扔出来一坨

Traceback (most recent call last):
  File "test.py", line 8, in

    print jinja2.Template(u'''当前月份 {{ date.strftime('%Y 年 %m 月') }}''').render(date=now)
  File "/usr/local/lib/python2.7/dist-packages/Jinja2-2.6-py2.7.egg/jinja2/environment.py", line 894, in render
    return self.environment.handle_exception(exc_info, True)
  File "

Created at 2013-04-13 18:21:26

Permanent Link: /p/510/

Post tags:

Flask 是个 Python Web 框架. 网站上文档例子都很详尽, 这里就不废话了, 只是来扯两个使用中需要注意的地方.

获取 POST 请求体

21 世纪的 Web 交互中服务器跟浏览器互相丢 JSON 已经成了司空见惯的事情. 在 Flask 框架作成的服务器上要搞到 JSON 数据当然是直接访问 POST 请求体了, 如

import flask
import functools

app = flask.Flask(__name__)

@app.route('/wtf', methods=['POST'])
def wtf():
    return 'Received: ' + flask.request.data

def main():
    app.run(port=7777)

if __name__ == '__main__': main()

按文档的说法, flask.request.data 包含请求数据字符串. 但其实这也是个坑, 默认情况下根本取不到请求数据

$ curl -d "[1,1,2,3,5,8]" http://localhost:7777/wtf
Received:

熊孩子你把拿到的字符串给吃了吧? 实际上如果去看看那文档会看到并不如上面所说的那样, 而是

Contains the incoming request data as string in case it came with a mimetype Flask does not handle.

后面这个状语从句真是着急, 那到底什么 mimetype 会使得 Flask does not handle 呢? 根本没说清楚啊. 扫一眼文档后面, 还有个东西可以用: flask.request.json, 但这货一般是 None, 只有当请求 mimetype 被设置为 application/json 的时候才有用, Flask 你真心是跟 mimetype 过不去啊. 也就是说得这样发请求

$ curl -d "[1,1,2,3,5,8]" localhost:7777/wtf
Received: null
$ curl -d "[1,1,2,3,5,8]" -H "Content-Type:application/json" localhost:7777/wtf
Received: [1, 1, 2, 3, 5, 8]

# Server codes

import json
import flask
import functools

app = flask.Flask(__name__)

@app.route('/wtf', methods=['POST'])
def wtf():
    return 'Received: ' + json.dumps(flask.request.json)

def main():
    app.run(port=7777)

if __name__ == '__main__': main()

问题是现在前端攻城狮都被浏览器兼容性折腾得满世界买表, 哪还有心情检查每个请求的 content-type 对不对. 况且这还只对 JSON 有效, 如果是山寨协议又怂了.
好吧, 如果实在不行, 就挖到 WSGI 里面去好了, 比如这样

def request_data():
    d = flask.request.data
    if not d:
        return ''.join(flask.request.environ['wsgi.input'].readlines())
    return d

Created at 2013-04-05 11:49:05

Permanent Link: /p/509/

Post tags:

Flask

移花接木 - 编译同步代码为异步代码 [条件表达式篇]

Web Server

接上篇

条件表达式

如果设计如下的类生成 Javascript 中条件表达式 predicate ? consequence : alternative

# semantic.py

class Conditional(Expression):
    def __init__(self, predicate, consequence, alternative):
        self.predicate = predicate
        self.consequence = consequence
        self.alternative = alternative

    def compile(self, context):
        return output.Conditional(self.predicate.compile(context),
                                  self.consequence.compile(context),
                                  self.alternative.compile(context))

# output.py

class Conditional(Expression):
    def __init__(self, predicate, consequence, alternative):
        self.predicate = predicate
        self.consequence = consequence
        self.alternative = alternative

    def str(self):
        return '({p} ? {c} : {a})'.format(p=self.predicate.str(),
                                          c=self.consequence.str(),
                                          a=self.alternative.str())

这在条件表达式的三个子表达式均不包含异步调用时, 或仅 predicate 包含正规异步调用没问题, 如

root_context = ContextFlow()
root_flow = root_context.block

Block([
        Arithmetics(
            Binary(
                '=',
                Reference('m'),
                Conditional(
                    Reference('a'),
                    Reference('b'),
                    Reference('c')))),
        Arithmetics(
            Binary(
                '=',
                Reference('n'),
                Conditional(
                    RegularAsyncCall(
                        Reference('f'),
                        [ NumericLiteral(0) ]),
                    Reference('x'),
                    Reference('y')))),
    ]).compile(root_context)

print root_flow.str()

这些节点编译后会生成类似如下代码

Created at 2013-03-17 09:38:47

Permanent Link: /p/508/

Post tags:

移花接木 - 编译同步代码为异步代码 [补述篇]

接上篇

编译步骤解释

多个正规异步调用出现在同一个语句中的编译顺序

RegularAsyncCall 对象的 compile 代码如下

def compile(self, context):
    # 0
    compl_callee = self.callee.compile(context)

    # 1
    compl_args = [ arg.compile(context) for arg in self.arguments ]

    # 2
    callback_body_context = ContextFlow()
    cb_body_flow = callback_body_context.block
    compl_args.append(output.Lambda([ 'error', 'result' ], cb_body_flow))

    # 3
    context.block.add(output.Arithmetics(output.Call(compl_callee, compl_args)))

    # 4
    context.block = cb_body_flow

    return output.Reference('result')

步骤依次是

0 编译被调用对象
1 依次编译调用实参
2 向实参列表中追加一个匿名函数, 函数体语句流是新建的一个 ContextFlow 中的语句流
3 向当前上下文语句流中插入一个算术节点, 节点的内容是编译后的异步调用
4 修改上下文语句流

它们的顺序不可随意颠倒, 不仅仅因为有些步骤依赖于前面的步骤 (比如步骤 3 构造 Call 对象须 0 与 1 中得到的结果), 更多地是因为在编译过程中上下文语句流随时可能变化. 比如下面这个例子

async_call('xx', %%)('oo', %%)

这应当生成下面这段 Javascript 代码

async_call('xx', function(error, result) {
    result('oo', function(error, result) {
        result;
    });
});

async_call('xx', %%) 编译时第一次修改了上下文语句流, 而之后对前一次异步调用结果的调用再一次修改了上下文语句流. 用语法树来表示即

+-------------+ | origin flow | +-------------+ | +-------------+ +---------| arithmetics | +-------------+ | [A]====================+ | regular async call | +====================+ / \ [B]====================+ +------+ | regular async call | | 'oo' | +====================+ +------+ / \ +------------+ +------+ | async_call | | 'xx' | +------------+ +------+

Created at 2013-03-13 11:05:29

Permanent Link: /p/507/

Post tags:

移花接木 - 编译同步代码为异步代码 [数据结构篇]

目标

我说 JS 代码的表达能力是一流的, 可能一票 Python 党 (作为高级黑, 我不得不说我自己也是个 Python 党) 要笑了. 我是说真的, Python 的 Lambda 基本上就是半残废, 所以, 要用 Python 写异步代码那就像是用挂面上吊一样不来劲了.
然而任何写 JS 代码遇到三层以上的异步代码套在一起的时候手撕键盘的心都有了, 蔽博先前也介绍了一个工具 (确切地说是玩具) 用来使用类似同步的代码生成异步代码. 而现在则有更明确的目标, 如把这样一段代码

fs: require('fs')
content: fs.readFile('/etc/passwd', %%)
console.log(content)

变成这样一段 Javascript

var fs, content;
fs = require('fs');
fs.readFile('etc/passwd', function(err, result) {
    content = result;
    console.log(content);
});

    为什么是这样? 首先 JS 中很多异步调用的回调函数都遵循 function(error, result) 这个形式, 这俨然成为了 Javascript 中的一种约定, 因此在接下来的分析中把这样的回调函数参数称为正规异步回调 (regular asynchronous callback). 既然它们都是这么个形式, 那么写代码的时候完全可以不这么罗嗦写个回调声明, 而是用 %% 这个符号来替代它.
    而包含正规异步回调的函数调用称之为正规异步调用 (regular asynchronous call).

    更详细地说, fs.readFile('/etc/passwd', %%) 这个表达式的意思是

调用 fs.readFile
第一个参数是字符串常量 '/etc/passwd'
第二个参数是一个正规异步回调函数
从这个表达式之后, 所有的语句归入上述正规异步回调函数的函数体中

那么下面要做的事请是, 如果在一次编译过程中, 语法分析已经完成, 对应的同步代码的语法树已经建起来, 怎么根据上述规则去生成异步代码.

比如上面的例子, 源语法树形式是

Created at 2013-03-11 21:48:16

Permanent Link: /p/506/

Post tags:

C++ Lambda 简易上手

本文所有代码示例通过 g++ 4.6 编译.

之前有吐槽过 C++ STL 算法中的 for_each 函数华而不实, 主要原因是受限于 C++ 的函数编写语法, 即传统上 C++ 要求函数须独立编写, 而不能嵌套在其它函数内. 不过, 欢迎来到二十一世纪的第一个 0x10 年, 现在有了 lambda.
与其它语言一样, C++ 的 lambda 就是个匿名函数, 它的语法结构如

[ 上下文变量绑定方式 ] ( 形式参数列表 ) 可省略的返回值类型声明
{
    函数体
}

匿名函数可以定义在任何地方, 作为一个表达式出现; 如果在匿名函数的函数体中使用了表达式所在上下文中定义的量, 则需要指定绑定方式. 如

// 定义变量 sqr 为一个匿名函数
// 这个匿名函数的上下文变量绑定方式为空, 因为它无须引入任何上下文变量
// 这个匿名函数接受一个 int 作为参数
// 返回值类型声明省略, 由编译器推倒出返回 int
auto sqr = [](int x)
           {
               return x * x;
           };

int x = 10;
// 这个匿名函数的上下文变量绑定方式为 & 即引用方式, 它引用了上文中定义的 x
// 这个匿名函数接受一个 int 作为参数
// 返回值类型声明为 bool
auto equalsToX = [&](int y) -> bool
                 {
                     return x == y;
                 };

// 这个匿名函数的上下文变量绑定方式为 = 即复制方式, 它引用了上文中定义的 x
// 这个匿名函数接受一个 int 作为参数
// 返回值类型声明省略
auto lessThanX = [=](int y)
                 {
                     return y < x;
                 };

可见多亏了 C++ 的强制类型声明和变量定义检查, 才把一个简单的匿名函数搞得这么复杂, 解决了不少其它语言中不存在的问题.

作为 C++ 程序员的一个特异能力便是能够在写代码时就预见到这段程序运行时内存与对象的流动. 看了上面匿名函数的各种奇葩绑定上下文的方法, 很明显它们不仅是一个函数那么简单, 如果必要匿名函数会占用一些内存空间, 可以做这样一个实验来试试.

struct Point {
    Point()
        : x(0)
        , y(0)
    {}

    double x;
    double y;
};

int main()
{
    Point p;
    auto f = [&]()
             {
                 std::cout << p.x << "," << p.y << std::endl;
             };
    auto g = [=]()
             {
                 std::cout << p.x << "," << p.y << std::endl;
             };
    std::cout << sizeof(f) << " - " << sizeof(Point*) << std::endl;
    std::cout << sizeof(g) << " - " << sizeof(Point) << std::endl;

    auto sqr = [](int x)
               {
                   return x * x;
               };
    std::cout << sizeof(sqr) << std::endl;

    return 0;
}

Created at 2013-03-03 13:58:20

Permanent Link: /p/505/

Post tags:

填坑 - Stekinscript 异步表达式

深夜潜入一家竞争对手公司, 可惜只偷到了最后一页源代码的打印稿, 回来一看

            });
        });
    });
})();

    这是何等的引人泪下的故事.

    这不再是 Javascript 刚刚发明的那个年代, 程序员一边用 Java 一边咒骂着花括号嵌套又嵌套何时是个头; 有经验的程序员告诫那些乳臭未干的学生军函数一定要写短, 逻辑多拆分. 有时会想着, 有什么语言会强制规定单一函数的复杂度, 以让每个函数几乎都能限制在一二十行之内呢? 结果现在这个梦想成真了, 对于 Javascript 程序员而言, 这是不得不做的纯天然方式.
    比如 Javascript 中采用异步的方式来解决 IO 效率低的问题, 下面是一段用来读取 "/etc/passwd" 内容的 node 代码

fs: require('fs');
fs.readFile('/etc/passwd', function(err, data) {
    if (err) {
        return console.error(err);
    }
    console.log(data.toString());
});

看着全局空间里洋洋洒洒一大串内容, 其实只有两句话, 第一句引入库, 第二句读文件; 而对文件的处理则单独放在另一个函数了. 多好的强制函数拆分机制, 现在再也不担心老大说函数写太长了. 不过稍微复杂一些的需求就开始疼了, 比如实现从 "/etc/passwd" 中读取前 32 个字节, node 代码为

fs: require('fs');
fs.open('/etc/passwd', 'r', function(err, fd) {
    if (err) {
        return console.error(err);
    }
    fs.read(fd, new Buffer(32), 0, 32, 0, function(err, bytes, buffer) {
        if (err) {
            fs.close(fd);
            return console.error(err);
        }
        console.log(buffer.toString());
        fs.close(fd);
    });
});

    望着这回调套回调向着行中陷落下去的代码, 感觉就是挖一个大坑. 各位 Javascript 程序员肯定不希望自己的宝贝女儿在幼儿园被问到「你父亲是做什么的」的时候回答「我也不太清楚但是看起来像是用在电脑里画楼梯的」吧.

    所以我想, 得从坑里爬出来.
    考虑到「相当一部分的异步调用貌似都是这个语句块的最后一个语句」继而有了「那为什么不在代码里面用标记让一个语句块里的语句实际上是两部分或更多部分, 第一个部分对应于当前语句块, 而后面的每个部分各是一个异步回调的函数体」这样的想法.
    有了这个想法后就打起了草稿, 比如上面的前一个例子, 要是写成这样

fs: require('fs')
fs.readFile('/etc/passwd', %(err, data))
if err
    return console.error(err)
console.log(data.toString())

感觉如何? %(err, data) 这就是一个标记, 称之为异步占位符, 它可以作为函数调用的实参出现 (不能单独写在语句中或者进行算术运算). 异步占位符表示一个匿名函数 (参数列表同异步占位符中标识符列表), 如果一个语句中的某个函数调用中有实参为异步占位符, 那么同一个语句块内, 这个函数调用之后的部分都会被移进异步占位符所表示的匿名函数的函数体中去.
也就是说, 上述代码中, 该匿名函数中的代码会包括

if err
    return console.error(err)
console.log(data.toString())

Created at 2013-01-18 18:12:14

Permanent Link: /p/504/

Post tags:

NodeJS

在 C++ 模板类体中将类名仍视为模板

用 Clang++ 编译下面的源代码 (已测试 ArchLinux clang 3.2-3)

template
 class T>
class A {};

template
class B {
    A member;
};

int main()
{
    B b;
    return 0;
}

会得到如下错误信息

error: template argument for template template parameter must be a class template
    A member;
      ^

也就是说, clang++ 会认为出现在模板类 B 的类体中的符号 B 是一个已经实例化过的类型, 不能够被传递给模板类 A 用于实例化.
而 g++ 4.7 可以正确编译通过, 说明 g++ 肯定内置了某种脑补机制, 能灵活处理这样的情况, 它甚至可以编译如下分裂的代码

template  class T>
class A {};

template
class C {};

template
class B {
    A member;
    C another;
};

int main()
{
    B b;
    return 0;
}

当然在 clang++ 下也不是没办法解决了, 方案是, 在类体中如果要将类名当作模板来使用, 则在名字前加上名字空间声明. 如上面 B 定义在全局名字空间中, 所以代码应该这样修改

template  class T>
class A {};

template
class B {
    A< ::B> member;
};

int main()
{
    B b;
    return 0;
}

话说小于号跟双冒号之间有个空格 < ::, 这绝不是我手残了抖上去的, 而是这地方必须要一个空格. C++ 程序设计领域流行着各种都市传说, 其中有模板套模板结束时的两个大于号之间要加个空格什么的, 类似, 小于号跟冒号之间也要加个空格, 否则 <: 会被认为是 [.
相应地, 如果 B 定义于某个有名字的名字空间 (这话说得...) 中那么上面代码应作相应修改

template  class T>
class A {};

namespace ns {
    template
    class B {
        A<ns::B> member;
    };
}

int main()
{
    ns::B b;
    return 0;
}

Created at 2013-01-14 12:26:03

Permanent Link: /p/503/

Post tags:

C++

Template

小记 Python yield 与生成器

yield 是 Python 中的一个关键字, 这个关键字比较特殊, 用于在任何表达式前, 但它不仅会对其后的表达式有影响, 对整个函数上下文都有影响. 实际上, 凡是在函数体中出现了 yield 关键字, Python 都会对此函数特殊处理, 调用这个函数不再返回值, 而是一个生成器对象.
比如

def f():
    yield 1

g = f()
print type(g)

其结果是

如果要获取产生器产生的值, 则需要调用产生器对象的 next 函数

def f():
    yield 1

g = f()
print g.next()

如果在函数中, 出现多个 yield, 或者函数的执行过程中反复路过某个 yield, 那么 next 每次调用会得到下一个产生的值, 比如

def f():
    yield 1
    yield 2

g = f()
print g.next(),
print g.next()

得到的会是 1 2. 或如下的循环

def f():
    for x in range(3):
        yield x * 2

g = f()
print g.next(),
print g.next(),
print g.next()

该循环中反复产生值, 每次产生一个就被传递给 next 函数作为返回值... 当然这样来说是不准确地, 如果上面 for 循环如果跑得太快, 那样会疾速产生值导致 next 函数应接不暇, 这样会有诡异的同步问题. 所以正确的语义应该是

当生成器函数执行到包含 yield 的表达式时, 函数挂起, 并将 yield 之后的表达式作为返回值传递给 next 函数调用
下一次 next 函数调用又会驱动该生成器的函数体继续执行此后的语句, 直到遇见下一个 yield 再次挂起并生成一个值交给 next
如果某次 next 调用驱动了生成器继续执行, 而此后函数正常结束的话, 那么不会有任何值传递给 next 函数, 同时, 生成器会抛出 StopIteration 异常

对于最后一点, 下面这个例子可作为参考

def f():
    yield 1

g = f()
print g.next(),
print g.next()

另外生成器中如果出现 return, 它必须是一句空返回, 即 return 之后不允许跟任何表达式, 这也是限制之一.

从下面这个例子可以更好地窥探生成器的执行模式

def f():
    print 'a'
    yield 1
    print 'b'
    yield 2
    print 'c'

g = f()
print 'start'
print g.next()
print 'next'
print g.next()
print 'end'

输出结果为

start
a
1
next
b
2
end

也就是说当第一次调用了 next 之后, f 函数体的执行就挂起了, 等着下一次调用 next. 另外, f 中最后一句应该输出的 c 并没有输出, 因为第二次生成器给出了 2 这个值之后就一直处于挂起状态.
如果要大慈大悲地让最后一句也执行, 那么需要再加一句 next 调用

def f():
    print 'a'
    yield 1
    print 'b'
    yield 2
    print 'c'

g = f()
print 'start'
print g.next()
print 'next'
print g.next()
print 'end'
g.next()

    然而如果这样的话, c 输出之后, 还会带出个异常. 所以这东西有时候并不那么好用.

    那它有何用?
    一个典型的非它不可的场景是模拟无穷列表, 比如

Created at 2012-12-06 19:33:41

Permanent Link: /p/502/

Post tags:

Generator

句读探析 - Stekinscript 实现折行及多行 lambda 语法

yield

接上篇

自动机与表达式折行语法分析

概述

    在分析折行实现前, 先说说对基本的算术结构的分析.
    自动机基类 grammar::AutomationBase (grammar/automation-base.h: 30) 能够处理所有没有在 Yacc 语法规则中给出的细节, 比如将因子与算符组成算式, 分析括号配对, 还有对逗号, 冒号等分隔符的处理.
    自动机对可以处理的项目作了基本的分类, 对应于其中各名为 pushXxx 的函数和 matchClosing 函数. 而 matchClosing 函数相当于将 pushCloseParen, pushCloseBracket 等三种不同的结束括号合并成一个函数了, 因为大部分自动机自身不处理三种结束括号, 而将它们派发给其它的自动机处理.
    什么, 自动机还有很多种? 没错, 在 Stekinscript 语法模块设计中, 用来分析表达式的自动机有多种, 不同的自动机互相利用使得代码复杂度能够大大降低. 举个例子, 算术运算自动机 grammar::ArithAutomation (grammar/expr-automations.h: 9) 本身不处理大括号配对, 但表达式里面终归是可以出现大括号裹起来的字典的; 当这种情况发生时, 算术自动机会创建一个字典识别自动机 grammar::DictAutomation (grammar/expr-automations.h: 132), 让它顶替自己处理接下来的部分; 而这个字典自动机自己又是很懒的, 它才不会自己动手去识别用表达式描述的字典的键跟值, 怎么办呢? 与是它再新建一些算术自动机来识别表达式, 而自己只坐等逗号冒号等分隔符, 或者花括号结束.
    无论哪一种自动机, 都只会对特定的一些种类的 Token 感兴趣, 而基类 grammar::AutomationBase 对任何项目的实现都是一句话 (grammar/automation-base.cpp: 58-97)

error::unexpectedToken(pos, image);

那就是报错. 也就是说如果实现的自动机子类不重写它的函数, 就相当于子类丢弃了这个 Token 并报错. 除了这种粗暴的对待方式, 大致上来说每个函数还有如下方式对待 Token

接受并记录, 比如 ArithAutomation 对象在正确的时候遇到运算符或者因子
接受并丢弃, 这个说法有点语死早的感觉, 例子就是上面 ArithAutomation 与 DictAutomation 的故事, 在 ArithAutomation 对象遇到开始的大括号时, 它会创建一个 DictAutomation 对象, 然后丢弃大括号 (留着也没用)
将自身归约并移交, 比如刚才提到, DictAutomation 会委托 ArithAutomation 为它识别键值表达式, 那么此时如果 ArithAutomation 遇到一个冒号, 那么它自身不会处理, 而是首先将自己归约成一个表达式 grammar::Expression (grammar/node-base.h: 24) 对象, 并传递给它的委托者, 然后将这个冒号也一并移交给其委托者处理
将自身归约并丢弃, 比如 DictAutomation 遇到结束的大括号时, 它会将自己归约成一个字典 grammar::Dictionary (grammar/expr-nodes.h: 228) 对象, 完成使命, 然后弃掉结束大括号

自动机栈

Created at 2012-11-23 22:39:17

Permanent Link: /p/501/

Post tags:

NodeJS liteview Postgres Stekinscript 搭建留言板 [完]

Syntax Analysis

接上篇

前期准备

安装软件与库

需要安装

Postgres (建议 9 或以上版本)
libpq-dev

npm 安装 Postgres 库

npm install pg

配置数据库与表

参考这篇文章前半部分配置 Postgres 数据库.
如果已经为 PG 用户 psuser 授权使用 mydb 这个数据库, 现在进入数据库

$ psql -Upsuser -dmydb -W
Password for user psuser:

建立数据表用于存放留言

mydb=> CREATE TABLE message (
mydb(>   id SERIAL,
mydb(>   content TEXT,
mydb(>   post_time TIMESTAMP DEFAULT NOW(),
mydb(>   PRIMARY KEY(id)
mydb(> );
NOTICE:  CREATE TABLE will create implicit sequence "message_id_seq" for serial column "message.id"
NOTICE:  CREATE TABLE / PRIMARY KEY will create implicit index "message_pkey" for table "message"
CREATE TABLE

显示留言信息

更新页面模板

之前的页面模板实在显得太单薄, 下面修改一下准备放入留言数据



Guestbook

#{foreach(#messages)}

    #{[post_time]}
    #{[content]}

#{end}

liteview 文档如是说

#{foreach(#XXX)} 即在 XXX 对象上作循环
#{[YYY]} 即每次循环的循环变量的 YYY 属性

因此上面的页面模板需要传入留言对象列表, 每个留言对象有属性 post_time, content. 这命名与数据库表是一致的.
然后改一下 index.stkn, 放假数据进去先看看效果

view: require('liteview').create()

exports.get: (request, response):
    response.writeHead(200, { 'Content-Type':: 'text/html' })
    response.end(view.render('index.html', {messages: [
        {
            post_time: '1970-01-01 00:00:00',
            content: 'Nostalgia',
        },
        {
            post_time: '1970-01-01 00:00:00',
            content: 'Eternal Rite',
        },
        {
            post_time: '1970-01-01 00:00:00',
            content: 'Shinto Shrine',
        },
    ]}))

刷下页面, 这些东西就出现了.

从数据库加载内容

巧妇难为无米之炊, 现在首先要做的是向数据库插入一些数据. 还是更刚才建表一样, 进入 psql, 使用下面的语句插入一些水帖

INSERT INTO message (content) VALUES ('Message 0');
INSERT INTO message (content) VALUES ('Message 1');
INSERT INTO message (content) VALUES ('Message 2');

Created at 2012-11-19 23:57:13

Permanent Link: /p/500/

Post tags:

NodeJS liteview Postgres Stekinscript 搭建留言板 [零]

前期准备

配置软件与库

需要安装

nodejs 0.8 或以上版本 (之后编译 Postgres 模块需要高版本)
npm
下载编译 Stekinscript (非必需) $ git clone git://github.com/neuront/stekinscript.git

Ubuntu 用户安装 nodejs 0.8 版本请加入下面的源

# add-apt-repository ppa:chris-lea/node.js

创建一个工作目录, 通过 npm 安装要用到的模块

npm install liteview
npm install validator

Stekinscript 快速入门 (非必需)

请参见 https://github.com/neuront/stekinscript/wiki/Language-Specification.
对 Stekinscript 没有兴趣的同学可以无视这一步, 在每节之后生成的 Javascript 代码会奉上, 对于 Stekinscript 代码, 可以认为它是更易阅读的 JS.

开工

上手

创建如下内容的 main.stkn 文件, 先启动一个简单的服务器

http: require('http')

port: 8888

http.createServer((request, response):
    response.writeHead(200, { 'Content-Type':: 'text/html' })
    response.end('
Hello, World!')
).listen(port, '127.0.0.1')

console.log('Server running at local host port=' + port)

使用 stekin 编译它 (请用合适的路径替换下面的 stekin, 或者将编译生成的 stekin 可执行程序加入 PATH)

$ stekin -i require < main.stkn > main.js

生成的 JS 代码类似 (下面这是经过去除额外括号与重新排版的, 实际上现在 Stekinscript 生成的代码真是惨不忍睹)

(function () {
    const s_http = require("http");
    s_http.createServer(function (s_request, s_response) {
        s_response.writeHead(200, {
            "Content-Type": "text/html"
        });
        s_response.end("Hello, World!");
    }).listen(8888, "127.0.0.1");
    console.log("Server running at local host port=8888");
})();

然后使用 node 来运行它, 就在本地搭建了一枚服务器

$ node main.js
Server running at local host port=8888

访问 http://localhost:8888/ 就可以看到服务器响应了.

Makefile

在目录下加入如下内容的 Makefile, 以便更便捷地生成 JS 文件 (其中的四点 .... 表示一个制表符, Makefile 必须用这货来缩进!)

Created at 2012-11-19 21:31:06

Permanent Link: /p/499/

Post tags:

句读探析 - Stekinscript 对缩进语法的实现

获取源代码

Stekinscript 的项目地址在 https://github.com/neuront/stekinscript, 获取最新版代码

$ git clone git://github.com/neuront/stekinscript.git

本文将以 2012 年 11 月 15 日签入的版本介绍如何设计编译器语法部分, 如果 clone 的版本不是此版本, 可以通过下面的指令回滚到该版本

$ cd stekinscript
$ git reset --hard 9b756ad111fa3cf1d78a89e050a1adf38fa5e0b6

外围模块概述

下面内容中, 凡是首次提到某个类或函数时, 会在括弧中用文件路径: 行号的方式给出它所声明或定义的位置, 如 main 函数 (stekin.cpp: 11); 上下文很明显有说明哪个文件时, 以 L 行号 说明在哪一行.

对 C++11 的使用

既然是用 C++ 实现那么内存管理不总是个大问题, Stekinscript 自然也要为此做好准备.
Stekinscript 的内存管理大量依赖于 C++11 中的 std::unique_ptr 跟 move semantic, 并且对 std::unique_ptr 自有一套封装, 包括如下的几个类型

util::sptr (util/pointer.h: 94) 是直接对 std::unique_ptr 的封装, 但不允许通过 get() 方法直接取得其中的裸指针, 也不允许通过单目 * 操作符获取对象的引用, 单目型号操作符获取的是 util::sref 类型对象
util::sref (util/pointer.h: 23) 是共享引用类型, 几乎等价于一般对象引用类型, 只是不可以通过单目 & 操作符取引用, 另外使用 -> 操作符使用其内部的对象而不是直接使用 . 操作符

以上类型一般只用于存在多态的情况.
C++11 的基础知识可以参考这些文章.

错误处理

需要安装有 Python 2.7 版本, 在源码目录下执行

$ make code-gen

生成 report/errors.h 与 report/errors.cpp 文件 (一同生成的还有单元测试需要的 test/phony-errors.h test/phony-errors.cpp).
report/errors.h 包括了所有编译报错函数, 凡是源代码中出现 error:: 名字空间中的调用均声明于此. (虽然生成的代码格式上寒碜了点, 勉强可读)

Lex/Yacc

    既然是讲 C++ 程序, 本该从 main 函数入手, 但 Stekinscript 有一些依赖在初始化环境 (stekin::initEnv env.h: 9) 之后, 立即调用了 Yacc 中的 yyparse() 函数, 所以这时要去看 Lex/Yacc 文件了.
    grammar/lexica.l 文件定义了词法单元, 其中行首空格 (L 19) 不可被忽略 (否则哪来的缩进语法), 而行首不能有制表符否则报错 (L 24). 缩进层次将被缓存在全局变量 grammar::last_indent 中 (grammar/yy-misc.h: 23). 其它的词法单元看看便罢.Analysis
    然后小的重头在 grammar/syntacticall.y 这个文件中, 它实现了部分简单的语法规则. 去掉其中的语句, 开头的一些产生式如下 (L 42)

Created at 2012-11-18 11:55:13

Permanent Link: /p/498/

Post tags:

句读探析 - 又一个 Javascript 生成器

Syntax Analysis

    前段时间博客没怎么更新, 因为不才去刷一个编译器项目了. 这项目是个 Javascript 产生器.
    起这个念头的契机是看到连 M$ 都动心思搞 JS 生成器了 (然而不得不吐槽的是, 这语言看起来跟 JS 简直一个德行). 而模仿的对象则是 CoffeeScript, 可是我又不想去分支 CoffeeScript 改点语法什么的改成 LatteScript 或 CappuccinoScript (我对 Coffee 的某些语法不很满意), 于是乎自己折腾了一个.
    不过另一方面, 这个编译器 (暂定名是 Stekinscript) 也不是完全无中生有, 而是从我的毕业项目修改过来的. 要说这样有什么不好的话, 就是 --- 这东西用 C++ 实现的 (准确地说是 C++11); 要说有什么好的话, 就是貌似这样可以直接集成 v8, 嗯 (自黑一下, 我没考察过这个, 也没有做这个事情的计划).

    下面介绍一下这个语言本身, 撇开日常的什么分支语句啦函数定义返回这些 (详情可参考文档), 先说说重点.
    首先 Stekinscript 支持缩进语法, 类似 Python 跟 CoffeeScript. 代码很重要的一点就是要看着舒服不是么?
    其次就是非强制类型, 强制类型给人的感觉呢, 就像三岁小孩子学写字旁边有个执戒尺的先生一样, 错一点就打手, 我们已经是断奶的程序员了好么, 所以什么 Dart 就先搁下不用了.
    最后是实际使用的感觉, 这一点我排斥 CoffeeScript 的 lambda 语法如 (x)-> x * x 这种. 要知道输入类似 -> 这样的符号两个字符都在右手无名指跟小指区, 还是一上一下, 而且减号不用按住 Shift 而大于号又需要, 这是有多别扭设计语言的人没知觉么? 还是说已经练成星际争霸九段这点微操不算什么?

    吐槽就到此为止, 下面贴个 Stekinscript 的例子

x: []
setTimeout(():
    if x.length = 10
        return
    x.push(document.getElementById('input').value)
, 2000)

Created at 2012-11-16 23:18:34

Permanent Link: /p/497/

Post tags:

C++