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);
var State = {
'0': nextState0,
'1': nextState1,
a: nextStateA,
// 以上是一个超大状态映射表, 将每个可能遇到的字符映射到下一个状态
// 这是最纯天然最暴力的状态机实现方法, 但原则上应该将这些东西弄成一个函数
// 因为映射全部的字符 (超过 216 个 Unicode 字符) 是不现实的
// 所以先假定 : 测试数据只含有 ASCII 字符
// 以下是每个状态本身的性质
_ignore: true, // 这个状态被忽略; 不引起错误, 也不产生结果, 如空格
_type: 'integer' // 接受的类型, 如 'integer', 'identifier'
};
simpleSymbols, ignore, loop, startWith, fixed 等等. 在编译原理中任何一个自动机都要有初始状态, 在下面的代码中将命名其为 entryState; 现实中还需要一个忽略状态, 它会被称为 ignoreState.以下是
simpleSymbols 的实现var entryState = {};
var ignoreState = {_ignore: true};
function simpleSymbols(symbols, name) {
var symbolState = {_type: name};
for (var i = 0; i < symbols.length; ++i) {
var ch = symbols[i];
if (entryState[ch]) {
throw 'duplicate entry: ' + ch;
}
entryState[ch] = symbolState;
}
// 之前写的是链式操作, 那就得返回 this, 虽然目前这个函数并没有处于任何合适的对象上下文中
return this;
}
simpleSymbols('+-*/=', 'operator') 之后, entryState 的 '+-*/=' 这些字符各自对应的状态映射被指向相同的一个 symbolState, 该状态的类型是 operator.ignore 函数的实现如下, 将 entryState 与 ignoreState 连接起来function ignore(symbols) {
for (var i = 0; i < symbols.length; ++i) {
var ch = symbols[i];
entryState[ch] = ignoreState;
ignoreState[ch] = ignoreState;
}
return this;
}
startWith, loop, accept 这一组, 可能还有其它的函数, accept 是最后收尾的, 而在之前可能多次以不同的方式调用 startWith, loop, 并且 startWith 还能省略. 这样产生了一些单个函数无法控制的状态转换, 必须新弄一个什么来记录var stateTrace = [];
function startWith(symbols) {
if (stateTrace.length) {
throw 'already started';
}
var startState = {};
for (var i = 0; i < symbols.length; ++i) {
var ch = symbols[i];
if (entryState[ch]) {
throw 'duplicate entry: ' + ch;
}
entryState[ch] = startState;
}
stateTrace.push(startState);
return this;
}
function loop(symbols) {
if (stateTrace.length === 0) {
startWith(symbols);
}
var currentState = stateTrace[stateTrace.length - 1];
for (var i = 0; i < symbols.length; ++i) {
var ch = symbols[i];
currentState[ch] = currentState;
}
return this;
}
function accept(type) {
if (stateTrace.length === 0) {
throw 'pattern not started';
}
var currentState = stateTrace[stateTrace.length - 1];
currentState._type = type;
stateTrace.length = 0; // 清空状态栈
return this;
}
stateTrace 这个状态栈保存当前进行到何处这一信息. (loop 的实现有瑕疵, 因为重复调用 loop 竟不会产生新的状态, 这显然与直觉不一致; 有兴趣的话可以尝试修复这个 bug)其它类似的函数就不赘述了. 最后说说这个状态机的状态跳转都构造完成后, 如何使用它来切割字符串.
function tokenize(input) {
var state = entryState;
var token = []; // 当前词元包含的字符
var result = [];
// 处理下一个字符
function nextChar(ch) {
// 如果下一个字符可以直接跳转状态
if (state[ch]) {
// 那就跳转状态呗
state = state[ch];
if (!state._ignore) {
token.push(ch);
}
return;
}
// 下一个字符跳不动了, 看看这个状态是否有类型, 即被接受
if (state._type) {
// 把之前临时存储的字符打包在一起, 作为一个被接受的词元
result.push({
token: token.join(''),
type: state._type
});
// 当前字符本身还需要被处理
return resetConsume(ch);
}
// 好吧, 字符跳不动了, 而当前停留的状态也不是一个接受状态
if (state._ignore) {
// 不过幸好这是需要忽略的
return resetConsume(ch);
}
// 万般无奈只能报错了
throw 'unexpected character';
}
// 重置状态并处理接下来的第一个字符
function resetConsume(ch) {
token.length = 0;
state = entryState;
nextChar(ch);
}
for (var i = 0; i < input.length; ++i) {
nextChar(input[i]);
}
// 当遍历所有字符后, 可能停留在一个可接受的状态上
if (token.length !== 0 && state) {
result.push({
token: token.join(''),
type: state._type
});
}
return result;
}
