问题标签 [dfa]

我试过在谷歌上寻找，但我想我无法找到正确的搜索短语来找到我想要的东西。如果你熟悉 afterNET IRC 服务器，有一个命令 '.8' 是一个 8 球。它回答的不仅仅是是/否问题。它会根据您在问题中使用的某些词语（例如时间、地点、颜色等）为您提供各种答案

我想做这样的东西，但不知道从哪里开始。我最近研究了 DFA（确定性有限自动机），我应该从那里开始吗？我知道我不想编写人们使用的每一种可能的单词组合，但如果有一个感觉有点现实的系统（比如 IRC 服务器上的 8ball 程序），并且可以扩展以获取更多“单词”，那就太好了' 不管什么时候我要。

感谢您提供任何帮助/链接！

是否有一种工具可以接受正则表达式列表并生成最小 DFA 的图片，以识别这些正则表达式，每个都进入其相应的最终状态？

它应该看起来像这样： http: //i.imgur.com/Vxw9X.jpg 图片来自斯坦福编译器课程，可能是老师自己制作的。此 FA 处理 Pascal 令牌的子集，编号/字母状态是最终状态。

我不需要 DFA 的实际代码，只需要它的外观图片。

如果没有这样的工具，我将如何制作这种图表？是否有某种专门的 python GUI 库可以做到这一点？

我有无限的字符串序列和许多按优先级排序的正则表达式。对于序列中的每个字符串，我必须找到第一个匹配的正则表达式和匹配的子字符串。字符串不是很长（<1Kb），而正则表达式的数量可能从数百到数千不等。

我正在寻找一种能够有效完成这项工作的 Java 工具。我想该技术应该是在前面构建 DFA。

我目前的选择是 JFLEX。我无法在 JFLEX 中解决的问题是它的规则没有优先级，而 JFLEX 会查找与文本最长部分匹配的规则。

我的问题是我的问题是否可以用 JFLEX 解决？如果没有，你能推荐另一种 Java 工具/技术吗？

我有一个程序，它简单地将所有状态作为一组状态作为输入。然后下一个输入是状态集合中的初始状态，然后是最终状态集合。

接下来是我在各州之间进行的一组转换。

例如：q0,1,q1

这意味着在输入 1 上存在从 q0 到 q1 的转换。

对于每个状态，都会输入转换。

但是在这里我面临的是可以以随机方式跳转引用，即转换可以是非重复字符的 n 次转换，因此我想动态地为每个状态维护一个 hashmap 对象。

我怎样才能做到这一点？

Lexer DFA 导致“代码太大”错误

我正在尝试使用 ANTLR 3 解析 Java 服务器页面。

Java 对单个方法的字节码有 64k 的限制，在编译 ANTLR 生成的 Java 源代码时，我一直遇到“代码太大”错误。

在某些情况下，我可以通过破坏我的词法分析器来修复它。例如，JSP 使用 XML“名称”标记，它可以包含多种字符。我决定在我的“名称”标记中只接受 ASCII 字符，这极大地简化了一些测试，并且词法分析器允许它编译。

但是，我已经到了不能再偷工减料的地步了，但是 DFA 仍然太复杂了。

我该怎么办？

是否存在导致复杂 DFA 的常见错误？

有没有办法抑制 DFA 的生成，也许依靠语义谓词或固定的前瞻来帮助预测？

手工编写这个词法分析器很容易，但在我放弃 ANTLR 之前，我想确保我没有忽略一些明显的东西。

背景

ANTLR 3 词法分析器使用 DFA 来决定如何标记输入。在生成的 DFA 中，有一个方法叫做specialStateTransition(). 此方法包含一个switch语句，其中包含 DFA 中每个状态的案例。在每种情况下，都有一系列if语句，每个语句用于状态转换。每个if语句的条件测试一个输入字符以查看它是否与转换匹配。

这些字符测试条件可能非常复杂。它们通常具有以下形式：

对我的词法分析器的一个看似微小的更改可能会导致对单个转换、每个状态的多个转换和多个状态进行数十次比较。我认为由于我的语义谓词，某些正在考虑的状态是不可能达到的，但 DFA 似乎忽略了语义谓词。（不过我可能会误读——这段代码绝对不是我能手写的！）

我在 Jsp2x 工具中找到了一个 ANTLR 2 语法，但我对它的解析树不满意，我想刷新我的 ANTLR 技能，所以我想我会尝试自己编写。我正在使用 ANTLRWorks，并尝试为 DFA 生成图表，但 ANTLRWorks 中似乎存在阻止它的错误。

我有一个远程“代理”，它在传递字符串时返回“是”或“否”。与这个代理进行通信是昂贵的，所以我希望找到一个库，它可以让我在给出正面和负面反馈的情况下迭代地构建一个正则表达式，同时对它的构建保持智能。这将允许我在发送端缓存答案。

例如，假设我们用“good”查询代理并收到“yes”。最初派生的正则表达式应该是“好”的。

假设我用“goop”查询并收到“是”。我希望派生的正则表达式是“goo[dp]”，而不是“good|goop”。

等等。

在派生的正则表达式中，我不需要回溯或任何其他花哨的非线性时间操作。据推测，生成的正则表达式将是引擎盖下的 DFA。有人知道任何能够做到这一点的 c/c++ 正则表达式库吗？或者，为什么这是一个愚蠢的想法以及对我的实际问题的更好解决方案的原因也将是有用的。

我想知道如何找到一组与给定正则表达式的所有匹配项，匹配数量有限。

例如：

您可以假设所有这些示例都^以$

如果有一种方法可以检索正则表达式的唯一解，或者是否有一种方法可以确定正则表达式是否具有有限解，我也会感兴趣。

如果该算法可以解析任何正则表达式，那就太好了，但是足够强大的正则表达式子集就可以了。

我对这个问题的 PHP 解决方案很感兴趣，但其他语言也可以。

编辑：

我在我的形式理论课上学到了关于DFA的知识，它可以用来实现正则表达式（和其他常规语言）。如果我可以将正则表达式转换为 DFA，那么解决方案对我来说似乎相当简单，但这种转换对我来说似乎相当棘手。

编辑2：

感谢您的所有建议，请参阅我关于我正在努力“回答”这个问题的公共 github 项目的帖子。

通常 DFA 用于检查给定的字符串是否以某种语言存在。例如 _ab1c 存在于 C 中的变量语言中。

我在做什么？ 但正如这个问题中所述，我正在使用 DFA 来跟踪所有评论、字符串等。

我过得怎么样？ 考虑一个在给定字符串/程序中跟踪 //comments 的示例。

为此，如果我有，

我的问题是...

我可以使用 DFA，以这种方式标记 //comment 的结束和开始，或者我必须遵循 CFG 等其他方式。

IE

我的声明：我可以使用 DFA，不仅可以检查特定语言，还可以跟踪给定字符串中属于某些语言的某些字符串。（证明：通过上述方法）。

我的上述说法正确吗？

正如我在这个问题中所说，我正在使用 DFA 来跟踪所有评论、字符串等。我完成了这个具有 11 个状态的 DFA。

现在我要编写 DFA 来识别 java 中的关键字。

主意：

最初，pos=0。pos 每次转换都加 1。

iskeyword() 是我自己的函数。

isalnum() 可以被任何用户定义的函数替换，这取决于未来的需求。

（许多不相关的转换和自循环虽然存在于实际的 DFA 中，但并未提供）。

(q0) -- !isalnum(pos)-------> (q1) ---iskeyword(pos,pos+len)---> (pos+=len)(q2)----- ！ isalnum(pos)-------->(q3[使读取的关键字加粗])---iskeyword(pos,pos+len)-->(q2)。

它至少需要 4 个状态。上述方法与 DFA 的正常实现有很大不同。

我的问题是……

1. 我可以按照上述方法吗？这样做是对的吗？（如果有效）
2. 如果我必须以上述方式实现这一点，我该怎么做？构建单独的 DFA 以提高可读性？或者我可以将此 DFA 与识别评论、字符串的 DFA 结合起来（以减少状态数）

(ab u aab u aba)*

我做到了，但我想要一些关于其正确性的反馈：

如果正确：我们可以进一步简化 (ab u aab u aba)* 吗？

如果没有：我错过了什么？

编辑：似乎我缺少从所有 3 个最终状态回到初始状态的电子转换，我需要一个初始和最终状态的新状态，它将在电子转换时进入旧的初始状态。（克莱恩星规则）。

PS我们也可以简化(a u b)*aabab和(a u b)*a(a u b)(a u b)(a u b)(a u b)。

我之所以问是因为如果没有办法简化/最小化，那将是一个非常长的 DFA ......