在8位嵌入式系统上编写像Flex/Bison一样可用的解析器

Question

在8位嵌入式系统上编写像Flex/Bison一样可用的解析器

parsingembeddedbisonflex-lexeravr-gcc

90

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

如果我要在Linux上运行该程序，我可以使用flex/bison。既然我限定了自己使用8位平台，那我应该如何编写解析器呢？

- Johan

1

你打算使用特定的芯片吗？它有多少ROM/RAM？ - Steve S

更新@mre的链接。embedded.com已经删除了他们的URL。（http://www.embedded.com/design/prototyping-and-development/4024523/Lex-and-Yacc-for-Embedded-Programmers） - pgvoorhees

似乎只有堆栈语言（例如Forth等）才有机会在2KB RAM上运行，需要刷入内核。 - Jacek Cz

4个回答

60

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

起初我考虑使用Flex/Bison。出于两个主要原因，我决定放弃这个选项：

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

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

LEMON
Ragel

re2c

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

最终，我选择手工编写词法分析器和语法分析器。

对于语法分析，我使用了递归下降分析器。我认为Ira Baxter已经对此进行了充分的讨论，并且有很多在线教程。

对于我的词法分析器，我为所有终端符号编写了正则表达式，绘制了等效的状态机图，并将其实现为一个巨大的函数，使用goto在不同状态之间跳转。虽然这很繁琐，但结果非常好。另外，goto是实现状态机的好工具--所有状态的标签都可以清晰地显示在相关代码旁边，没有函数调用或状态变量开销，速度也尽可能快。在构建静态状态机方面，C确实没有更好的构造方法。

需要考虑的一件事情：词法分析器实际上只是解析器的一种特殊形式。最大的区别在于，正则语法通常足以进行词法分析，而大多数编程语言具有（基本上）上下文无关的语法结构。因此，您可以使用递归下降解析器作为词法分析器，或者使用解析器生成器编写词法分析器。只是通常不像使用更专业的工具那么方便。

- Steve S

小问题，但是C语言可以很好地处理AVR和哈佛架构。相反，gcc编译器并不是为了处理哈佛架构而设计的。当AVR指令集被创建时，硬件设计师咨询了一家知名的编译器供应商：https://web.archive.org/web/20060529115932/https://web.engr.oregonstate.edu/~traylor/ece473/pdfs/atmel_wpaper_compiler_C.pdf - Prof. Falken

1

我老实说没有跟上最新C标准的细节，但我所了解的是，C99规定了一个单一的数据地址空间，因此在哈佛结构的程序存储器中放置常量需要一些非标准的东西。标准的“嵌入式C”扩展确实提供了一种处理多个不同地址空间数据的机制。http://www.open-std.org/JTC1/SC22/WG14/www/docs/n1169.pdf（第37页）。 - Steve S

1

我没有测试过，但我预计“goto”方法的内存占用会比查找表大，并且它无法移动到外部ROM，因为它是可执行代码。另一方面，我承认这种方法可能非常快速，在嵌入式系统中可能非常重要。 - Piotr Siupa

1

我没有测试过，但我预计“goto”方法的内存占用会比查找表大，并且它不能移动到外部ROM，因为它是可执行代码。另一方面，我承认它可能非常快速，这在嵌入式系统中可能非常重要。 - undefined

11

您可以在Linux上使用本地gcc编译器使用flex/bison生成代码，然后使用AVR gcc进行交叉编译以用于嵌入式目标。

- Paul R

我非常确定AVR甚至没有malloc和free，因为它不支持完整的C语言。（嵌入式系统实际上没有足够的内存来支持这些高级功能。）这可能会使交叉编译变得具有挑战性。 - Piotr Siupa

我非常确定 AVR 并没有 malloc 和 free，因为它不支持完整的 C 语言。（嵌入式系统实际上没有足够的内存来支持这些高级功能。）这可能会使交叉编译变得具有挑战性。 - undefined

2

GCC可以进行跨平台编译，但是你需要在运行编译器的平台上运行flex和bison。它们只是生成C代码，然后由编译器构建。测试一下生成的可执行文件的大小。请注意，它们有运行时库（libfl.a等），你也需要将其交叉编译到目标平台。

- ConcernedOfTunbridgeWells

我仍需调查这些库的大小，这也是我首先提出问题的原因。我想要针对小型MCU特别定制的东西。 - Johan

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Ira Baxter · Accepted Answer

如果您想要一种简单的方式来编写解析器，或者空间有限，那么您应该手写递归下降解析器；这些本质上是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://dev59.com/KF8f5IYBdhLWcg3wFvWn#25106688，该答案实际上详细说明了这一点。

2015年7月：

有很多人想编写一个简单的表达式求值器。您可以通过执行与上面“AST构建器”链接中建议的相同类型的操作来实现此目的；只需执行算术运算而不是构建树节点即可。这是用这种方式完成的表达式求值器。

2021年10月：

值得注意的是，这种类型的解析器适用于您的语言没有递归下降处理不好的复杂性的情况。我提供了两种复杂性：a）真正的歧义解析（例如，解析短语的方法不止一种），以及b）任意长的前瞻（例如，不受常数限制）。在这些情况下，递归下降变成了递归下降进入地狱的时候，就是使用可以处理它们的解析器生成器的时候了。请参见我的个人简介，其中提供了一种使用GLR解析器生成器处理50多种不同语言的系统，甚至到了荒谬的地步。