学习 Parser Combinator (一) 深层调用方式的解析器组合子
学习 Parser Combinator (一) 深层调用方式的解析器组合子
刘军兴 发表于1年前
学习 Parser Combinator (一) 深层调用方式的解析器组合子
  • 发表于 1年前
  • 阅读 31
  • 收藏 0
  • 点赞 0
  • 评论 0

腾讯云 新注册用户 域名抢购1元起>>>   

Parser combinator 在 wiki 的条目: https://en.wikipedia.org/wiki/Parser_combinator

解析器组合子的翻译文章: http://www.jianshu.com/p/0a39d58ff0e0

等等.

 

为研究 parser combinator, 先定义一个简单的字符串流的类.

function StringStream(str, start) {
  this.str = str;
  this.start = start || 0;    // 可以从某个位置开始读取.
  this.ptr = this.start;      // 读取指针
  this.end = str.length;      // 尾部.
}

// 得到当前读取位置的字符, 但不移动读取指针. 如果在流的末尾, 则返回 null.
StringStream.prototype.peek = function () {
  if (this.ptr >= this.end)
    return null;
  return this.str[this.ptr];
};

// 判定流是否到了结束.
StringStream.prototype.eof = function () {
  return this.ptr >= this.end;
};

// 移动读取指针.
StringStream.prototype.move = function (delta) {
  // 断言不要超出范围.
  console.assert(this.ptr + delta <= this.end && this.ptr + delta >= this.start);
  this.ptr += delta;
};

 

因为重点放在 combinator (组合)上, 从这个 string-stream 中每次我们就读取单个字符. 能匹配其它的, 如 word, number, string, space, regex 等以后研究.

 

定义一个匹配单个字符的解析器:

// 创建一个识别单个字符 c 的解析器.
function char1(c) {
  function char1_parse(state, sok, serr) {
    var stream = state.stream;
    // 如果到了流的末尾, 则发出错误. 错误时回调 serr()
    if (stream.eof())
      return serr('end of stream', state);
    
    // 如果流当前字符/符号不是 c, 则发出错误.
    if (c !== stream.peek())
      return serr('Char ' + c + ' expected', state);
    
    // 移动读取指针, 这里改变了流本身属性, 也有不改变的做法, 以后研究.
    stream.move(1);
    // 正确时调用 sok()
    return sok(c, state);
  }

  return new Parser(char1_parse);
}

 

类 Parser 简而言之是对一个 parse() 函数的包装(以后可以在其实例中存一些别的属性):

function Parser(fn) {
  this.parse = fn;
}

 

简单的 ParseState 类用于包装解析状态, 流等全局数据, 现在只有 stream:

function ParseState(stream) {
  this.stream = stream;
}

 

现在建立一个简单 parser, 并开始调用它.

test('call a parser', function () {
  // 创建解析器: 识别单个字符 `x' 的(最)简单的解析器.
  var x = char1('x');

  // 构造流, 解析状态. 这是为解析做准备工作.
  var stream = new StringStream('xyz'),
    state = new ParseState(stream);

  // 定义当解析正确时的 sok() 回调函数, 缺省行为是返回解析结果.
  function default_sok(result, state) {
    return result;
  }
  
  // 定义当解析错误时的 serr() 回调函数, 缺省行为是抛出异常.
  function default_serr(msg, state) {
    throw new Error(msg);
  }

  // 现在调用 x 解析器:
  var result = x.parse(state, default_sok, default_serr);  

  // 解析结果为 'x', 即 result === 'x'
  assert.equal(result, 'x');
});

其中缺省的 default_sok(), default_serr() 是定义在 test() 外面的, 为方便看, 放在这个代码里面.

上述繁琐的构造 state, 执行过程我们分解到一个 run_parser(p, str) 中, 以后直接调用 run_parser() 即可.

function run_parser(p, str) {
  var stream = new StringStream(str);
  var state = new ParseState(stream);

  return p.parse(state, default_sok, default_serr);
}

 

现在研究几种特定的基本的解析器:

1. 总是正确调用信号函数 sok() 并以给定结果的解析子 always:

function always(result) {
  function always_parse(state, sok, _serr) {
    return sok(result);
  }
  return new Parser(always_parse);
}

test('always', function () {
  var p = always('ALWAYS');

  var result = run_parser(p, 'xyz');
  assert.equal(result, 'ALWAYS');
  // 这里还可断言 stream 指针未改变过, 就不写了...
});

这里从来不会调用 _serr() 信号函数. 也不读取/消耗流中任何数据(解析术语叫 消费 consume).

这种解析子不同的程序中名字不太一样, 有的叫 succeed, 或 of, 或 xxx

 

2. 总是失败调用信号函数 serr() 的解析子 never (别名 fail 等)

function never(msg) {
  return new Parser(function never_parse(state, _sok, serr) {
    return serr(msg, state);
  });
}

test('never/fail', function () {
  var p = never('throwed_message');
  
  assert.throws(function () {
    // 这里抛出异常.
    run_parser(p, 'stream content is not important');
  });
});

与 always() 相对应, 这里总是走 serr() 信号分支, 从不调用 _sok().

 

有了这几个最基本的解析器之后, 我们主要要研究如何组合. 有三种基本的组合符:

1. 连接: p -> a b     即 a 之后跟着 b, 这里 a,b 是解析器, p 是组合之后的解析器

2. 选择: p -> a | b   即 a 或 b. 同样 p 是组合之后的解析器.

3. 闭包: p -> a*      即重复 a 0 次到任意多次.

一些其它运算符(组合)可以从这三者推导出:

   + 运算符   a+ = a a*

   ? 运算符    a? = ε | a 

   {n}            a{n} = a a ... a (重复 n 次)

   {n, m}       a{n, m} = a a ... a (n 个) (ε | a {m-n}) 

 

一. 连接组合符  (p -> a b)  next(别名或变体实现形式 then, chain 等)

// 创建 p -> x y
function next(x, y) {
  return new Parser(function (state, sok, serr) {
    // 先用 x 解析器解析. 这里重点是调用 x 的 sok 换成了 next_sok
    return x.parse(state, next_sok, serr)
    
    // x 解析器正确之后, 再用 y 解析器解析. x 的结果被抛弃, 返回 y 的解析结果.
    function next_sok(_x_result, state) {
      return y.parse(state, sok, serr);
    }
  });
}

test('next', function () {
  var x = char1('x'), y = char1('y'),
    p = next(x, y);
    
  var result = run_parser(p, 'xyz');
  assert.equal(result, 'y');    // 解析 x 之后解析 y, 返回解析结果 'y'
  
  assert.throws(function () {
    run_parser(p, 'abc');   // failed at a!=x
  });
  assert.throws(function () {
    run_parser(p, 'xbc');   // failed at b!=y
  });
});

 

能连接两个, 再组合就能连接更多, 如 :

    p = next(next(x, y), z)   ----- 识别 'xyz'

    p = next(x, next(y, z))   ---- 同样识别 'xyz'

    p = next(next(x, y), next(z, u))     ---- 识别 'xyzu'

 

二. 选择组合符 p -> a | b  (or, 别名 either 等等):

// p -> a | b
function or(a, b) {
  return new Parser(function (state, sok, serr) {
    // 先尝试 a 解析器, serr 换成 or_serr.
    return a.parse(state, sok, or_serr);
    
    // 如果 a 解析失败, 则 `或' b.
    function or_serr(_msg, state) {
      return b.parse(state, sok, serr);
    }
  });
}

test('or', function () {
  var x = char1('x'), y = char1('y'),
    p = or(x, y);  // 构造 p -> x | y
  assert.equal(run_parser(p, 'x'), 'x');   // 可解析 'x'
  assert.equal(run_parser(p, 'y'), 'y');   // 可解析 'y'
  assert.throws(function () { run_parser(p, 'z') });  // 不识别 'z'
});

 

组合更多如 p -> a | b | c                   p = or(or(a, b), c)

     p->a | (b | c)                                p = or(a, or(b, c))

和 next 一起组合更复杂的:

    p -> a b | c d                               p = or(next(a, b), next(c, d))

 

三. 闭包算符 * (名字 many):

为方便测试, 引入一种新的基本解析器 letter, 其识别任意字母.

// 识别单个字符的解析器.
function letter() {
  return new Parser(function (state, sok, serr) {
    var stream = state.stream;
    if (stream.eof()) return serr('end of stream', state);
    var c = stream.peek();
    if (!/[a-zA-Z]/.test(c)) return serr('Letter expected');
    stream.move(1);
    return sok(c);
  });
}

实现 many() 及其测试:

// p -> a*
function many(a) {
  return new Parser(function (state, sok, _serr) {
    var rs = [];
    while (a.parse(state, many_sok, many_serr)) {
      ; // 继续循环
    }
    return sok(rs);  // 返回解析结果, 可能是一个空数组.
    
    // 当 a 解析成功时, 结果收集到 rs[] 数组中.
    function many_sok(result) {
      rs.push(result);
      return true;   // 返回 true 让 while() 循环继续
    }
    function many_serr() {
      return false;  // 返回 false 退出循环.
    }
  });
}

test('many', function () {
  var x = letter(),
    p = many(x);
  var result = run_parser(p, 'xyz+');
  console.log(result);
  assert.equal_array(result, ['x', 'y', 'z']);
  
  assert.equal_array(run_parser(p, '+'), []);
});

 

这里 many() 通过 while 循环不断调用 a, 当 a 成功时结果收集到 rs[] 数组中, 失败时退出循环, 返回 rs[] 解析结果. 就 many() 自身而言, 其永远不会调用 _serr() .

有了 many(), 常见的 p -> a+ 算符可以实现为:

   p -> a+     即   p -> a a*            组合为 p = next(a, many(a))  

当然返回结果需要...一些别的处理方法, 但仅就识别而言, 是这样组合的.

 

=====================================================

一些可选的变体. 为了方便使用, 可以实现一些组合的变体形式.

如 next3(a, b, c) -- 将3个解析器 a,b,c 组合在一起, 不用写 next(next(a, b), c) 了:

function next3(a, b, c) {
  return new Parser(function (state, sok, serr) {
    // 先调用 a 解析器.
    return a.parse(state, a_sok, serr);
    
    // a 成功后, 继续调用 b 解析器.
    function a_sok(_, state) {
      return b.parse(state, b_sok, serr);
    }
    
    // b 成功后, 继续调用 c 解析器.
    function b_sok(_, state) {
      // 最终返回给 sok() 的是 c 解析器的解析结果.
      return c.parse(state, sok, serr);
    }
  });
}

test('next3', function () {
  var x = char1('x'), y = char1('y'), z = char1('z'),
    p = next3(x, y, z);
  var result = run_parser(p, 'xyz');
  assert.equal(result, 'z');
});

 

组合任意数量个 next_n(a, b, c, ...args):

// 组合任意个 p -> a b c ...
function next_n(args) {
  var ps = ([]).slice.call(arguments, 0);  // 先化为数组存起来.
  console.assert(ps.length >= 2);  // 必须组合超过2个.
  if (ps.length === 2) return next(ps[0], ps[1]);  // 2 个的用 next() 组合即可.
  
  return new Parser(function (state, sok, serr) {
    var i = 0;
    return ps[0].parse(state, next_n_sok, serr);
    
    function next_n_sok() {
      ++i;
      if (i === ps.length-1)   // 最后一个.
        return ps[i].parse(state, sok, serr);
        
      // 调用下一个.
      return ps[i].parse(state, next_n_sok, serr);
    }
  });
}

test('next_n', function () {
  var x = char1('x'), y = char1('y'), z = char1('z'), u = char1('u'),
    p = next_n(x, y, z, u);
  var result = run_parser(p, 'xyzu');
  assert.equal(result, 'u');
  assert.equal(run_parser(p, 'xyzu+'), 'u');
});

next 组合任意个, 结果收集到一个数组中的变体:

// 组合任意个, 收集所有结果为数组 rs[]
function next_na() {
  var ps = ([]).slice.call(arguments, 0);  // 先化为数组存起来.
  return new Parser(function (state, sok, serr) {
    var i = 0, rs = [];
    return ps[0].parse(state, next_na_sok, serr);
    
    function next_na_sok(result) {
      ++i; rs.push(result); // 结果收集到 rs[] 数组中.
      if (i === ps.length)  // 最后一个调用了, 结果在 rs[] 中, 返回给 sok().
        return sok(rs);
      // 调用下一个.
      return ps[i].parse(state, next_na_sok, serr);
    }
  });
}
// 测试部分类似于 next_n().

 

next 组合两个 a,b, 但返回 a 的结果, 抛弃b 的结果, 名为 skip:

// 构造 p->a b 但返回 a 的结果, 跳过 b:
function skip(a, b) {
  return new Parser(function (state, sok, serr) {
    return a.parse(state, skip_asok, serr);
    
    function skip_asok(a_result, state) {
      return b.parse(state, skip_bsok, serr);
      
      function skip_bsok(_) {   // b_result 被忽略(跳过)
        return sok(a_result);
      }
    }
  });
}

 

类似的可以有 or_3(), or_n() 等等的变体.

many() 的变体 times(a, min, max), 最少min次, 最多 max次, 即  p -> a{min, max}

// times(a, min, max)   p -> a{min, max}
function times(a, min, max) {
  return new Parser(function(state, sok, serr) {
    var i, rs = [], err_msg;
    // 先重复 a{min} 次. 实现 p -> a{min} (a{max-min} | epsilon) 前面部分.
    for (i = 0; i < min; ++i) {
      // 如果从 min_serr() 中返回 false, 则未能循环满 min 次, 返回错误.
      if (a.parse(state, times_sok, min_serr) === false)
        return serr(err_msg);
    }
    
    function times_sok(result) {
      rs.push(result); return true;  // 收集结果, 返回 true.
    }
    function min_serr(msg) {
      err_msg = msg; return false;   // 保存错误信息, 返回 false.
    }
    
    // 实现后面 a{max - min} | epsilon 部分.
    for (; i < max; ++i) {
      if (a.parse(state, times_sok, max_serr) === false)
        break;  // 如果识别失败, 则相当于匹配 epsilon 部分.
    }
    function max_serr() {
      return false;
    }
    
    return sok(rs);  // 返回最终数组 rs[] 给 sok()
  });
}

test('times', function () {
  var x = char1('x'),
    p = times(x, 3, 5);   // 最少3个x, 最多5个.
  var result = run_parser(p, 'xxxxxxxy');  // 结果为 ['x' * 5]
  assert.equal(result.join(''), 'xxxxx');
  
  result = run_parser(p, 'xxxy');  // 结果为 ['x' * 3]
  assert.equal(result.join(''), 'xxx');
  
  result = run_parser(p, 'xxxxy');  // 结果为 ['x' * 4]
  assert.equal(result.join(''), 'xxxx');
  
  assert.throws(function () {
    result = run_parser(p, 'xxy');    // exception, 不足 3 个 x
  });
});

 

为了方便使用, 还可实现其它种类的组合, 如 chain(), map(), cons() 等等.

 

共有 人打赏支持
粉丝 55
博文 141
码字总数 221359
×
刘军兴
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: