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);

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

Posted at May 06 2014 - 08:40:39

Permanent Link: /p/519 Load full text

Post tags:

Javascript
VerbalExpressions
Compiler Construction

PLY 构造词法分析工具

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.

    <From Wikipedia:Pi>
''')

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 中以供这次使用), 需要至少以下这些词元类型

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

Posted at Aug 03 2013 - 11:18:01

Permanent Link: /p/513 Load full text

Post tags:

Compiler Construction
Python
Tutorial
PLY

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

接上篇

条件表达式

如果设计如下的类生成 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()

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

Posted at Mar 17 2013 - 00:38:47

Permanent Link: /p/508 Load full text

Post tags:

Python
Javascript
Asynchronous Expression
Compiler Construction

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

接上篇

编译步骤解释

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

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' | +------------+ +------+

Posted at Mar 13 2013 - 02:05:29

Permanent Link: /p/507 Load full text

Post tags:

Python
Javascript
Asynchronous Expression
Compiler Construction

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

目标

我说 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'
第二个参数是一个正规异步回调函数
从这个表达式之后, 所有的语句归入上述正规异步回调函数的函数体中

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

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

Posted at Mar 11 2013 - 12:48:16

Permanent Link: /p/506 Load full text

Post tags:

Compiler Construction
Python
Javascript
Asynchronous Expression

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

接上篇

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

概述

    在分析折行实现前, 先说说对基本的算术结构的分析.
    自动机基类 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) 对象, 完成使命, 然后弃掉结束大括号

自动机栈

Posted at Nov 23 2012 - 13:39:17

Permanent Link: /p/501 Load full text

Post tags:

Syntax Analysis
Stekin
Compiler Construction

句读探析 - 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)

Posted at Nov 18 2012 - 02:55:13

Permanent Link: /p/498 Load full text

Post tags:

Stekin
Compiler Construction
Syntax Analysis

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

    前段时间博客没怎么更新, 因为不才去刷一个编译器项目了. 这项目是个 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)

Posted at Nov 16 2012 - 14:18:34

Permanent Link: /p/497 Load full text

Post tags:

Compiler Construction
Stekin
C++

Page 0 1

VerbalExpressions 与状态机词法分析器 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); 看起来应该是这么回事. 以这种方式构造出来的东西应该是一个状态机而不是一大波正则表达式形成的集群. 因此首先得构造一个状态数据结构. 作为一个演示就不弄太复杂了, 它看起来类似 Posted at May 06 2014 - 08:40:39 Permanent Link: /p/519 Load full text	Post tags: Javascript VerbalExpressions Compiler Construction
PLY 构造词法分析工具 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. <From Wikipedia:Pi> ''') 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 中以供这次使用), 需要至少以下这些词元类型二元算符 /^ 二元或一元算符 +- 括号整数 Posted at Aug 03 2013 - 11:18:01 Permanent Link: /p/513 Load full text	Post tags: Compiler Construction Python Tutorial PLY
移花接木 - 编译同步代码为异步代码 [条件表达式篇] 接上篇条件表达式如果设计如下的类生成 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() 这些节点编译后会生成类似如下代码 Posted at Mar 17 2013 - 00:38:47 Permanent Link: /p/508 Load full text	Post tags: Python Javascript Asynchronous Expression Compiler Construction
移花接木 - 编译同步代码为异步代码 [补述篇] 接上篇编译步骤解释多个正规异步调用出现在同一个语句中的编译顺序 `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' \| +------------+ +------+ Posted at Mar 13 2013 - 02:05:29 Permanent Link: /p/507 Load full text	Post tags: Python Javascript Asynchronous Expression Compiler Construction
移花接木 - 编译同步代码为异步代码 [数据结构篇] 目标我说 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'` 第二个参数是一个正规异步回调函数从这个表达式之后, 所有的语句归入上述正规异步回调函数的函数体中那么下面要做的事请是, 如果在一次编译过程中, 语法分析已经完成, 对应的同步代码的语法树已经建起来, 怎么根据上述规则去生成异步代码. 比如上面的例子, 源语法树形式是 Posted at Mar 11 2013 - 12:48:16 Permanent Link: /p/506 Load full text	Post tags: Compiler Construction Python Javascript Asynchronous Expression
句读探析 - Stekinscript 实现折行及多行 lambda 语法接上篇自动机与表达式折行语法分析概述在分析折行实现前, 先说说对基本的算术结构的分析. 自动机基类 `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) 对象, 完成使命, 然后弃掉结束大括号自动机栈 Posted at Nov 23 2012 - 13:39:17 Permanent Link: /p/501 Load full text	Post tags: Syntax Analysis Stekin Compiler Construction
句读探析 - 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) Posted at Nov 18 2012 - 02:55:13 Permanent Link: /p/498 Load full text	Post tags: Stekin Compiler Construction Syntax Analysis
句读探析 - 又一个 Javascript 生成器前段时间博客没怎么更新, 因为不才去刷一个编译器项目了. 这项目是个 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)` Posted at Nov 16 2012 - 14:18:34 Permanent Link: /p/497 Load full text	Post tags: Compiler Construction Stekin C++
Page 0 1

	Back to Bit Focus
	NijiPress - Copyright (C) Neuron Teckid @ Bit Focus
	About this site

Bit Focus

VerbalExpressions

基于自动机的词法分析器

基本例子

利用分词输出

条件表达式

编译步骤解释

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

目标

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

概述

自动机栈

获取源代码

外围模块概述

对 C++11 的使用

错误处理

Lex/Yacc