在8位嵌入式系统上,是否有一种可以用于Flex/Bison的替代方案?

内容来源于 Stack Overflow,并遵循CC BY-SA 3.0许可协议进行翻译与使用

  • 回答 (2)
  • 关注 (0)
  • 查看 (37)

我正在用AVR-GCC工具链在C中的AVR微控制器上为一种简单的基本语言编写一个小型解释器,作为一个练习。但是,我想知道是否有开源工具可以帮助我编写Lexer和解析器。

提问于
用户回答回答于

我已经实现了针对ATmega328p的简单命令语言的解析器。该芯片具有32k ROM和2k RAM。

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

  • 默认情况下,Flex和Bison依赖于一些标准的库函数(特别是I / O),这些函数在avr-libc中不可用或不能工作。我很确定有支持的解决方法,但这需要额外的努力。
  • AVR拥有哈佛架构。C的设计并不是为了解释这一点,所以即使是常量变量也默认加载到RAM中。你必须使用特殊的宏/函数来存储和访问闪存EEPROM中的数据。Flex和Bison创建了一些相对较大的查找表,并且这些会很快消耗你的RAM。

在拒绝Flex&Bison之后,我去寻找其他的工具。以下是我考虑的一些内容:

最终,我最终编写了词法分析器和解析器。

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

用户回答回答于

如果你想要一种简单的方法来编写解析器,或者你的空间很紧,那么你应该手动编写递归下降解析器;这些解析器本质上是LL(1)解析器。好消息是这些代码不包含任何库代码,这正是你所写的。

如果你已经有了语法,那么它们很容易编写。

如果你有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也是如此。

如果你的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;

扫码关注云+社区

领取腾讯云代金券