手工编码解析器

你写的东西叫做下推自动装置。这通常比你写一个lexer所需要的能力更强,如果你是为像css这样的现代语言写一个lexer,这当然是过度的。递归下降解析器与下推自动机的功能非常接近,但是递归下降解析器更容易编写和理解。大多数解析器生成器生成下推自动机。

lexer几乎总是作为有限状态机编写的,例如,除了除去“stack”对象之外,与您的代码类似。有限状态机与正则表达式密切相关(事实上,它们相互等价)。在设计这种解析器时,通常从正则表达式开始,并使用它们来创建确定性有限自动机,在转换过程中使用一些额外的代码来记录每个标记的开始和结束。

有一些工具可以做到这一点。这个 lex 工具及其后代是众所周知的,并已被翻译成多种语言。这个 ANTLR toolchain还有一个lexer组件。我喜欢的工具是 ragel 在支持它的平台上。用手写一个lexer没有什么好处 最 当然,这些工具生成的代码可能更快、更可靠。

如果你真的想用手写你自己的雷克萨斯,好的雷克萨斯通常看起来像这样:

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)

然后可以将解析器编写为递归下降解析器。不要试图将lexer/parser阶段合并为一个阶段,这会导致代码混乱。(根据Parsec的作者,速度也较慢)。

如果您打算从头开始编写所有代码,我肯定会考虑使用一个递归的、合适的解析器。在您的帖子中,您并没有真正地说明一旦解析了源代码,您将如何处理令牌流。

我建议你做点什么
1。为您的扫描器/lexer设计得很好,这就是将为您的解析器标记源代码的地方。
2。下一件事是解析器,如果您对源语言有一个良好的EBNF,解析器通常可以很好地转换成一个递归的、合适的解析器。
三。另一个真正需要了解的数据结构是符号表。这可以像哈希表一样简单,也可以像表示复杂记录结构的树结构一样复杂。我认为对于CSS,您可能介于两者之间。
4。最后,您要处理代码生成。你有很多选择。对于解释器,您可以简单地在解析代码时进行即时解释。一个更好的方法可能是生成一个for-of-i代码,然后您可以为它编写一个iterpreter,甚至稍后编写一个编译器。当然,对于.NET平台,您可以直接生成IL(可能不适用于CSS:)


作为参考,我认为你并不沉迷于深层次的理论,我也不怪你。如果你不介意帕斯卡的话,一个很好的起点就是杰克·克伦肖的“让我们构建一个编译器”。
http://compilers.iecc.com/crenshaw/
祝你好运,我相信你会喜欢这个项目的。

你需要自己写 Recursive Descent Parser 来自您的bnf/ebnf。我最近不得不自己写,而且 this page 帮了很多忙。我不知道你所说的“只带代码”是什么意思。您的意思是想知道如何编写自己的递归解析器吗?

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

当我编写解析器时,我做的第一件事是读取所有内容,然后标记化文本。所以我最终得到了一个标记数组,我把它当作一个栈来处理。为了减少从堆栈中提取一个值的冗长性/开销,然后在不需要时将其推回到堆栈中,您可以 peek 方法,只返回堆栈上的最大值而不弹出该值。

更新

根据您的评论,我不得不从头开始用JavaScript编写递归下降解析器。你可以看一下解析器 here . 只需搜索 constraints 功能。我自己写的 tokenize 函数来标记输入。我还写了另一个方便函数( 偷看 我之前提到过)。解析器根据EBNF进行解析 here .

我花了一点时间才弄明白,因为我写解析器已经有好几年了(上一次是在学校写的!)但是相信我,一旦你得到它,你 得到 它。我希望我的例子能让你在前进的道路上走得更远。

另一个更新

我还认识到,我的示例可能不是您想要的,因为您可能将要使用一个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" parser ,其中显式构建令牌堆栈。通常的替代方法是“递归下降”解析器,在这种解析器中,过程深度调用在实际的硬件堆栈上用它们自己的局部变量构建相同的令牌堆栈。

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

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

具体地说,因为移位-减少解析器有一个明确的规则编码来进行“减少”,解析器很容易被扩展来明确哪些类型的令牌可以合法地遵循。(例如,“预期”)。递归下降实现不能轻易地扩展为执行相同的操作。

关于这两种类型的解析器以及实现不同类型移位减少的权衡的一本好书是 "Introduction to Compiler Construction", by Thomas W. Parsons .

shift reduce有时称为“自下而上”解析,递归下降有时称为“自上而下”解析。在所使用的类比中,具有最高优先级的节点(例如,乘法表达式中的“因子”)被认为是解析的“底部”。这与“递归下降”的“下降”中使用的相同类比是一致的。

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

对于文学,我会推荐一些尼古拉斯·沃特的老作品。他知道怎么写。 算法+数据结构=程序 是我用过的,但你可以找到他的 Compiler Construction 在线。