83

我正在使用 avr-gcc 工具链为类似 BASIC 的简单语言编写一个小型解释器，作为 C 语言 AVR 微控制器上的练习。

如果我写这个是为了在我的 Linux 机器上运行，我可以使用 flex/bison。既然我将自己限制在 8 位平台，我将如何编写解析器？

4

4 回答 4

237

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

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

然后，如果您有以下形式的 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 多种不同语言的系统，包括所有这些复杂性甚至到了荒谬的地步。

于 2010-02-25T19:00:35.913 回答
60

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

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

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

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

您可能还想看看Wikipedia 的比较。

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

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

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

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

于 2010-02-26T00:15:34.390 回答
11

您可以在 Linux 上使用 flex/bison 及其本机 gcc 来生成代码，然后您将使用 AVR gcc 为嵌入式目标进行交叉编译。

于 2010-02-11T16:59:58.297 回答
2

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

于 2010-02-11T17:04:11.810 回答