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

• 下载源代码 - 137.1 KB

引言

我们终于要用我们在第 1 课和第 2 课中创建的内容来构建一个解析器了。

背景

我们所需要做的就是结合一个词法分析器和一个解析表以及一个栈，我们将得到一个被称为下推自动机 (PDA) 的东西，我们可以用它来进行解析。

我们将使用栈来跟踪我们的树，并使用输入词法分析器来获取用于解析的标记，而我们的解析表用于将标记符号与规则匹配。

当我们遇到一条规则时，我们会遍历它，将其推导压入栈中，从而将其添加到解析树中。

我们还必须注意错误情况。我们采用一种称为“恐慌模式错误恢复”的简单错误恢复形式，试图在发生错误时继续解析，同时仍然报告错误。

演练

如果我们想对这个过程有另一种解释，我们可以再次回到Andrew Begel 的论文。

这里是我们的解析表，供参考。

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

我们将考虑输入字符串 "3+5*7"。

当我们开始时，我们的栈必须是空的。我们要做的第一件事是将“起始符号”推入栈中。对于我们的语法，它是E，因为它是语法中的第一个非终结符。我们现在还需要从词法分析器中读取下一个标记并存储它，即使我们暂时不会使用它。

到目前为止，我们的栈是 { E }。 我们的词法分析器位于 3 上，这是一个 int。

由于我们在栈中有一个E，并且我们的输入符号是int，我们从表中选择转换E -> T E'。这意味着，我们必须将E从栈中弹出，然后将其推导T E'推入栈中（我们按相反的顺序执行）

请注意，我们的解析器所做的另一件事是，我们将特殊标记推入栈中，以指示非终结符的结束。我们在这里不会考虑这些，因为它们不是实际解析树的一部分 - 它们只是帮助我们找出非终结符的开始和结束位置。

所以现在无论如何，我们的栈是 { T, E' }，并且我们在输入中仍然是一个 int。查看表中的行T和输入int，我们找到T -> F T'，因此再次从栈中弹出，删除T，然后将其推导推入栈中。

这使得我们的栈为 { F, T', E' }，并且我们仍然在输入中有一个 int。查看表中的行F和输入int，我们找到F -> int，因此再次从栈中弹出，删除F，然后将其推导推入栈中，现在是 {int, T', E' }

最后，由于我们的栈顶是int，并且我们的输入也是如此，我们弹出栈，并推进词法分析器。

现在我们的栈是 { T', E' }，这次，我们的输入是 +，这给了我们规则T'->，所以我们只需弹出栈。

它就这样一直进行下去，直到我们完成并输入了#EOS。

编写这个混乱的程序

这里要考虑的主要类是Parser，我们需要一个，所以让我们为我们的输入创建它。

// create a parser using our 
// parse table and lexer, and 
// input text
var text = "3+5*7";

var parser = new Parser(
    cfg.ToParseTable(),
    new Tokenizer(lexer, text),
    "E");

解析器本身的工作方式类似于XmlReader，因此如果您熟悉其中涉及的Read/NodeType模式，那么您将很容易学会使用它。

它还包含一个ParseSubtree方法，如果您希望处理该方法，您可以使用它将当前子树读入解析树。

解析器的核心是Read方法

public bool Read()
{
    var n = NodeType;
    // early exit if we're in the middle of handling an error
    if (ParserNodeType.Error == n && "#EOS" == _tokEnum.Current.Symbol)
    {
        _errorToken.Symbol = null;
        _stack.Clear();
        return true;
    }
    // initialize the stack on the first read call and advance the input
    if (ParserNodeType.Initial == n)
    {
        _stack.Push(_startSymbol);
        _tokEnum.MoveNext();
        return true;
    }
    _errorToken.Symbol = null; // clear the error status

    if(0<_stack.Count) // there's still more to parse
    {
        var sid = _stack.Peek(); // current symbol
        if(sid.StartsWith("#END ")) // end non-terminal marker
        {
            _stack.Pop();
            return true;
        }
        // does the stack symbol match the current input symbol?
        if(sid==_tokEnum.Current.Symbol) // terminal
        {
            // lex the next token
            _tokEnum.MoveNext();

            _stack.Pop();
            return true;
        }
        // non-terminal
        // use our parse table to find the rule.
        IDictionary<string, CfgRule> d;
        if(_parseTable.TryGetValue(sid, out d))
        {
            CfgRule rule;
            if(d.TryGetValue(_tokEnum.Current.Symbol, out rule))
            {
                _stack.Pop();

                // store the end non-terminal marker for later
                _stack.Push(string.Concat("#END ", sid));

                // push the rule's derivation onto the stack in reverse order
                var ic = rule.Right.Count;
                for (var i = ic - 1; 0 <= i;--i)
                {
                    sid = rule.Right[i];
                    _stack.Push(sid);
                }
                return true;
            }
            _Panic(); // error
            return true;
        }
        _Panic(); // error
        return true;
    }
    // last symbol must be the end of the input stream or there's a problem
    if ("#EOS" != _tokEnum.Current.Symbol)
    {
        _Panic(); // error
        return true;
    }
    return false;
}

有关使用代码的更多信息，请参见Lesson 3/Program.cs文件。

就这样！

历史

• 2019 年 7 月 14 日 - 初始提交