问题
给定具有任意规则和标记流的上下文无关语法，如何有效地识别与语法匹配的流片段？
例子：
语法
S -> ASB | AB
A -> a
B -> b
（因此，本质上，一个
as的数字后跟一个相等的bs的数字）流：
aabaaabbc...
预期结果：
从位置1开始比赛：AB
从位置4开始匹配：aabb
当然，关键是“有效”没有测试太多绝望的候选人太长时间。关于我的数据，我唯一知道的是，尽管语法是任意的，但实际上匹配序列相对较短（10000个终端）。
理想情况下，我还需要一个语法树，但这并不太重要，因为一旦识别出片段，我就可以在它上面运行一个普通的解析器来获得该树。
我应该从哪里开始哪种类型的解析器可以适应这种类型的工作？
最佳答案
“任意语法”让我建议你看看wberry的评论。
这些语法有多复杂是否有手动干预步骤？
我试试看如果我修改了你的示例语法：
S -> ASB | AB
A -> a
B -> b
包括：
S' -> S | GS' | S'GS' | S'G
G -> sigma*
所以g=garbage和s'是许多s片段，它们之间有垃圾（我可能对我的生产规则不太在意）。我想我们可以解决你的问题。您只需要一个语法分析器来匹配G之前的其他规则。您可能需要根据语法分析器修改这些生成规则我几乎可以保证，根据解析器的不同，会有规则顺序的更改由于大多数解析器库将LISTIN与解析分开，所以您可能需要一个catch -LeEvE，然后修改G以包含所有可能的LIPEES。根据您的具体情况，这可能不会比在流中的每个位置开始每次尝试要好得多（效率方面）。
但是假设我的生产规则是固定的（为了正确性和解析器的特殊风格），这不仅应该匹配流中的片段，而且应该为整个流提供一个解析树。您只对根植于s类型节点的子树感兴趣。