我想知道，用什么数据结构来表示DFA最好？
我正在考虑将一个正则表达式转换为DFA，并将这个特定功能作为Java库。
主要问题在于，正则表达式中的每个实体都带有一组值，而不是像"car"那样的单个字符串值。在我的情况下，每个实体都会带有许多属性，如{car，Honda，4x4，sedan，...}（尽管我不是在搜索汽车，这只是一个例子）。
有什么建议吗？
用于表示DFA的数据结构
3
- bsoundra
4
1正则表达式库不是已经做了这个吗？ - JoshD
JFlap可以做到这一点。请查看他们的作品。
http://www.cs.duke.edu/csed/jflap/ - Mike
@Josh：我认为正则表达式只能处理具有单个属性的字符串输入。但是转换的输入可能会占用多个值。 - bsoundra
@Mike：我查看了jflap，但它没有解决我的问题。我的问题是转换的输入不是单值的，而是多值的。希望我表述清楚了我的问题。 - bsoundra
3个回答
0
在网上搜索可以找到一些Java中的DFA示例。然而，最好的表示取决于您特定的应用要求；例如，您的应用程序将如何使用DFA。我认为您需要自己解决这个问题。
- Stephen C
0
如果我正确理解您的问题，您想要一个匹配/过滤库，用于动态类型字母表上的任意正则语言？以您的汽车示例为例，我想您希望能够创建一个表达式，以便在列表中匹配所有符合以下条件的汽车（颜色为红色，乘客数量在2到6人之间，每个乘客年龄在8到88岁之间）或（有1名乘客）。
巧合的是，我自己也一直在寻找这样的东西（用于文档验证），我找到了最接近的Jing；一个Java RELAX-NG库。不幸的是，Jing中的字母表由XML节点组成，因此它没有解决我的问题。目前，我正在尝试编写一个库，它可以基于Jing中的模式匹配来实现对任意类型字母表上的正则语言进行匹配。如果您愿意帮助我，请告诉我。;)
巧合的是，我自己也一直在寻找这样的东西（用于文档验证），我找到了最接近的Jing；一个Java RELAX-NG库。不幸的是，Jing中的字母表由XML节点组成，因此它没有解决我的问题。目前，我正在尝试编写一个库，它可以基于Jing中的模式匹配来实现对任意类型字母表上的正则语言进行匹配。如果您愿意帮助我，请告诉我。;)
- hakvroot
4
我不确定我是否正确理解了你的解释。实际上，该文档只包含单词“car”。但是，与之相关联的对象称为注释。因此，汽车被注释为“Vehicle”。因此，我通常搜索注释类型为“vehicle”的值为“car”的注释。这个实体是许多实体中的第一个，这使得正则表达式具有多个值。通过多个值，我的意思是，像汽车这样的类型是Vehicle。因此，我可能会搜索类似于“<vehicle，car> sold”的内容。这告诉了文档中销售的汽车总数。这就是你所说的吗？ - bsoundra
@bsoundra：我实际上并不是在谈论文本方面，而更多地是在谈论对象方面。如果你正在搜索文本，那么它确实是不同的；）。也许你可以更深入地阐述一下你的用例？ - hakvroot
我的输入可能是类似于“保时捷已售出”的内容。这个词“保时捷”可能被标记为“汽车”或“交通工具”等许多其他标签。这些信息存储在与文件相关联的其他对象中。因此，如果我搜索“<交通工具，保时捷>已售出”，那么它应该找到匹配项。我还可以搜索“<交通工具>已售出”，这将列出所有已售出的交通工具。 - bsoundra
我偶然发现了来自http://laser.cs.umass.edu/opensource/的正则语言/有限状态自动机工具包（用于Java）。它是一个相当理论的解决方案，仍然专注于有限字母表，但至少它抽象出了字符串，是开源且非常完整的（NFA，DFA，构建器等）。修改源代码以支持不同标签之间的匹配并不是一项微不足道的练习，但也不是不可能的;）。 - hakvroot
0
我相信这个答案对于原问题来说可能并不有用，因为涉及到数据，但如果有人通过谷歌偶然看到这个问题...
DFA和NFA可以被存储为状态转移表，然后你可以通过按照链接移动表格来执行解析。
- Joey Ciechanowicz
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接