65.9K
CodeProject 正在变化。 阅读更多。
Home

如何构建一个在运行时生成状态引擎

osy
starIconstarIconstarIcon
emptyStarIcon
starIcon
emptyStarIcon

3.67/5 (9投票s)

2007 年 10 月 28 日

CPOL

3分钟阅读

viewsIcon

33565

downloadIcon

190

一个高效的内存状态引擎的C++模板。

tag tree

摘要

如果你想在一个数据流中检测关键词或特殊标签，你通常会使用像yacc或ANTLR这样的语法分析器生成器。否则，你可以使用正则表达式的强大功能。在某些情况下，手工编写的解析器可以满足需求。为了简化这项任务，我编写了模板tag_tree（作为使用boost的更大库的一部分）来在运行时创建一种内存中的状态引擎。它内存占用低，效率比任何分词器-字符串比较方法都要高。

引言

手写的解析器/扫描器需要很多状态，看起来类似于下面的代码片段

boost::tribool parser::consume(char input)
{
  switch (state_)
  {
  case state_1:
    if (input == 'P')
    {
      state_ = state_2;
      return boost::indeterminate;
    }
    else
    {
      return false;
    }
  case state_2:
    if (input == 'O')
    {
      return true;
    }
    ... <snip> ...
  default:
    return false;
  }
}

这是状态引擎的实现，如果你必须管理很多状态，它很容易出错。它对你的工作很好而且很快，但是修改关键词需要很多工作。下面的代码片段展示了如何使用tag_tree模板来解决这个问题

class parser
{
public:
    ...
    typedef tag_tree < std::string, unsigned >     TagTree_;
    typedef typename TagTree_::MyPtr_    TagTreePtr_;
    
    TagTree_    kt_;
    
};

parser::parser()
    : prev_( NULL )
{
    kt_.insertKeyWord( "POST", 10 );
    kt_.insertKeyWord( "HOST", 20 );
    kt_.insertKeyWord( "XONN", 30 );
}

unsigned parser::run()
{
    TagTreePtr_    prev = &kt_;
    for (;;)
    {
        TagTreePtr_ p = prev->findNode( next() );
        if (p == NULL)
        {
            break;
        }
        prev = p;
    }
    
    return (prev->isLeaf())
        ? prev->getValue()
        : -1;    //! nothing found
}

next()从数据流返回下一个字符。当findNode()正在匹配时，方法继续循环。循环结束后，isLeaf()测试是否找到了有效的关键词，方法返回一个标识符。返回prev指针本身也是完全可能的。prev始终指向一个有效的地址，并包含你需要的所有信息。

它是如何工作的

主要思想是每个关键词都构建一个独特的链接节点的轨迹，其中每个节点代表一个特定的解析器状态。为了构建这个轨迹，将使用一个数组树。下图显示了一个包含关键词PORT和POST的树

tag tree

现在给你一些便利。如果你更重视速度而不是内存，请选择数组的最大大小（例如，对于char为256）。然后选择最简单的哈希算法——ASCII码作为数组索引。为了节省内存，可以缩小数组。但是，然后我们必须管理一个冲突列表。

下载部分有一个名为TagTree的项目，其中包含tag_tree模板更复杂的用法示例。

参考

tag_tree_base

定义一些typedef和所有节点值的方法。tag_tree_base不限于字符串。你可以使用任何定义了const_iterator和value_type类型的类似字符串的容器。

tag_tree_base 构造函数和析构函数

tag_tree_base::tag_tree_base( char_type c );
参数
  • c: 此节点表示的字符。

getValue

value_type & tag_tree_base::getValue();
返回值

此节点的值。

tag_tree 构造函数和析构函数

tag_tree::tag_tree( char_type c );

tag_tree设计用于流式解析器。tag_tree可以帮助你在内存中构建紧凑的状态引擎，因为每个节点都代表一个唯一的状态解析器。

参数
  • c: 此节点表示的字符。

所有指针都设置为NULL是由容器完成的。

findNode

tag_tree::MyPtr_ tag_tree::findNode( char_type c );
参数
  • c: 要查找的字符。
返回值

指向包含指定字符c或NULL的节点的指针。

empty

bool tag_tree::empty     (          )      const;
返回值

如果没有传出的节点指针，则为true。

语义类似于STL - 容器empty()方法。如果节点数组nodeMap_不包含任何指针，那么nodeList_也不应该包含。它应该是一个叶子节点。否则，就出问题了。

leaf_count

size_t tag_tree::leaf_count( bool branch = false )     const;
返回值

从这一点开始的关键词计数。

dump

void tag_tree::dump(     ostream_type_ &      os,
        size_t      depth = 0L,
        size_t      branch = 0L
    )             const;
参数
  • os: 一个打开的输出流，例如std::cout。

打印所有节点及其属性的简单列表。用于调试。

lookUp

tag_tree::lookUp(    char_const_iterator from, char_const_iterator to ) const
参数
  • from: 指向关键词中第一个元素位置的输入迭代器。
  • to: 指向关键词中最后一个元素之后位置的输入迭代器。
返回值

关键词的值。如果关键词不存在，则返回空值。

查找指定的关键词。

历史
  • 2007年10月29日 - 初次发布。
© . All rights reserved.