c++ - 有限状态机解析器

Question

我想使用类似 FSM 的解析器在 C++ 中 解析自行设计的文件格式(这是一个teach-myself-c++-the-hard-way-by-做一些大而难的 类的项目 :))。我有一个带有换行符的标记化字符串，表示一行结束。参见 here for an input example .所有的评论都会被过滤掉，所以我有一个像这样的 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 example和 class example .编辑:那this suggestion呢？对于 goto，我认为它们在 C++ 中是邪恶的？
2. 阅读列表时，我需要注意不要忽略 \n。我的首选方式是通过 stringstream 使用 string，默认情况下会忽略 \n。所以我需要简单的方法来告诉(相同!)stringstream 在启用特定状态时不要忽略换行符。
3. 简单的 enum 状态是否足以进行多级解析(范围 {...{...}...} 内的范围)或者是否需要骇人听闻的实现？
4. 这是我想到的草案状态:
   • upper:读取全局、exe、lib+目标名称...
   • 正常:在作用域内，可以读取 SOURCES...，创建用户变量...
   • list:将项目添加到列表中，直到遇到换行符。

每个作用域都有一种条件(例如 win32:global { gcc:CFLAGS = ... })并且需要以完全相同的方式处理每个地方(即使在 list 中)状态，每个项目)。

感谢任何输入。

Answer 1

如果您有嵌套作用域，那么有限状态机不是正确的方法，您应该查看上下文无关语法分析器。一个LL(1) parser可以写成一组递归函数，或 LALR(1) parser可以使用解析器生成器(例如 Bison)编写。

如果您将堆栈添加到 FSM，那么您将进入 pushdown automaton领土。非确定性下推自动机等同于上下文无关文法(虽然 deterministic pushdown automaton 严格来说没有那么强大。)LALR(1) 解析器生成器实际上在内部生成确定性下推自动机。一本好的编译器设计教科书将涵盖从语法构造下推自动机的确切算法。 (这样，添加堆栈就不是“hacky”了。)This Wikipedia article还介绍了如何根据您的语法构造 LR(1) 下推自动机，但 IMO，这篇文章并没有那么清晰。

如果您的范围嵌套只有有限深度(即您有 upper、normal 和 list 级别，但您没有嵌套 list 或嵌套的 normal)，那么您可以使用没有堆栈的 FSM。