在为我的编程语言的词法分析器构建 DFA 时，每个字符（例如n，，，i）是否应该作为所有标记路径中的单个共享节点出现，或者如果它们出现在不同的路径中，我是否应该允许同一字符出现重复的节点（例如，，和 的f单独n节点）？intreturnblank
在实施效率、清晰度和正确性方面，这两种方法之间的权衡是什么？
我添加了一张图片来直观地表达我的意思。
AskOverflow.Dev
DFA 表示中的一个节点对应一个状态。如果要表示两个不同的状态，则至少需要两个不同的节点。
因此，当您的语言中有单词
return和func，并且您到目前为止已经读到 时ret，您处于与读到不同的f状态，即使在这两种状态下，字母 都有过渡u。问题是，在处理完 之后，u您仍然必须知道您是否正在完成单词return或func，否则您也会接受单词furn和retunc。所以不，您不能将这两种状态视为相等。意识到状态与您可能接受的下一个字符没有直接关系。更正确的做法是将其视为代表您已经读取的内容。
因此，在 DFA 图中，您可以将节点
i和i3合并为一个节点，然后从那里进行两个传出转换以继续进行if或int。您已经将此原则应用于起始字母e，但可以继续对后续的l（合并l1和l2）和s（合并s1和s2）执行此操作，以便拆分只会在后一种状态下发生，即e（对于else）和i（对于elsif）。