代码之家 › 专栏 › 技术社区 › sepp2k

lookaround是否影响哪些语言可以与正则表达式匹配?

lookaround lookahead lookbehind regex

sepp2k · 技术社区 · 16 年前

现代regex引擎中有一些特性允许您匹配没有这些特性就无法匹配的语言。例如,以下使用返回引用的regex与包含重复自身的单词的所有字符串的语言匹配: (.+)\1 . 此语言不是常规语言,不能与不使用返回引用的regex匹配。

lookaround是否还影响哪些语言可以与正则表达式匹配?也就是说,是否有任何语言可以通过lookaround进行匹配,否则无法匹配?如果是这样的话,这对于所有的环顾(消极的、积极的、超前的或超前的)或者仅仅是对其中一些人来说是真的吗?

4 回复 | 直到 14 年前

8 revs<br/>Aryabhatta 16 年前

正如其他答案所声称的,lookarounds不会为正则表达式增加任何额外的功能。

我想我们可以用以下方式来展示:

One Pebble 2-NFA (见本文引言部分)。

1-Pebble2NFA不处理嵌套的lookaheads,但是,我们可以使用多Pebble2NFA的变体(参见下面的部分)。

介绍

2-NFA是一种非确定性的有限自动机,能够在输入端左右移动。

一个卵石机器是指机器可以将一个卵石放在输入带上(即用卵石标记一个特定的输入符号),并根据当前输入位置是否有卵石进行可能不同的转换。

众所周知,一个圆石2-NFA有相同的权力,作为一个普通的DFA。

非嵌套lookaheads

基本思路如下:

2NFA允许我们通过在输入磁带中向前或向后移动来回溯(或“前轨”)。因此,对于lookahead,我们可以对lookahead正则表达式进行匹配,然后在匹配lookahead表达式时回溯所消耗的内容。为了准确知道何时停止回溯,我们使用了鹅卵石!我们在进入德国足协(DFA)进行先行检查之前,先放下鹅卵石,以标记回溯需要停止的地方。

因此,在通过Pebble 2NFA运行字符串的末尾,我们知道是否匹配lookahead表达式,而左边的输入(即剩余的要消费的内容)正是匹配剩余内容所需的内容。

那么,对于形式u(?= V)W

我们有u,v和w的dfas。

从dfa的接受状态(是的,我们可以假设只有一个)开始,我们对v的起始状态进行e-转换,用圆石标记输入。

从V的接受状态,我们转换到一个保持输入向左移动的状态,直到它找到一个圆石,然后转换到W的开始状态。

从V的拒绝状态,我们E-转换到一个一直向左移动直到它找到鹅卵石的状态,并转换到U的接受状态(即我们离开的位置)。

用于常规NFA的证据,用于显示R1 R2或R*等,对这一块卵石2NFA进行结转。见 http://www.coli.uni-saarland.de/projects/milca/courses/coal/html/node41.html#regularlanguages.sec.regexptofsa 有关如何将组件机器组合在一起以便为r*表达式等提供更大的机器的详细信息。

上述R*ETC工作证明的原因是,当我们输入组件nfas进行重复时,回溯确保输入指针始终位于正确的位置。另外,如果一个圆石正在使用中,那么它将由一个lookahead组件机器进行处理。由于没有从lookahead机器到lookahead机器的转换,就不需要完全回溯和返回Pebble,所以只需要一个Pebble机器。

例如考虑([^a]a(?=…B)*

以及字符串abbb。

我们有一个abbb,它通过peb2nfa获得了a(?=…b),在其末尾,我们处于状态:(b b b,matched)(即在输入b b b中剩余,它匹配“a”,后跟“…b”)。现在,由于*,我们回到开头(请参见上面链接中的构造),并为[^a]输入dfa。匹配b,返回开头,再次输入[^a]两次,然后接受。

处理嵌套的lookaheads

要处理嵌套的lookaheads,我们可以使用此处定义的受限制版本的k-pebble 2nfa: Complexity Results for Two-Way and Multi-Pebble Automata and their Logics (见定义4.1和定理4.2)。

一般来说,2个卵石自动机可以接受非正则集,但在以下限制条件下,k-卵石自动机可以证明是正则的(本文中的定理4.2)。

如果鹅卵石是P_1,P_2,…,P_k

P_I+1不得放置,除非P_I已经在磁带上,并且P_I不得被拾取,除非P_I+1不在磁带上。基本上,鹅卵石需要用后进先出法。
在放置p_i+1和拾取p_i_或放置p_i+2的时间之间,自动机只能遍历位于p_i_的当前位置和位于p_i+1_方向的输入字结尾之间的子字。此外,在这个子词中,自动机只能作为一个带有圆石p_i+1_的1-圆石自动机。尤其是不允许提升、放置或感觉到另一块卵石的存在。

因此,如果v是深度k的嵌套先行表达式,那么(?=v)是深度k+1的嵌套先行表达式。当我们进入一个先行机器时,我们知道到目前为止必须放置多少个鹅卵石,因此可以精确地确定要放置哪个鹅卵石,当我们退出机器时,我们知道要提升哪个鹅卵石。在深度t处的所有机器都是通过放置Pebble T进入的,而通过移除Pebble T退出的(即我们返回到深度t-1机器的处理)。整个机器的任何运行都像是树的递归DFS调用,并且可以满足多Pebble机器的上述两个限制。

现在,当您组合表达式时,对于r r1,因为您concat,r1的圆石编号必须增加r的深度。对于r*和r r1,圆石编号保持不变。

因此,任何具有lookaheads的表达式都可以转换为等效的多卵石机器,在卵石放置方面有上述限制,因此是规则的。

结论

这基本上解决了Francis最初的证明中的缺点:能够防止lookahead表达式使用将来匹配所需的任何东西。

因为lookbehinds只是有限字符串(不是真正的regex),所以我们可以先处理它们,然后再处理lookaheads。

抱歉,写得不完整,但完整的证据需要画很多数字。

这对我来说是对的,但我很高兴知道有任何错误(我似乎喜欢这样的错误)。

BlueRaja - Danny Pflughoeft 16 年前

对于您所问的问题的答案是否定的,即是否可以通过环顾来增强正则表达式来识别比常规语言更大的语言类。

证明相对简单,但是将包含查找的正则表达式转换为不包含查找的正则表达式的算法是混乱的。

首先:请注意,您总是可以否定正则表达式(在有限字母表中)。给定一个识别表达式生成的语言的有限状态自动机,您可以简单地将所有接受状态交换为不接受状态,得到一个完全识别该语言的否定的FSA,对于该语言,有一系列等价的正则表达式。

第二:因为正则语言(以及正则表达式)在否定下是闭的,所以它们在交集下也是闭的,因为根据德摩根定律,交集b=neg(neg(a)union neg(b))。换句话说,对于给定的两个正则表达式,您可以找到另一个匹配这两个表达式的正则表达式。

这允许您模拟lookaround表达式。例如U?=v)w只匹配将匹配uv和uw的表达式。

对于负向前看,需要等价于集合理论a \b的正则表达式,它只是一个相交(neg b)或等价的neg(neg(a)union b)。因此,对于任何正则表达式r和s,您都可以找到一个正则表达式r-s,它与那些与r不匹配的表达式相匹配。在负先行条件下:u(?!v)w只匹配那些与uw-uv匹配的表达式。

环顾是有用的有两个原因。

首先,因为对正则表达式的否定会导致更不整洁的东西。例如 q(?!u)=q($|[^u]) .

其次,正则表达式做的不仅仅是匹配表达式,它们还使用字符串中的字符——或者至少这是我们喜欢的思考方式。例如,在Python中,我关心.start()和.end(),因此当然:

>>> re.search('q($|[^u])', 'Iraq!').end()
5
>>> re.search('q(?!u)', 'Iraq!').end()
4

第三,我认为这是一个非常重要的原因,正则表达式的否定不能很好地提升到连接上。neg(a)neg(b)与neg(a b)不同,这意味着你不能将lookaround从你找到它的上下文中转换出来——你必须处理整个字符串。我想这会使人们不喜欢和正则表达式一起工作,并破坏人们对正则表达式的直觉。

我希望我已经回答了你的理论问题(深夜,如果我不清楚,请原谅我)。我同意一位评论员的观点,他说这确实有实际的应用。当我试图抓取一些非常复杂的网页时,遇到了同样的问题。

编辑

我为不清楚而道歉:我不相信你能用结构归纳法证明正则表达式+观察的规律性,我的u(?!v)w example就是一个简单的例子。结构归纳法不起作用的原因是,环视的行为方式是非组合的——我在上面试图说明的关于否定的观点。我怀疑任何直接的正式证据都会有很多混乱的细节。我试着想出一个简单的方法来展示它,但却无法想出一个我的头。

用乔希的第一个例子来说明 ^([^a]|(?=..b))*$ 这相当于7个州的FSA,所有州都接受:

A - (a) -> B - (a) -> C --- (a) --------> D 
Î          |           \                  |
|          (not a)       \               (b)
|          |              \               | 
|          v                \             v
(b)        E - (a) -> F      \-(not(a)--> G  
|            <- (b) - /                   |
|          |                              |
|         (not a)                         |
|          |                              |
|          v                              |
\--------- H <-------------------(b)-----/

单独状态A的正则表达式如下所示:

^(a([^a](ab)*[^a]|a(ab|[^a])*b)b)*$

换言之,任何通过消除环顾而得到的正则表达式通常都要长得多,而且要混乱得多。

回应乔希的评论——是的,我认为最直接的证明等效性的方法是通过金融服务管理局。造成这种混乱的是,构建FSA的通常方法是通过一个非确定性的机器——它更容易将u v表示为简单地由u和v的机器构造而成,并向其中两个机器进行epsilon转换。当然,这相当于一个确定性机器,但处于状态指数爆炸的风险中。相反,通过确定性机器进行否定要容易得多。

一般的证明包括取两台机器的笛卡尔积,并选择那些你希望在每一个你想要插入环视图的点上保留的状态。上面的例子在某种程度上说明了我的意思。

我为没有提供建筑而道歉。

进一步编辑: 我找到了一个 blog post 它描述了一种从带有查找功能的正则表达式中生成dfa的算法。它很简洁,因为作者以明显的方式扩展了带有“标记epsilon转换”的NFA-E的概念,然后解释了如何将这种自动机转换为DFA。

我以为这样做是一种方法,但我很高兴有人写了。我想不出这么整洁的东西来。

Josh Haberman 16 年前

我同意其他关于lookaround是正则的文章(也就是说它不向正则表达式添加任何基本功能),但是我有一个论点,它比我看到的其他文章更简单。

我将通过提供一个DFA结构来证明环顾是正常的。只有当一种语言有一个可识别它的dfa时,它才是常规语言。请注意,Perl实际上并没有在内部使用dfas(有关详细信息,请参阅本文): http://swtch.com/~rsc/regexp/regexp1.html ),但我们构建了一个dfa用于证明目的。

为正则表达式构造DFA的传统方法是首先使用汤普森算法构建NFA。给定两个正则表达式片段 r1 和 r2 ,汤普森的算法为正则表达式的串联( r1 r2 )、交替( r1 r2 )和重复( r1*. )提供构造。这允许您一点一点地构建一个NFA来识别原始的正则表达式。请参阅上面的文章了解更多详细信息。

为了证明正的和负的lookahead是正则的,我将提供一个正则表达式连接的构造,其中正的或负的lookahead: (?=v) or (?!v)<代码>。只有连接需要特殊处理;通常的交替和重复结构工作良好。

该结构适用于两个U(?= v)和U(?)v)是:


   
    
     
      
     
     
      换言之,将现有NFA的每个最终状态连接到接受状态和NFA,但修改如下。函数
      
       f(v).
       
        is defined as:。
       
      
     
     
      
       
        
         让
         
          a a(v)
          
           be a function on an nfa
           
            v
            
             that changes every accept state into an“anti accept state”.反接受状态被定义为一种状态,如果给定字符串的NFA路径结束于此状态,则会导致匹配失败,即使不同路径通过
             
              v
              
               for
               
                s
                
                 ends in an accept state.
                
               
              
             
            
           
          
         
        
        
         
          
           
           
          
         
        
        
         
          
           
            让
            
             loop(v)
            
            be a function on an nfa
            
             v
             
              that adds a self transition on any accept state.换句话说,一旦一条路径导致一个接受状态,那么不管后面有什么输入,该路径都可以永远保持在接受状态。
             
            
           
          
         
        
        
         
          
           
           
          
         
        
        
         
          
           
            对于负向前看,
            
             f(v)=aa(loop(v))
             
              。
             
            
           
          
         
        
        
         
          
           
            对于正前方,
            
             f(v)=aa(neg(v))
             
              。
             
            
           
           
            
            
           
          
         
        
       
       
        
         
          
           为了提供一个直观的例子来说明为什么这个方法有效,我将使用regex
           
            (b a(?:.b))+
            
             ,这是我在弗朗西斯证明的注释中提出的regex的一个稍微简化的版本。如果我们把我的结构和传统的汤普森结构一起使用,我们最终会得到:
            
           
          
          
           
            
             
            
            
             
              e
              
               s是epsilon转换(可以在不使用任何输入的情况下进行转换),并且反接受状态标记为
               
                x
                
                 。在图表的左半部分,您可以看到
                 
                  (a b)+.
                  
                   :any
                   
                    a.
                    
                     or
                     
                      b.
                      
                       puts the graph in an accept state,but also allows a transition back to the begin state so we can do it again.但是请注意,每次我们匹配
                       
                        a时,我们也会输入图表的右半部分,在这里我们处于反接受状态,直到我们匹配“any”,然后再匹配a
                        
                         b
                         
                          。
                         
                        
                       
                      
                     
                    
                   
                  
                 
                
               
              
             
            
            
             
              
               
                这不是传统的NFA,因为传统的NFA没有反接受状态。但是,我们可以使用传统的NFA->DFA算法将其转换为传统的DFA。该算法的工作原理与往常一样,我们通过使我们的dfa状态对应于我们可能处于的nfa状态的子集来模拟nfa的多次运行。唯一的问题是,我们稍微增加了一点规则,以决定DFA状态是否为接受(最终)状态。在传统的算法中,如果NFA状态的
                
                 any
                 
                  是一个接受状态,那么DFA状态就是一个接受状态。我们将此修改为:当且仅当以下情况时,DFA状态为接受状态:
                 
                
               
               
                
                 
                  
                   
                    
                     =1 NFA状态是接受状态,
                     
                      和
                     
                    
                    
                    
                   
                  
                  
                   0个NFA状态是反接受状态。
                  
                  
                  
                 
                 
                  该算法将为我们提供一个用lookahead识别正则表达式的DFA。因此,向前看是正常的。请注意,lookback需要单独的证明。
                 
                 
                  它没有给正则表达式增加任何基本的功能),但我有一个理由认为它比我见过的其他表达式更简单。
                 
                 
                  我将通过提供一个DFA结构来证明环顾是正常的。只有当一种语言有一个可识别它的dfa时,它才是常规语言。请注意,Perl实际上并没有在内部使用dfas(有关详细信息,请参阅本文:
                  
                   http://swtch.com/~rsc/regexp/regexp1.html
                  
                  )但为了证明,我们构建了一个DFA。
                 
                 
                  为正则表达式构造DFA的传统方法是首先使用汤普森算法构建NFA。给定两个正则表达式片段
                  
                   r1
                  
                  和
                  
                   r2
                  
                  汤普森的算法提供了连接的构造。(
                  
                   r1r2
                  
                  )交替(
                  
                   r1|r2
                  
                  )和重复(
                  
                   r1*
                  
                  )正则表达式。这允许您一点一点地构建一个NFA来识别原始的正则表达式。请参阅上面的文章了解更多详细信息。
                 
                 
                  为了证明正的和负的lookahead是正则的,我将提供正则表达式串联的构造。
                  
                   u
                  
                  正面或负面展望:
                  
                   (?=v)
                  
                  或
                  
                   (?!v)
                  
                  .  只有连接需要特殊处理;通常的交替和重复结构工作良好。
                 
                 
                  该结构适用于两个U(?= v)和U(?)v)是:
                 
                 
                  
                 
                 
                 
                 
                  换句话说,连接现有NFA的每个最终状态
                  
                   U
                  
                  接受状态
                  
                   和
                  
                  一个NFA
                  
                   v
                  
                  ,但修改如下。函数
                  
                   f(v)
                  
                  定义为:
                 
                 
                  
                   让
                   
                    aa(v)
                   
                   在NFA上发挥作用
                   
                    V
                   
                   这会将每个接受状态更改为“反接受状态”。反接受状态定义为导致匹配失败的状态,如果
                   
                    任何
                   
                   对于给定的字符串,通过NFA的路径以该状态结束
                   
                    s
                   
                   ,即使通过不同的路径
                   
                    V
                   
                   对于
                   
                    S
                   
                   以接受状态结束。
                  
                  
                   让
                   
                    loop(v)
                   
                   在NFA上发挥作用
                   
                    V
                   
                   这会在任何接受状态上添加一个自转换。换句话说,一旦一条路径导致了一个接受状态,那么不管后面有什么输入,该路径都可以永远保持在接受状态。
                  
                  
                   对于负面展望,
                   
                    f(v) = aa(loop(v))
                   
                   .
                  
                  
                   对于积极的展望,
                   
                    f(v) = aa(neg(v))
                   
                   .
                  
                 
                 
                  为了提供一个直观的例子来说明这一点,我将使用regex
                  
                   (b|a(?:.b))+
                  
                  这是我在弗朗西斯的证明评论中提出的正则表达式的一个稍微简化的版本。如果我们将我的结构与传统的汤普森结构一起使用,我们最终会得到:
                 
                 
                  
                 
                 
                 
                 
                  这个
                  
                   e
                  
                  s是epsilon转换(可以在不消耗任何输入的情况下进行转换),反接受状态标记为
                  
                   X
                  
                  .  在图的左半部分,您可以看到
                  
                   (a|b)+
                  
                  任何
                  
                   a
                  
                  或
                  
                   b
                  
                  将图形置于“接受”状态,但也允许转换回“开始”状态,以便我们可以再次执行此操作。但请注意,每次我们匹配
                  
                   一
                  
                  我们还输入图的右半部分,在这里我们处于反接受状态,直到我们匹配“any”,后跟一个
                  
                   乙
                  
                  .
                 
                 
                  这不是传统的NFA,因为传统的NFA没有反接受状态。但是,我们可以使用传统的NFA->DFA算法将其转换为传统的DFA。该算法的工作原理与平常一样,我们通过使我们的dfa状态对应于我们可能处于的nfa状态的子集来模拟nfa的多次运行。唯一的问题是,我们稍微增加了一个规则,以决定DFA状态是否为接受(最终)状态。在传统算法中,如果
                  
                   任何
                  
                  NFA的州是一个接受的州。我们将此修改为DFA状态是接受状态,前提是:
                 
                 
                  
                   
                    
                     =1 NFA状态为接受状态,
                     
                      和
                     
                    
                   
                  
                  
                   0 NFA状态是反接受状态。
                  
                 
                 
                  该算法将为我们提供一个用lookahead识别正则表达式的DFA。因此,向前看是正常的。请注意,lookback需要单独的证据。

NealB 16 年前

我觉得这里有两个不同的问题:

regex引擎是否更多地融入了“lookaround”功能? 比Regex引擎更强大,不是吗?
“环顾四周”吗? 使regex引擎能够解析以下语言: 比从 Chomsky Type 3 - Regular grammar ?

从实际意义上讲,第一个问题的答案是肯定的。lookaround将提供一个regex引擎, 从根本上说,使用这个功能比不使用的功能更强大。这是因为它为匹配过程提供了一组更丰富的“锚”。 lookaround允许您将整个regex定义为可能的定位点(零宽度断言)。你可以对这个功能的功能有一个很好的概述 here .

虽然功能强大,但环顾四周并不能将regex引擎提升到理论之外。类型3语法对其设置的限制。例如,你永远无法 可靠地 基于 Context Free - Type 2 Grammar 使用Regex引擎装备有了望台。Regex引擎的功率仅限于 Finite State Automation 这从根本上限制了他们可以解析的任何语言的表达能力,使其达到3类语法的水平。不管在regex引擎中添加了多少“技巧”,这些语言是通过 Context Free Grammar 将始终超出其能力范围。分析上下文无关的-2型语法需要下推自动化来“记住”它在哪里递归语言结构。任何需要对语法规则进行递归评估的内容都不能使用正则表达式引擎。

总而言之:lookaround为regex引擎提供了一些实际的好处,但不会在理论水平。

编辑

在类型3(常规)和类型2(上下文无关)之间是否存在复杂的语法?

我相信答案是否定的,原因是没有理论上的限制放在NFA/DFA的大小上,用于描述常规语言。它可能变得任意大因此无法使用(或指定)。在这里,诸如“环顾四周”之类的闪避是有用的。他们提供一个简短的机制来说明什么会导致非常大/复杂的NFA/DFA。规格。它们不会增加常规语言,它们只是使指定它们更加实用。一旦你明白了这一点,它就变成了很明显,有很多“特性”可以添加到regex引擎中,使它们更强大。从实际意义上说是有用的——但没有什么能使他们超越常规语言的限制。

规则语言和上下文无关语言的基本区别在于不包含递归元素。为了评估递归语言,需要下推式自动化 “记住”你在递归中的位置。NFA/DFA不堆叠状态信息,因此无法处理递归。因此,对于非递归语言定义,将有一些nfa/dfa(但是不一定是一个实际的regex表达式)来描述它。