3

ちょっとした背景: 私は正規表現マッチング エンジン (NFA) を実装しており、PCRE 互換モードをサポートする必要があります (つまり、PCRE と同じオフセットで部分式をキャプチャする必要があります)。

PCRE の testinput1 には、完全には理解できないテストがあります。遅延量指定子をテストします。

したがって、正規表現は

/<a[\s]+href[\s]*=[\s]*          # find <a href=
 ([\"\'])?                       # find single or double quote
 (?(1) (.*?)\1 | ([^\s]+))       # if quote found, match up to next matching
                                 # quote, otherwise match up to next space
/isx

そして文字列は

<a href="abcd xyz pqr" cats

PCRE の試合は次のとおりです。

<a href="abcd xyz pqr"

明らかに遅延量指定子を使用しています。

私が理解している限り、別の「貪欲な」方法がまったく不可能になるまで、遅延量指定子を使用しないでください。ここで可能な貪欲な一致は次のとおりです。

<a href="abcd

条件付きサブパターンの負の分岐を使用し、遅延量指定子は使用しません。

したがって、この PCRE の動作の説明、または遅延量指定子がこのテストで一致する理由の詳細/提案を探しています。ありがとう！

EDIT ： TREライブラリの仕組みも調べました。POSIX 互換の NFA エンジンです。TRE の構文に合わせて元の正規表現を少し変更しました。

#include <stdlib.h>
#include <stdio.h>
#include <tre/tre.h>

int main()
{
    regex_t preg;
    const char * regex = "<a[ ]+href[ ]*=[ ]*(?:(')(.*?)'|[^ ]+)";
    const char * string = "<a href='abcd xyz pqr' cats";
    int cflags = REG_EXTENDED;
    int eflags = 0;
    size_t nmatch = 3;
    regmatch_t pmatch[100];

    tre_regcomp(&preg, regex, cflags);
    tre_regexec(&preg, string, nmatch, pmatch, eflags);

    for (int i = 0; i < nmatch; i++) {
        printf("%d: (%d, %d)\n", i, pmatch[i].rm_so, pmatch[i].rm_eo - pmatch[i].rm_so);
    }

    return 0;
}

出力 (終了オフセットの代わりに長さを使用) は次のとおりです。

0: (0, 22)
1: (8, 1)
2: (9, 12)

したがって、PCRE のバックトラッキング固有の動作に関する提案は、おそらく間違っています...

4

2 に答える 2

1

まず第一に、私は REGEX の世界では初心者です。したがって、この回答が間違っていたり、質問を誤解していたり​​したら申し訳ありません。

この本正規表現クックブックから取られたこの定義を読む：

(?(1)then|else)は、最初のキャプチャ グループが既に何かに一致しているかどうかをチェックする条件です。存在する場合、正規表現エンジンは一致を試みます。キャプチャ グループがこれまでにマッチ試行に参加していない場合は、else 部分が試行されます。

  • この件名で： <a href="abcd xyz pqr" cats

    最初のキャプチャ グループが最初の"文字と一致しました。そのため、期待される動作は、then 部分の一致を試みることです。then 部分の 2 番目のキャプチャ グループは文字列abcd xyz pqrと一致し(.*?)、最後に then 部分は と一致abcd xyz pqr"し(.*?)\1ます。REGEX は成功して終了する場合があります。

    そのため、 greddy 量指定子を持つ else 部分は必要ありません。実際には使用されません。あたかも greddy 量指定子が存在しなかったかのようです。

  • この件名で：<a href="abcd

    最初のキャプチャ グループが文字と一致しました"。then の部分はなんとか文字列abcdと一致しますが、件名の末尾にそのような文字がないため(.*?)、最後の文字とは一致しません。"条件は失敗します。

    REGEX エンジンはここで停止しません。これを使用しました。文字がオプションで([\"\'])?あるため、エンジンは再試行する可能性があり"、最初のキャプチャ グループが一致しなかったかのように続行します (実際にはバックトラックがあります)。そのため、エンジンは最初のキャプチャ グループに一致せずに条件に達し、else 部分が試行され、文字列を一致させることができます"abcd("文字はバックトラックのために最初のキャプチャ グループに一致せず、現在は一致していますelse 部分の 3 番目のキャプチャ グループ) REGEX は成功して終了する場合があります。

PS: 私は正規表現について楽しいことを学んでいるので、おそらくこの答えは完全に間違っています。より良い答えを待ちます。

于 2014-01-16T19:49:02.840 に答える
0

ここであなたの質問を完全には理解していませんが、貪欲でない量指定子により、パターンの最初の出現まで検索できます。pcretest では、貪欲な形式と貪欲でない形式を同じ入力で試します。

非貪欲な形式:

  re> /<a[\s]+href[\s]*=[\s]*([\"\'])?(?(1)(.*?)\1|([^\s]+))/i
  data> <a href="ab"cd"
    0: <a href="ab"
    1: "
    2: ab

貪欲なフォーム:

 re> /<a[\s]+href[\s]*=[\s]*([\"\'])?(?(1)(.*)\1|([^\s]+))/i
 data> <a href="ab"cd"
    0: <a href="ab"cd"
    1: "
    2: ab"cd
于 2014-01-17T21:59:08.483 に答える