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

快速分词器

Alexander Berthold
starIconstarIconstarIconstarIcon
emptyStarIcon
starIcon

4.71/5 (9投票s)

2001 年 4 月 19 日

6分钟阅读

viewsIcon

81070

downloadIcon

1454

C++ 的快速分词器 - 类似于 'lexx'。

Sample Image - cpLexxer.gif

引言

作为我正在进行的一个相当大的项目的一部分，我需要一个快速分词器。我可以使用“lexx”，但它会生成相当难看的 C 代码。所以我决定自己写一个分词器——这个项目。

该项目是一个快速词法分析器/分词器，应该非常易于使用。演示应用程序允许用户输入一些文本，并扫描其中预定义的一组可供计算器使用的标记。

该代码使用了 STL，在警告级别 4 下应该能很好地编译。Unicode 编译也应该可以工作——下载中的所有项目都定义了构建配置“Debug”/“Release”以及“Debug Unicode”/“Release Unicode”。

如果您发现错误，请除了在本文章的论坛上发表评论外，还请给我发送电子邮件：alexander-berthold@web.de。

项目

项目工作区包含三个子项目（仅源代码下载中只有两个，其中省略了lexxerDlgTest）

  • lexxer - 主项目
  • tkCommon - 包含lexxer使用的一些共享基类
  • lexxerDlgTest - 示例 MFC 基于对话框的应用程序

lexxer项目编译成一个静态库，但这些类也可以直接使用。由于该项目是一个更大项目的一部分，您可能会发现某些部分有点“过度编码”——但大多数情况下，性能不会因此受到影响。

用法

我认为在展示如何使用该包的代码片段之后，对这些类的解释会更容易理解。分词器的输出会发送到一个类型为cooLexxerListener的回调类，所以我们从它开始

class cooMsgBoxListener : public cooLexxerListener
{
// Operations
public:
    // The next two methods are inherited from ctkCheckValid, see below
    virtual bool fCheckValid() const   { return true; };
    virtual bool fShouldDelete() const { return false; };

    virtual void vRegisterToken(const std::tstring& strTokenText,
                                const cooLexxerTokenRule* pptrRule)
        {
        CString strTemp;
        if(pptrRule!=NULL)
            {
            strTemp.Format("(%d): %s",pptrRule->nGetIDValue(),strTokenText.data());
            ::MessageBox(NULL,strTemp,_T("Token recognized"),MB_OK);
            }
        else
            {
            ::MessageBox(NULL,strTokenText.data(),_T("Token not recognized"),MB_OK);
            }
        }
};

如您所见，这个类除了简单地为每个标记显示一个消息框之外，什么也没做。现在是分词器的规则

void test()
    {
    std::tstringstream  strm(_T("[seperators]\n")
                             _T("100:,\n")
                             _T("101:;\n")
                             _T("[tokens]\n")
                             _T("200:empty\n")
                             _T("201:blank\n")
                             _T("[rules]\n")
                             _T("300:strings\n")
                             _T("301:numbers\n")

    cooLexxerMap                map(strm);

这意味着

  • 标记“,”和“;”可以出现在输入流的任何位置
  • 标记“empty”和“blank”只能作为整个单词出现
  • “strings”和“numbers”指的是预定义规则。

数字是分配给标记的 ID。vRegisterToken的参数pptrRule通过pptrRule->nGetIDValue()携带此 ID。

下一部分是实际的工作

    cooLexxerTextInputStream    tis(_T("100,empty,blank;blanky"));
    cooMsgBoxListener           lis;
    cooLexxer                   lexxer(&tis,&map,&lis);

    // Initialize map
    map.vLoadFromStream(strm);

    // Tokenize ...
    while(!tis.fIsEofReached())
        lexxer.vParseCharacter();
    }

这将导致六个标题为“Token recognized”的消息框——分别对应“100”，...，“blank”，“;”，然后是一个“Token not recognized”消息框。

关于分词器设置字符串的更多细节

正如您在上面的示例中看到的，词法分析器映射是从字符串初始化的。格式如下

[seperators]
{id}:{text}
...
[tokens]
{id}:{text}
...
[rules]
{id}:strings and/or
{id}:numbers

每个标记前面的数字 {id}，以后可以由 cooLexxerListener 派生类用来识别标记的类型。请参阅上面的示例代码 (pptrRule->nGetIDValue)。

[seperators] 部分列出了所有可以在输入流中任何位置出现并因此作为分隔符的标记。举一些 C++ 的例子，这可以是“++”或“+=”或“?”。

[tokens] 部分列出了所有只能作为整个单词出现的标记。在 C++ 中，例如“for”、“if”甚至是“while”。这些不能出现在其他文本中。在示例中，“forwhile”将是一个未定义的标记，而不是“for”后面跟着“while”。

最后一个部分 [rules] 目前最多只能有两个条目：strings 和 numbers。strings 表示将类 cooLexxerStringTokenRule 包含到分词器中（有关更多说明请参阅代码），而 numbers 表示 cooLexxerNumberTokenRule。cooLexxerStringTokenRule 识别形式为“text”的字符串，其中文本也可以包含 C++ 中常见的转义序列（有一些例外）。cooLexxerNumberTokenRule 只识别数字，目前没有花哨的功能（即没有 0x...）

类

首先：源代码意在有良好的文档，所以如果这里的一些信息有点肤浅，请原谅我。如果有些部分难以理解，请告诉我。

lexxer项目的主要类是cooLexxer。它提供了以下公共方法

cooLexxer::cooLexxer(cooLexxerInputStream *plisData,
                     cooLexxerMap *plmTokenMap,
                     cooLexxerListener *pllReceiver);

void cooLexxer::vParseCharacter();

构造函数接受三个参数。第一个参数是 cooLexxerInputStream 类型，顾名思义，它为词法分析器提供输入。有关如何实现派生自 cooLexxerInputStream 的类的示例，请参阅 lexxer 项目中的 cooLexxerTextInputStream 类。

第二个参数更有趣。cooLexxerMap 包含令牌的映射（更像一棵树）。

假设映射为空，并且您添加了一个像上面示例中那样的令牌“blank”。那么根级别的映射只包含一个节点，一个“b”。这个节点只有一个子节点，一个“l”。这会一直持续到“k”出现，它是一个叶子。

现在你添加另一个令牌，“blanky”。这将遵循相同的路径直到再次遇到“k”，但会添加另一个子节点，“y”。这个节点现在也是一个“叶子”，这意味着这将是一个完整的令牌。

现在，如果输入流包含一个“b”，分词器会识别出这是一个至少一个令牌的有效开头。继续使用“l”、“a”、“n”、“k”，没有字符违反顺序，但这两个令牌仍然可以匹配模式。下一个字符将决定是识别出“blank”令牌还是“blanky”令牌。

如您所见，这只需要一次匹配一个字符——而不是整个字符串。

最后一个参数是“监听”分词器输出的类。纯虚基类 cooLexxerListener（它本身派生自 ctkCheckValid 和 ctkExternalObjectPointer，见下文）定义了方法

virtual	void cooLexxerInputStream::vRegisterToken(
                 const std::tstring& strTokenText,
                 cooLexxerTokenRule* pltrRule) = 0;

并且每当识别出一个令牌时，都会由 cooLexxer 调用。

工具包类

tkCommon 项目定义了以下部分虚基类（以及其他一些不相关的类）

  • ctkCheckValid
  • ctkExternalObjectPointer

ctkCheckValid 定义了用于调试支持和一致性检查的方法。它包含以下方法

  • bool fCheckValid() const
    如果类处于一致状态，则应返回true。

  • static bool fRunDiagnostics()
    应该运行类的自诊断。由于此方法是静态的，因此它不能是虚函数，尤其是纯虚函数，所以它只是一个蓝图。目前 cooLexxer、cooLexxerContext 和 cooLexxerMap 正确地实现了此方法。

另一个类 - ctkExternalObjectPointer - 只定义了一个方法

  • bool fShouldDelete() const

如果指向此类的指针在包含它的对象被销毁时应该被删除，则此方法必须返回 true。

更多内容即将推出 ...

以下是我现在想到的待办事项列表

  1. 目前该项目依赖于 MFC。它们不直接使用 MFC，只使用堆调试功能。我计划移除 MFC 依赖，并将其替换为原生 API。
  2. 更新 cooLexxerNumberTokenRule 以正确处理浮点值和十六进制/八进制表示法。我计划在 2001 年 5 月内完成。
  3. 添加另一个类来正确处理字符常量（'x'）。
  4. 修复错误 :)

如果有人发现 bug，我会尽快更新这个页面。我也会在这里和我的主页 absd.hypermart.net 上发布增强功能（即将推出）。

在我们正在进行的大项目中，我们目前正在完成一个像“yacc”一样的语法分析器——带有一些改进，例如使用 C++ 而不是 LARL(1) 分析器——（以及一个大缺点：它会有更多的 bug…… :-）。它还具有使用优先级规则自动构建分析树以及更多巧妙功能。我们不能也**不会**免费提供，但如果有人感兴趣，我们可以提供一个不带源代码的库。您可以免费在免费软件项目中使用该库——我们将从错误报告中受益。如果您感兴趣，请给我发邮件：alexander-berthold@web.de。

© . All rights reserved.