如何制作 LL(1) 解析器：第 2 课

• 下载源代码 - 137.1 KB

引言

本文基于我们上一课。

在那一课中，我们使用 CFG 定义了引用终结符的非终结符，但尚未定义终结符的结构。

在本课中，我们将构建一个辅助的正则表达式引擎来匹配输入string中的终结符。我们不会使用 Microsoft 的 .NET 正则表达式，因为那样会更复杂。然后，我们将创建一个小类，允许您遍历输入文本字符串中的终结符。

背景

首先，终结符究竟是什么？我们从来没有真正讲过。简单来说，终结符是解析器识别的文本元素。它是基本元素。您无法将其分解。在我们之前的语法中，我们的终结符是+、*、(、)和int。终结符与可以包含它们以及彼此的非终结符一起组成一个解析树。终结符是叶子，非终结符是节点。

概念上，我们将使用正则表达式定义终结符，但我们不会费心去创建一个完整的正则表达式引擎。相反，我们将在代码中手动构建正则表达式。

对于我们之前的语法，这相当直接。

E  -> T E'
E' -> + T E'
E' ->
T  -> F T'
T' -> * F T'
T' ->
F  -> ( E )
F  -> int

唯一不是简单字面量的终结符是“int”。在本练习中，我们将int 视为一串数字，类似于正则表达式[0-9]+

为了方便匹配表达式，我们将使用有向图来表示跳转表，并在遍历它们以进行标记化时使用这些有向图。这比说更容易展示，但我们会实现的。这背后的数学被称为有限自动机。

我们正在构建一个作为正则表达式匹配器的词法分析器。它由几个正则表达式组成，每个终结符一个。每个表达式都关联一个终结符符号。

再次强调，终结符是+、*、(、)和int。

我们的有向图需要看起来像这样：

这是一个状态机。圆圈是我们的状态，线条是我们的转移。虚线在不消耗任何输入的情况下进行转移。黑线在上面标记的输入上进行转移。双圆圈是接受状态，并且关联的终结符符号显示在圆圈中。

有关此工作的更详细信息，请参阅我的正则表达式引擎文章。

在生产代码中，我们会将此“NFA”转换为“DFA”，然后再使用它，因为结果会快得多，但为了保持简单，我们只使用“NFA”。这个算法一旦掌握，很容易优化，并且在优化后可以生成最快的词法分析代码，这也是我们选择它的原因之一，尽管它在这个实现中很慢。它可以轻松地进行扩展和优化。

要使用它，我们将其反复应用于输入流中的下一个位置。每次我们获得接受，或者每次我们无法接受并出现错误时，我们都会报告该情况，然后将机器重置回q0。基本上，我们正在运行一个匹配，这会导致光标前进，再次运行匹配，这又会导致光标前进，依此类推，这就是我们如何遍历文本。每次我们获得匹配或错误时，都会有一个与之关联的终结符符号，告诉我们匹配是什么，一个int，或其他终结符，如(、+、 ，或者在错误的情况下，#ERROR

这些是我们最终将传递给解析器的内容，解析器将使用解析表在遍历文本时构建这些“标记”的树。

你还在跟着吗？花点时间。=)

编写这个混乱的程序

这里的代码包含几个部分：

首先，我们有FA。FA的每个实例代表状态机中的一个状态，或者图中的一个圆圈。它们通过Transitions（实黑线）和EpsilonTransitions（虚线）属性相互连接。这是一个以char值和集合为键的字典，分别。

它还具有用于创建基本表达式的静态构建器方法 - Literal、Set、Concat、Or、Repeat和Optional，它们在创建这些图中的线条方面做了繁重的工作。通常将它们组合起来以创建类似正则表达式的内容。

这是我们为此项目创建词法分析器的方法：

var lexer = new FA();
lexer.EpsilonTransitions.Add(FA.Literal("+", "+")); // dashed line to +
lexer.EpsilonTransitions.Add(FA.Literal("*", "*")); // dashed line to *
lexer.EpsilonTransitions.Add(FA.Literal("(", "(")); // dashed line to (
lexer.EpsilonTransitions.Add(FA.Literal(")", ")")); // dashed line to ) 
lexer.EpsilonTransitions.Add(FA.Repeat(FA.Set("0123456789"), "int")); // dashed line to int

如果您研究一下并查看上面的图表，您应该会看到它的组合。

这里另一个超级重要的方法是FillMove，它获取我们当前所在的状态集，并应用一个输入字符，在遵循所有必要线条后，给出我们最终到达的状态。我们的标记器将使用它来获取我们的词法单元/标记。

接下来，我们需要实际处理我们刚刚创建的图（lexer）。这就是我们的标记器的作用。标记器将接受输入字符串和FA图，并从输入字符串中检索一系列标记/词法单元。本项目中的Tokenizer类使用 .NET 枚举器模式实现，因此您可以使用foreach 对其进行迭代以获取标记。繁重的工作由实现IEnumerator<Token>的TokenEnumerator类完成。

在该类中，大部分繁重的工作是由_Lex方法完成的。这里是我们正则表达式处理器的核心。

string _Lex()
{
    string acc;
    var states = _initialStates;
    _buffer.Clear();
    switch (_state)
    {
        case -1: // initial
            if (!_MoveNextInput())
            {
                _state = -2;
                acc = _GetAcceptingSymbol(states);
                if (null != acc)
                    return acc;
                else
                    return "#ERROR";
            }
            _state = 0; // running
            break;
        case -2: // end of stream
            return "#EOS";
    }
    // Here's where we run most of the match. 
    // FillMove runs one iteration of the NFA state machine.
    // We match until we can't match anymore (greedy matching) 
    // and then report the symbol of the last 
    // match we found, or an error ("#ERROR") if we couldn't find one.
    while (true)
    {
        var next = FA.FillMove(states, _input.Current);
        if (0 == next.Count) // couldn't find any states
            break;
        _buffer.Append(_input.Current);

        states = next;
        if (!_MoveNextInput())
        {
            // end of stream
            _state = -2;
            acc = _GetAcceptingSymbol(states);
            if (null != acc) // do we accept?
                return acc;
            else
                return "#ERROR";
        }
    }
    acc = _GetAcceptingSymbol(states);
    if (null != acc) // do we accept?
        return acc;
    else
    {
        // handle the error condition
        _buffer.Append(_input.Current);
        if (!_MoveNextInput())
            _state = -2;
        return "#ERROR";
    }
}

本质上，它只是在循环中调用FillMove，直到不再有从它返回的状态，并存储找到的字符，同时处理输入结束和错误条件的一些边界情况。其余的只是记账。

在下一课中，我们将创建Tokenizer的一个新实例，并将其与上一课中创建的解析表一起传递给我们即将开发的解析器。

历史

• 2019年7月14日 - 首次提交