regex – 可以使用正则表达式来匹配嵌套模式吗？

发布时间：2020-12-14 00:39:39 所属栏目：百科来源：网络整理

导读：是否可以编写与发生未知次数的嵌套模式匹配的正则表达式。例如，当外部大括号中嵌有未知数量的打开的大括号时，正则表达式是否匹配开始和结束大括号。例如： public MyMethod(){ if (test) { // More { } } // More { }} // End 应匹配： { if (test) { //

是否可以编写与发生未知次数的嵌套模式匹配的正则表达式。例如，当外部大括号中嵌有未知数量的打开的大括号时，正则表达式是否匹配开始和结束大括号。

例如：

public MyMethod()
{
  if (test)
  {
    // More { }
  }

  // More { }
} // End

应匹配：

{
  if (test)
  {
    // More { }
  }

  // More { }
}

不，这很容易。有限自动机(它是正则表达式基础的数据结构)除了它的状态之外没有内存，如果你有任意深的嵌套，你需要一个任意大的自动机，它与有限自动机的概念相冲突。

您可以将嵌套/配对元素匹配到固定深度，其中深度仅受您的内存限制，因为自动机非常大。然而，在实践中，您应该使用下推自动机，即用于上下文无关语法的解析器，例如LL(自顶向下)或LR(自下而上)。你必须考虑更糟糕的运行时行为：O(n ^ 3)与O(n)，n =长度(输入)。

有许多解析器生成器可用，例如用于Java的ANTLR。找到Java(或C)的现有语法也不难。
更多背景：Automata Theory在维基百科

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!