有限状态机解析器

Question

我想在C++中用类似FSM的解析器解析一个自行设计的文件格式(这是teach-myself-c++-the-hard-way-by-doing-something-big-and-difficult一种项目:)).我有一个带有换行符的标记化字符串,表示euh ...行的结束.请参阅此处获取输入示例.所有的评论和垃圾都会被过滤掉,所以我有一个像这样的std :: string:

global \n { \n SOURCE_DIRS src \n HEADER_DIRS include \n SOURCES bitwise.c framing.c \n HEADERS ogg/os_types.h ogg/ogg.h \n } \n ...

语法说明:

• {}是范围,大写单词表示要遵循选项/文件列表.
• \n仅在选项/文件列表中很重要,表示列表的结尾.

所以我认为FSM对我的需求/知识来说足够简单/可扩展.据我所知(并希望我的文件设计),我不需要并发状态或任何类似的东西.一些设计/实施问题:

1. 我应该为我的州使用一个enum或一个抽象class+衍生物吗？第一个可能更适合小语法,但后来可能会变得丑陋,第二个恰恰相反.因为它的简单,我倾向于第一个.enum示例和类示例.编辑:什么这个建议的goto,我认为他们在C++是恶？
2. 阅读清单时,我不必忽视\n.默认情况下,我首选使用stringvia的方法.因此,当启用某个状态时,我需要简单的方式告诉(相同!)不要忽略换行符.stringstream\nstringstream
3. 简单enum状态是否足以进行多级解析(范围内的范围{...{...}...}),还是需要hacky实现？
4. 这是我想到的草案状态:
   • upper:读取全局,exe,lib +目标名称......
   • normal:在范围内,可以读取SOURCES ...,创建用户变量......
   • list:将项添加到列表中,直到遇到换行符.

每个范围都有一种条件(例如win32:global {gcc:CFLAGS = ...}),需要以完全相同的方式处理eveywhere(即使在list状态,每个项目).

感谢您的任何意见.

Answer 1

如果你有嵌套作用域,那么有限状态机不是正确的方法,你应该看一下Context Free Grammar解析器.的LL(1)解析器可被写为一组递归funcitons的,或LALR(1)解析器可以使用解析器生成如野牛写入.

如果您向FSM添加堆栈,那么您将进入下推自动机区域.非确定性下推自动机相当于上下文无关语法(尽管确定性下推自动机严格地说不那么强大.)LALR(1)解析器生成器实际上在内部生成确定性下推自动机.一个好的编译器设计教科书将涵盖从语法构造下推自动机的确切算法.(通过这种方式,添加一个堆栈不是"hacky".​​)这篇维基百科文章 还描述了如何从你的语法构建LR(1)下推自动机,但IMO,文章并不是那么清晰.

如果你的范围巢只有有限深(即你有upper,normal和list水平,但你没有嵌套listS或嵌套normal多个),那么你可以使用一个FSM不会堆栈.