是否有可以在8位嵌入式系统上使用的flex/bison替代方案？

Question

我正在使用avr-gcc工具链在AVR微控制器上用C语言编写一个简单的BASIC类语言的小解释器作为练习。但是，我想知道是否有任何开源工具可以帮助我编写词法分析器和解析器。

如果我要在我的Linux机器上运行这段代码，我可以使用flex/bison。现在我将自己限制在一个8位平台上，我必须手工完成所有的工作，还是不？

Answer 1

我为一种针对ATmega328p的简单命令语言实现了一个解析器。该芯片有32k的ROM，只有2k的RAM。RAM绝对是更重要的限制--如果您还没有绑定到特定的芯片，请选择具有尽可能多RAM的芯片。这将使你的生活变得更容易。

起初，我考虑使用flex/bison。出于两个主要原因，我决定不使用此选项：

• 默认情况下，Flex & Bison依赖于一些标准库函数(尤其是I/O)，这些函数在avr-libc中是不可用的，或者工作方式不同。我很确定有支持的解决方法，但这是一些额外的努力，你将需要考虑。
• AVR有一个Harvard Architecture。C的设计没有考虑到这一点，所以在默认的下，即使是常量变量也会被加载到内存中。您必须使用特殊的宏/函数来存储和访问flash和EEPROM中的数据。Flex & Bison创建了一些相对较大的查找表，这些查找表很快就会消耗掉你的内存。除非我弄错了(这是很有可能的)，否则您必须编辑输出源，以便利用特殊的闪存和EEPROM接口。

在拒绝了Flex & Bison之后，我开始寻找其他生成器工具。以下是我考虑过的几个问题：

• LEMON
• Ragel
• re2c

您可能还想看看Wikipedia's comparison。

最终，我手工编写了词法分析器和解析器。

对于解析，我使用了递归下降解析器。我认为Ira Baxter已经在这个主题上做了足够的工作，网上有很多教程。

对于我的词法分析器，我为我的所有终端编写了正则表达式，绘制了等价的状态机，并使用goto的状态跳转将其实现为一个巨大的函数。这很繁琐，但效果很好。顺便说一句，goto是实现状态机的一个很好的工具--所有的状态都可以在相关代码旁边有清晰的标签，没有函数调用或状态变量开销，而且它几乎是你能得到的最快的速度。C真的没有更好的构造来构建静态状态机。

需要考虑的问题:词法分析器实际上只是解析器的一种特化。最大的区别是，常规语法通常足以进行词法分析，而大多数编程语言具有(大多数)上下文无关的语法。因此，实际上没有什么可以阻止您将词法分析器实现为递归下降解析器，或者使用解析器生成器来编写词法分析器。这通常不像使用更专业的工具那样方便。

Answer 2

如果您想要一种编写解析器的简单方法，或者您的空间很紧张，那么您应该手工编写一个递归下降解析器；这些解析器本质上是LL(1)解析器。这对于像Basic一样“简单”的语言尤其有效。(早在70年代，我就做过几次！)好消息是，这些代码不包含任何库代码；只包含您编写的代码。

如果你已经有了语法，它们很容易编码。首先，你必须摆脱左递归规则(例如，X=X，Y )。这通常很容易做到，所以我把它作为练习。(对于列表形成规则，您不必这样做；请参阅下面的讨论)。

那么如果你有形式的BNF规则：

 X = A B C ;

为规则(X，A，B，C)中的每一项创建一个子例程，该例程返回一个布尔值，即“我看到了相应的语法构造”。对于X，代码：

subroutine X()
     if ~(A()) return false;
     if ~(B()) { error(); return false; }
     if ~(C()) { error(); return false; }
     // insert semantic action here: generate code, do the work, ....
     return true;
end X;

A、B、C也是如此。

如果令牌是终端，则编写代码来检查输入流中组成终端的字符串。例如，对于一个数字，检查输入流是否包含数字，并使输入流光标前进超过数字。如果您通过简单地前进或不前进缓冲区扫描指针来解析出缓冲区(对于BASIC，您倾向于一次得到一行)，这尤其容易。这段代码本质上是解析器的词法分析器部分。

如果您的BNF规则是递归的...别担心。只需编写递归调用。它处理的语法规则如下：

T  =  '('  T  ')' ;

这可以编码为：

subroutine T()
     if ~(left_paren()) return false;
     if ~(T()) { error(); return false; }
     if ~(right_paren()) { error(); return false; }
     // insert semantic action here: generate code, do the work, ....
     return true;
end T;

如果您有一个BNF规则和一个替代规则：

 P = Q | R ;

然后使用可选选项来编码P：

subroutine P()
    if ~(Q())
        {if ~(R()) return false;
         return true;
        }
    return true;
end P;

有时，您会遇到列表形成规则。这些往往是左递归的，这种情况很容易处理。基本思想是使用迭代而不是递归，这避免了以“显而易见”的方式进行无限递归。示例：

L  =  A |  L A ;

您可以使用迭代进行编码，如下所示：

subroutine L()
    if ~(A()) then return false;
    while (A()) do { /* loop */ }
    return true;
end L;

通过这种方式，您可以在一两天内编写数百条语法规则。还有更多的细节需要填写，但这里的基础知识应该足够了。

如果你的空间真的很紧张，你可以构建一个虚拟机来实现这些想法。这就是我在70年代所做的，当时你可以得到8K的16位字。

如果你不想手工编写代码，你可以用一个元编译器(Meta II)自动化它，它会产生本质上相同的东西。这些都是令人兴奋的技术乐趣，真的把所有的工作都拿出来了，即使是大文法也是如此。

2014年8月：

我收到了很多关于“如何使用解析器构建AST”的请求。有关这个问题的详细信息，请参阅我的另一个SO答案https://stackoverflow.com/a/25106688/120163

2015年7月：

有很多人想写一个简单的表达式求值器。您可以通过执行上面的"AST builder“链接所建议的相同类型的操作来完成此操作；只需执行算术运算，而不是构建树节点。这是an expression evaluator done this way。

2021年10月：

值得注意的是，当您的语言没有递归下降处理不好的复杂性时，这种解析器就可以工作。我提供了两种复杂性: a)真正的歧义解析(例如，不止一种解析短语的方法)和b)任意长的前视(例如，不受常量的限制)。在这些情况下，递归下降变成了地狱中的递归下降，是时候获得一个能够处理它们的解析器生成器了。请参阅我的简介，了解使用GLR解析器生成器来处理超过50种不同语言的系统，包括所有这些复杂的语言，甚至到了可笑的地步。

Answer 3

您可以在Linux上使用flex/bison和它的本机gcc来生成代码，然后将这些代码与您的AVR gcc针对嵌入式目标进行交叉编译。