중첩 패턴과 일치하는 데 정규 표현식을 사용할 수 있습니까? [복제하다

StackOverflow https://stackoverflow.com/questions/133601

  •  02-07-2019
  •  | 
  •  

문제

이 질문은 이미 여기에 답이 있습니다.

알려지지 않은 숫자가 발생하는 중첩 패턴과 일치하는 정규 표현을 작성할 수 있습니까? 예를 들어, 외부 브레이스 내에 중첩 된 알 수없는 수의 개방/닫기 버팀대가있을 때 정규 표현식이 개구부 및 닫는 브레이스와 일치 할 수 있습니까?

예를 들어:

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

  // More { }
} // End

일치해야합니다 :

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

  // More { }
}
도움이 되었습니까?

해결책

아뇨. 쉽습니다. 유한 Automaton (정규 표현식의 기본 데이터 구조)은 상태와는 별도로 메모리가 없으며, 임의로 깊은 둥지가 있으면 임의로 큰 오토 마톤이 필요합니다. 한정된 오토 마톤.

자동화 된/페어링 된 요소를 고정 된 깊이까지 일치시킬 수 있습니다. 여기서 오토 마톤이 매우 커지기 때문에 깊이는 메모리에 의해서만 제한됩니다. 그러나 실제로 푸시 다운 오토 마톤 (예 : LL) 또는 LR (상향식)과 같은 컨텍스트가없는 문법에 대한 파서를 사용해야합니다. n = 길이 (입력)를 가진 O (n^3) vs. O (n)을 고려하여 더 나쁜 런타임 동작을 고려해야합니다.

예를 들어 많은 파서 생성기가 있습니다 antlr 자바를 위해. Java (또는 C)의 기존 문법을 찾는 것도 어렵지 않습니다.
더 많은 배경 : 오토마타 이론 Wikipedia에서

다른 팁

정규 표현식을 사용하여 중첩 패턴을 확인하는 것은 매우 쉽습니다.

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

문자열이 한 줄에있는 경우 작동하는 Perl 솔루션이 작동합니다.

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

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

HTH

편집하다: 확인하다:

그리고 한 가지 더 Torsten Marek (올바르게 지적한 사람은 더 이상 재 겔이 아니라는 것을 지적했습니다) :

예, .NET Regex-Engine 인 경우. .NET 엔진은 외부 스택과 함께 제공되는 유한 상태 기계를 지원합니다. 보다 세부

그만큼 일반 언어를위한 레마를 펌핑합니다 당신이 그렇게 할 수없는 이유입니다.

생성 된 오토마톤은 K+1의 열린 버팀대 (Opening Brace)가 어딘가에있는 상태를 반복해야한다 (k+1 개구부 브레이스)는 유한 한 수의 상태를 갖게 될 것이다 (오토 마톤이 문자를 처리함에 따라). 동일한 상태 사이의 문자열의 일부는 무한히 복제 될 수 있으며 오토 마톤은 그 차이를 알지 못할 것입니다.

특히, K+1 개구부 브레이스와 K+1의 닫는 버팀대를 허용하면 (해야하는지) 펌핑 된 개구부 버팀대와 변경되지 않은 K+1 닫는 브라스 (하지 않아야 함)를 허용합니다.

정기적 인 표현은 정기적 인 언어 영역을 컨텍스트 자유 언어 영토에 착륙시키기 때문에 그렇게 할 수 없습니다.

그럼에도 불구하고 많은 언어가 제공하는 "정규 표현"패키지는 엄격하게 강력합니다.

예를 들어, 루아 정규 표현에는 "%b()"균형 잡힌 괄호와 일치 할 인식 자. 귀하의 경우 사용할 것입니다."%b{}"

SED와 유사한 또 다른 정교한 도구 GEMA, 당신이 균형 잡힌 곱슬 괄호와 매우 쉽게 일치하는 곳 {#}.

따라서, 당신이 처분 할 수있는 도구에 따라 당신의 "정규 표현"(더 넓은 의미에서)은 중첩 된 괄호와 일치 할 수 있습니다.

PHP Regex 엔진에서 재귀 매칭을 사용하는 것은 괄호의 절차 적 일치보다 훨씬 빠릅니다. 특히 더 긴 줄로.

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

예를 들어

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

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

vs.

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;
}

예

... 기꺼이 멈출 수있는 최대 중첩 수가 있다고 가정합니다.

설명하겠습니다.

@torsten-marek 정규 표현이 이와 같은 중첩 패턴을 확인할 수 없다는 것이 옳습니다. 하지만 가능하다 정의하다 이와 같은 중첩 구조물을 캡처 할 수있는 중첩 된 정규 패턴 최대 깊이까지. 나는 캡처하기 위해 하나를 만들었습니다 EBNF 스타일 코멘트 (여기에서 시도해보십시오), 처럼:

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

Regex (단일 심도 주석)는 다음과 같습니다.

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

이것은 \(+\*+ 그리고 \*+\)+ ~와 함께 { 그리고 } 그리고 간단한 사이에 모든 것을 교체합니다 [^{}]:

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

(여기 링크가 있습니다 그것을 시도하려면.)

중첩하려면 블록 자체 내 에서이 패턴을 허용합니다.

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

트리플 뉴스 블록을 찾으려면 다음을 사용하십시오.

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

명확한 패턴이 나타났습니다. 깊이에 중첩 된 주석을 찾기 위해 N, 간단히 Regex를 사용하십시오 :

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

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

이 regexes를 재귀 적으로 생성하기 위해 스크립트를 작성할 수 있지만, 이것이 내가 필요한 범위를 벗어납니다. (이것은 독자를위한 운동으로 남아 있습니다. 😉)

Zsolt가 언급했듯이 일부 Regex 엔진은 재귀를 지원합니다. 물론,이 엔진은 일반적으로 역 추적 알고리즘을 사용하는 엔진이므로 특히 효율적이지 않습니다. 예시: /(?>[^{}]*){(?>[^{}]*)(?R)*(?>[^{}]*)}/sm

아니, 당신은 영역에 들어가고 있습니다 맥락이없는 문법 그 시점에서.

이것은 작동하는 것 같습니다 : /(\{(?:\{.*\}|[^\{])*\})/m

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top