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

Question

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

如果我写这个在我的Linux机器上运行,我可以使用flex/bison.现在我把自己限制在一个8位平台上,我必须手动完成所有操作,不是吗？

Answer 1

如果你想要一种简单的方法来编码解析器,或者你的空间很紧,你应该手工编写一个递归下降解析器; 这些基本上是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.

如果令牌是终端,则编写代码以检查输入流以查找构成终端的字符串.例如,对于Number,检查输入流是否包含数字并使输入流光标超过数字.如果您通过简单地前进或不前进缓冲区扫描指针来解析缓冲区(对于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答案/sf/answers/1757468191/

2015年7月:

有很多人想写一个简单的表达式评估器.您可以通过执行上面"AST builder"链接建议的相同类型的操作来完成此操作; 只是做算术而不是构建树节点.这是一个以这种方式完成的表达式求值程序.

Answer 2

我已经为一个针对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后,我去寻找其他的发电机工具.以下是我考虑的一些内容:

• 柠檬
• Ragel
• re2c

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

最终,我最终手工编写了词法分析器和解析器.

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

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

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

Answer 3

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