26

对于所有编译器专家，我想编写一个递归下降解析器，我只想用代码来完成。没有从其他语法生成词法分析器和解析器，也不要告诉我阅读龙书，我最终会解决这个问题。

我想深入了解有关为一种合理的简单语言（例如 CSS）实现词法分析器和解析器的细节。我想正确地做到这一点。

这可能最终会成为一系列问题，但现在我从词法分析器开始。可以在此处找到 CSS 的标记化规则。

我发现我自己编写的代码是这样的（希望你可以从这段代码中推断出其余的）：

public CssToken ReadNext()
{
    int val;
    while ((val = _reader.Read()) != -1)
    {
        var c = (char)val;
        switch (_stack.Top)
        {
            case ParserState.Init:
                if (c == ' ')
                {
                    continue; // ignore
                }
                else if (c == '.')
                {
                    _stack.Transition(ParserState.SubIdent, ParserState.Init);
                }
                break;

            case ParserState.SubIdent:
                if (c == '-')
                {
                    _token.Append(c);
                }
                _stack.Transition(ParserState.SubNMBegin);
                break;

这个叫什么？我离合理理解的东西还有多远？我正在尝试平衡一些在效率方面公平且易于使用的东西，使用堆栈来实现某种状态机效果很好，但我不确定如何继续这样。

我拥有的是一个输入流，我一次可以从中读取 1 个字符。我现在不做任何头，我只是阅读角色然后根据当前状态尝试对此做些什么。

我真的很想进入编写可重用代码片段的思维模式。这个Transition方法目前的意思是这样做，它会弹出堆栈的当前状态，然后以相反的顺序推送参数。这样，当我编写Transition(ParserState.SubIdent, ParserState.Init)它时，它将“调用”一个子例程SubIdent，该例程完成后将返回到该Init状态。

解析器将以几乎相同的方式实现，目前，将所有内容都放在一个大方法中，这样我可以在找到一个标记时轻松返回一个标记，但它也迫使我将所有内容保存在一个大方法中。有没有一种很好的方法可以将这些标记化规则拆分为单独的方法？

4

5 回答 5

29

您正在编写的内容称为下推自动机。这通常比您编写词法分析器所需的功能更强大，如果您正在为 CSS 等现代语言编写词法分析器，这肯定是过度的。递归下降解析器的功能接近下推自动机，但递归下降解析器更容易编写和理解。大多数解析器生成器生成下推自动机。

词法分析器几乎总是写为有限状态机，即，除了摆脱“堆栈”对象之外，就像您的代码一样。有限状态机与正则表达式密切相关（实际上，可以证明它们彼此等价）。在设计这样的解析器时，通常从正则表达式开始，并使用它们来创建确定性有限自动机，并在转换中使用一些额外的代码来记录每个标记的开始和结束。

有工具可以做到这一点。该lex工具及其后代是众所周知的，并已被翻译成多种语言。工具链还有ANTLR一个词法分析器组件。我首选的工具是ragel在支持它的平台上。大多数时候手工编写词法分析器几乎没有什么好处，而且这些工具生成的代码可能会更快、更可靠。

如果您确实想手动编写自己的词法分析器，好的词法分析器通常看起来像这样：

function readToken() // note: returns only one token each time
    while !eof
        c = peekChar()
        if c in A-Za-z
            return readIdentifier()
        else if c in 0-9
            return readInteger()
        else if c in ' \n\r\t\v\f'
            nextChar()
        ...
    return EOF

function readIdentifier()
    ident = ""
    while !eof
        c = nextChar()
        if c in A-Za-z0-9
            ident.append(c)
        else
            return Token(Identifier, ident)
            // or maybe...
            return Identifier(ident)

然后，您可以将解析器编写为递归下降解析器。不要试图将词法分析器/解析器阶段合并为一个，这会导致代码一团糟。（根据 Parsec 作者的说法，它也更慢）。

于 2010-04-13T20:07:36.163 回答
5

您需要从 BNF/EBNF编写自己的递归下降解析器。我最近不得不自己写，这个页面很有帮助。我不确定您所说的“仅使用代码”是什么意思。你的意思是你想知道如何编写自己的递归解析器？

如果你想这样做，你需要先把你的语法准备好。一旦你有了 EBNF/BNF，就可以很容易地用它编写解析器。

当我编写解析器时，我做的第一件事就是读入所有内容，然后对文本进行标记。所以我基本上最终得到了一个我将其视为堆栈的令牌数组。为了减少从堆栈中提取值然后在不需要时将其推回的冗长/开销，您可以使用一种peek方法来简单地返回堆栈上的顶部值而不弹出它。

更新

根据您的评论，我不得不从头开始用 Javascript 编写递归下降解析器。您可以在此处查看解析器。只需搜索constraints功能。我也编写了自己的tokenize函数来标记输入。我还写了另一个便利函数（peek我之前提到过的）。解析器根据此处的 EBNF 进行解析。

我花了一点时间才弄明白，因为我已经好几年没有写解析器了（上次我写它是在学校！），但相信我，一旦你明白了，你就明白了。我希望我的例子能让你走得更远。

另一个更新

我还意识到我的示例可能不是您想要的，因为您可能会使用 shift-reduce 解析器。您提到现在您正在尝试编写标记器。就我而言，我确实用 Javascript 编写了自己的标记器。它可能不够强大，但足以满足我的需求。

 function tokenize(options) {
            var str = options.str;
            var delimiters = options.delimiters.split("");
            var returnDelimiters = options.returnDelimiters || false;
            var returnEmptyTokens = options.returnEmptyTokens || false;
            var tokens = new Array();
            var lastTokenIndex = 0;

            for(var i = 0; i < str.length; i++) {
                if(exists(delimiters, str[i])) {
                    var token = str.substring(lastTokenIndex, i);

                    if(token.length == 0) {
                        if(returnEmptyTokens) {
                            tokens.push(token);
                        }
                    }

                    else {
                        tokens.push(token);
                    }

                    if(returnDelimiters) {
                        tokens.push(str[i]);
                    }

                    lastTokenIndex = i + 1;
                }
            }

            if(lastTokenIndex < str.length) {
                var token = str.substring(lastTokenIndex, str.length);
                token = token.replace(/^\s+/, "").replace(/\s+$/, "");

                if(token.length == 0) {
                    if(returnEmptyTokens) {
                        tokens.push(token);
                    }
                }

                else {
                    tokens.push(token);
                }
            }

            return tokens;
        }

根据您的代码，您似乎正在同时阅读、标记和解析 - 我假设这就是 shift-reduce 解析器的作用？我所拥有的流程是首先标记化以构建标记堆栈，然后通过递归下降解析器发送标记。

于 2010-04-13T19:43:16.343 回答
5

如果您要从头开始编写所有代码，我肯定会考虑使用递归的体面解析器。在您的帖子中，您并没有真正说明一旦您解析了源代码，您将使用令牌流做什么。

有些事情我会建议处理
1. 扫描仪/词法分析器的良好设计，这就是为解析器标记源代码的原因。
2. 接下来是解析器，如果你有一个很好的源语言 ebnf，解析器通常可以很好地翻译成一个递归的体面的解析器。
3. 另一个你真正需要了解的数据结构是符号表。这可以像哈希表一样简单，也可以像可以表示复杂记录结构的树结构一样复杂。我认为对于 CSS，您可能介于两者之间。
4. 最后你要处理代码生成。你在这里有很多选择。对于解释器，您可能只是在解析代码时即时解释。更好的方法可能是生成一个 for of i-code，然后您可以编写一个 iterpreter，然后甚至是一个编译器。当然对于 .NET 平台，您可以直接生成 IL（可能不适用于 CSS :)）


作为参考，我认为您并不热衷于深入的理论，我不怪您。如果您不介意 Pascal，那么无需复杂代码即可获得基础知识的一个非常好的起点，即 Jack Crenshaw 的“让我们构建一个编译器”
http://compilers.iecc.com/crenshaw/
祝你好运，我相信你将享受这个项目。

于 2010-04-13T20:09:28.640 回答
4

看起来您想要实现一个“shift-reduce”解析器，在其中显式构建一个令牌堆栈。通常的替代方案是“递归下降”解析器，其中深度过程调用在实际硬件堆栈上构建具有自己的局部变量的相同令牌堆栈。

在 shift-reduce 中，术语“reduce”是指在显式维护的令牌堆栈上执行的操作。例如，如果堆栈的顶部已变为，Term, Operator, Term则可以应用缩减规则，从而Expression替换模式。归约规则明确编码在移位归约解析器使用的数据结构中；因此，所有归约规则都可以在源代码的同一位置找到。

与递归下降相比，移位减少方法带来了一些好处。在主观层面上，我认为 shift-reduce 比递归下降更容易阅读和维护。更客观地说，当出现意外标记时，shift-reduce 允许来自解析器的更多信息错误消息。

具体来说，因为 shift-reduce 解析器具有用于进行“减少”的规则的显式编码，所以解析器很容易扩展以阐明可以合法遵循的令牌类型。（例如，“；预期”）。递归下降实现不能轻易扩展来做同样的事情。

Thomas W. Parsons 所著的《编译器构造简介》是一本关于这两种解析器以及实现不同类型移位归约的权衡的好书。

Shift-reduce 有时称为“自下而上”解析，而递归下降有时称为“自上而下”解析。在所使用的类比中，以最高优先级（例如，乘法表达式中的“因子”）组成的节点被认为是解析的“底部”。这与“递归下降”的“下降”中使用的类比相同。

于 2010-04-13T19:46:17.633 回答
3

如果您还想使用解析器来处理格式不正确的表达式，那么您真的需要一个递归下降解析器。更容易获得可用的错误处理和报告。

对于文学作品，我会推荐 Niklaus Wirth 的一些旧作品。他知道怎么写。算法+数据结构=程序是我用的，但是你可以在网上找到他的编译器构建。

于 2010-04-13T21:57:09.160 回答