algorithm - 在标记流中解析上下文无关语言

Question

问题

给定一个具有任意规则的上下文无关文法和标记流，如何有效地识别与文法匹配的流片段？

示例:

语法

S -> ASB | AB
A -> a 
B -> b

(本质上，一定数量的 a 后跟相同数量的 b)

流:

aabaaabbc...

预期结果:

1. 匹配从位置 1 开始:ab
2. 匹配从位置 4 开始:aabb

当然关键是“有效”。没有测试太多无望的候选人太久。关于我的数据，我唯一知道的是虽然语法是任意的，但实际上匹配序列会相对较短(<20 个终端)，而流本身会很长(>10000 个终端)。

理想情况下，我还想要一个语法树，但这不太重要，因为一旦识别出片段，我就可以在其上运行一个普通的解析器来获取树。

我应该从哪里开始？哪种类型的解析器可以适应这种类型的工作？

Answer 1

“任意语法”让我建议你看看 wberry 的评论。

这些语法有多复杂？是否有人工干预步骤？

我会努力的。如果我修改了您的示例语法:

S -> ASB | AB
A -> a 
B -> b

包括:

S' -> S | GS' | S'GS' | S'G
G -> sigma*

所以 G = garbage 和 S' 是许多 S 片段，中间有垃圾(我可能对我的生产规则粗心了。你明白了)，我想我们可以解决你的问题。你只需要一个解析器来匹配 G 之前的其他规则。你可能必须根据解析器修改这些生产规则。我几乎可以保证会根据解析器更改规则顺序。由于大多数解析器库将词法分析与解析分开，因此您可能需要一个包罗万象的词素，然后修改 G 以包含所有可能的词素。根据您的具体情况，这可能不会比在流中的每个位置开始每次尝试更好(效率方面)。

但是...假设我的生产规则是固定的(既为了正确性也为了解析器的特殊风格)，这应该不仅匹配流中的片段，而且应该为您提供整个流的解析树。您只对以类型 S 的节点为根的子树感兴趣。