ide - 从示例数据创建解析器语法

Question

我一直在四处寻找可以帮助用户创建语法的工具。有各种 IDE，但是......它们似乎是处理语法文件本身的文本编辑器。我正在寻找以数据为中心的方法起作用的东西。因此，假设我有很多要使用解析器解析的数据示例。因此，我想处理该示例数据并直接从中定义语法。

有没有现成的软件可以做类似的事情？

我会尝试更清楚...

我提到的以数据为中心的方法是用户加载数据样本的地方。然后他们会选择它的片段来表明它们是字段，或者选择项目并将它们标记为分隔符等。

与我看到的大多数 IDE 不同，它们只是用于使用语法语言本身编写的文本编辑器。

Answer 1

任何有限的字符串集都构成了常规语言。编写接受这种语言的 NFA 是微不足道的。由此，您可以使用子集构造生成 DFA，并使用 DFA 对不可区分性关系的每个等价类只需要一个状态这一事实将其最小化。所以这是一个完全算法的过程......然后获得正则表达式和/或语法同样简单。

话虽这么说，如果你想生成一个语法来生成字符串，可能还有其他……你的问题似乎是不适定的。对于任何有限的字符串集，无限多的语法会生成它们和其他字符串……数字的无限性来自这样一个事实，即只要您命中目标数据集，您就可以生成任何其他字符串。您的问题本质上是“给定序列 a1、a2、...、an、... 的开头，说出接下来的 n 个元素是什么。”这是不可能做到的，除非您只是想要一些答案...在这种情况下，您总是可以从 DFA 开始并提出概括此问题的方法(即只接受更多字符串)。

确实，给定例如一个常规的语法，很容易引入新的字符串......所以也许使用第一个答案作为起点。但请注意，从 NFA 到 DFA 的转换可能效率极低……渐近指数。