在貪婪的重複中回溯平衡組可能會導致失衡？

作爲此問題的一般釀造示例，我的意圖是匹配a的某些數字，然後匹配相同數量的b，再加上一個b。在貪婪的重複中回溯平衡組可能會導致失衡？

檢查在這個片段（also on ideone.com）所表現出的兩種模式：

var r1 = new Regex(@"(?xn) 
    (?<A> a)+ (?<B-A> b)+ (?(A)(?!)) b 
"); 
var r2 = new Regex(@"(?xn) 
    (?<A> a)+ (?<B-A> b)+? (?(A)(?!)) b 
"); 

Console.WriteLine(r1.Match("aaabbb")); 
// aaabbb 

Console.WriteLine(r2.Match("aaabbb")); 
// aabbb

注意，存在兩種模式的匹配的差。 r1，其在平衡組構建體上使用貪婪重複，匹配3,a和3,b，這是非如預期的那樣。 r2，其使用不情願的重複，給予我如預期的那樣的和的，其中爲。

我可以解釋這個問題的唯一辦法是，當(?<B-A> b)+回溯匹配一個都不能少b，它從B棧中彈出，但不推背什麼也相應地從A棧中彈出。因此，即使因爲回溯而現在減少了一個b，A堆棧仍爲空。這是我能解釋r1如何匹配aaabbb的唯一方法。

請注意，在r2中使用不情願+?不會導致此問題。我看到它的方式，這是因爲不像貪婪的重複，不情願的重複不必「撤銷對堆棧的損害」，這就是說話。相比之下，貪婪的重複會造成儘可能多的「損害」，但回溯不能「保持現狀」到A堆棧。

這是對發生的事情的正確分析嗎？如果是這樣，這是設計的行爲？因爲它基本上看起來像是在一個貪婪的重複中回溯一個平衡組可能會導致不平衡，因此這可能會被歸類爲一個錯誤（或者至少是一個有些令人驚訝的行爲，但沒有充分記錄）。

來源

2010-09-17 polygenelubricants

我無法重現您的觀察結果。我直接將代碼粘貼到Visual Studio中，並按預期的方式兩次輸出'aabbb'。 – Timwi 2010-09-17 05:19:50

適用於我。我正在使用.NET框架的4.0版本。 – Jens 2010-09-17 07:22:11

@Jens，@Timwi：您是否知道其他在線應用程序，我可以在其中粘貼我的C＃代碼段並使其可以在各種版本的.NET框架中運行？因爲很明顯，ideone.com上的那個提供了不同的輸出。 – polygenelubricants 2010-09-17 07:37:19

這是位於Mono的bug。

人們在IdeOne上獲得像.NET一樣的Environment.Version的原因是Mono要求與.NET向後兼容，包括與基於框架版本做出決策的應用程序的兼容性。

來源

2012-03-12 22:27:57

在貪婪的重複中回溯平衡組可能會導致失衡？

回答

相關問題