我想解析一个自我设计的文件格式与类似FSM的解析器 in C++ （这是一个 teach-myself-c++-the-hard-way-by-doing-something-big-and-difficult 项目:)） . 我有一个带有换行符的标记化字符串，表示euh ...行的结束 . 见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对我的需求/知识来说足够简单/可扩展 . 据我所知（并希望我的文件设计），我不需要并发状态或任何类似的东西 . 一些设计/实施问题：
-
我应该为我的州使用
enum或抽象的class衍生物吗？第一个可能更适合小语法，但后来可能会变得丑陋，第二个恰恰相反 . 因为它的简单，我倾向于第一个 . enum example和class example . 编辑：this suggestion为goto怎么样，我以为他们在C中是邪恶的？ -
在阅读列表时，我不需要忽略
\n. 我通过stringstream使用string的首选方法默认会忽略\n. 所以我需要简单的方法来告诉（相同！）stringstream在启用某个状态时不要忽略换行符 . -
简单的
enum状态是否足以进行多级解析（范围{...{...}...}中的范围）还是需要hacky实现？ -
这是我想到的草案状态：
-
upper：读取global，exe，lib目标名称...... -
normal：在范围内，可以读取SOURCES ...，创建用户变量...... -
list：将项添加到列表中，直到遇到换行符 .
每个范围都有一种条件（例如win32：global {gcc：CFLAGS = ...}），并且需要以完全相同的方式处理eveywhere（即使在 list 状态，每个项目） .
感谢您的任何意见 .
3 回答
对于解析，我总是尝试使用已经证明有用的东西：ANTLR with ANTLRWorks这对设计和测试语法有很大帮助 . 您可以为C / C（和other languages）生成代码，但是您需要为这些语言构建ANTLR运行时 .
当然，如果您发现flex或bison更容易使用，您也可以使用它们（我知道它们只生成C和C但我可能错了，因为我有一段时间没有使用它们） .
如果你有嵌套作用域，那么有限状态机不是正确的方法，你应该看一下Context Free Grammar解析器 . 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 .分析文本输入流以进行解析有两个阶段：
Lexical Analysis: 这是输入流被分解为词汇单位的地方 . 它查看一系列字符并生成令牌（与口头或书面语言中的单词类似） . 如果您对词法结构做出了很好的设计决策，那么有限状态机非常擅长词法分析 . 根据您的上述数据，单个词汇类似于您的关键字（例如"global"），标识符（例如"bitwise"，"SOURCES"），符号tokesn（例如"{" "}"，"."，"/"），数值，转义值（例如"\n"）等 .
Syntactic / Grammatic Analysis: 生成一系列令牌（或者在您这样做时），您需要能够分析结构以确定令牌序列是否与您的语言设计一致 . 您通常需要某种解析器，但如果语言结构不是很复杂，您可以使用有限状态机来代替它 . 通常（并且因为您特别需要在您的情况下使用嵌套结构），您将需要使用Ken Bloom描述的技术之一 .
所以回答你的问题：
我应该为我的州使用枚举或抽象类衍生物吗？
我发现对于小型标记化器，状态/转移值的矩阵是合适的，类似于
next_state = state_transitions[current_state][current_input_char]. 在这种情况下，next_state和current_state是一些整数类型（可能包括枚举类型） . 转换到无效状态时会检测到输入错误 . 基于有效状态的状态标识来识别令牌的结束，在给定下一个输入字符的情况下，没有有效转换可用于另一状态 . 如果你认为事情可能比你需要的更困难 .在阅读列表时，我不需要忽略\ n .
您可以要么创建一个名为“\ n”的标记，要么创建一个更通用的转义标记（一个前面带有反斜杠的标识符 . 如果你在谈论识别源代码中的换行符，那么这些只是你需要在你的转换中创建转换的字符状态转换矩阵（但要注意Unix和Windows换行符之间的差异;您可以创建一个可在其上运行的FSM） .
简单的枚举状态是否足以进行多级解析（范围{... ...}中的范围）还是需要hacky实现？
这是您需要语法或下推自动机的地方，除非您可以保证嵌套不会超过某个级别 . 即使这样，它也可能使您的FSM变得非常复杂 .
这是我想到的草案状态：......
请参阅上面关于词汇和语法分析的文章 .