从词法分析到正则表达式（2）

从词法分析到正则表达式（2）

本文所有代码在vs2013下通过编译

从词法分析到正则表达式（1）

完整源码

花了两天完成模式匹配器，虽然过程坎坷，不过当时自信心膨胀，觉得自己可以搞定一切，而自己所写的程序在自己看来也是挺厉害的……

自然而然地，就想到能不能把程序的界面再升级一下，毕竟模式就是通过正则表达式的手段构建的，再写一个函数将正则表达式翻译成模式应该不难，所以就着手去做了。

首先设计所用的正则表达式，除了基本的三个操作 star(*), connect(隐含), either(|) ，还需要通配符 _ ，和转义字符 / （转义字和母语C++的转义字相同简直是失败的不可救药……）。

三个组合手段之间有优先级

* > connect > | 

为了改变组合的优先级，括号 () 也是不可或缺的。

正则解释器

一开始的正则表达式的解释函数 reg_exp 其实相当简单，有一个储存模式的栈，顺序逐个读取字符

• 是 _ 就调用 is_any_char ， is_any_char 很好实现 not_one_of("")
• 是 * 就从模式栈中取出一个模式，用 star 修饰后放回去
• 是 |
  1. 递归调用 reg_exp ，得到 right
  2. 将整个栈用 connect 连接起来，得到 left （最初居然没注意到要把整个栈串起来）
  3. either(left, right) 入栈
• 是 ( 就递归调用 reg_exp ，结果入栈
• 是 ) 就把栈用 connect 串起来，返回
• 是 / 就再读一个字符，入栈
• 其它，入栈

其实可以写成迭代形式的，稍微想了一下，这个其实跟《数据结构》栈那一章所实现的计算器很像，应该可以用同样的方法去除递归。不过真动手的时候，瞬间迷茫，于是作罢。

缺陷

函数写好以后就迫不及待地去写了这种语言的第一个表达式，最简单的那种，字符字面量

…… ……

写不出来，因为不支持否定。

于是如果要求除了 / 之外的字符，就要用 | 把整个字母表除 / 的字符串起来……

在上面的解释器里加入否定：

• 是 ! ,再读一个字符，用 is_not_char 修饰，入栈

经过不断的失败，特别是认识到和母语用同一个转义字的愚蠢后，我终于写出了能运行的字符字面量表达式

'(!//|//_)' 

实际在c++里面是

"'(!////|////_)'" 

接下来把它拓展一下就可以用到字符串字面量上了……不对，又写不出来了……

这次还是否定，因为在字符串字面量里要同时否定两个字符 / 和 " , ! 不够用啊

在解释器的否定里加入：

• 如果 ! 后是 ( ，则读取到 ) ，对读取的串用 not_one_of 修饰，入栈

实际上没有上面这步，因为整个过程中充满了BUG，又穿插着上课，所以思维不太连贯，当时因为某个现在想不起来的BUG彻底绝望了，放弃了继续打补丁。最终决定重写整个正则表达式解析模块。

正则计算器

首先要搞清楚一个概念性的问题，整个表达式的特殊符号分成三类

1. 转义字
2. 拓展符号（“语法糖”）
3. 正则运算符

它们在不同的时候被处理

1. 转义字 在读取原始表达式串时就被处理了，不进入后续计算
2. 拓展符号 表示了原始表达式中的一个特殊子串，内部格式自定，这个子串在解析时和普通字符一样得出一个模式
3. 正则运算符 运算符操作的对象是正则表达式（得出的模式）

另一个棘手的问题是 connect ，因为它是隐含的，不在原始表达式里，但是如果希望用和计算器一样的算法去计算它，就要把它加上。

综上，我对原始表达式增加了一个预处理步骤，将正则表达式自身的单元分割工作和后来的语义识别分开。

预处理的输出是 list<RegToken> , RegToken 即带类型的单元串。

顺带地，预处理还根据相邻Token的类型在 list 中插入 connect 的Token。

list<RegToken> preprocess(const string &primary) { //break to tokens and add connect  list<RegToken> acc;  string::const_iterator iter = primary.begin();  string::const_iterator end = primary.end();  while (iter != end) {   acc.push_back(read_and_tag(iter));  }  list<RegToken>::iterator fst = acc.begin(), snd = acc.begin(); ++snd;  for (; snd != acc.end(); fst = snd, ++snd) {   if (should_insert_connect(fst->second, snd->second)) {    acc.insert(snd, RegToken("", Op_conn));   }  }  return acc; }  

接下来是从 list<RegToken> 到模式的组合过程，跟中缀表达式的计算如出一辄

void zip(stack<Pattern> &operands, stack<RegTag> &ops, RegTag op_now) {  while (ops.size() > 0 && (op_cmp(ops.top(), op_now) > 0)) {   bool test = (op_cmp(ops.top(), op_now) > 0);   switch (ops.top()) {   case Op_star :    zip_star(operands);    break;   case Op_or :    zip_or(operands);    break;   case Op_conn :    zip_conn(operands);    break;   default :    throw "zip : op error";    break;   }   ops.pop();  }  if (op_now == Op_right) {   assert(ops.top() == Op_left);   ops.pop();  }  else {   ops.push(op_now);  } } Pattern calculator(list<RegToken>::const_iterator begin, const list<RegToken>::const_iterator end) {  stack<Pattern> operands;  stack<RegTag> ops;  while (begin != end) {   if (begin->second == Clause) {    operands.push(cal_clause(begin->first));   }   else {    zip(operands, ops, begin->second);   }   ++begin;  }  assert(operands.size() == 1 && ops.size() == 0);  return operands.top(); }  

于是，只剩下将普通字符和拓展格式映射到对应得模式构造器上了。

来自《SICP》的启示

在某节课的走神时，突然《SICP》 4.3节那个神奇的语言模型进入脑海，当时瞬间大脑充血，满脑子都是实现这个模型的好处（非确定性计算，之前star的问题直接不存在）。

不过下课坐在电脑前才发现自己对于如何实现完全没有一点概念，探索了一天，一筹莫展。

第二天的上课例行走神，思路又神奇的回到了这个问题，居然有了思路（只是其中的一点点，毕竟C++不是Scheme）

现在想想，当时完全是大脑充血，加上对自己在干什么不是很清楚。

事后说起来其实相当简单，就是想把递归转成迭代。

经历了很长时间的思考与失败，终于形成了以下的模型

新的Pattern形式

class AbstractPatternClass { public :     virtual Context exec(Cursor &code, std::shared_ptr<AbstractPatternClass> succ, Context fail) = 0; };  typedef std::shared_ptr<AbstractPatternClass> Pattern; 

Context ，上下文类有两类子类，

• 一类是特殊状态标识
• 一类用于运行时（类比为一组寄存器），保存 一个 Cursor 一个 Current 模式（类比于PC寄存器） 一个 succ 模式 一个 fail 上下文

succ和fail代表了计算的两个走向

• 如果当前计算成功，则继续执行succ
• 如果当前计算失败，则执行fail

注意到fail是一个上下文，不需要当前上下文给出运行的信息，而succ是一个模式，它的运行需要指定一些额外的信息以形成自己的上下文。

整理一下思路

初始（待匹配）模式现在被视为一种不变的结构，即代表了一个正则表达式的机器。

我们通过给初始模式三个参数（资源游标 cursor ，成功指示符 succ ，失败指示符 fail ）以启动机器

机器的一个运行时状态由一个上下文表示，而运行本身就是上下文的转换

• 当一次计算顺利进行后，运行的下一步就是由succ指定。

• 而当计算失败，我们在fail里保存了之前某些需要做出选择的地方的其他选择，所以我们跳过去（替换上下文），继续寻找希望。

succ和fail各自有一个终点，也就是在最初启动时给出的那两个。

只要我们给出字符串是有限长的而机器又不会不正常地改变游标，机器就总会运行到两个终点中的一个。（终于找到了希望 VS 彻底没希望了）

基本的模式

template<typename Predicate> struct CharAtom : public AbstractPatternClass { private :  Predicate pred; public :  CharAtom(Predicate pred) : pred(pred) { }  Context exec(cursor_succ_fail) {   if (!cursor.is_end() && pred(cursor.get_char())) {    cursor.step_fore();    return make_run_ctx(cursor, succ, get_epsilon(), fail);   }   else {    return fail;   }  } }; struct CharIsPredicate { private :  const char target; public :  CharIsPredicate(const char &target) : target(target) { }  bool operator () (const char &c) { return c == target; } }; struct EpsilonAtom : public AbstractPatternClass { public :  Context exec(cursor_succ_fail) { return make_run_ctx(cursor, succ, undefined_pattern, fail); } };  

因为抵达基本元素时，如果成功，当前模式被消耗掉，则只剩下succ了，则用epsilon做为其后继（占位）。

而epsilon将undefined_pattern（它会直接返回一个特殊上下文）作为填充，希望永远不会运行至此。（只要初始succ不会返回一个运行状态的上下文）

组合模式

struct StarPatternClass : public AbstractPatternClass { private :  Pattern pattern; public :  StarPatternClass(Pattern pattern) : pattern(pattern) { }  Context exec(cursor_succ_fail) {   // try from the most longest star-pattern   Context directly_go_to_succ = make_run_ctx(cursor, get_epsilon(), succ, fail);   return make_run_ctx(cursor, pattern, connect(star(pattern), succ), directly_go_to_succ);  } };  

组合模式是真正表现Context跳转的地方，star模式会首先将匹配拓展到最大，并在这一过程中扩充失败链（栈），如果后继匹配发生失败，则会（通过返回fail）退回到短一次的匹配成功处继续尝试后继。

通过star其实就可以看出来整个匹配模型其实只是某种形式的递归转迭代+栈（失败链）。也就是说跟之前的版本没有本质差别。

领悟到这一点的时候还是有些失望。

不过下面的函数还是让我有些激动

bool run_loop(Context ctx) {  while (ctx->get_state() == ctx->Running) {   ctx = run_ctx_step_next(ctx);  }  assert(ctx->get_state() != ctx->Undefined);  return ctx->get_state() == ctx->HaltHapply; }  

这就是这一整套机制的表层

bool RegExp::Machine::match_all(const string &source) const {  struct CursorEndPredicate : public CursorPredicate {  public:   bool operator () (Cursor cursor) { return cursor.is_end(); }  };  Context beginning = make_run_ctx(Cursor(source), pattern, get_terminate(new CursorEndPredicate), get_halt_sadly());  return run_loop(beginning); }  

记一些教训

• 虽然都大三了，还是不会很有效率的Debug，记得最开始时的问题是文件读取失败导致的，我花了很久在其它部分
• 在第一个版本里对于代码资源我用的Code（本身保存代码，要求所有改动它的函数引用传递），随后一个Bug是一个函数用了值传递……
• 想当然，在第一个版本要组合一些符号串时我用了for_each,当时想自己写一个通用的累积器，要用到二元函数，然后把binary_function拿来当父类，用ptr_fun转换函数参数，编译时发现没有重载 operator () ，其实问题很明显了，不过我一直没有意识到，最后耐下心来读msdn才发现binary_function本身确实没有重载 operator () ，辜负了我的满心信任……