☰

有沒有辦法在交替時選擇最短的匹配？

tag-icon • tag-icon awk grep regular-expression
有沒有辦法在交替時選擇最短的匹配？

我的印像是 grep 和 awk 使用 NFA（非確定性）正規表示式機器。
本頁中間的圖片是關於正規表示式匹配可以簡單而快速確認情況確實如此。

眾所周知，當第一個交替匹配時，NFA 實作可能會停止。例如，連結文章中的這個 NFA 機器例如，考慮 abab|abbb 的 NFA：

在此輸入影像描述

對應的正規表示式在符合第一個 時abab|abbb會達到與字串右側的符合狀態。此時它將在到達終點時停止，到達匹配狀態(S10)。即使可能存在另一場匹配，也無需測試更多輸入。ababbbbabababbb

也就是說，在這段程式碼中：

echo 'catfish' | grep -Eo 'cat|catfish'

結果應該是，cat但是卻是catfish。無論交替與否，結果都是一樣的。

是什麼讓 grep 正規表示式引擎總是找到最長的匹配項？

並且，是否可以更改預設值？

答案1

我認為沒有辦法用 POSIX 相容的grepor來做到這一點awk，因為標準確實需要最長的匹配（例如請參閱線上regex(7)幫助頁）。

例如，您可以透過修改程式和正規表示式來awk獲得所需的輸出awk

echo 'SetValue' | awk '{ if (match($0, /Set(Value)?/)) { print substr($0, RSTART, 3); }

在這種情況下，我會使用pcregrep（pcre perl 相容正規表示式庫的一部分），它允許您使用以下命令指定編號子組-o：

echo SetValue | pcregrep -o1 '(Set)(Value)?'

或者，因為 PCRE 具有非貪婪匹配的語法，

echo SetValue | pcregrep -o0 'Set(Value)??'

答案2

據我所知，事實證明，事實上，兩台 NFA 機器：

  • 傳統 NFA 引擎
    一種可回溯的 NFA 機器最長的最左邊的匹配並不總是受到尊重。

  • POSIX NFA 引擎
    一種非回溯 NFA 引擎，並行處理所有狀態，並可以選擇輸入字串中的任何匹配項。選擇最左邊、最長的配對是 POSIX 的要求。

然而，DFA 回溯機（Perl）可能會指數級爆炸 (2^n)由文字（而不是正規表示式）驅動，並且可以選擇（或不選擇）交替中的第一個。

據說還有一個DFA 並行識別所有可能的匹配。

而且，從問題中連結的文章的作者看來，re2 實作將交替定義為： x|y ==> x 或 y （首選 x），即：偏好交替中的第一個。

因此，總而言之，沒有辦法真正將 NFA 或 DFA 與將選擇交替的哪一部分相關聯，這取決於具體的實現。

而且，不，我還沒有找到一種方法來告訴特定的實現更改其預設值。

有關的：

相關內容