2

我想知道，代表 DFA 的最佳数据结构是什么？

我正在考虑将正则表达式转换为 DFA，并将此特定功能作为 Java 中的库。

主要的是，正则表达式中的每个实体都带有一组值，而不是像 "car" 这样的单个字符串值。在我的例子中，每个实体都会带有许多属性，例如 {car, Honda, 4x4,轿车, ... }（虽然我不是在搜索汽车，但这只是一个示例。）

有什么建议么？

4

3 回答 3

0

网络搜索将产生一些 Java 中的 DFA 示例。但是，最佳表示取决于您的具体应用要求；例如，您的应用程序将如何使用 DFA。我认为你需要自己解决这个问题。

于 2010-10-12T03:20:23.453 回答
0

如果我正确理解您的问题，您是否希望在具有动态类型的字母表上为任意常规语言提供匹配/过滤库？以您的汽车示例为例，我想您希望能够创建一个表达式以匹配一个列表，其中所有汽车（红色，有 2 到 6 名乘客，每个乘客在 8 到88 岁）或（有 1 名乘客）。

巧合的是，我自己一直在寻找类似的东西（用于文件验证），而我能得到的最接近的是Jing；Java RELAX-NG 库。不幸的是，Jing 中的字母表由 XML 节点组成，所以它没有解决我的问题。目前，我正在尝试自己编写一个库，它可以根据 Jing 中的模式匹配来执行此操作（通过任意类型的字母与常规语言匹配）。如果您想对此提供帮助，请告诉我；）。

于 2010-10-12T14:59:53.727 回答
0

由于数据的原因，我确信这个答案对原始问题没有用，但如果有人从谷歌遇到这个问题......

DFA 和 NFA 可以存储为状态转换表，然后您通过移动链接后面的表来执行解析。

于 2011-11-03T09:22:04.140 回答