About
RSS

Bit Focus


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

Permanent Link: ?p=519 Load full text

Post tags:

 Javascript
 VerbalExpressions
 Compiler Construction


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