手编码解析器

Question

对于你所有的编译器大师,我想编写一个递归下降解析器,我想用代码来做.没有从其他语法生成词法分析器和解析器并且不告诉我阅读龙书,我最终会到达那里.

我想进入关于为一个合理的简单语言实现词法分析器和解析器的细节,比如说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状态.

解析器将以大致相同的方式实现,目前,在这样的单个大方法中,所有内容都允许我在找到令牌时轻松返回令牌,但它也迫使我将所有内容保存在一个单一的大方法中.有没有一种很好的方法将这些标记化规则拆分成单独的方法？

Answer 1

你正在写的是一个下推自动机.这通常比编写词法分析器所需的功能更强大,如果你正在为像CSS这样的现代语言编写词法分析器,那肯定会过度.递归下降解析器接近下推自动机,但递归下降解析器更容易编写和理解.大多数解析器生成器生成下推自动机.

Lexers几乎总是被写成有限状态机,就像你的代码一样,除了摆脱"堆栈"对象.有限状态机与正则表达式密切相关(实际上,它们可以证明彼此相当).当设计这样的解析器,人们通常用正则表达式开始,并用它们来创建一个确定性有限自动机,在转变一些额外的代码来记录每个令牌的开头和结尾.

有工具可以做到这一点.该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作者说,它也慢了).

Answer 2

你需要从你的 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 解析器的作用？我所拥有的流程是首先标记化以构建令牌堆栈，然后通过递归下降解析器发送令牌。

Answer 3

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

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


对于引用,我猜你是不重入深的理论,我不怪你.如果你不介意Pascal,那么获得没有复杂代码的基础知识的一个非常好的起点是Jack Crenshaw的'让我们构建一个编译器'
http://compilers.iecc.com/crenshaw/
祝你好运我相信你将要享受这个项目.