同步正则表达式：形式语言理论中的重要概念及应用实践探讨

网址：http://www.elsevier.nl/locate/entcs/volume62.html16页同步正则表达式*Giuseppe Della Penna1，2 Benedetto Intrigila1，3Enrico Tronci恩里科·特龙奇1，4AreaInformatica，Universita`diL玛丽莎Venturini Zilli1，5文凭diScienzedel摘要文本处理是每个使用计算机的人最常见的任务之一每个计算机用户每天收集的电子文本信息越来越多，这就需要更强大的工具来与文本进行交互。事实上，已经做了很多工作来提供非编程工具，这些工具可以用于最常见的文本操作问题。Kleene提出的正则表达式（RegularExpressions，RE）是形式语言理论中的一个重要概念。 RE收到了几个扩展，这取决于感兴趣的应用程序。 在RE搜索算法的几乎所有实现中（例如，egrep [14] UNIX命令，或Perl [17]语言模式匹配结构），我们发现反向引用（如[1]中定义的），即引用前一个子表达式匹配的字符串的表达式。 一般来说，RE中子表达式之间的所有类型的同步在与文本交互时都非常有用。因此，我们引入同步正则表达式（SRE）作为正则表达式的派生我们使用SRE提出了一个正式的研究已经知道的反向引用扩展，并提出了一个新的扩展我们称之为同步指数此外，由于我们讨论的是应该具有实际效用并且可以在现实世界中使用的形式主义，因此我们有如何向最终用户呈现SRE的问题。因此，在本文中，我们还提出了一个*本文的扩展版本将在Acta Informatica上发表。1这项研究得到了MURST项目TOSCA的部分支持2电子邮件：gdellape@univaq.it3电子邮件：intrigila@univaq.it4电子邮件：tronci@univaq.it5电子邮件：zilli@dsi.uniroma1.it·c2002年由ElsevierScienceB出版。 诉 操作访问根据C CB Y-NC-N D许可证进行。21介绍文本处理是每个使用计算机的人最常见的任务之一。每个计算机用户每天收集的电子格式的文本信息越来越多（电子邮件，网页，文字处理器文档，甚至纸质文档通常都转换为电子格式以节省空间），强调需要更强大的工具来与文本进行交互从初学者到高级用户，每个级别都是如此事实上，已经做了很多工作来提供Kleene提出的正则表达式（RegularExpressions，以下简称RE）是形式语言理论中的一个重要分支RE现在几乎存在于所有的文本处理程序中，主要用于搜索/替换功能。用户熟悉这种形式主义，这表明可以利用RE的所有功能来对文本执行更复杂的操作 RE收到了几个扩展，这取决于感兴趣的应用程序。例如，像'？'或Angluin [2]介绍的模式，其他作者也进行了研究（见[16]用于概述），是用于在同一字符串中查找相同子串的扩展RE。在几乎所有RE搜索算法的实现中（例如egrep[14]，sed和awkUNIX命令，或Perl[17]语言模式匹配结构），我们发现反向引用（如[1]中定义的，也见[8]）作为模式的概括，即。引用的表达式与前一个子表达式匹配的字符串。另一个有趣的扩展，据我们所知，还没有被研究或实现，可能允许确定某些子表达式是否在文本中重复相同的次数这在各种情况下都很有用，从完整性检查到高级字数统计工具，特别是当与其他扩展（如反向引用）混合使用时。一般来说，RE中子表达式之间的所有类型的同步（如反向引用）在与文本交互时都非常有用因此，我们引入同步正则表达式（SRE）作为著名的正则表达式的派生 我们使用SRE提出了一个正式的研究已经知道的反向引用扩展，我们提出了一个新的扩展，我们称之为同步指数。我们专注于这些类型的同步，因为它们具有非常好的特性：• 它们似乎在很多情况下是有用的• 它们可以以非常用户友好的方式实现，严格类似于普通通配符的使用（见第6节）;• 当在合理的约束下使用时，它们具有可接受的计算复杂度（参见第5节）。在本文中，我们给出了一个正式的语法和语义的扩展。然后，我们研究了SRE在形式语言层次中的分类。最后，我们研究了模式匹配问题的复杂性。3由于我们讨论的是应该具有实际效用并可以在现实世界中使用的形式主义，因此我们也有如何向最终用户呈现SRE的问题。我们开始研究如何在知名程序中将反向引用和其他实际上，许多低级别的非程序员用户无法编写使用这些扩展所需的复杂命令（有时甚至是小程序）。此外，这些实现是非标准的：用户很难理解为这些扩展提出的新语法结构在每个应用程序中。例如，反向引用有一个递归定义，允许嵌套表达式及其引用，并在绑定操作中使用全部RE功能相反，大多数用户并不需要所有这些功能，而且他们的反向引用方法也很困难。本文的第二个目的是提出一个我们的语法有两个层次：第一，针对尽管如此，完整语法也可以被看作是用于处理大量结构化数据的算法的高级这样，SRE可以帮助程序员快速编写代码来解决复杂的数据操作问题。另一方面，我们确定了一组处理任务，在我们看来，这些任务代表了初学者用户可能需要的任务，并且在第二级语法中，我们提出了一组宏结构，以非常简单和直观的本文的结构如下。在第2节中，我们定义了同步正则表达式，并展示了如何为它们分配语言。在第3节中，我们研究了这些语言在形式语言体系结构中的位置，表明它们是上下文敏感的，并且在一定条件下，包括在分散上下文文法中[6]。在第4节中，我们讨论了我们背景下的成员问题我们表明，成员资格问题原来是NP-完全的，即使每个同步元素的出现次数是绑定到两个。在第5节中，我们考虑SRE的一个自然限制，即限制同步元素的数量。这一次，问题变成了多项式。在第6节中，我们将讨论如何为SRE定义一个用户友好的相关的工作第7节包含了我们的方法和其他方法之间的比较，无论是在形式语言的理论还是在正则表达式的实现412同步正则表达式2.1同步正则表达式在本节中，我们定义了经典RE的扩展。我们给出了RE的标准定义，丰富了[1]中的反向引用语法，以及同步指数的新语法。定义2.1关于字母表A、一组变量V和一组指数X的同步正则表达式定义如下：• ∈SRE（空语言）• 空字符串• a∈A a∈SRE（字母）• v∈V v∈SRE（变量）如果e1，e2∈SRE，则：(i) e<$1∈SRE（star）(ii) nx∈X ex∈SRE（指数运算）(iii) v∈V（e1）%v∈SRE（变量绑定）(iv) e1e2∈SRE（concatenation）(v)e1+e2∈SRE（并）我们将把不是绑定操作参数的变量作为反向引用。[1]中的backreferences语法似乎未被指定。该定义允许不同的解释（例如，比较[1]与更面向最终用户的[8]），因为某些表达式的预期含义意味着语法中没有表达的几个限制，这些可能会给用户带来问题。事实上，上述定义允许：• 同一变量上的多个绑定。例如，考虑SRE（a）%vb v（b）%vc v。如果我们假设一个绑定取代了前一个绑定，那么语言生成将依赖于一个未指定的• 变量绑定上的循环 这些可能会导致死锁，如表达式（v1a）% v2d（v2b）% v1中所示。包含绑定循环的表达式总是表示空语言或不生成任何定义语言，这取决于解释。• 变量绑定上的递归。这是前一个问题的一个特例。• 后期绑定。变量可以在绑定到表达式之前使用，例如av b（c）%v。这可能会导致各种问题，在实践中是不必要的。• 未绑定的变量。可以在表达式中没有绑定的情况下使用变量具有未绑定变量的SRE并不表示定义语言。5• 表达式和它的反向引用之间的分离。表达式可以在sum“+”的一端绑定变量，并在另一端反向引用它。例如，考虑SRE（a）%v+v。由于两个子表达式的求值是互斥的，所以我们在右边有一个未绑定的为了固定语法，我们对有效的SRE施加以下限制定义2.2当表达式按从左到右的顺序进行分析时，如果满足以下条件，则同步正则表达式有效(i) 绑定总是在新鲜（即未在前面的子表达式中使用）变量。(ii) 反向引用总是引用绑定的（即不是新鲜的）变量。这样的限制解决了上述所有问题，除了由2.2节中的语义规则处理的析取问题。命题2.3有效的SRE不允许：(i) 同一变量上的多个绑定(ii) 循环变量绑定，(iii) 递归绑定，(iv) 后期绑定，(v) 未绑定的变量。注1在本文中，我们省略了所有命题的证明。 这些证明可以在论文的完整版本中找到，由于它已提交给Acta Informatica，因此目前无法获得。注2.4由于我们只考虑有效的SRE，我们规定，从现在起，2.2同步正则表达式语义我们提出了一个语义SRE，对应于原来提出的在[1]中，使用归纳的表达式结构。设Eval（PS，VB，VF，EB）为我们的评价函数，其中• PS是一组（模式，字符串）对;• VB是一组（变量，字符串）对，表示通过绑定操作已经关联到字符串• VF是一组（变量，字符串）对，表示未解决的反向引用（使用但尚未绑定的变量）和它们应该匹配的字符串• EB是一组（exponent，number）对，表示所有已经设置为一个数的指数。如果对于PS中的每个（模式，字符串）对，模式匹配字符串使用的绑定规则在VB，VF和EB。6...∅Eval的规则如下：Eval（{（a，α）} PS，VB，VF，EB）=Eval（PS，VB，VF，EB）（α=a）Eval（{（e1e2，α）} PS，VB，VF，EB）=α1α2=αEval（{（e1，α1），（e2，α2）}<$PS，VB，VF，EB）Eval（{（e1+e2，α）}PS，VB，VF，EB）=Eval（{（e1，α）} PS，VB，VF，EB）Eval（{（e2，α）}PS，VB，VF，EB）其中e2是通过将e2中未绑定的每个变量的最左边的反向引用替换为从e1获取的相应绑定而从e2获得的。这解决了在2.1节中介绍的Eval（{（（e）%v，α）}PS，VB，VF，EB）=Eval（{（e，α）} <$PS，VB<$，VF<$，EB）<$（<$（v，α<$）∈VF）（α<$=α）哪里VBVF =（VB\{（v，α\）|α<$∈A<$}）<${（v，α）}=VF\{（v，α）|α<$∈A<$}请注意，如果Eval仅适用于有效的SRE（参见定义2.2），则规则关于VB VB可以简化删除多重绑定检查：=VB <${（v，α）}Eval（{（v，α）} PS，VB，VF，EB）=Eval（PS，VB，VF，EB）<$（α=α <$）if<$（v，α<$）∈VBEval（PS，VB，VF <${（v，α）}，EB）否则Eval（{（ex，α）} PS，VB，VF，EB）=Eval（{（en，α）}<$PS，VB，VF，EB）如果（x，n）∈EBnEval（{（en，α）}PS，VB，VF、E和B{（x，n）}）否则注意，该规则也适用于星形表达式Ex，其可以被认为是指数表达式Ex，其中指数x总是新鲜的，不同步。Eval（{}，VB，VF，EB）=真 ifVF =0否则为false给定一个字符串s和一个SRE e，e在s上的模式匹配问题用表达式Eval（{（s，e）}，n，n，n）来评价.请注意，函数Eval始终在每个输入上定义。事实上，上面给出的规则可7以扩展PS集，但总是降低其元素的复杂性。当一个元素减少到一个字母或变量时，它将从集合中删除，而不添加其他元素，因此最终评估达到退出规则PS=。然而，Eval只有在定义2.2中给出的限制下才能得到很事实上，如果没有这些限制，Eval总是有定义的，但不是确定的（对于2.1节中解释的8（e）%vife（e）%vσX11≡1“我的天，为了更容易地评估SRE，读者可以在评估开始时实际分配所有指数。下面的定义2.5和命题2.6证明了这种方法的正确性。定义2.5指数赋值是函数σX：X→N。SRE上的指数赋值操作如下：v如果e v伊夫堡σ（e）ifee（一）σX（e）=Xσ1（e）σ1（e）如果e电话：+86-21 -88888888<$σX（e1）+σX（e2）如果e<$e1+e2（e）n = σX（e1）.σX（e1），其中n = σX（x），如果e<$e1xn−times我们有以下命题2.6对于每个SREe，L（e）=σXL（σX（e））3形式语言在这里，我们将同步正则表达式分类在形式语言层次结构中。3.1同步正则表达式是上下文敏感的为了证明SRE是上下文敏感的[11]，并且SRE的成员算法是NP [9]（结果将在后面的第4节中使用），我们证明了以下内容命题3.1 SRE的语言可以被线性空间和多项式时间的非确定图灵机接受。在第4.1节中，我们使用以下更一般的结果来证明SRE的成员算法是NP完全的：推论3.2存在一个不确定图灵机M，给定SRE e和字符串α，如果α ∈ L（e），则接受字符串，如果α/∈ L（e），则拒绝字符串，使用p多项式时间w.r.t.|α|+的|e|我的意思是，我的意思是，R. 不|α| ·log|e|.3.2同步正则表达式和分散上下文语法分散上下文语法（SC语法）属于以下家族：有控制派生的文法[6]。让我们简单回顾一下他们的定义：SC文法是一个四元组G=（N，A，P，S），其中：9≥ ∈ ∈ ∪ ≤≤• N、A和S在上下文无关语法中被指定（即，它们分别是非终结符的字母表、终结符的字母表和起始符），并且• P是矩阵（γ1→γ1，γ2→γ2，...，k→ γk）其中k1，n∈ N，γi（N A）∈ N，对于1i k（数k可以从矩阵到矩阵区分）。众所周知（见[6]）：• 不擦除产生式的SC文法的语言包含在上下文敏感语言中;• 具有擦除产生式的SC文法的语言与递归可擦除语言的语言一致。在下文中，我们应该将分散的上下文语法命名为SC，而不删除产生式。我们介绍了一个适当的子类SRE，即1级或1-SRE是SRE的一个有用但不太复杂的子类，它可以自然地作为SC语法的一个适当子类放在具有受控派生的语法层次中我们无法证明这是否同样适用于一般SRE。定义3.31-level SRE（1-SRE）是变量和指数不能嵌套的SRE（即，变量和指数不能出现在exponentiated表达式或绑定到变量的表达式中）命题3.4不包含空字符串的所有1-SRE语言他在SC。3.3同步正则表达式不会生成所有上下文无关语言我们证明了一个字母表上的同步正则表达式不包含同一个字母表上的所有上下文无关（CF）语言为了这个目的，我们使用了回文语言，这是已知的上下文无关。命题3.5没有同步正则表达式可以在字母表A上生成回文语言，|一|> 1.4SRE隶属度算法的复杂性在这里，我们展示了SRE上成员测试的复杂性，并查看了一些限制，这些限制可以降低这种复杂性，同时为语言留下足够的表达能力。10--4.1SRE上的成员资格是NP完全的我们已经证明了（在3.1节中）SRE的成员问题是NP问题。此外，带有反向引用的正则表达式已经被证明是NP完全的[1]，这显然也扩展到我们的SRE。然而，我们想证明，即使对于没有反向引用的SRE，也就是只使用同步指数，成员关系也是NP完全的。我们通过多项式变换将著名的3-CNF问题（每个子句有三个文字的合取范式中的布尔表达式的满足性）简化为命题4.1 3-CNF问题可以归结为SRE的成员问题。在上述命题的证明中，我们使用了指数同步多次的同步正则表达式，因此人们可能会认为，如果我们以其基本形式使用同步，复杂性可能会降低：每个指数只重复两次，即。每个指数只允许一次同步为了回答这个问题，我们还证明了在0， 1范围内的指数（如命题4.1的证明中使用的那些）可以同步，而无需在每个指数上使用超过两次的SRE显式同步，因此如果表达式中的同步次数增加，则不会增加复杂使用这种技术，我们可以只使用显式指数同步对来重写上面的证明（即同一指数只使用两次）。由于转换是多项式的，我们确保命题4.1的证明是有效的，而不管使用的同步次数。因此，我们有以下内容：命题4.2SRE的成员资格问题，• 不包含反向引用，• 包含最多同步两次的指数，是NP完全的。换句话说，指数同步问题的复杂性是内在的。利用同样的技巧，我们还可以改进[2]的结果如下：命题4.3SRE的成员资格问题，• 不包含指数，• 包含每个反向引用最多两次（包括绑定发生），• 反向引用的SRE总是A，是NP完全的。观察到，通过第三个假设，变量的行为与[2]中的变量115有限同步元素在第4节中，我们证明了一般的模式匹配问题与SRE是NP完全的，即使只有两个符号的字母表，或者当我们限制每个变量或指数的同步数量对于包含变量、指数或两者的表达式，这是正确的然而，SRE使用的例子（如第6节中的例子）表明，在实际应用中，单个表达式通常非常少。典型的应用程序可以安全地限制用户可以在每个表达式中写入的变量和/或指数的此限制通常由应用程序域本身建议当表达式中的同步变量和指数的数量受到约束（但不是每个变量和指数的使用次数）时，SRE成员复杂度变为多项式。这一点已经只在反向引用中说明过[1]。在这里，我们扩展证明扩展到指数同步。备注5.1当我们声明同步元素的数量是固定的时，我们也应该考虑嵌套的表达式。也就是说，例如，取幂变量（（v）x）计为两个元素。5.1一种简单的SRE模式匹配多项式算法SRE模式匹配的多项式算法与动态规划技术有一些相似之处，但实际上是枚举式的。像动态规划算法一样，我们也有状态的概念.我们的状态是像（pattern，string，assignments）这样的元组，它显示了一个模式，它必须匹配的字符串以及到目前为止对变量和指数所做的赋值。初始状态s包含用户给算法的模式和字符串，赋值为空。在每一步中，算法都会查看在当前状态集合中的所有状态，并对这些状态中的每一个执行单个匹配步骤，生成下一个状态集合。请注意，单个匹配步骤通常可以以多种方式执行（例如，指数可以分配给不同的值），从而产生多个状态。当生成空状态（字符串和模式为空）时，算法停止，这意味着匹配成功，或者当新的状态集为空时，即无法以任何方式进行匹配该算法的复杂性很容易表达：设n为目标字符串的长度，m为模式的长度（以字符为单位）。如果我们将可能的同步（包括变量和指数）的数量固定为k，则由同步元素生成的状态的数量最多为nk。 所有其他RE匹配C。可以考虑线性w.r.t.n·m，所以我们的算法的复杂度是Om·nk，一个多项式的次数等于我们修复的同步限制我们可以将本节的结果总结为以下命题：命题5.2数量有限的SRE成员问题12\--同步元素。（即：l小于或等于固定数k）可以是在多项式时间内解决O m·nk，其中n是字符的大小目标字符串，m是要匹配的模式的大小（以字符为单位）6一种用户友好的同步定时器调试器本文的第二个目标是为SRE扩展定义一个通用语法，用于文本编辑器、命令行搜索工具（如grep[14]）等实现中在本节的其余部分，我们使用语法一词来表示在计算机终端上编写SRE所使用的语法，这显然与第2节中介绍的正式语法略有不同我们的想法是让用户在不同的层次上使用SRE的功能，因为我们观察到，即使反向引用和指数对所有类别的用户都有用，初学者用户通常会应用它们来解决有限数量的常见问题。在这些情况下，相反，我们引入其他结构来完成这些作为宏的常见任务（即，可以在SRE语法中扩展的快捷方式让我们首先介绍SRE的完整语法我们继承了RE使用的所有通用语法，并添加了以下结构：• /（e）var/是名为var的变量到SREe的绑定。• /var/是一个名为var的变量的反向引用。•任何子表达式右侧的id将称为id的指数绑定到该表达式。当然，在我们的语法中，字符/是保留的，可以使用表达式//直接访问。这是一个非常常见的技术，实际上用于其他元字符，如。在本文中，我们只限于SRE应用程序的两个例子。许多其他的例子，无论是使用简化语法还是完整语法，都可以在全文中找到6.1非专业用户反向引用的一个非常常见的用法是将一个子字符串分组，然后在同一个或另一个表达式中使用例如，我们可能想确定一个字符串是否包含在两个不同位置重复的子串，或者我们可能从一个表达式中获得一个子串并将其用于另一个表达式，这通常是搜索/替换或数据提取函数。 在这两种情况下，我们通常对可以使用/（.*）之类的表达式绑定到SRE变量的泛型子字符串感兴趣。v/，然后用/v/引用。对于像这样非常简单的任务，强迫低级用户使用这种语法似乎很不自然。我们可以重新引入星号键的概念，所有用户都知道它是几乎所有UNIX命令shell的文件名globbing实用程序的一部分。在这些程序中，星号没有RE，但代表通用字符串。13因此，我们可以使用我们的同步变量作为同步任务。我们说，如果某个名称从未绑定到表达式中的SRE，那么它可以绑定到A中的任何字符串。因此，/v/既作为绑定到（.*）表达式和反向引用，其中第一次使用特定的变量是它的绑定，以下所有都是反向引用。这就是用户通常期望。例6.1在标准C头文件math. h的某些版本中，有一个预定义的宏random（n），用于获取[0. n]。 这个宏使用标准的rand（）函数扩展为表达式rand（）% n，该函数返回范围[0. MAXINT]。以来这个宏不是标准的，很多编译器解决这个问题的最好方法是在搜索和替换函数中对源文件使用同步的正则表达式我们只需要使用这个表达式：搜索：随机（/arg/）替换为：rand（）%/arg/例6.2如果我们在文件F1和F2中有两个文本，并且怀疑其中一个文本是通过简单地“shu”其段落和短语从另一个文本中获得的Cat F1 Sep F2|match（/p1/+/p2/+/p3/）{n}我们假设有一个名为Sep的第三个文件，它包含一个在F1和F2中没有出现的分隔符文本。此命令的含义如下：(i) 将文件F1与文件Sep连接，然后将F2附加到结果;(ii) 将获得的文件传递给match命令，如果其输入与给定的SRE匹配，则应该请注意，在SRE的中间，我们使用了标准的UNIX shell替换命令（由 于 分 隔 符 文 本 的 存 在 ， SRE 被 迫 将 两 个 文 件 的 内 容 与 表 达 式（/p1/+/p2/+/p3/）{n}相匹配，这意味着如果这个表达式匹配所有变量之间同步的两个文件，那么我们知道这两个文件都由具有相同内容的n这意味着只有顺序发生了变化，可能有些部分已经被其他部分取代我们在表达式中使用的反向引用变量的数量增加了比较的粒度，因此我们可能能够发现更复杂的操作。14{←}−→{−→ − →}6.2为专家用户提供全面的解决方案我们展示了一个使用SRE语法的例子。所使用的ex-task当然是非常复杂的，但是，正如我们在本节的介绍中所述，一般的SRE语法是为专家用户保留的。例6.3用HTML编写的Web文档通常包含指向其他资源的链接。这些链接有一个显示形式，通常标识链接目标，和一个内部形式，其中包含其他有用的信息，最有趣的是，链接地址。例如，一行HTML，如排这个链接<关于我们在任何浏览器中都会显示为如果我们打印网页，我们失去了所有的链接地址。自动处理页面并将这些地址写在其描述文本附近可能非常有用我们可以在搜索/替换中使用SRE：搜索：]*HREF="/（[^"]*）1/"[^>]*）2/>/（（[^<]|<[^A]）*）3替换为：/2/ /3（/1/）7相关工作我们已经在论文的主体中考虑了几个相关的概念;在这里，我们将自己限制在其他一些重要的相关作品中。在ECFG（扩展上下文无关文法）[7]中，参数被添加到上下文无关产生式规则的非终端字符中，以控制规则的应用因此，在这种情况下，参数的实例化值充当例如，A（N）aA（N1），A（1）a，其中N3产生A（3）aA（2）aaA（1）n。有一类这样的文法，有一组无限的终结符，代表逻辑程序的语法扩展，即DCG（定义子句文法），在几个Prolog实现中使用。在它们中，字符串是一阶语言的原子或术语，产生式规则可以处理它们的序列事实上，产生式规则中的参数出现可以追溯到WG（van Wijngaarden Grammars），旨在定义上下文编程语言的语法，其变体广泛用于编译器构造。 WG规则是一组无限的上下文无关产生式规则的规则模式。因此，非终结符的字母表可以是无限的，而终结符的字母表是有限的。一个参数的取值由上下文无关文法处理所以WG语法有15\\被认为是两个层次的语法。我们没有指出前面的文法之间的确切关系，而是注意到一个已知的事实，即它们都包含在称为AG（属性文法）、RAG（关系属性文法）、FAG（功能属性文法）或CAG（条件属性文法）的上下文敏感文法的这种扩展也能够表达编程语言的语义（所谓的Knuth语义）。然而，所有这些扩展都远远超出了我们的目标。这同样适用于DCG文法的另一个扩展，即著名的λHHG（Higher Harrop Grammars）。它们代表了λ-Prolog作为Prolog的DCG的语法观点最后，我们将介绍一下在常用工具和语言中对后向引用的实际实现 正如在我们的SRE中一样，文本编辑工具中的反向引用允许与其表达式的任意前面的子表达式同步，该子表达式已被标记并用括号分组。例如，表达式（.*） 1将匹配任何由两个相同的一半。 这里（.*） 代表“任何字符的任何序列”，1是对赋值给（.*）的值的反向引用. 在我们的SRE语法中，这将用模式（A）% vv表示。同步正则表达式变量的作用与反向引用完全此外，它们规则我们的SRE还允许不同类型的同步，求幂，其中两个子表达式的内容可以改变，但它们的重复必须相同。反向引用的一个著名实现是GNU正则表达式 li-10。多亏了这一点，许多GNU工具，如egrep[14]允许用户使用它们。GNU匹配引擎演示了我们关于复杂性的声明：当正则表达式中存在反向引用时，它会切换从非常快速的DFA算法到NFA [8]。实际上，该实现与（数学定义的）NFA非常相似，但在某些方面与之不同这种扩展的识别能力的代价是NFA实现是一种具有非常广泛的递归使用的指数算法也就是说，算法较慢，并且可能需要更多的内存来运行。已经做了一些尝试来扩展DFA模型的实现据我们所知，目前为止做得最好的是稍微扩展DFA和NFA域之间的边界，即正则表达式引擎可以匹配更多模式而无需切换到NFA。但是，只要NFA被完全排除在这些匹配引擎之外（如果它们可以被排除的话），使用反向引用和类似的matacharters的复杂性问题将仍然存在。反向引用的另一种实现是在Perl语言中[17]。我们知道很多书都不鼓励在Perl中使用反向引用，因为这会使匹配变得非常复杂和耗时[8]。16Perl还允许使用无限数量的反向引用（而GNU代码将此数量限制为9个），这似乎是不安全的，因为没有经验的用户可能会随意使用它们太多次，编写非常低效的程序。引用[1] A.V. Aho，在字符串中查找模式的算法，J. van Leeuwen ， 编 辑 Handbook of Theoretical ComputerSciencevol1 ， pp.257-300 （ Elsevier Science PublishersB.V.，1990年）[2] D. Angluin ， Finding Patterns Common to a Set ofStrings，Journal of Computer abd System Sciencesvol21，（1980）pp.46-72[3] D. Boneh，J. Shaw，Coppermith，editorProceedings，PTO95 LNCS vol963， pp. 452-465（Springer-Verlag，1995）[4] M.克罗切莫尔RytterText Algorithms（牛津大学出版社，1994）[5] A. De Luca，S. Varricchio，《半群和形式语言中的正则性和非正则性》（Springer，1999）[6] J.这 是 G. Patagun ， A. Salomaa ， G 中 具 有 C_ （ ？ ）Rozenberg ， A. Salomaa ， 《 形 式 语 言 手 册 》 编 辑（Springer-Verlag 1997）[7] P.Deransart，J.Maluszyn′ski，AGrammaticalViewofLogicProgramminginJournal of SymbolicComputation（1993）[8] J. E. F. FriedlMastering Regular Expressions（[9] M.R. Garey，D.S.约翰逊，计算机和棘手性：NP-完全性理论指南（弗里曼，1979年）[10] GNU工程：http://www.gnu.org/[11] J.E. Hopcroft ， J.D. Ullman ， Introduction to AutomataTheory，Languages，and Computation（Addison-Wesley，1979）[12] J.van Leeuwen ， 编 辑 Handbook of Theoretical ComputerSciencevol1 ， （ Elsevier Science Publishers B.V.， 1990年）[13] M. Lothaire ， Combinatorics on Words ， in Gian-CarloRota，editorEncyclopedia of Mathematics and its Applicationsvol17， pp. 6-8（Addison-Wesley，1983年）17[14] A.Magloire，Grep：SearchingforaPattern（iUniverse.com，2000）18[15] F. A. P. 珀蒂科拉斯河J. 安德森，M。G. Kuhn，信息隐藏，综述，IEEE会议录，多媒体内容保护专刊（IEEE，1999）[16] G. Rozenberg ， A. Salomaa ， 《 形 式 语 言 手 册 》 编 辑（Springer-Verlag 1997）[17] L. Wall，T. Christiansen，J. OrwantProgramming Perl，3rd Edition（