TPL: 一个新的C++正则表达式(regex)库

概要

C++ 中正则表达式(regex)库已经很多。光 boost 中就有3个:regex、spirit、xpressive。那么我们为什么还需要一个新的呢?

多数正则表达式库都需要一个编译(compile)过程。即:通过解释一个正则表达式的字符串(pattern)来生成该正则表达式的内部表示(字节码)。例如 boost regex 就是这样。这类我们称之为动态正则表达式库。

spirit、xpressive 例外。他们直接通过重载 C++ 的操作符来表达一个正则表达式。在你用C++语法描述完一个正则表达式,它已经是内部表示(被C++编译器编译成了机器码)。这一类我们称之为静态正则表达式库。

静态正则表达式库的好处主要有二:

  • 性能好。由于匹配代码直接编译成为了机器码,故此通常性能会好过动态的正则表达式。
  • 与 C++ 语言可形成良好的互动。可以非常容易在正则表达式中获得执行C++代码的时机。

缺点:

  • 正则表达式必须在编译期确定。如果你希望用户可以输入一个正则表达式,那么静态正则表达式库不能直接满足你的需求。

TPL 属于静态正则表达式库。本文也不准备讨论动态正则表达式。需要指出,xpressive 既支持动态正则表达式,也支持静态的正则表达式,但是我们并不考虑其动态正则表达式部分。

TPL 全称为 Text Processing Library(文本处理库)。spirit、xpressive 是很好的东西,实现 TPL 库中对这两者有所借鉴。

说起来开发 TPL 库的理由看起来挺好笑的:原因是 spirit、xpressive 太慢。不是执行慢,而是编译慢。我的机器算起来也不算差,但是每次修改一点点代码,编译过程都等待半天,实在受不了这样的开发效率。

从机理上讲,TPL 并无特别让人振奋之处。该有的 spirit、xpressive 相信都有了。三者都基于“表达式模板(Expression Templates)” 这样的技术。

闲话少说,这里给几个实际的样例让大家感受下:

样例一:识别以空格分隔的浮点数并放入vector中

代码:tpl/test/testtpl/Simplest.cpp

#include 
#include <tpl/RegExp.h>
 
using namespace tpl;
 
// What we use:
//    * Rules: /assign(), %, real(), ws()
//    * Matching: tpl::simple::match()
 
void simplest()
{
    std::vector<double> values; // you can change vector to other stl containers.
 
    if ( simple::match(
        "-.1 -0.1 +32. -22323.2e+12",
         real()/assign(values) % ws()) )
    {
        for (
            std::vector<double>::iterator it = values.begin(); 
            it != values.end(); ++it)
        {
            std::cout << *it << "\n";
        }
    }
} 

输出:

-0.1
-0.1
-32
-2.23232e+016 

解释:

以上代码我相信比较难以理解的是 / 和 % 算符。

/ 符号我称之为“约束”或“动作”。它是在一个规则(Rule)匹配成功后执行的额外操作。这个额外的操作可能是:

  • 使用另一个Rule进行进一步的数据合法性检查。
  • 赋值(本例就是)。
  • 打印调试信息(正则表达式匹配比较难以跟踪,故此 Debug 能力也是 TPL 的一个关注点)。
  • 其他用户自定义动作。

% 符号是列表算符(非常有用)。A % B 等价于 A (B A)* 这样的正则表达式。可匹配 ABABAB..A 这样的串。一个典型案例是用它匹配函数参数列表。

样例二:识别以逗号分隔的浮点数并放入vector中

代码:tpl/test/testtpl/SimpleGrammar.cpp

// A simple grammar example.
 
// What we use:
//    * Rules: /assign(), %, real(), gr(','), skipws()
//    * Matching: tpl::simple::match()
 
void simple_grammar()
{
    simple::Allocator alloc;
 
    std::vector<double> values; // you can change vector to other stl containers.
 
    if ( simple::match(
        " -.1 , -0.1 , +32. , -22323.2e+12 ",
        real()/assign(values) % gr(','), skipws(), alloc) )
    {
        for (
            std::vector<double>::iterator it = values.begin();
            it != values.end(); ++it)
        {
            std::cout << *it << "\n";
        }
    }
} 

输出:与样例一相同。

解释:尽管看起来好像没有发生太大的变化。但是这两个样例本质上是不同的。主要体现在:

  • 正则表达式的类型不同。real()/assign(values) % ws() 是一个Rule。而 real()/assign(values) % gr(',') 是一个 Grammar。简单来说,Rule 可以认为是词法级别的东西。Grammar 是语法级别的东西。Grammar 的特点在于,它匹配一个语法单元前,总会先调用一个名为Skipper的特殊Rule。上例中 Skipper 为 skipws()。
  • 两个 match 的原型不同。第一个match的原型是:match(Source, Rule), 第二个match的原型是:match(Source, Grammar, Skipper, Allocator)。

第二个例子如果用 Rule 而不是用 Grammar 写,看起来是这样的:

if ( simple::match(
    " -.1 , -0.1 , +32. , -22323.2e+12 ",
    (skipws() + real()/assign(values)) % (skipws() + ',')) ) ... 

你可能认为这并不复杂。单对这个例子而言,确实看起来如此。但是如果你这样想,不妨用 Rule 做下下面这个例子。

样例三:运算器(Calculator)

功能:可处理+-*/四则运算、()、函数调用(sin, cos, pow)。代码:tpl/test/testtpl/Calculator2.cpp (呵呵,只有60行代码哦!)

#include 
#include <tpl/RegExp.h>
#include <tpl/ext/Calculator.h>
#include <cmath>
 
using namespace tpl;
 
void calculate2()
{
    typedef SimpleImplementation impl;
 
    // ---- define rules ----
 
    impl::Allocator alloc;
 
    std::stack<double> stk;
 
    impl::Grammar::Var rFactor;
 
    impl::Grammar rMul( alloc, '*' + rFactor/calc<std::multiplies>(stk) );
    impl::Grammar rDiv( alloc, '/' + rFactor/calc<std::divides>(stk) );
    impl::Grammar rTerm( alloc, rFactor + *(rMul | rDiv) );
 
    impl::Grammar rAdd( alloc, '+' + rTerm/calc<std::plus>(stk) );
    impl::Grammar rSub( alloc, '-' + rTerm/calc<std::minus>(stk) );
    impl::Grammar rExpr( alloc, rTerm + *(rAdd | rSub) );
 
    impl::Rule rFun( alloc, 
        "sin"/calc(stk, sin) | "cos"/calc(stk, cos) | "pow"/calc(stk, pow) );
 
    rFactor.assign( alloc, 
        real()/assign(stk) |
        '-' + rFactor/calc<std::negate>(stk) |
        '(' + rExpr + ')' |
        (gr(c_symbol()) + '(' + rExpr % ',' + ')')/(gr(rFun) + '(') |
        '+' + rFactor );
 
    // ---- do match ----
 
    for (;;)
    {
        std::string strExp;
        std::cout << "input an expression (q to quit): ";
	if (!std::getline(std::cin, strExp) || strExp == "q") {
		std::cout << '\n';
		break;
	}
 
        try {
            while ( !stk.empty() )
                stk.pop();
            if ( !impl::match(strExp.c_str(), rExpr + eos(), skipws(), alloc) )
                std::cout << ">>> ERROR: invalid expression!\n";
            else
                std::cout << stk.top() << "\n";
        }
        catch (const std::logic_error& e) {
            std::cout << ">>> ERROR: " << e.what() << "\n";
        }
    }
}
 
// ------------------------------------------------------------------------- 

解释:

  • Grammar::Var 用于定义一个未赋值即被引用的Grammar。相应地,我们也有 Rule::Var。
  • gr(Rule) 是将一个 Rule 转换为 Grammar。
  • SimpleImplementation 是什么?嗯,这个下回聊。
  • 并不属于 tpl regex 库。代码也不多。参见:tpl/ext/Calculator.h

TPL的样例See http://winx.googlecode.com/svn/trunk/tpl/examples/.

目前 tpl/RegExp.h (正则库)相关的样例有:

simplest: 最简单TPL样例,类似Hello, world! grammar: 还是简单样例,稍微加了点复杂性。 urlparams: 用TPL分析url参数。即prop1=val1&prop2=val2&prop3=val3… calculator: 用TPL实现一个计算器。支持+-*/、()、sin/cos/pow/max removecomments: 删除C++代码中的注释。 removecomments2: 还是C++代码中的注释。但是使用了tpl/c/Lex.h扩展模块。 includefiles: 提取C++源文件中的include文件列表。可改善下做代码依赖关系的定性分析。 目前 tpl/Emulator.h (虚拟机)相关的样例有:

emulator: 演示我们的虚拟机汇编指令。 variant: 演示虚拟机的类型系统。 TPL工程主页及下载地址主页:http://code.google.com/p/libtpl/ 下载地址:http://code.google.com/p/libtpl/downloads/list 文章出处:http://www.diybl.com/course/3_program/c++/cppsl/2008625/128227.html

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏点滴积累

geotrellis使用(三十)使用geotrellis读取PostGIS空间数据

前言 最近事情很多,各种你想不到的事情——such as singing and dancing——再加上最近又研究docker上瘾,所以geotrellis看...

45870
来自专栏一个番茄说

一个extension让你在Swift中用NSTimer更少操心

它会持有target的引用计数,不出意外的话你的target还会持有它的引用计数。另外,还会被runloop持有它的引用计数。

9110
来自专栏程序你好

.Net中Finalize()和Dispose()有什么区别?

11320
来自专栏Golang语言社区

GO语言标准库概览

在Go语言五周系列教程的最后一部分中,我们将带领大家一起来浏览一下Go语言丰富的标准库。 Go标准库包含了大量包,提供了丰富广泛的功能特性。这里提供了概览仅仅是...

29640
来自专栏编码小白

tomcat源码解读二 tomcat的生命周期

1    生命周期 1.1    观察者模型 tomcat生命周期采用了观察者模式,所以在介绍生命周期的时候不得不介绍观察者模式 观察者模式定义了对象间的一种一...

47160
来自专栏Java成长之路

折半查找法

这个程序用while循环也行,好像while循环看上去更规范,下面写上while循环的示例(来自百度百科):

30320
来自专栏Golang语言社区

GO语言标准库概览

在Go语言五周系列教程的最后一部分中,我们将带领大家一起来浏览一下Go语言丰富的标准库。 Go标准库包含了大量包,提供了丰富广泛的功能特性。这里提供了概览仅仅是...

76860
来自专栏开源优测

[接口测试 - 基础篇] 11 掌握下python解析YAML格式也是需要的

什么是YAML YAML参考了其他多种语言,包括:XML、C语言、Python、Perl以及电子邮件格式RFC2822。 Clark Evans在2001年5月...

38270
来自专栏Golang语言社区

GO语言标准库概览

在Go语言五周系列教程的最后一部分中,我们将带领大家一起来浏览一下Go语言丰富的标准库。 Go标准库包含了大量包,提供了丰富广泛的功能特性。这里提供了概览仅仅是...

402100
来自专栏逸鹏说道

C# 温故而知新:Stream篇(六)

BufferedStream 目录: 简单介绍一下BufferedStream 如何理解缓冲区? BufferedStream的优势 从BufferedStre...

35550

扫码关注云+社区

领取腾讯云代金券