a ^ nb ^ n을 Java 정규식과 어떻게 일치시킬 수 있습니까?
이것은 교육용 정규식 기사 시리즈의 두 번째 부분입니다. 비정규 언어 a n b n 을 일치시키기 위해 미리보기 및 중첩 참조를 사용하는 방법을 보여줍니다 . 중첩 참조는 처음 도입되었습니다. 이 정규식은 삼각형 숫자를 어떻게 찾습니까?
전형적인 비정규 언어 중 하나 는 다음과 같습니다.
L = { anbn: n > 0 }
이것은 일부 수의 a's와 동일한 수의 b's 로 구성된 모든 비어 있지 않은 문자열의 언어입니다 . 이 언어에서 문자열의 예는 ab, aabb, aaabbb.
이 언어는 펌핑 기본형에 의해 비정규적인 것으로 보일 수 있습니다 . 사실 문맥 자유 문법에 의해 생성 될 수 있는 전형적인 문맥 자유 언어 입니다. S → aSb | ab
그럼에도 불구하고 현대의 정규식 구현은 일반 언어 이상의 것을 분명히 인식합니다. 즉, 공식 언어 이론 정의에 의해 "일반적"이지 않습니다. PCRE 및 Perl은 재귀 정규식을 지원하고 .NET은 균형 그룹 정의를 지원합니다. 예를 들어 역 참조 일치와 같은 덜 "멋진"기능은 정규식이 규칙적이지 않음을 의미합니다.
그러나이 "기본"기능이 얼마나 강력합니까? L예를 들어 Java 정규식으로 인식 할 수 있습니까 ? 우리는 아마도 lookarounds 및 중첩 된 참조를 결합하는 예와 작품을하는 패턴을 가질 수 String.matches와 같은 문자열을 일치하도록 ab, aabb, aaabbb, 등?
참고 문헌
- perlfaq6 : Perl 정규식을 사용하여 균형 잡힌 텍스트를 일치시킬 수 있습니까?
- MSDN-정규식 언어 요소-균형 그룹 정의
- pcre.org-PCRE 매뉴얼 페이지
- regular - expressions.info-찾아보기 및 그룹화 및 역 참조
java.util.regex.Pattern
연결된 질문
대답은 말할 필요도없이 YES입니다! n b n 과 일치 하는 Java 정규식 패턴을 가장 확실하게 작성할 수 있습니다 . 어설 션에는 긍정적 인 예견을 사용하고 "카운팅"에는 하나의 중첩 참조를 사용합니다.
이 답변은 즉시 패턴을 제공하는 대신 독자에게 패턴 을 유도 하는 과정 을 안내 합니다. 솔루션이 천천히 구성됨에 따라 다양한 힌트가 제공됩니다. 이 측면에서 바라건대이 답변은 다른 깔끔한 정규식 패턴 이상을 포함 할 것입니다. 독자들이 "정규식으로 생각"하는 방법과 다양한 구성을 조화롭게 조합하는 방법을 배우면 앞으로 스스로 더 많은 패턴을 도출 할 수 있기를 바랍니다.
솔루션 개발에 사용되는 언어는 간결함을 위해 PHP입니다. 패턴이 완성되면 최종 테스트는 Java로 수행됩니다.
1 단계 : 어설 션에 대한 예측
더 간단한 문제로 시작 해보자 : 우리 a+는 문자열의 시작 부분에서 일치 를 원 하지만 바로 뒤에 b+. 를 사용 ^하여 일치 항목 을 고정 할 수 있으며를 사용 a+하지 않고 일치하는 것만을 원하기 때문에 미리보기 어설 션을 b+사용할 수 있습니다 .(?=…)
다음은 간단한 테스트 도구를 사용한 패턴입니다.
function testAll($r, $tests) {
foreach ($tests as $test) {
$isMatch = preg_match($r, $test, $groups);
$groupsJoined = join('|', $groups);
print("$test $isMatch $groupsJoined\n");
}
}
$tests = array('aaa', 'aaab', 'aaaxb', 'xaaab', 'b', 'abbb');
$r1 = '/^a+(?=b+)/';
# └────┘
# lookahead
testAll($r1, $tests);
출력은 다음과 같습니다 ( ideone.com에 표시됨 ).
aaa 0
aaab 1 aaa
aaaxb 0
xaaab 0
b 0
abbb 1 a
이것은 정확히 우리가 원하는 출력 a+입니다. 문자열의 시작 부분에 있고 바로 뒤에 오는 경우에만 일치 합니다 b+.
Lesson : 어설 션을 만들기 위해 lookaround에서 패턴을 사용할 수 있습니다.
2 단계 : 미리보기 (및 자유 간격 모드)에서 캡처
이제 b+경기의 일부가되는 것을 원하지 않더라도 어쨌든 그룹 1로 캡처 하고 싶다고 가정 해 보겠습니다 . 또한 더 복잡한 패턴이있을 것으로 예상 되므로 자유 간격에x modifier를 사용 하겠습니다. 정규식을 더 읽기 쉽게 만들 수 있습니다.
이전 PHP 스 니펫을 기반으로 이제 다음과 같은 패턴이 있습니다.
$r2 = '/ ^ a+ (?= (b+) ) /x';
# │ └──┘ │
# │ 1 │
# └────────┘
# lookahead
testAll($r2, $tests);
이제 출력은 다음과 같습니다 ( ideone.com에 표시됨 ).
aaa 0
aaab 1 aaa|b
aaaxb 0
xaaab 0
b 0
abbb 1 a|bbb
예를 들어 각 그룹이으로 캡처 한 내용 aaa|b을 join-ing 한 결과입니다 '|'. 이 경우 그룹 0 (즉 aaa, 일치하는 패턴)이 캡처 되고 그룹 1이 캡처 b됩니다.
Lesson : 둘러보기 내부를 캡처 할 수 있습니다. 빈 공간을 사용하여 가독성을 높일 수 있습니다.
3 단계 : 미리보기를 "루프"로 리팩토링
카운팅 메커니즘을 도입하기 전에 패턴을 한 가지 수정해야합니다. 현재, 미리보기는 +반복 "루프" 밖에 있습니다. 이것은 우리가 우리의 b+뒤에 오는 것이 있다고 단언하고 싶었 기 때문에 지금까지는 괜찮습니다 a+. 그러나 우리가 정말로 하고 싶은 a것은 우리가 "루프"내부에서 일치 하는 각각에 대해 b그것에 상응하는 것이 있다고 주장하는 것입니다.
지금은 계산 메커니즘에 대해 걱정하지 말고 다음과 같이 리팩토링을 수행하십시오.
- 우선 팩터
a+에(?: a )+(주는(?:…)비 촬상 기) - 그런 다음이 비 캡처 그룹 내에서 예견을 이동합니다.
- 이제를 "보기"
a*전에 "건너 뛰기" 해야b+하므로 그에 따라 패턴을 수정해야합니다.
- 이제를 "보기"
이제 우리는 다음을 가지고 있습니다.
$r3 = '/ ^ (?: a (?= a* (b+) ) )+ /x';
# │ │ └──┘ │ │
# │ │ 1 │ │
# │ └───────────┘ │
# │ lookahead │
# └───────────────────┘
# non-capturing group
출력은 이전과 동일하므로 ( ideone.com에서 볼 수 있음 ) 이와 관련하여 변경 사항이 없습니다. 중요한 것은 이제 우리는 "루프" 의 모든 반복 에서 주장을하고 있다는 것입니다 +. 현재 패턴에서는 이것이 필요하지 않지만 다음으로 자기 참조를 사용하여 그룹 1을 "수"로 만들 것입니다.
Lesson : 비 캡처 그룹 내에서 캡쳐 할 수 있습니다. 둘러보기를 반복 할 수 있습니다.
4 단계 : 계산을 시작하는 단계입니다.
다음과 같이 할 것입니다. 그룹 1을 다음과 같이 다시 작성합니다.
- 의 첫 번째 반복이 끝날
+때 첫 번째 항목a이 일치하면 캡처해야합니다.b - 두 번째 반복이 끝날 때 다른 반복
a이 일치하면bb - 세 번째 반복이 끝나면 다음을 캡처해야합니다.
bbb - ...
- n 번째 반복 이 끝나면 그룹 1은 b n을 캡처해야합니다.
b그룹 1로 캡처 하기에 충분하지 않으면 어설 션이 실패합니다.
지금은 그룹 1, 그래서 (b+), 같은를 다시 작성해야합니다 (\1 b). 즉 b, 이전 반복에서 캡처 한 그룹 1에 a를 "추가"하려고합니다 .
여기에는이 패턴에 "기본 케이스"가 누락되어 있다는 점에서 약간의 문제가 있습니다. 즉, 자체 참조없이 일치 할 수있는 경우입니다. 그룹 1이 "초기화되지 않음"을 시작하기 때문에 기본 케이스가 필요합니다. 아직 아무것도 캡처하지 않았으므로 (빈 문자열조차도) 자체 참조 시도는 항상 실패합니다.
이이 주위에 많은 방법이 있지만, 지금의하자에 대한 바로 자기 참조 일치 할 옵션을 예 \1?. 이것은 완벽하게 작동 할 수도 있고 그렇지 않을 수도 있지만 그게 뭔지 보자. 문제가 있으면 그 다리를 건너 갈 것이다. 또한, 우리가 진행하는 동안 더 많은 테스트 케이스를 추가 할 것입니다.
$tests = array(
'aaa', 'aaab', 'aaaxb', 'xaaab', 'b', 'abbb', 'aabb', 'aaabbbbb', 'aaaaabbb'
);
$r4 = '/ ^ (?: a (?= a* (\1? b) ) )+ /x';
# │ │ └─────┘ | │
# │ │ 1 | │
# │ └──────────────┘ │
# │ lookahead │
# └──────────────────────┘
# non-capturing group
이제 출력은 다음과 같습니다 ( ideone.com에 표시됨 ).
aaa 0
aaab 1 aaa|b # (*gasp!*)
aaaxb 0
xaaab 0
b 0
abbb 1 a|b # yes!
aabb 1 aa|bb # YES!!
aaabbbbb 1 aaa|bbb # YESS!!!
aaaaabbb 1 aaaaa|bb # NOOOOOoooooo....
아하! 이제 솔루션에 정말 가까워진 것 같습니다! 우리는 자기 참조를 사용하여 그룹 1을 "계수"하도록 관리했습니다! 하지만 잠깐 ... 두 번째 및 마지막 테스트 케이스에 문제가 있습니다 !! bs 가 충분하지 않으며 어떻게 든 잘못 계산했습니다! 다음 단계에서 왜 이런 일이 발생했는지 살펴 보겠습니다.
Lesson : 자체 참조 그룹을 "초기화"하는 한 가지 방법은 자체 참조 일치를 선택 사항으로 만드는 것입니다.
4½ 단계 : 무엇이 잘못되었는지 이해
문제는 우리가 자기 참조 매칭을 선택적으로 만들었 기 때문에 "카운터"가 충분하지 않을 때 "재설정"할 수 있다는 것 b입니다. aaaaabbb입력으로 패턴을 반복 할 때마다 어떤 일이 발생하는지 자세히 살펴 보겠습니다 .
a a a a a b b b
↑
# Initial state: Group 1 is "uninitialized".
_
a a a a a b b b
↑
# 1st iteration: Group 1 couldn't match \1 since it was "uninitialized",
# so it matched and captured just b
___
a a a a a b b b
↑
# 2nd iteration: Group 1 matched \1b and captured bb
_____
a a a a a b b b
↑
# 3rd iteration: Group 1 matched \1b and captured bbb
_
a a a a a b b b
↑
# 4th iteration: Group 1 could still match \1, but not \1b,
# (!!!) so it matched and captured just b
___
a a a a a b b b
↑
# 5th iteration: Group 1 matched \1b and captured bb
#
# No more a, + "loop" terminates
A-ha! On our 4th iteration, we could still match \1, but we couldn't match \1b! Since we allow the self-reference matching to be optional with \1?, the engine backtracks and took the "no thanks" option, which then allows us to match and capture just b!
Do note, however, that except on the very first iteration, you could always match just the self-reference \1. This is obvious, of course, since it's what we just captured on our previous iteration, and in our setup we can always match it again (e.g. if we captured bbb last time, we're guaranteed that there will still be bbb, but there may or may not be bbbb this time).
Lesson: Beware of backtracking. The regex engine will do as much backtracking as you allow until the given pattern matches. This may impact performance (i.e. catastrophic backtracking) and/or correctness.
Step 5: Self-possession to the rescue!
The "fix" should now be obvious: combine optional repetition with possessive quantifier. That is, instead of simply ?, use ?+ instead (remember that a repetition that is quantified as possessive does not backtrack, even if such "cooperation" may result in a match of the overall pattern).
In very informal terms, this is what ?+, ? and ?? says:
?+
- (optional) "It doesn't have to be there,"
- (possessive) "but if it is there, you must take it and not let go!"
?
- (optional) "It doesn't have to be there,"
- (greedy) "but if it is you can take it for now,"
- (backtracking) "but you may be asked to let it go later!"
??
- (optional) "It doesn't have to be there,"
- (reluctant) "and even if it is you don't have to take it just yet,"
- (backtracking) "but you may be asked to take it later!"
In our setup, \1 will not be there the very first time, but it will always be there any time after that, and we always want to match it then. Thus, \1?+ would accomplish exactly what we want.
$r5 = '/ ^ (?: a (?= a* (\1?+ b) ) )+ /x';
# │ │ └──────┘ │ │
# │ │ 1 │ │
# │ └───────────────┘ │
# │ lookahead │
# └───────────────────────┘
# non-capturing group
Now the output is (as seen on ideone.com):
aaa 0
aaab 1 a|b # Yay! Fixed!
aaaxb 0
xaaab 0
b 0
abbb 1 a|b
aabb 1 aa|bb
aaabbbbb 1 aaa|bbb
aaaaabbb 1 aaa|bbb # Hurrahh!!!
Voilà!!! Problem solved!!! We are now counting properly, exactly the way we want it to!
Lesson: Learn the difference between greedy, reluctant, and possessive repetition. Optional-possessive can be a powerful combination.
Step 6: Finishing touches
So what we have right now is a pattern that matches a repeatedly, and for every a that was matched, there is a corresponding b captured in group 1. The + terminates when there are no more a, or if the assertion failed because there isn't a corresponding b for an a.
To finish the job, we simply need to append to our pattern \1 $. This is now a back reference to what group 1 matched, followed by the end of the line anchor. The anchor ensures that there aren't any extra b's in the string; in other words, that in fact we have anbn.
Here's the finalized pattern, with additional test cases, including one that's 10,000 characters long:
$tests = array(
'aaa', 'aaab', 'aaaxb', 'xaaab', 'b', 'abbb', 'aabb', 'aaabbbbb', 'aaaaabbb',
'', 'ab', 'abb', 'aab', 'aaaabb', 'aaabbb', 'bbbaaa', 'ababab', 'abc',
str_repeat('a', 5000).str_repeat('b', 5000)
);
$r6 = '/ ^ (?: a (?= a* (\1?+ b) ) )+ \1 $ /x';
# │ │ └──────┘ │ │
# │ │ 1 │ │
# │ └───────────────┘ │
# │ lookahead │
# └───────────────────────┘
# non-capturing group
It finds 4 matches: ab, aabb, aaabbb, and the a5000b5000. It takes only 0.06s to run on ideone.com.
Step 7: The Java test
So the pattern works in PHP, but the ultimate goal is to write a pattern that works in Java.
public static void main(String[] args) {
String aNbN = "(?x) (?: a (?= a* (\\1?+ b)) )+ \\1";
String[] tests = {
"", // false
"ab", // true
"abb", // false
"aab", // false
"aabb", // true
"abab", // false
"abc", // false
repeat('a', 5000) + repeat('b', 4999), // false
repeat('a', 5000) + repeat('b', 5000), // true
repeat('a', 5000) + repeat('b', 5001), // false
};
for (String test : tests) {
System.out.printf("[%s]%n %s%n%n", test, test.matches(aNbN));
}
}
static String repeat(char ch, int n) {
return new String(new char[n]).replace('\0', ch);
}
The pattern works as expected (as seen on ideone.com).
And now we come to the conclusion...
It needs to be said that the a* in the lookahead, and indeed the "main + loop", both permit backtracking. Readers are encouraged to confirm why this is not a problem in terms of correctness, and why at the same time making both possessive would also work (though perhaps mixing mandatory and non-mandatory possessive quantifier in the same pattern may lead to misperceptions).
It should also be said that while it's neat that there's a regex pattern that will match anbn, this is in not always the "best" solution in practice. A much better solution is to simply match ^(a+)(b+)$, and then compare the length of the strings captured by groups 1 and 2 in the hosting programming language.
In PHP, it may look something like this (as seen in ideone.com):
function is_anbn($s) {
return (preg_match('/^(a+)(b+)$/', $s, $groups)) &&
(strlen($groups[1]) == strlen($groups[2]));
}
The purpose of this article is NOT to convince readers that regex can do almost anything; it clearly can't, and even for the things it can do, at least partial delegation to the hosting language should be considered if it leads to a simpler solution.
As mentioned at the top, while this article is necessarily tagged [regex] for stackoverflow, it is perhaps about more than that. While certainly there's value in learning about assertions, nested references, possessive quantifier, etc, perhaps the bigger lesson here is the creative process by which one can try to solve problems, the determination and hard work that it often requires when you're subjected to various constraints, the systematic composition from various parts to build a working solution, etc.
Bonus material! PCRE recursive pattern!
Since we did bring up PHP, it needs to be said that PCRE supports recursive pattern and subroutines. Thus, following pattern works for preg_match (as seen on ideone.com):
$rRecursive = '/ ^ (a (?1)? b) $ /x';
Currently Java's regex does not support recursive pattern.
Even more bonus material! Matching anbncn !!
So we've seen how to match anbn which is non-regular, but still context-free, but can we also match anbncn, which isn't even context-free?
The answer is, of course, YES! Readers are encouraged to try to solve this on their own, but the solution is provided below (with implementation in Java on ideone.com).
^ (?: a (?= a* (\1?+ b) b* (\2?+ c) ) )+ \1 \2 $
Given that no mention has been made of PCRE supporting recursive patterns, I'd just like to point out the simplest and most efficient example of PCRE that describes the language in question:
/^(a(?1)?b)$/
As mentioned in the question — with .NET balancing group, the patterns of the type anbncndn…zn can be matched easily as
^
(?<A>a)+
(?<B-A>b)+ (?(A)(?!))
(?<C-B>c)+ (?(B)(?!))
...
(?<Z-Y>z)+ (?(Y)(?!))
$
For example: http://www.ideone.com/usuOE
Edit:
There is also a PCRE pattern for the generalized language with recursive pattern, but a lookahead is needed. I don't think this is a direct translation of the above.
^
(?=(a(?-1)?b)) a+
(?=(b(?-1)?c)) b+
...
(?=(x(?-1)?y)) x+
(y(?-1)?z)
$
For example: http://www.ideone.com/9gUwF
참고URL : https://stackoverflow.com/questions/3644266/how-can-we-match-an-bn-with-java-regex
'development' 카테고리의 다른 글
| 핸들 바에서 객체 배열을 반복하는 방법은 무엇입니까? (0) | 2020.08.28 |
|---|---|
| jQuery로 단어 강조 (0) | 2020.08.28 |
| Jackson을 사용하여 객체에 원시 JSON을 포함하려면 어떻게해야합니까? (0) | 2020.08.28 |
| CMake 출력 / 빌드 디렉토리 (0) | 2020.08.28 |
| Firestore 쿼리 하위 컬렉션 (0) | 2020.08.28 |