使用 YARD 解析器实现的正则表达式分词器

• 下载源代码文件 - 68.9 Kb

引言

本文介绍了一个简单的分词器，它使用 YARD（Yet Another Recursive Descent）解析器。我们使用这个分词器来处理一个简单的文本文件，并生成一个单词列表。

分词器

分词器根据一些简单的规则，从输入中创建一个字符串或标记列表。通常，分词器是根据分隔符（即分隔标记的内容，例如逗号或空格）来表达的。相反，我们介绍 YARD 字符串分词器，它允许我们解析可以表示为正则表达式的任何类型的标记。

YARD StringTokenizer 解析器的机制非常简单。它需要将一个正则表达式描述（称为规则）传递给它作为模板参数，以描述要识别的标记。它提供了一个函数，void Parse(char const* pBegin, char const* pEnd)，该函数根据作为模板参数传递的规则生成一个标记列表。例如

  // p is a pointer to a null terminated string
  const char* pEnd = &(p[strlen(p)]);
  StringTokenizer<MatchWord> tknzr;
  tknzr.Parse(p, pEnd);
  OutputTokens(tknzr.begin(), tknzr.end());

为了正常工作，StringTokenizer 需要我们用一个描述每个标记的规则来声明它。我们使用的规则定义在文件 "rules.hpp" 中，如下所示

  typedef MatchCharRange<'a', 'z'> MatchLowerCaseLetter;
  typedef MatchCharRange<'A', 'Z'> MatchUpperCaseLetter;
  typedef re_or<MatchLowerCaseLetter, MatchUpperCaseLetter> MatchLetter;
  typedef re_or<MatchLetter, MatchChar<'\''> > MatchWordChar;
  typedef re_plus<MatchWordChar> MatchWord;

请注意，这些规则是根据其他规则描述的，并使用被称为正则表达式运算符的规则组合在一起。简而言之，它们是

• re_opt<Rule_T> - 匹配 Rule_T 0 或 1 次。
• re_star<Rule_T> - 匹配 Rule_T 0 或多次。
• re_plus<Rule_T> - 匹配 Rule_T 1 或多次。
• re_repeat<Rule_T, N> - 匹配 Rule_T 恰好 N 次。
• re_or<Rule_T0, Rule_T1> - 匹配 Rule_T0，如果失败则匹配 Rule_T1。
• re_and<Rule_T0, Rule_T1 > - 匹配 Rule_T0，然后匹配 Rule_T1。

YARD StringTokenizer 类

这是 StringTokenizer 类和辅助类的源代码

  typedef std::pair<char const*, char const*> Token;
  typedef std::list<Token> TokenList;
  typedef TokenList::const_iterator TokenIter;

  template<typename Rules_T>
  struct StringTokenizer
  {
    void Parse(char const* pBegin, char const* pEnd)
    {
      ParserInputStream<char> stream(pBegin, pEnd);
      while (!stream.AtEnd()) {
        char const* pos = stream.GetPos();
        if (Rules_T::Accept(stream)) {
          mTkns.push_back(Token(pos, stream.GetPos()));
        }
        stream.GotoNext();
      }
    }
    TokenIter begin() { return mTkns.begin(); }
    TokenIter end() { return mTkns.end(); }
  private:
    TokenList mTkns;
  };

输出标记

一旦解析了文本文件，我们仍然需要对标记做一些处理。这里有一个函数，它将前 10 个标记作为字符串输出到标准输出流

  void OutputTokens(TokenIter iter, TokenIter end)
  {
    // outputs first 10 tokens as strings
    for (int i=0; (i < 10) && (iter != end); i++, iter++) {
      int n = iter->second - iter->first;
      std::string s(iter->first, 0, n);
      std::cout << s.c_str() << std::endl;
    }
  }

摘要

这就是整个库的概括。分词器只是 YARD 库可以做的冰山一角。尽情尝试解析器，您可能会对可以将其应用于的任务感到惊讶。

Postscript

值得一提的是 Boost Spirit 库，它具有与 YARD 解析器相同的一些功能。使用 Spirit 编写类似的分词器可以如下进行（注意：我不是 Spirit 的专家，它不是一个下午就能学会的工具）

  #include <boost/spirit/core.hpp>
  #include "../yard/tokenizer.hpp"

  using namespace boost::spirit;
  using namespace yard;

  TokenList* gpTkns;

  void StoreToken(char const* str, char const* end) {
    gpTkns->push_back(Token(str, end));
  }

  void SpiritTest(char const* str, TokenList* pTkns) {
    gpTkns = pTkns;
    rule<> word_r = (alpha_p >> *(alpha_p | ch_p('\'')));
    rule<> r = *(word_r[&StoreToken] | space_p);
    parse(str, r);
  }

Spirit 库的设计采用了完全不同的方法，并且比 YARD 解析器复杂得多。另一方面，一旦你弄清楚如何使用它，它就自带了更多的功能。无论如何，选择权在你手中，祝你解析愉快。