是否有可用于 8 位嵌入式系统的 flex/bison 替代方案? [英] Is there an alternative for flex/bison that is usable on 8-bit embedded systems?
问题描述
我正在为一种简单的类似 BASIC 的语言编写一个小型解释器，作为使用 avr-gcc 工具链在 C 语言中的 AVR 微控制器上的练习.但是，我想知道是否有任何开源工具可以帮助我编写词法分析器和解析器.
I'm writing a small interpreter for a simple BASIC like language as an exercise on an AVR microcontroller in C using the avr-gcc toolchain. However, I'm wondering if there are any open source tools out there that could help me writing the lexer and parser.
如果我写这个在我的 Linux 机器上运行，我可以使用 flex/bison.现在我把自己限制在 8 位平台上，我必须手工完成，还是不?
If I would write this to run on my Linux box, I could use flex/bison. Now that I restricted myself to an 8-bit platform I have to do it all by hand, or not?
推荐答案
我已经实现了一个针对ATmega328p.这个芯片有32k ROM，只有2k RAM.RAM 绝对是更重要的限制——如果您还没有绑定到特定芯片，请选择一个具有尽可能多 RAM 的芯片.这将使您的生活更轻松.
I've implemented a parser for a simple command language targeted for the ATmega328p. This chip has 32k ROM and only 2k RAM. The RAM is definitely the more important limitation -- if you aren't tied to a particular chip yet, pick one with as much RAM as possible. This will make your life much easier.
起初我考虑使用 flex/bison.我出于两个主要原因决定不使用此选项:
At first I considered using flex/bison. I decided against this option for two major reasons:
- 默认情况下，Flex &Bison 依赖于一些在 avr-libc 中不可用或无法正常工作的标准库函数(尤其是 I/O).我很确定有受支持的变通方法，但您需要考虑一些额外的工作.
- AVR 有一个哈佛架构.C 不是为了解决这个问题而设计的，所以即使是常量变量也默认加载到 RAM 中.您必须使用特殊的宏/函数来存储和访问 flash 和 EEPROM.Flex &Bison 创建了一些相对 大的查找表，这些表会很快耗尽您的 RAM.除非我弄错了(这很有可能)，否则您必须编辑输出源才能利用特殊的 Flash &EEPROM 接口.
- By default, Flex & Bison depend on some standard library functions (especially for I/O) that aren't available or don't work the same in avr-libc. I'm pretty sure there are supported workarounds, but this is some extra effort that you will need to take into account.
- AVR has a Harvard Architecture. C isn't designed to account for this, so even constant variables are loaded into RAM by default. You have to use special macros/functions to store and access data in flash and EEPROM. Flex & Bison create some relatively large lookup tables, and these will eat up your RAM pretty quickly. Unless I'm mistaken (which is quite possible) you will have to edit the output source in order to take advantage of the special Flash & EEPROM interfaces.
在拒绝 Flex & 之后野牛，我去寻找其他生成器工具.以下是我考虑过的一些:
After rejecting Flex & Bison, I went looking for other generator tools. Here are a few that I considered:
您可能还想看看维基百科的比较.
最终，我手工编写了词法分析器和解析器.
Ultimately, I ended up hand coding both the lexer and parser.
为了解析，我使用了递归下降解析器.我认为 Ira Baxter 已经在涵盖这个主题方面做了充分的工作，并且网上有很多教程.
For parsing I used a recursive descent parser. I think Ira Baxter has already done an adequate job of covering this topic, and there are plenty of tutorials online.
对于我的词法分析器，我为我的所有终端编写了正则表达式，绘制了等效的状态机，并使用 goto 在状态之间跳转将其实现为一个巨大的函数.这很乏味，但结果很好.顺便说一句，goto 是一个很好的实现状态机的工具——你的所有状态都可以在相关代码旁边有清晰的标签，没有函数调用或状态变量开销，它是关于尽可能快.C 确实没有更好的构造来构建静态状态机.
For my lexer, I wrote up regular expressions for all of my terminals, diagrammed the equivalent state machine, and implemented it as one giant function using goto's for jumping between states. This was tedious, but the results worked great. As an aside, goto is a great tool for implementing state machines -- all of your states can have clear labels right next to the relevant code, there is no function call or state variable overhead, and it's about as fast as you can get. C really doesn't have a better construct for building static state machines.
需要考虑的事情:词法分析器实际上只是解析器的一种特殊化.最大的区别是常规语法通常足以进行词法分析，而大多数编程语言(大部分)具有上下文无关语法.因此，实际上没有什么能阻止您将词法分析器实现为递归下降解析器或使用解析器生成器来编写词法分析器.它通常不如使用更专业的工具方便.
Something to think about: lexers are really just a specialization of parsers. The biggest difference is that regular grammars are usually sufficient for lexical analysis, whereas most programming languages have (mostly) context-free grammars. So there's really nothing stopping you from implementing a lexer as a recursive descent parser or using a parser generator to write a lexer. It's just not usually as convenient as using a more specialized tool.
这篇关于是否有可用于 8 位嵌入式系统的 flex/bison 替代方案?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
