有没有可用于8位嵌入式系统的flex / bison的替代品？ [英] Is there an alternative for flex/bison that is usable on 8-bit embedded systems?
问题描述
我正在使用avr-gcc工具链，在C语言中使用简单的BASIC类似语言编写一个小型解释器作为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依赖于某些标准库函数（特别是对于I / O），在avr-libc中不可用或不起作用。我很确定有支持的解决方法，但这是需要考虑的一些额外的工作。
- 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:
- LEMON
- Ragel
- re2c
您可能还需要查看维基百科的比较
You might also want to take a look at Wikipedia's comparison.
最终，我最终对词法分析器和解析器进行了手动编码。
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屋！
