7

我想在 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. string我使用via的首选方式，默认情况下stringstream会忽略\n。所以我需要简单的方法来告诉（同样！）stringstream在启用某个状态时不要忽略换行符。
  3. 简单enum状态是否足以进行多级解析（范围内的范围{...{...}...}），还是需要 hacky 实现？
  4. 这是我想到的草案状态：
    • upper: 读取全局、exe、lib+ 目标名称...
    • normal: 在一个范围内，可以读取 SOURCES...，创建用户变量...
    • list：将项目添加到列表中，直到遇到换行符。

每个范围都会有一种条件（例如 win32:global { gcc:CFLAGS = ... }），并且需要在任何地方以完全相同的方式处理（即使在list状态中，每个项目）。

感谢您的任何意见。

4

3 回答 3

18

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

如果您将堆栈添加到 FSM，那么您将进入下推自动机领域。非确定性下推自动机等价于上下文无关文法（尽管确定性下推自动机严格来说没有那么强大）。LALR(1) 解析器生成器实际上在内部生成确定性下推自动机。一本好的编译器设计教科书将涵盖从语法构造下推自动机的确切算法。（通过这种方式，添加堆栈并不是“hacky”。​​）这篇维基百科文章 还描述了如何从你的语法构造 LR(1) 下推自动机，但是 IMO，这篇文章并不像它可能的那样清楚。

如果您的作用域嵌套深度有限（即您有upper,normal和list级别但没有嵌套lists 或嵌套normals），那么您可以使用没有堆栈的 FSM。

于 2010-06-21T13:42:47.557 回答
3

分析文本输入流以进行解析有两个阶段：

词法分析：这是您的输入流被分解为词法单元的地方。它查看一系列字符并生成标记（类似于口语或书面语言中的单词）。有限状态机非常擅长词法分析，前提是您已经对词法结构做出了良好的设计决策。从您上面的数据来看，单个词位可能是您的关键字（例如“global”）、标识符（例如“bitwise”、“SOURCES”）、符号标记（例如“{”“}”、“.”、“/”） )、数值、转义值（例如“\n”）等。

句法/语法分析： 在生成标记序列时（或者可能在您这样做时），您需要能够分析结构以确定标记序列是否与您的语言设计一致。为此，您通常需要某种解析器，但如果语言结构不是很复杂，您可以使用有限状态机来代替。通常（并且由于您特别希望在您的案例中使用嵌套结构）您将需要使用 Ken Bloom 描述的技术之一。

因此，针对您的问题：

我应该为我的状态使用枚举还是抽象类+衍生物？

我发现对于小型标记器，状态/转换值矩阵是合适的，例如next_state = state_transitions[current_state][current_input_char]. 在这种情况下，next_stateandcurrent_state是一些整数类型（可能包括枚举类型）。当您转换到无效状态时，会检测到输入错误。令牌的结束是基于有效结束状态的状态标识来标识的，在给定下一个输入字符的情况下，没有有效的转换可用于另一个状态。如果您担心空间，则可以改用地图矢量。制作国家课程是可能的，但我认为这可能会让事情变得比你需要的更困难。

阅读列表时，我不需要忽略 \n。

您可以创建一个名为“\n”的标记，或者创建一个更通用的转义标记（前面带有反斜杠的标识符。如果您正在谈论识别源中的换行符，那么这些只是您需要创建转换的字符在您的状态转换矩阵中（但是请注意 Unix 和 Windows 换行符之间的区别；您可以创建一个在其中任何一个上运行的 FSM）。

简单的枚举状态是否足以进行多级解析（范围内的范围 {...{...}...}）还是需要 hacky 实现？

这是您需要语法或下推自动机的地方，除非您可以保证嵌套不会超过某个级别。即使那样，它也可能会使您的 FSM 变得非常复杂。

这是我想到的草案状态：...

请参阅上面我对词汇和语法分析的评论。

于 2010-06-21T14:52:29.500 回答
1

对于解析，我总是尝试使用已经证明有效的东西：ANTLR和ANTLRWorks，这对设计和测试语法有很大帮助。您可以为 C/C++（和其他语言）生成代码，但您需要为这些语言构建 ANTLR 运行时。

当然，如果你发现flex或bison更容易使用，你也可以使用它们（我知道它们只生成 C 和 C++，但我可能错了，因为我有一段时间没有使用它们了）。

于 2010-06-21T14:19:02.367 回答