在8位embedded式系统上可以使用flex / bison吗？
我正在使用avr-gcc工具链为C语言的AVR微控制器编写一个简单的BASIC语言的解释器。 不过，我想知道是否有任何开源工具可以帮助我编写词法分析器。
如果我写这个在我的Linux机器上运行，我可以使用flex / bison。 现在我把自己限制在一个8位的平台上，我必须全部手工完成，否则呢？
我已经实现了针对ATmega328p的简单命令语言的parsing器。 这个芯片有32K ROM和只有2K RAM。 内存绝对是更重要的限制 – 如果你还没有绑定到一个特定的芯片，select尽可能多的RAM尽可能。 这会让你的生活更轻松。
起初我考虑使用flex / bison。 我决定反对这个select有两个主要原因：
- 默认情况下，Flex和Bison依赖于一些标准的库函数（特别是I / O），这些函数在avr-libc中不可用或者不兼容。 我很确定有支持的解决方法，但这是一些额外的工作，你需要考虑。
- AVR有哈佛架构 。 C并不是为了解决这个问题而devise的，所以即使是常量variables也默认加载到RAM中 。 您必须使用特殊的macros/函数来存储和访问闪存和EEPROM中的数据。 Flex和Bison创build了一些相对较大的查找表，这些会很快消耗掉RAM。 除非我弄错了（这很可能），否则你将不得不编辑输出源以利用特殊的Flash和EEPROM接口。
拒绝Flex＆Bison后，我去寻找其他的发电机工具。 以下是我考虑的几个问题：
- 柠檬
- Ragel
- re2c
你可能也想看看维基百科的比较 。
最后，我结束了对词法分析器和parsing器的编码。
为了parsing，我使用了recursion下降parsing器。 我认为艾拉·巴克斯特（Ira Baxter ）已经在这个话题上做了足够的工作，网上有很多教程。
对于我的词法分析器，我写了所有terminal的正则expression式，绘制了等价的状态机，并将它作为一个巨大的函数来实现，使用goto来跳转状态。 这很乏味，但结果很好。 goto一下， goto是实现状态机的一个很好的工具 – 你所有的状态都可以在相关的代码旁边有清晰的标签，没有函数调用或者状态variables的开销，并且它的速度和你所能得到的一样快。 C真的没有一个更好的构build静态机器。
需要考虑的事情：词法分析器实际上只是parsing器的一个专业化。 最大的区别是正规语法通常足以进行词法分析，而大多数编程语言都有（大部分）上下文无关文法。 所以没有什么能阻止你将词法分析器作为recursion下降parsing器来实现，或者使用parsing器生成器来编写词法分析器。 这通常不像使用更专业的工具那么方便。
如果你想要一个简单的方法来编码parsing器，或者你在空间上很紧张，你应该手动编码一个recursion下降parsing器; 这些本质上是LL（1）parsing器。 这对于像Basic这样“简单”的语言来说特别有效。 （我在70年代做过其中的几个！）。 好消息是这些不包含任何库代码; 就是你写的。
如果你已经有一个语法，那么它们很容易编码。 首先，你必须摆脱左recursion规则（例如，X = XY）。 这一般很容易做，所以我把它作为一个练习。 （您不必为列表形成规则执行此操作，请参阅下面的讨论）。
那么如果你有BNF规则的forms：
X = ABC ;
为规则（X，A，B，C）中的每个项目创build一个子例程，返回一个布尔值，表示“我看到了相应的语法结构”。 对于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
如果令牌是terminal，则编写代码来检查inputstream中是否包含组成terminal的string。 例如，对于一个数字，检查inputstream是否包含数字，并将inputstream游标推进到数字之后。 如果您正在parsing出一个缓冲区（对于BASIC，您倾向于一次只获取一行），那么这样做尤其容易，只需简单地推进或不推进缓冲区扫描指针即可。 这段代码本质上是parsing器的词法分析器部分。
如果你的BNF规则是recursion的…别担心。 只需编码recursion调用。 这处理语法规则，如：
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 ;
然后用另一种select编码P：
subroutine P() if ~(Q) {if ~(R) return false; return true; } return true; end P;
有时候你会遇到列表形成规则。 这些往往是recursion的，这种情况很容易处理。 例：
L = A | LA ;
你可以这样编码：
subroutine L() if ~(A()) then return false; while (A()) do // loop return true; end L;
你可以用这种方法在一两天内编写几百个语法规则。 有更多的细节可以填写，但这里的基础应该是绰绰有余。
如果你的空间非常紧张，你可以build立一个实现这些想法的虚拟机。 这就是我在70年代所做的，当时可以得到8K 16位的字。
如果你不想手动编写这个代码，你可以用一个产生本质上相同的东西的元编译器（ Meta II ）自动化它。 这些都是令人兴奋的技术乐趣，并且真的把所有的工作都做了，甚至对于大的语法。
2014年8月：
我收到了很多关于“如何用parsing器构buildAST”的请求。 有关详细信息，本质上阐述了这个答案，请参阅我的其他答案https://stackoverflow.com/a/25106688/120163
2015年7月：
有很多人想写一个简单的expression式评估器。 你可以通过做与上面的“AST生成器”链接相同的东西来做到这一点; 只是做算术而不是build立树节点。 这里是一个expression式评估器 。
您可以在Linux上使用flex / bison来生成代码，然后使用您的AVR gcc对embedded式目标进行交叉编译。
GCC可以交叉编译到各种平台，但是在运行编译器的平台上运行flex和bison。 他们只是吐出编译器随后构build的C代码。 testing一下，看看有多大的可执行文件是真的。 请注意，他们有运行时库（ libfl.a等），你也必须交叉编译到您的目标。
尝试Boost :: Spirit。 这是一个只有头文件的库，你可以在C ++中完整地构build一个非常快速，干净的parsing器。 使用C ++中的重载操作符而不是特殊的语法文件。
看看LUA：www.lua.org ，而不是重新发明轮子。 它是一种解释性语言，意味着embedded到其他软件中，并用于embedded式系统等小型系统。 内置程序语法parsing树，控制逻辑，math和variables支持 – 不需要重新创build其他成千上万个已经debugging和使用的东西。 它是可扩展的，这意味着你可以通过添加自己的C函数来添加到语法。
