logo标签列表

手写解析器的编码

c#compiler-constructionparsinglexer
27
对于所有编译器专家，我想编写一个递归下降解析器，只使用代码。不要从其他语法生成词法分析器和解析器，也不要告诉我读《龙书》，我最终会来处理它的。
我想深入了解实现一个适用于一个相对简单的语言（比如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”状态。
解析器将以类似的方式实现，当前，像这样将所有内容放在一个单独的大方法中使我能够轻松返回标记，但它也迫使我将所有内容都保留在一个单独的大方法中。是否有一种好的方法将这些标记化规则拆分成单独的方法？
1
我不明白为什么需要使用 _stack 来进行递归下降。 - stacker
这是一个状态机实现，我将使用它来向解析器提供标记。目前我正在寻求有关词法分析/标记化部分的帮助。 - John Leidegren
4
不知道这是否能帮到你，但我发现http://msdn.microsoft.com/en-us/magazine/cc136756.aspx对于编写简单的编译器非常有帮助。它是关于为.NET框架编写编译器的，但基本的编译器原则适用于除.NET框架编译器以外的其他编译器。 - Zach Johnson
@Zach - 感谢提供链接，里面有一些很好的代码示例。 - John Leidegren
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的作者所说，这样做还会更慢)。

2
你知道的，如果我在写论文时有这样的帮助，事情会更容易理解。感谢你提供了一个很好的答案！我已经吃过亏，不会再将词法分析器和语法分析器合并了。 - John Leidegren
1
感谢您详细介绍词法分析器！+1 - Vivin Paliath
1
我只有一个问题，c 去哪了？当我说返回 IDENTIFIER 时，令牌值存储在哪里？这是一个微不足道的问题，但我必须问！如果我只是把字符放在字符串构建器中，那么我什么时候刷新它？我是否会有留下垃圾在我的字符串构建器中的风险？ - John Leidegren
1
我更正了伪代码，展示了一种处理跟踪c的方法。最初我比较含糊，因为人们通常有几种不同的方式来跟踪标记值。 - Dietrich Epp
2
尝试将词法分析器构建为一个对象，可以通过调用Lexer.Next()来实现，然后构建语法分析器，该分析器将使用词法分析器。我建议您的词法分析器返回标识符的值和类型，例如：identifier:a,integer:3,string:"hello"。这将使您更容易进行语法分析。 - Francisco Noriega
5
你需要从BNF/EBNF中编写自己的递归下降解析器。最近我也不得不写了一个，这个页面帮了我很多忙。我不确定你所说的“只是代码”是什么意思。你是想知道如何编写自己的递归解析器吗？
如果你想这样做，首先需要准备好你的语法。一旦你有了EBNF/BNF，就可以很容易地从它中编写出解析器。
当我编写解析器时，我做的第一件事就是读取所有内容然后标记化文本。因此，我最终得到了一个将其视为堆栈的令牌数组。为了减少从堆栈中拉出一个值并在不需要时将其推回去的冗余开销，你可以有一个peek方法，它仅返回堆栈顶部的值而不弹出它。 更新 根据您的评论，我不得不从头开始使用Javascript编写递归下降解析器。您可以在此处查看解析器。只需搜索constraints函数即可。我还编写了自己的tokenize函数对输入进行标记化处理。我还编写了另一个方便的函数（peek，我之前提到过）。该解析器按照EBNF 此处进行解析。
这花了我一些时间来理解，因为距离我上次写解析器已经过去多年了（上次是在学校里！），但请相信我，一旦你掌握了它，你就会明白。我希望我的例子能够让您更进一步。 另一个更新 我还意识到我的例子可能不是您想要的，因为您可能正在考虑使用移位-规约解析器。您提到您现在正在尝试编写一个标记生成器。在我的情况下，我确实在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;
        }

根据您的代码，看起来您正在同时读取、分词和解析 - 我猜这就是移位约简解析器所做的事情？我所拥有的流程是首先进行分词以构建令牌堆栈，然后将令牌通过递归下降解析器。

只是编写代码意味着你选择你的语言，我的是C#，然后你完全在语言内部编写你的词法分析器和解析器。不允许使用工具。我最终希望得到像Boost Spirit解析器框架那样的东西，它完全用C++编写，并为解析器生成提供了一个C++编程模型。这是可以接受的，但对我来说现在还是一个遥远的目标。 - John Leidegren
很有趣，你这么说！我不得不在Javascript中从头开始编写一个递归下降解析器:p。 - Vivin Paliath
谢谢提供的链接，看起来非常有帮助。但是现在我只是试图编写一个词法分析器/标记生成器，以便稍后用于编写解析器。 - John Leidegren
感谢提供 JavaScript 源代码。当我查看解析器时，它并不太正式。我真的想避免在特定字符和模式上进行拆分和 / 或子字符串操作。尽管通常可能会这样做，但我真的希望在此处采用正式的词法分析器方法，其中我的词法分析器是一个定义良好的状态机。 - John Leidegren
@Vivin 对的！看看Dietrich的回答，它解释了很多。 - John Leidegren
显示剩余12条评论
5
如果你打算从头开始手工编写所有内容，我建议考虑使用递归下降解析器。在你的帖子中，你并没有说一下当你解析源代码后会用令牌流做些什么。

以下是我建议掌握的几个要点：
1. 设计良好的扫描器/词法分析器，这是将源代码标记化为解析器所需的。
2. 接下来是解析器，如果对源语言有一个好的 EBNF，那么解析器通常可以很好地转化为递归下降解析器。
3. 另一个数据结构是符号表，你真正需要理解它。它可以是简单的哈希表，也可以是表示复杂记录结构等的树形结构。我认为对于 CSS，你可能会处于两者之间。
4. 最后你需要处理代码生成。你有很多选择。对于一个解释器，你可以简单地在解析代码时即时解释。更好的方法可能是生成一些 i-code，然后编写一个解释器，甚至稍后编写一个编译器。当然，对于 .NET 平台，你可以直接生成 IL（可能不适用于 CSS :))。


对于参考资料，我了解到你并不深入研究深层理论，我也不怪你。如果你不介意使用 Pascal，那么 Jack Crenshaw 的“让我们构建一个编译器”是一个非常好的入门基础。
http://compilers.iecc.com/crenshaw/
祝你好运，我相信你会喜欢这个项目。
我不会做代码生成 ;) 你完全错了，我喜欢理论。只是有时候很难开始... - John Leidegren
@John，我了解到你不打算使用代码生成器，因此我认为递归下降解析器对你来说是一个不错的选择。我同意这个理论，如果你有一些实践经验，那么以后更容易理解这个理论。 - Chris Taylor
4
看起来你想实现一个"移位-归约"解析器，其中你需要显式构建一个标记堆栈。通常的替代方案是"递归下降"解析器，在这种解析器中，过程调用的深度使用它们自己的本地变量构建相同的标记堆栈，在实际硬件堆栈上。
在移位-归约中，术语"归约"指对显式维护的标记堆栈执行的操作。例如，如果堆栈顶部变为，则可以应用归约规则，将作为模式的替换结果。归约规则明确编码在移位-归约解析器使用的数据结构中；因此，所有归约规则都可以在源代码的同一位置找到。
与递归下降相比，移位-归约方法带来了一些好处。在主观层面上，我认为移位-归约比递归下降更易于阅读和维护。更客观地说，移位-归约允许解析器在出现意外标记时提供更多信息丰富的错误消息。
具体来说，由于移位-规约解析器对于进行“规约”操作的规则有明确的编码，因此该解析器很容易扩展以表达哪些标记可以合法地跟随（例如，“需要分号”）。递归下降实现无法轻松扩展以执行相同的操作。
一本关于两种类型解析器以及实现不同类型的移位-规约存在的权衡的好书是《编译原理导论》（Thomas W. Parsons著）"Introduction to Compiler Construction"。
移位-规约有时被称为“自底向上”解析，而递归下降有时被称为“自顶向下”解析。在使用的比喻中，具有最高优先级的节点（例如乘法表达式中的“因子”）被认为是解析的“底部”。这与“递归下降”的相同比喻一致。
说到编写解析器，我相信我更喜欢递归下降变体。我相信我目前只是使用堆栈和while循环来构建状态机，这将是我的词法分析器...我的替代方案是什么？我仍然需要一个词法分析器，不是吗？ - John Leidegren
你正在构建的状态机非常类似于移位-归约。这意味着你用这种方式会更有乐趣。而且，最终产品也会更好。 - Heath Hunnicutt
嗯...除非有证据表明否则进行移位-规约。 - John Leidegren
我只想指出，使用递归下降解析器有非常好的理由。当然，他们完全可以不必在重写错误处理方面走得那么远才能实现这种效果，但对于更复杂的情况，这仍然是一个很好的理由去做。 - violet_white
3
如果你想使用解析器来处理不规范的表达式，你确实需要一个递归下降解析器。这样更容易使错误处理和报告可用。
对于文学作品，我建议阅读尼古拉斯·沃斯的一些旧作品。他知道如何写作。我使用的是《算法+数据结构=程序》，但你可以在网上找到他的编译器构造Compiler Construction。
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接