VerbalExpressions

VerbalExpressions

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.



''')

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

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

Tutorial

接上篇

条件表达式

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

Asynchronous Expression

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

接上篇

编译步骤解释

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

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:

Asynchronous Expression

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

目标

我说 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:

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) 对象, 完成使命, 然后弃掉结束大括号

自动机栈

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

Permanent Link: /p/501/

Post tags:

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

Stekin

Syntax Analysis

获取源代码

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 生成器

Stekin

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

Stekin

Python 中函数交叉引用中的问题与解决方法

Python (下面的讨论都是基于 2.7 版本的) 中, 先定义的函数可以调用后定义的函数, 比如下面这段代码

def first():
    return second()

def second():
    return 0

x = first()

不过, 这种调用是有局限性的, 稍作修改为下面这个样子

def first():
    return second()

x = first()

def second():
    return 0

就会产生符号错误, 解释器给出的信息是符号 second 不存在.

Python 作为一门解释型语言, 出现这样的事情很有可能是这样的原因, 假设现在正在交互模式下执行, 那么输入

def first():
    return second()

x = first()

到此为止, second 这个符号确实还没有被定义, 故产生错误. 但是如果上述代码内容是写在文件里的, 那么 Python 完全可以扫描整个文件以获得充分的上下文信息, 并正确地检测出 second 函数定义, 只是 Python 没有这么做.

熟悉 C++ 的同学这时候肯定跳出来了, 因为在 C++ 类空间中, 这种引用是合法的, 如

struct type {
    int first()
    {
        return second();
    }

    type()
        : x(first())
    {}

    int second()
    {
        return 0;
    }

    int x;
};

不过, C++ 这种事情其实极其危险的, 比如下面这一段代码

struct type {
    int first()
    {
        return second();
    }

    type()
        : x(first())
    {}

    int second()
    {
        return x;
    }

    int x;
};

这实际上使用了还处于量子态的 x 来初始化它自身, 虽然这样的代码只有手贱的程序员在极其罕见的情况下才会写出这样的代码 (比如我在写这篇博客的时候), 但是本着编译器的职责, 完全应该想方设法让这种情况编不过去.

好了, 还是先回到 Python 上来, Python 不允许这样的代码编译过去, 是因为这个原因么? 假设有下面的程序成功被解释执行

def first():
    return second()

x = first()

def second():
    return x

Created at 2011-05-16 22:38:21

Permanent Link: /p/314/

Post tags:

C++

表达式求值之优先关系矩阵法

YACC 或者 ANTLR 或者 PLY 之类的东西是很不错啦, 不过当面对一个类似 C(++) 这么变态的需要将语法和符号表勾搭在一起的语言形式时, 还是可以考虑一下使用 Python 纯手工打造.

搞定表达式求值这种现代高级程序设计语言中基础部分, 用 LR(n), LALR 分析之类的当然是可行的, 假定需要支持括号和下面这些运算

	算符
优先级由高到低	+ - (正负号)	^ (幂运算)	* /	+ - (加减号)
结合方式	数值左边	右结合	左结合	左结合

    先搞个产生式集合 (运算符就不搞什么转义了, | 表示或)
Expr := Term +|- Expr
     := Term
Term := Exponential *|/ Term
     := Exponential
Exponential := Factor ^ Exponential
            := Factor
Factor := +|- Factor
       := Number
       := ( Expr )
    接着还要再计算 FIRST 集啊什么的, 等到最后写成代码, 秀吉都嫁人了.

    所幸这个世界上无痛的解决方案还是挺多的, 比如为符号设定优先级, 使用优先级来指导算符是应该移进还是规约. 这个方法可称为优先关系矩阵法.
    这里仍然会用到移进 (Shift) 和规约 (Reduce) 这两个术语, 不过它们的意义跟 LR 分析法里面的有些不同. 在 LR 分析中, 符号指的是词法分析中得到的 Token, 而不是运算符, 也就是说数和运算符, 以及其它任何东西都放在同一个栈中; 而在运用优先关系法的表达式分析过程中, 符号栈包括两个不同的栈, 一个专门用来存运算符 (这个栈称为算子栈), 另一个存放数或者已解析的表达式 (这个栈称为表达式栈). 在这里, 移进表示将运算符压入算子栈, 或将数压入表达式栈; 而规约指的是, 根据运算符的元数, 从表达式栈中弹出指定数目的
    遇到一个数时无条件移进, 而遇到运算符则要视情况决定移进还是规约, 而所谓的情况就是算符优先级. 比如下面这个表达式
3 + 4 * 5 + 6
    首先读入 3, 移进

表达式栈 3 算子栈 (空)

然后是 +, 算子栈栈顶为空, 没得比, 那好, 先移进

表达式栈 3 算子栈 +

继续, 4 移进, 接着是 *, 比一下, 发现 * 优先级较栈顶的 + (加号, 不是正号) 优先级高, 那肯定得移进

表达式栈 3 4 算子栈 + *

接着移进 5, 再往后又是一个 + (加号), 这时栈顶的 * 优先级高于它, 所以可以开始规约流程: 从算子栈弹出 *, 它是二元的, 于是再从表达式栈弹出栈顶 (刚刚压入的 5) 和次栈顶 (4), 将这三者组成表达式 4 * 5, 再压回表达式栈 (下面以一个二叉树的形象描述)

表达式栈 3 * / \ 4 5 算子栈 +

还没完呢, 现在的算子栈顶 + (加号) 与手头上拿着的 + (加号) 平级, 由于加号是左结合的, 所以应当继续规约, 得到

表达式栈 + / \ 3 * / \ 4 5 算子栈 (空)

现在算子栈又空了, 于是 + (最后强调一次, 加号) 压栈, 最后是 6, 移进之, 结束时, 整个算符栈从头到尾规约一次, 大功告成.

回顾一下刚才的过程, 规则是

前面说过的, 数无条件入栈
如果算子栈为空, 移进当前算子
如果算子栈顶的优先级高于当前算子, 或者两者优先级相等, 但当前符号是左结合的, 那么进行规约, 直到不满足规约条件
算子无法规约时则移进

这一些初步地写成代码类似这样

Created at 2011-04-11 22:31:40

Permanent Link: /p/250/

Post tags: