4

我正在尝试创建一个允许有限的用户定义替换规则的文本解析器。

也就是说，我正在从 DOS ASCII 文件中读取代码，其中的顺序很重要，并且必须保持行号。有了这个输入，我想应用用户定义的替换规则（用这个字符串交换那个字符串，如果我们看到这个字符串后面跟着那个字符串执行这个翻译，等等）。

输出也是一个格式化的 DOS ASCII 文件。

大多数规则都是直接替换以牙还牙的类型替换，但是，在某些情况下，我想定义一个规则，例如如果 A 在将来的任何时候跟随 B，请应用此规则。

为此，我使用了这样的结构树：

struct node {
    list<string> common;  // the text which is not affected by conditions
    string condition;     // matching this string selects the left, otherwise the right
    node *lptr, *rptr;    // pointers to the child nodes, if needed
};

每当我遇到这样的规则时，我都可以在忽略和应用规则的情况下维护输出，延迟决定使用哪个规则，直到它明确解决。

这有点浪费内存，但似乎是避免两次传递输入数据的最佳方法（输入数据的大小未知，但可能小于 1 兆）。

当然，可能存在这样一种情况，即在一个或两个子节点中触发这种类型的不同规则，这就是树结构的原因。

没有限制必须在父母之前决定孩子，可能父母只能在孩子的一个分支上决定。遇到 EOF 将决定任何未决定的孩子在错误的方向。

所以很明显，在倒带和折叠节点时我必须小心。

这个一般问题有更简单的解决方案吗？有没有办法以比我的树更有效的方式使用标准库容器？

4

3 回答 3

0

听起来你应该尝试正则表达式。这是关于选择库的讨论链接：C++ RegEx Library Choice。Boost是一种流行的方法。

另外，您是否考虑过使用另一种语言来解决问题？Python 拥有大量有用的库，包括一个用于正则表达式的库（import re）。如果它在您的驾驶室中，您可能会发现它比 C++ 解决方案更容易。

最后，考虑为输入文件使用“已定义”的文本格式，而不是自定义格式。XML 是一个不错的选择。在 XML 树中嵌套规则可能更容易。C++ 你可以使用 The Expat XML Parser（Python 是 xml.etree.ElementTree）。

于 2012-06-14T19:50:26.280 回答
0

您可能想查看 NFA 和 DFA，即非确定性有限状态自动机和确定性有限状态自动机。这两种方法是编写解析器的最常见且通常非常有效的方法。

节点中其实不需要存储数据，否则会四处传递，浪费内存。更好的方法是分配一个变量（比如 int state = 0）来跟踪当前的解析状态。根据当前状态和输入，您的算法将改变状态。状态总是向前发展，但是如果某个条件不匹配（称为“回溯”），您可以告诉您的算法返回到某个先前的状态。

例如，如果 "ab" 和 "ac" 是两个有效输入，则在解析 "ac" 时，算法可能如下所示：

char is 'a' ==> go to state.checkB
char is not 'b' ==> go back to state.checkA
checkB was already done ==> go to state.checkC
char is 'c' ==> DoSomething();

需要大量文章和图表才能完全解释所有内容，希望这会给您一些进一步了解的想法。

于 2012-05-23T19:49:13.880 回答
0

假设“文本解析器”是指您试图压缩具有相同含义的单词和短语以简化对命令的反应。

在这种情况下，根据旧的文本冒险程序，使用规则查找表的简单左右解析器将在这里工作。

除非我误解了您的问题域，否则您的解决方案似乎设计过度。

于 2012-05-23T21:38:25.940 回答