编写一个可在 8 位嵌入式系统上使用的解析器，如 Flex/Bison

您可以在 Linux 上使用 flex/bison 及其原生 gcc 来生成代码，然后将这些代码与嵌入式目标的 AVR gcc 交叉编译。

GCC 可以交叉编译到各种平台，但您需要在运行编译器的平台上运行 flex 和 bison。他们只是吐出编译器随后构建的 C 代码。测试它以查看生成的可执行文件到底有多大。请注意，它们具有运行时库（等），您还必须将其交叉编译到目标。libfl.a

如果你想要一种简单的方法来编写解析器，或者你的空间有限，你应该手动编写一个递归下降解析器;这些本质上是 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”链接建议的相同类型来做到这一点;只需进行算术运算，而不是构建树节点。 下面是一个以这种方式完成的表达式计算器。

2021年10月：

值得注意的是，当你的语言没有递归下降不能很好地处理的复杂情况时，这种解析器就会起作用。我提供了两种复杂功能：a）真正模棱两可的解析（例如，解析一个短语的多种方法）和b）任意长的展望（例如，不受常量的限制）。在这些情况下，递归下降变成了递归下降到地狱，是时候获得一个可以处理它们的解析器生成器了。请参阅我的简历，了解一个使用 GLR 解析器生成器处理 50 多种不同语言的系统，包括所有这些复杂功能，甚至到了荒谬的地步。

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

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

• 默认情况下，Flex 和 Bison 依赖于一些标准库函数（尤其是 I/O），这些函数在 avr-libc 中不可用或工作方式不相同。我很确定有受支持的解决方法，但这是您需要考虑的一些额外工作。
• AVR 具有哈佛架构。C 语言并不是为了解决这个问题而设计的，因此默认情况下，即使是常量变量也会加载到 RAM 中。您必须使用特殊的宏/函数来存储和访问闪存和EEPROM中的数据。Flex & Bison 创建了一些相对较大的查找表，这些查找表会很快占用你的 RAM。除非我弄错了（这是很有可能的），否则您必须编辑输出源才能利用特殊的闪存和EEPROM接口。

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

• 柠檬
• 拉格尔
• TETC公司

您可能还想看看维基百科的比较。

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

为了解析，我使用了递归下降解析器。我认为艾拉·巴克斯特（Ira Baxter）已经做了足够的工作来涵盖这个主题，并且网上有很多教程。

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

需要考虑的事情：词法分析器实际上只是解析器的专门化。最大的区别是常规语法通常足以进行词法分析，而大多数编程语言（大部分）具有上下文无关的语法。因此，没有什么能阻止您将词法分析器实现为递归下降解析器或使用解析器生成器编写词法分析器。它通常不如使用更专业的工具方便。