在8位嵌入式系统上,是否有其他可供使用的flex/bison?

我已经实现了针对 ATmega328p .这个芯片有32K的只读存储器,只有2K的随机存储器。RAM无疑是更重要的限制——如果您还没有绑定到特定的芯片,请选择一个具有尽可能多的RAM的芯片。这会让你的生活更轻松。

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

• 默认情况下,flex&bison依赖于一些在avr libc中不可用或不工作的标准库函数(尤其是I/O函数)。我很确定有支持的解决方法,但这是您需要考虑的一些额外工作。
• AVR有 Harvard Architecture . C不是为了解释这个,所以 默认情况下,甚至常量变量也加载到RAM中。 . 您必须使用特殊的宏/函数来存储和访问 flash 和 EEPROM . flex&bison创建一些 相当地 大的查找表,这些会很快吃掉你的内存。除非我弄错了(这很可能),否则您必须编辑输出源以利用特殊的flash&eeprom接口。

在拒绝了flex&bison之后,我开始寻找其他的发电机工具。以下是我考虑的几个问题:

• LEMON
• Ragel
• re2c

你可能还想看看 Wikipedia's comparison .

最后,我手工编写了lexer和解析器。

为了解析,我使用了递归下降解析器。我想 Ira Baxter 已经做了足够的工作来涵盖这个主题,并且有很多在线教程。

对于lexer,我编写了所有终端的正则表达式,绘制了等价状态机的图表,并使用 goto 是为了在各州之间跳跃。这很乏味,但效果很好。顺便说一下, 古托 是实现状态机的一个很好的工具——您的所有状态都可以在相关代码的旁边有清晰的标签,没有函数调用或状态变量开销,而且它是尽可能快的。C并没有更好的构造来构建静态机器。

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

如果您想要一种简单的代码解析器方法,或者您的空间很紧,您应该手工编写一个递归下降解析器;这些基本上是 LL (1)解析器。这对于“简单”和基本的语言尤其有效。(我在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。

如果令牌是终端,则编写检查的代码 构成终端的字符串的输入流。 例如,对于数字,请检查输入流是否包含数字,并将 输入流光标经过数字。如果你 正在从缓冲区中分析(对于基本,您往往一次得到一行) 通过简单地前进或不前进缓冲扫描指针。 这段代码本质上是解析器的lexer部分。

如果您的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”的请求。关于这个问题的详细信息,它基本上阐述了这个答案,请参阅我的另一个答案。 https://stackoverflow.com/a/25106688/120163

2015年7月:

有很多人想写一个简单的表达式计算器。您可以通过执行上面“ast builder”链接所建议的相同类型的操作来实现这一点;只需执行算术而不是构建树节点。 这里是 an expression evaluator done this way .

您可以使用Linux上的flex/bison及其本机gcc来生成代码,然后用avr gcc对嵌入的目标进行交叉编译。

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

试试Boost::Spirit。它是一个只有头文件的库,可以在C++中完全下载并构建一个非常快、干净的解析器。使用C++中的重载运算符代替特殊语法文件。

与其重新发明轮子,不如看看 LUA: www.lua.org . 它是一种解释性语言,旨在嵌入其他软件中,并用于小型系统,如嵌入式系统。内置的过程语法分析树、控制逻辑、数学和变量支持无需重新设计其他成千上万人已经调试和使用的东西。它是可扩展的,也就是说你可以通过添加自己的C函数来添加到语法中。