هل يمكن استخدام التعبيرات العادية لمطابقة الأنماط المتداخلة؟[ينسخ]

https://stackoverflow.com/questions/133601

02-07-2019
|

سؤال

هذا السؤال لديه بالفعل إجابة هنا:

التعبير العادي لمطابقة الأقواس المتوازنة 16 إجابة

هل من الممكن كتابة تعبير عادي يتطابق مع نمط متداخل يتكرر عدد غير معروف من المرات؟على سبيل المثال، هل يمكن للتعبير العادي مطابقة قوس الفتح والإغلاق عندما يكون هناك عدد غير معروف من أقواس الفتح/الإغلاق المتداخلة داخل الأقواس الخارجية؟

على سبيل المثال:

public MyMethod()
{
  if (test)
  {
    // More { }
  }

  // More { }
} // End

يجب أن تطابق:

{
  if (test)
  {
    // More { }
  }

  // More { }
}

المحلول

لا.انه من السهل.لا يمتلك الإنسان الآلي المحدود (وهو بنية البيانات التي يقوم عليها التعبير العادي) ذاكرة بصرف النظر عن الحالة التي هو فيها، وإذا كان لديك تداخل عميق بشكل عشوائي، فأنت بحاجة إلى إنسان آلي كبير بشكل عشوائي، والذي يتعارض مع فكرة محدود إنسان آلي.

يمكنك مطابقة العناصر المتداخلة/المزدوجة حتى عمق ثابت، حيث يقتصر العمق على ذاكرتك فقط، لأن الإنسان الآلي يصبح كبيرًا جدًا.ومع ذلك، من الناحية العملية، يجب عليك استخدام آلية الضغط للأسفل، أي محلل لقواعد نحوية خالية من السياق، على سبيل المثال LL (من أعلى إلى أسفل) أو LR (من أسفل إلى أعلى).عليك أن تأخذ في الاعتبار السلوك الأسوأ في وقت التشغيل:يا (ن ^ 3) مقابل.يا (ن)، مع ن = الطول (الإدخال).

هناك العديد من المولدات المحللة المتاحة، على سبيل المثال أنتلر لجافا.العثور على قواعد نحوية موجودة لـ Java (أو C) ليس بالأمر الصعب أيضًا.
لمزيد من الخلفية: نظرية الأتمتة في ويكيبيديا

نصائح أخرى

يعد استخدام التعبيرات العادية للتحقق من الأنماط المتداخلة أمرًا سهلاً للغاية.

'/(\((?>[^()]+|(?1))*\))/'

من المحتمل أن يعمل حل Perl، إذا كانت السلسلة في سطر واحد:

my $NesteD ;
$NesteD = qr/ \{( [^{}] | (??{ $NesteD }) )* \} /x ;

if ( $Stringy =~ m/\b( \w+$NesteD )/x ) {
    print "Found: $1\n" ;
  }

هث

يحرر: يفحص:

http://dev.perl.org/perl6/rfc/145.html
معلومات روبي: http://www.ruby-forum.com/topic/112084
المزيد من بيرل: http://www.perlmonks.org/?node_id=660316
المزيد من بيرل: https://metacpan.org/pod/Text::متوازن
بيرل، بيرل، بيرل: http://perl.plover.com/yak/regex/samples/slide083.html

وشيء آخر تورستن ماريك (الذي أشار بشكل صحيح إلى أنه لم يعد تعبيرًا عاديًا بعد الآن):

http://coding.derkeiler.com/Archive/Perl/comp.lang.perl.misc/2008-03/msg01047.html

نعم، إذا كان محرك .NET RegEx.يدعم محرك Net آلة الحالة المحدودة المزودة بمكدس خارجي.يرى تفاصيل

ال ضخ lemma للغات العادية هو السبب وراء عدم قدرتك على فعل ذلك.

سيكون لدى الإنسان الذي تم إنشاؤه عدد محدود من الحالات، على سبيل المثال k، لذا فإن سلسلة من الأقواس الافتتاحية k + 1 لا بد أن يكون لها حالة متكررة في مكان ما (حيث يقوم الإنسان بمعالجة الأحرف).يمكن تكرار جزء السلسلة الموجود في نفس الحالة عدة مرات بشكل لا نهائي ولن يعرف الإنسان الفرق.

على وجه الخصوص، إذا قبلت أقواس الفتح k+1 متبوعة بأقواس الإغلاق k+1 (وهو ما ينبغي)، فسوف تقبل أيضًا العدد المضخم من أقواس الفتح متبوعة بأقواس الإغلاق k+1 غير المتغيرة (وهو ما لا ينبغي).

لن تتمكن التعبيرات العادية المناسبة من القيام بذلك لأنك ستترك عالم اللغات العادية لتهبط في مناطق لغات السياق الحرة.

ومع ذلك فإن حزم "التعبير العادي" التي تقدمها العديد من اللغات تعتبر أكثر قوة.

على سبيل المثال، لوا التعبيرات العادية لها "%b()"أداة التعرف التي ستطابق الأقواس المتوازنة.في حالتك سوف تستخدم "%b{}"

أداة أخرى متطورة مشابهة لـ sed هي جيما, حيث يمكنك مطابقة الأقواس المتوازنة بسهولة شديدة {#}.

لذلك، اعتمادًا على الأدوات المتوفرة لديك، قد يكون "التعبير العادي" (بالمعنى الأوسع) قادرًا على مطابقة الأقواس المتداخلة.

يعد استخدام المطابقة العودية في محرك PHP regex أسرع بشكل كبير من المطابقة الإجرائية للأقواس.خاصة مع السلاسل الأطول.

http://php.net/manual/en/regexp.reference.recursive.php

على سبيل المثال

$patt = '!\( (?: (?: (?>[^()]+) | (?R) )* ) \)!x';

preg_match_all( $patt, $str, $m );

ضد.

matchBrackets( $str );

function matchBrackets ( $str, $offset = 0 ) {

    $matches = array();

    list( $opener, $closer ) = array( '(', ')' );

    // Return early if there's no match
    if ( false === ( $first_offset = strpos( $str, $opener, $offset ) ) ) {
        return $matches;
    }

    // Step through the string one character at a time storing offsets
    $paren_score = -1;
    $inside_paren = false;
    $match_start = 0;
    $offsets = array();

    for ( $index = $first_offset; $index < strlen( $str ); $index++ ) {
        $char = $str[ $index ];

        if ( $opener === $char ) {
            if ( ! $inside_paren ) {
                $paren_score = 1;
                $match_start = $index;
            }
            else {
                $paren_score++;
            }
            $inside_paren = true;
        }
        elseif ( $closer === $char ) {
            $paren_score--;
        }

        if ( 0 === $paren_score ) {
            $inside_paren = false;
            $paren_score = -1;
            $offsets[] = array( $match_start, $index + 1 );
        }
    }

    while ( $offset = array_shift( $offsets ) ) {

        list( $start, $finish ) = $offset;

        $match = substr( $str, $start, $finish - $start );
        $matches[] = $match;
    }

    return $matches;
}

نعم

...على افتراض أن هناك حدًا أقصى لعدد مرات التعشيش التي سيكون من دواعي سرورك التوقف عندها.

دعني أشرح.

@ تورستن ماريك صحيح أن التعبير العادي لا يمكنه التحقق من الأنماط المتداخلة مثل هذا، لكن من الممكن يُعرِّف نمط regex متداخل والذي سيسمح لك بالتقاط الهياكل المتداخلة مثل هذا يصل إلى بعض الحد الأقصى للعمق.لقد قمت بإنشاء واحدة لالتقاطها EBNF على غرار تعليقات (جربه هنا)، يحب:

(* This is a comment (* this is nested inside (* another level! *) hey *) yo *)

التعبير العادي (للتعليقات المفردة) هو كما يلي:

m{1} = \(+\*+(?:[^*(]|(?:\*+[^)*])|(?:\(+[^*(]))*\*+\)+

يمكن تكييف هذا بسهولة لأغراضك عن طريق استبدال \(+\*+ و \*+\)+ مع { و } واستبدال كل شيء بينهما بشيء بسيط [^{}]:

p{1} = \{(?:[^{}])*\}

(إليك الرابط لمحاولة ذلك.)

للتداخل، ما عليك سوى السماح بهذا النمط داخل الكتلة نفسها:

p{2} = \{(?:(?:p{1})|(?:[^{}]))*\}
  ...or...
p{2} = \{(?:(?:\{(?:[^{}])*\})|(?:[^{}]))*\}

للعثور على كتل متداخلة ثلاثية، استخدم:

p{3} = \{(?:(?:p{2})|(?:[^{}]))*\}
  ...or...
p{3} = \{(?:(?:\{(?:(?:\{(?:[^{}])*\})|(?:[^{}]))*\})|(?:[^{}]))*\}

وقد ظهر نمط واضح.للعثور على تعليقات متداخلة على عمق N, ، ما عليك سوى استخدام التعبير العادي:

p{N} = \{(?:(?:p{N-1})|(?:[^{}]))*\}

  where N > 1 and
  p{1} = \{(?:[^{}])*\}

يمكن كتابة برنامج نصي لإنشاء هذه التعابير المنطقية بشكل متكرر، ولكن هذا خارج نطاق ما أحتاج إليه.(ويترك هذا كممارسة للقارئ.😉)

كما ذكر zsolt، تدعم بعض محركات regex التكرار - بالطبع، هذه هي عادةً تلك التي تستخدم خوارزمية التراجع، لذلك لن تكون فعالة بشكل خاص.مثال: /(?>[^{}]*){(?>[^{}]*)(?R)*(?>[^{}]*)}/sm

لا، أنت تدخل إلى عالم قواعد النحو الحرة السياق في تلك النقطة.

يبدو أن هذا يعمل: /(\{(?:\{.*\}|[^\{])*\})/m

مرخصة بموجب: CC-BY-SA مع الإسناد

لا تنتمي إلى StackOverflow