确定正则表达式是否是另一个的子集

前端之家收集整理的这篇文章主要介绍了确定正则表达式是否是另一个的子集前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。
我有一个大的正则表达式的集合,当匹配调用一个特定的http处理程序。一些旧的正则表达式是不可达的(例如a.c *⊃abc *),我想修剪它们。

是否有一个库,给了两个正则表达式会告诉我,如果第二个是第一个的子集?

我不知道这是可以决定的(它闻起来像停止问题,一个不同的名字)。但事实证明it’s decidable

Trying to find the complexity of this problem lead me to this paper.

问题的正式定义可以在这里找到:这通常被称为包含问题

The inclusion problem for R,is to test for two given expressions r,r′ ∈ R,
whether r ⊆ r′.

这篇文章有一些伟大的信息(总结:所有,但最简单的表达式是相当复杂),然而搜索关于包含问题的信息直接一个回到StackOverflow的答案已经有一个链接a paper describing a passable polynomial time algorithm应该覆盖很多常见的情况。

猜你在找的正则表达式相关文章