LTTL：那个能干的小文本转换语言

• 下载源代码 - 294.9 KB

引言

The Little Text Transform Language (LTTL，读作“little”) 允许你的应用程序用户输入一个简单的公式，该公式可以转换一个或多个输入值以生成一个输出文本片段。你定义输入值；唯一真正的要求是每个输入值都有一个名称并且可以转换为字符串。该公式被编译成内部表示，这允许你使用 LTTL 处理大量记录，而无需为每一条记录都经历解析过程。

背景

LTTL 源于我在公司内部调试工具中添加的一个功能。该工具记录了一组分布式服务和应用程序的网络消息。每条消息都包含几个固定用途的字段和一个自由格式的文本字段。我们经常需要从这些记录的消息中提取数据用于分析或文档。提取过程很麻烦，需要反复使用文本编辑器、在 Excel 中编写复杂的公式，或者两者兼而有之。我们需要一种简单的方法来识别我们想要的部分，提取感兴趣的片段，并将它们组合成有用的格式。

这篇文章讲述了我如何实现 LTTL 的故事，就像它讲述 LTTL 本身一样。由于这不是为一个特定产品编写的代码，并且我一部分时间是在业余时间完成的，事情变得有点失控。我发现我必须定义一个 语法[^]。该语法定义了标记和它们之间的关系。如果你想在语言中添加括号表达式（我确实加了），你就会谈论“LL(k) 解析器[^]”、“递归下降解析[^]”和“抽象语法树[^]”。

“但我并不害怕！”
“你会的……你会会的。”

当我处理一个问题时，大多数时候我从我所知道和理解的开始，向着我不知道的领域前进。我采取的一些步骤在你看来可能顺序颠倒。

第 0 步：寻找缩写词 (*)

我小时候，我最喜欢的故事之一是 'Watty Piper'（Arnold Munk 的笔名）创作的 《汽笛小火车》[^]。在我进行这个项目时，我突然觉得一个“小”语言会很有用，我的大脑就联想到了这个，就这样了。(*) 这实际上是最后一步，但在这里讨论更有意义，而且它也解释了测试程序的图标。

第 1 步：定义语法

你们中的许多人会引用那些久经考验的工具来完成这些任务：lex、yacc、Bison 等等。这些工具都有一个明显的学习曲线，而且文献大多侧重于一种工具或一种方法相对于另一种方法的学术价值。大多数工具都基于“C”，而我想要一些不需要三层指针间接寻址才能找到任何东西的东西。实用的建议似乎很难找到。我带着我可靠的 KISS（ KISS 原则：保持简单、愚蠢）原则，开始动手了。

当我们手动编辑数据时，总是那样：找到我们想要的文本，提取它，查找/替换某些部分，然后添加一些固定文本。我年纪大了，所以我记得用过很多命令行编辑器：TECO[^]、EDLIN[^] 等等。从那段经历中，我为我的语言提出了非常简单的要求。保持语法尽可能少，因为这是为了一个被使用然后不再需要时就被丢弃的东西。我不想让用户觉得这是编程，而更像是输入电子表格单元格中的公式。使其易于以区分大小写或不区分大小写的方式处理文本。

公式语法

e1 e2 ...
... eN

就是这么简单。一个公式是一个或多个表达式（e1 到 eN），用空格、制表符或换行符分隔。公式中的换行符按原样传递到输出。什么是表达式？你问得真巧。LTTL 表达式是变量名或常量字符串，可以选择性地与运算符和任何必需的操作数结合。该定义是递归的，因为操作数可以是其他表达式。

变量

在我最初的应用程序中，我有一个“变量”列表，它们是每条消息字段的名称。因为我知道使用这些的人没有耐心键入“Connection”或“EventTime”，所以我为每个项目提供了单个或两个字符的同义词。我还将变量名匹配设置为不区分大小写，因为否则会很麻烦且吹毛求疵。

旁注：对于演示/测试程序，我定义了六个变量：alpha（同义词“A”；纯文本）、beta（“B”；纯文本）、gamma（“G”；一个 int）、delta（“D”；一个 double）、epsilon（“E”；一个 enum）和 zeta（“Z”；一个 bool）。我将在接下来的讨论中使用它们。

常量

我需要的另一件事是常量文本：插入到从变量中提取的项目之间、搜索文本等文本。双引号界定“区分大小写”的常量，单引号标记“不区分大小写”的常量。事实证明，这不足以满足我处理大小写敏感性的需求，但稍后我们会讲到。我为单引号、双引号、回车符和换行符添加了转义序列。后两者不严格必需，但添加它们很容易，并且可能使某些公式更容易阅读。

运算符

当我刚开始这个项目时，我有一个模糊的想法，认为一个公式是一个或多个由空格分隔的“表达式”，这些表达式被求值以生成输出文本。我的第一个尤里卡时刻是当我意识到我已经有了第一个运算符：空格字符实际上是连接运算符。为了不矫枉过正，我决定多个连续的空格或制表符意味着一次连接操作。如果我们的 alpha 变量是“Little”，beta 是“Transform”，公式是

"LTTL: " alpha " Text " beta " Language"

那么输出将是

LTTL: Little Text Transform Language

第二个运算符是提取：在值中查找一段文本，从开始位置开始，提取字符直到找到结束位置。听起来很简单，对吧？提取部分很容易。指定开始和结束位置是难点。有时你知道从开始处开始的确切字符数，以及要提取的字符数。其他时候，你需要先找到一个字符串，然后移动几个字符，然后提取直到找到另一个字符串。可能需要几个步骤才能在数据中找到位置。考虑到这一点，我得出了提取运算符的以下语法

expr.b.e

开头的 expr 是你想要从中提取文本的源。它可以是变量名、常量或语言中的另一个表达式。句点“.”是提取运算符。b 值指示如何查找提取的开始点，其中开始位置为零。如果 b 是正数，则表示字符串开头的偏移量。如果 b 是双引号字符串“like this”，LTTL 将向前搜索以进行区分大小写的匹配。同样，如果 b 是单引号字符串“like that”，LTTL 将使用不区分大小写的匹配。字符串位置搜索包括搜索字符串作为提取结果的一部分。值 e 具有相同的语法，但使用 b 位置作为起始点。表达式的结果是开始和结束位置之间的文本。

我添加了明显的快捷方式：expr.b 从开始点 b 提取到 expr 值末尾的文本。expr..e 从 expr 的开头提取到结束点 e。请注意，这与指定公式 expr.0.e 相同。

使其灵活的关键是允许多个 b 和多个 e 值，并按顺序应用它们。最终的语法是

expr.b[;b][;b][.e][;e][;e]

分号分隔连续的 b 和 e 值。有点难看，但举个例子会更清楚。假设 alpha 变量包含

Sequence number: 1365
CommandID: OpenDevice
Message: "File opened successfully."

而公式是

alpha."CommandID:";10."\r\n";-2 " = " alpha."Message";"\"";1."\"";-1

你可以这样理解这个公式

1. 从 alpha 变量的开头开始。
2. 搜索直到找到“CommandID:”为止。
3. 向前移动 10 个字符。
4. 从这里提取到当前行的末尾。向后退两个字符以省略换行符。
5. 添加“ = ”到输出。
6. 从 alpha 变量的开头开始。
7. 搜索直到找到“Message”。
8. 搜索直到找到开引号。
9. 向前移动一个字符以跳过开引号。
10. 提取直到找到闭引号。向后退一个字符以省略引号。

评估后，将产生以下输出

OpenDevice = File opened successfully.

我真正需要的另一个运算符是替换：给定一个表达式，将所有出现的字符串替换为另一个字符串

expr*f[*r]

其中 expr 是文本的源，* 是替换运算符，f 是要查找的文本的表达式，r 是替换文本的表达式。请注意，第二个替换运算符和替换表达式是可选的。这意味着你可以使用替换运算符从表达式中删除给定字符串的所有出现。

接下来是“C”条件运算符的有限形式

e1 comparison e2 ? e3 [: e4]

或

e1 ? e3 [: e4]

其中 e1、e2、e3 和 e4 是表达式。比较运算符可以是 ==、!=、<、<=、>、>=。我还定义了两个新的比较：^（包含）和 !^（不包含）。当 e2 表达式出现在 e1 中时，包含比较求值为 true。如果任一操作数被标记为不区分大小写，则包含匹配使用不区分大小写匹配。

与“C”和 C++ 不同，“else”子句 : e4 是可选的。没有逻辑运算符（AND 和 OR）。你可以通过使条件运算符的“then”子句成为另一个条件运算符来实现逻辑 AND 的效果。逻辑 OR 只是两个顺序的条件运算符。

条件运算符的第二种形式是另一种快捷方式。如果表达式 e1 非空，则生成表达式 e3，否则生成表达式 e4。

LTTL 中的表达式可以是变量、常量、运算符表达式之一，或者是由空格、制表符或换行符分隔并用括号 ( 和 ) 包围的这些元素的组合。如果你在 LTTL 表达式前面加上加号 (+) ，它将被视为区分大小写；如果你加上减号 (-)，它将被视为不区分大小写。

第 2 步：定义接口

我希望 LTTL 的接口尽可能简单，并隐藏实现细节。另一个设计目标是所有错误都在“编译”阶段检测到，即在公式被解析成内部表示时。我的用例是定义一次公式，但多次求值。在求值时发出错误信号会很令人讨厌。在求值时的最坏情况行为是返回一个空字符串。

namespace LTTL
{
    class Variables
    {
    public:
    
        Variables()
        { };
        
        virtual ~Variables()
        { };
        
        virtual const CStringArray& Names() = 0;
        
        virtual CString Evaluate(void *context,CString name) = 0;
    };

    class Expression;

    class Formula
    {    
    public:
    
        Formula();
        virtual ~Formula();
    
        bool Define(CString definition,
                    Variables *variables);

        CString Error();
        int ErrorOffset();
        
        CString Evaluate(void *context);
    
    protected:
    
        CString                 _Definition;
        Variables               *_Variables;
        
        CString                 _Error;
        int                     _ErrorOffset;
    
        Expression              *_Group;
    };
};

边栏：是的，我正在使用 MFC 的 CString 和集合类。我的目标环境是一个古老的 MFC 应用程序。将代码重构为使用 STL 或其他库相对容易。

你提供一个派生自抽象 Variables 类的实例。Names() 成员返回你希望支持的变量名称数组。Evaluate() 成员由 LTTL 调用以根据 context 值求值指定的变量，并返回变量的字符串形式。由于特定值的名称识别完全取决于你，因此你可以为同一个值提供多个名称。我用它来提供更短的“同义词”名称。

Formula 类是 LTTL 的实现。将公式定义（用户提供的字符串）和你的变量传递给 Define() 成员。如果定义有效，它返回 true，否则返回 false。如果 Define() 返回 false，你可以使用 Error() 和 ErrorOffset() 成员来检索问题的描述及其相对于定义字符串开头的偏移量。我在测试程序中使用了这个来在定义下方显示消息，并将光标重新定位到定义编辑控件的问题位置。

你调用 Evaluate() 成员来根据提供的上下文求值字符串。上下文值是一个 void 指针，LTTL 将其视为不透明。通常，这将是一个指向类的指针，该类包含你 Variables 实现中定义的变量的实际值。在测试程序中，Variables 实现和上下文由同一个类提供。这不是必需的；你可以使用任何适合你需求的方法。Evaluate() 返回一个字符串。最坏情况的返回值是一个空字符串（""）。

你会注意到，底层实现唯一暴露的地方是在 Expression 类的前向声明以及指向其实例的指针的受保护成员。

第 3 步：组织实现

我的“编译”过程的第一步是将字符串定义转换为标记列表，因此我知道我需要一个 Token 类。为表达式（自然称为 Expression）设置一个基类，并从该基类派生每种特定的表达式类型似乎也很合理。我选择在内部使用异常来处理错误。考虑到这段代码在某个时候将是递归的，并且逻辑上也很“密集”，这似乎是合适的。

与常规最佳实践不同，我决定将整个实现放在一个 .cpp 文件中。内部类定义与其声明内联。我这样做是为了方便将 LTTL 放入其他应用程序。

第 4 步：构建“词法分析器”

一个 词法分析器[^] 是将字符输入流转换为标记序列的代码。我有以下类型的标记

enum TokenType
{
    Unknown,

    Break,                  // line break

    Constant,               // "abc"
    CONSTANT,               // 'abc'

    Variable,               // name
    
    ForceCaseSensitive,     // +
    ForceCaseInsensitive,   // -

    Replace,                // *
    Extract,                // .
    Position,               // ;
    Number,                 // [-]###

    Equal,                  // ==
    NotEqual,               // !=
    LessThan,               // <
    LessThanOrEqual,        // <=
    GreaterThan,            // >
    GreaterThanOrEqual,     // >=
    Contains,               // ^
    NotContains,            // !^

    Conditional,            // ?
    ConditionalElse,        // :

    Open,                   // (
    Close                   // )
};

Constant、CONSTANT、Variable 和 Number 标记类型也带有相关值。

这是应用程序中最容易编写的部分。我使用了一个有限状态机，为语法中的每种标记类型都有一个状态，还有一个初始/终止状态“未知”。我以前写过很多次这样的代码，所以不需要状态图。下面是代码的纲要，实现在 Formula::Define() 成员函数中

bool     result = true;

List<Token>     tokens;

try
{
    Token::TokenType    type = Token::Unknown; // the 'state' variable
    CString             value;

    int offset = 0;
    int length = _Definition.GetLength();

    while (offset < length)
    {
        char current = _Definition[offset];

        char next    = '\0';
        if  (offset < (length - 1))
        {
            next = _Definition[offset + 1];
        }

        switch (type)
        {
            case Token::type:

                switch (current)
                {
                    case character:
                    
                        handle character according token type
                        break;
                }
                break;
        }
    }
}

catch (FormulaException *exception)
{
    result = false;
}

状态机一次处理一个或两个字符的定义字符串。它使用单个字符前瞻（next 值）来缩短一些状态转换。这简化了对条件表达式中的转义序列和比较运算符的处理。外部 switch 语句基于状态变量 type（当前标记的类型）。对于每个状态，通常都有一个基于当前字符的内部 switch 语句。状态处理可以向当前标记的值添加字符，完成当前标记并将其添加到列表中，将状态更改为另一种标记类型，组合这些操作，或者根据需要通过抛出 FormulaException 来发出错误信号。

第 5 步：创建表达式处理程序

我知道我需要处理每种表达式类型的代码，所以接下来我为每种类型创建了类，所有类都派生自抽象基类 Expression

class LTTL::Expression
{
public:

    enum ExpressionType
    {
        Constant,
        Variable,
        Replace,
        Extract,
        Offset,
        Position,
        Conditional,
        Comparison,
        Group
    };

    Expression();

    virtual ~Expression();
    
    virtual ExpressionType Type() = 0;

    virtual CString Evaluate(void *context) = 0;
    
    bool CaseSensitive;
    int SyntaxOffset;
};

每个表达式都会根据上下文返回其类型并进行求值。表达式可能区分大小写（或不区分）。最后，在解析过程中会记录表达式在原始定义中的初始偏移量。

Constant 表达式类型实现常量字符串，而 Variable 处理变量。Replace、Extract 和 Conditional 类型实现了它们各自的运算符。Offset 和 Position 表达式支持提取运算符的操作数，而 Comparison 类型支持条件运算符。Group 表达式类型实现了括号中的嵌套表达式。

第 6 步：创建解析器：将标记流转换为高效表示

现在我的“词法分析器”工作得相当不错了。它甚至处理了我需要的一些语法检查。我现在必须将标记列表转换为某种结构，该结构可以关联我创建的各种 Expression 类。

天哪。

我开始在 Formula::Define() 成员函数中内联编写代码，因为那是需要解析过程的地方。很快我就意识到这是一个错误。根据我的阅读，我记得解析器往往是递归的，所以我将解析代码重构为自己的函数。啊哈！用我写的一点点解析代码放在它自己的函数里，我认出了一个现在看起来非常明显的东西。基本的公式语法 e1 e2 e3 ... eN 实际上是被括号分组的表达式的内部。然后我将解析函数作为 GroupExpression 类（处理括号）的成员，并将最外层的表达式设为该类的实例。这就是为什么在 LTTL.h 文件中，表达式成员被称为 _Group。

有了这个，我开始充实解析代码。我有一个外部循环遍历词法分析步骤构建的标记列表。循环的主体是一个基于标记类型的 switch。我有一个 Expression 类对象的“工作”实例。根据当前标记类型，我要么向工作实例添加信息，要么将该实例添加到当前组表达式的列表中并创建一个新的工作实例。我最终在单个函数中构建了一个完整的解析器。它甚至递归地处理嵌套的括号表达式。

代码很长，而且有些重复。有很多地方的代码重复，除了每个重复之间的细微差别。它是可以工作的，所以我用它更新了我诊断工具的一个新版本。

这是一个非常有趣的项目，所以我告诉了一些程序员朋友。他们鼓励我写一篇 CP 文章，所以我从我们工具的源代码中提取了代码并开始编写。将“变量”的概念从原始代码抽象到上面描述的 Variables 类相对容易。我添加了一个简单的测试程序，并开始写文章。当写到“第 6 步：创建解析器”时，我卡住了。解析器不对。虽然它似乎有效，但它存在局限性。提取和替换运算符不能在其周围有空格，因为解析器将其视为当前表达式的“中断”条件。验证遗漏了一些情况，修复其中几个只是让人们更清楚地认识到这种方法不对。各种 Expression 类没有处理它们在解析和验证过程中的一部分，这让我很恼火。

原始代码中最明显的缺点是解析器“知道”太多关于各种表达式类内部结构的信息。一定有办法重构解析，让那些类来实现它们任务的一部分。我知道关键在于原始代码中使用的“工作”表达式，该表达式被当前标记的处理产品添加或替换。我向每个 Expression 类添加了一个新的 virtual 成员，它看起来像这样

Expression *Parse(Token *token,
                  Expression *current)
{
    if (current can be used by this expression)
    {
        add current to this expression
        current = NULL;
    }
    
    return current;
}

然后我将所有“表达式类型”特定的部分移到了它们各自的 Parse() 成员函数中。通过这个更改，它似乎更接近了。原始解析器的主体现在小了很多，并且表达式类型特定的逻辑也归到了它应该在的地方。我查看了 Parse() 函数的实现，意识到其中没有一个使用了 token 参数，所以我把它删除了。解析器现在由创建新的表达式对象，然后将它们传递给当前工作对象的 Parse() 函数组成。

事情仍然显得有点笨拙，直到我记得我在一个解析算法描述中看到过一句话。那是关于表达式消耗标记的。我认为我终于找到了最关键的一块拼图。

解析器（仍然是 GroupExpression 类的一部分）遍历标记列表。它有一个“工作”表达式实例，最初为 NULL。根据当前标记类型，它创建一个名为 current 的新 Expression 类实例。如果工作实例是 NULL，则将工作实例设置为当前实例，并继续到下一个标记。但是，如果工作实例不是 NULL，则将新创建的“current”表达式实例传递给工作实例的 Parse() 函数。如果工作表达式使用了“current”实例（“消耗”了它），它将返回 NULL。如果它不能使用，它将返回当前实例。

解析器现在看起来大致如下

Expression *working = NULL;

for (token in token_list)
{
    Expression *current = NULL;
    
    switch (token->Type)
    {
        case type:
        
            current = new ExpressionType(...);
            break;
    }
    
    if (working != NULL)
    {
        current = working->Parse(current);
        
        if (current != NULL)
        {
            working = current;

            add working to GroupExpression list of expressions
        }
    }
    else
    {
        working = current;

        add working to GroupExpression list of expressions
    }
}

对过程的最后一次改进发生在当我仍然在验证方面遇到麻烦时。我最终意识到，在解析器的主体中创建的一些 Expression 类可以简单地在构造时消耗工作表达式实例，而不是在它们被解析时试图获取它们。例如，提取运算符和替换运算符都作用于一个“源”表达式。当在这些表达式之一中找到第一个提取或替换运算符时，该源表达式就是当前的工作实例。这有助于将这些值的验证移到它们各自的表达式类中，解析器终于完成了。呼。

最后一步：测试程序

当然，在编写和调试 LTTL 类时，我已经有了相当多的测试程序，但这对于这个故事来说并不重要。测试程序对 LTTL 类最大的影响是在 Token 和 Expression 类中添加了一个整数 SyntaxOffset 成员变量。这个值记录了标记及其关联的 Expression 实例在原始定义字符串中的偏移量。当 LTTL 代码需要发出错误信号时，它会使用适当的 SyntaxOffset 值和描述错误并抛出异常的字符串来构建一个 FormulaException。异常在 Formula::Define() 函数的外部边界被捕获，并且如果应用程序需要，偏移量和错误值会被保存以供以后检索。

关注点

LTTL 还有进一步的机会。当前的 C++ 代码可以稍作修改以使用 STL 字符串和集合类。.NET 版本需要用 C# 编写一个版本，但逻辑会非常相似。当前的调试代码（随处可见的 ToString() 函数）受到我的 .NET 背景的影响。

外部应用程序定义的 Variables 类可以增强以实现应用程序特定的比较。例如，枚举值可以根据枚举值的顺序而不是其字符串表示的顺序进行比较。条件表达式可以增强以支持逻辑运算符和带括号的逻辑表达式。

另一个增强是添加“内置”函数。这些函数可以提供大小写转换、去除前导/尾随空格等操作。

最后一个 LTTL 曾经支持的增强是正则表达式。我最初计划允许在提取运算符的位置参数、替换运算符的“查找”操作数等中使用正则表达式。我开始被管理 regex 上下文值的要求所困扰，所以我删除了它。

历史

• 2015 年 4 月 6 日 - 首次发布