如何在实现正则表达式解析器时实现 dot(.) 符号

Question

我正在使用龙书中的算法实现正则表达式解析器。现在我可以生成一个 DTran 表并解析一些基本的正则表达式，例如：(a|b)*abb .

但是我在实现与任何字符匹配的.符号时遇到了问题。龙书中没有关于它的文字，有没有一些关于实现它的例子或文章？

Answer 1

自己解决，这就是它的乐趣。 下面没有太多答案，但尽管如此。

1. 跟踪 n 个数字 "." 的匹配状态/条件。[n]，然后继续模式匹配。
2. 作弊并向前看，这不是一个好主意。 自.[n] 可能很大，但可能不是。

它

确实与其他模式匹配非常相似，比如*，并且记住在同一文本上可能会出现多个匹配;这就是为什么可能将其排除在外(当语法丰富时，Dtran或状态机会变得困难(;此外，它非常相似，但接受字符。 哎呀，你可能不得不切换到NFA(非确定性有限自动机(以保持简单。

显然，我没有读过龙的书，但在大学里讲过它，"计算理论"。 我画了很多状态机。