NLTK 正则表达式和 CFG

Question

以 NLTK 的文档为例的“正则表达式”和同一个 CFG 之间在功率上有什么实际区别吗？肯定应该有，因为有不规则的上下文无关语言，但我找不到一个具体的例子，其中 CFG 方法胜过正则表达式。

http://nltk.org/book/ch07.html

Answer 1

从 RegexpParser 的文档中：

子句的模式按顺序执行。较早的模式可能会引入阻止执行较晚模式的块边界。有时，单个模式将匹配输入的多个重叠范围。与更普遍的正则表达式替换一样，chunker 将识别第一个可能的匹配项，然后在该匹配项结束后继续查找匹配项。

文法的子句也是按顺序执行的。级联块解析器是具有多个子句的解析器。此块解析器创建的解析树的最大深度与文法中的子句数相同。

也就是说，每个子句/模式都执行一次。因此，一旦您需要将较晚的子句的输出与较早的子句匹配，您就会遇到麻烦。

一个实际的例子是可以将一个完整的句子本身用作更大句子中的从句的方式：

猫发出咕噜声。

他听到猫发出咕噜声。

她看到他听到了猫的呼噜声。

正如我们从上面的文档中看到的那样，当您构建 RegexpParser 时，您正在为此类句子的“深度”设置任意限制。上下文无关文法没有“递归限制”。

文档提到您可以使用循环来稍微缓解这种情况——如果您运行合适的语法两三四次，您可以获得更深入的解析。您可以添加外部逻辑来多次循环您的语法，或者直到无法解析更多内容为止。

但是，正如文档中还指出的，这个解析器的基本方法仍然是“贪婪的”。对于固定或可变数量的步骤，它是这样进行的：

• 一步做尽可能多的分块。
• 使用上一步的输出作为下一步的输入，并重复。

这是幼稚的，因为如果早期步骤出错，这将破坏整个解析。

想一个“花园小径句子”：

马跑过谷仓倒下。

和一个类似的字符串，但一个完全不同的句子：

那匹马跑过谷仓。

构建一个解析这两个句子的 RegexpParser 可能很困难，因为该方法依赖于正确的初始分块。一个正确的初始分块可能是另一个不正确的初始分块，但是直到您处于解析逻辑的后期级别，您才能知道“您在哪个句子中”。

例如，如果“谷仓倒塌”在早期被组合在一起，解析将失败。

当你最终得到一个“糟糕”的解析时，你可以添加外部逻辑来回溯，看看你是否能找到更好的。但是，我认为此时您会发现，解析算法的更多重要部分在您的外部逻辑中，而不是在 RegexpParser 中。