Perl 정규표현식 엔진 파헤치기
Perl 정규표현식 엔진 파헤치기 (perlreguts)
이 문서는 정규식 엔진의 내부(guts)와 그것이 어떻게 동작하는지에 빛을 비추려는 시도예요. 정규식 엔진은 perl 코드베이스의 상당한 덩어리를 차지하지만, 상대적으로 잘 이해되지 못하고 있어요. 이 문서는 그 상황을 다루려는 소박한 시도예요. 저자의 경험, 소스 코드의 주석, 정규식 엔진에 대한 다른 논문들, perl5-porters 메일 목록의 피드백, 그리고 분명 다른 곳들에서도 파생됐어요.
본문
주의! 여기서 논의되는 동작과 구조는 이 문서를 쓸 때 저자가 이해한 엔진의 상태를 나타낸다는 점을 분명히 이해해야 해요. 이것은 API 정의가 아니고, 순수하게 정규식 엔진을 해킹하고 싶거나 정규식 엔진이 어떻게 동작하는지 이해하고 싶은 사람들을 위한 내부 가이드예요. 이 문서를 읽는 독자는 perl의 정규식 문법과 사용법을 자세히 이해하고 있다고 기대돼요. Perl 정규표현식의 기초를 배우고 싶다면 perlre를 보세요. 정규식 엔진을 자신의 것으로 교체하고 싶다면 perlreapi를 보세요.
개요 (OVERVIEW)
용어에 대한 짧은 참고 (A quick note on terms)
"regexp"라고 할지 "regex"라고 할지에 대해 약간의 논쟁이 있어요. 이 문서에서는 특별한 이유가 없는 한 "regex"라는 용어를 쓸게요. 특별한 이유가 있으면 그 이유를 설명할게요.
정규식에 대해 말할 때 우리는 그 소스 코드 형태와 내부 형태를 구분해야 해요. 이 문서에서는 텍스트·소스 코드 형태를 말할 때 "pattern(패턴)", 내부 표현을 말할 때 "program(프로그램)"이라는 용어를 쓸게요. 이것들은 Mark Jason Dominus가 "Rx"([1] in "REFERENCES")에 관한 논문에서 쓰는 S-regex 와 B-regex 용어에 해당해요.
정규표현식 엔진이란 무엇인가? (What is a regular expression engine?)
정규표현식 엔진은 미니 언어로 지정된 제약 집합을 받아 그 제약을 대상 문자열에 적용하고, 문자열이 그 제약을 만족하는지 결정하는 프로그램이에요. 언어의 완전한 정의는 perlre를 보세요.
덜 웅장하게 말하면, 일의 첫 부분은 패턴을 컴퓨터가 문자열에서 매치 지점을 효율적으로 찾는 데 쓸 수 있는 것으로 바꾸는 것이고, 두 번째 부분은 검색 자체를 수행하는 거예요.
이를 위해 텍스트를 파싱해 프로그램을 만들어야 해요. 그런 다음 프로그램을 실행해 문자열에서 매치되는 지점을 찾아야 해요. 그리고 그 전체를 효율적으로 해야 해요.
Regexp 프로그램의 구조 (Structure of a Regexp Program)
높은 수준 (High Level)
약간 혼란스럽고 일부 사람들은 그 용어에 반대하지만, regexp.h 에 수년간 있었던 주석을 살펴볼 가치가 있어요:
This is essentially a linear encoding of a nondeterministic finite-state machine (aka syntax charts or "railroad normal form" in parsing technology). (이것은 본질적으로 비결정적 유한 상태 머신의 선형 인코딩이다. 파싱 기술에서는 신택스 차트나 "railroad normal form"이라고도 한다.)
"railroad normal form"이라는 용어는 다소 난해하고, "syntax diagram/charts"나 "railroad diagram/charts"가 더 흔한 용어예요. 그럼에도 정규식 프로그램에 대한 유용한 심상(mental image)을 제공해요. 각 노드는 단일 진입점과 대부분의 경우 단일 탈출점을 가진 트랙 한 유닛으로 생각할 수 있어요(갈라지는 트랙 조각도 있지만 통계적으로 많지는 않아요), 그리고 전체는 단일 진입·단일 탈출점을 가진 배치를 형성해요. 매치 과정은 트랙을 따라 움직이는 자동차로 생각할 수 있는데, 시스템을 통한 특정 경로는 각 가능한 커넥터 지점에서 읽힌 문자에 의해 결정돼요. 자동차는 어느 지점에서든 트랙에서 떨어질 수 있지만, 트랙과 매치하는 한에서만 진행할 수 있어요.
그래서 패턴 /foo(?:\w+|\d+|\s+)bar/는 다음 차트로 생각할 수 있어요:
[start]
|
<foo>
|
+-----+-----+
| | |
<\w+> <\d+> <\s+>
| | |
+-----+-----+
|
<bar>
|
[end]
진실은 요즘 perl의 정규표현식이 이런 종류의 구조보다 훨씬 복잡하다는 거지만, 이런 식으로 시각화하면 방향을 잡을 때 도움이 될 수 있고, 현재 구현과 꽤 가깝게 맞아요.
더 정확히 말하면, 정규식 프로그램은 그래프의 인코딩이라고 할게요. 그래프의 각 노드는 원래 정규식 패턴의 일부(리터럴 문자열이나 브랜치 같은)에 해당하고, 다음에 매치될 컴포넌트를 나타내는 노드를 가리키는 포인터를 가져요. "node"와 "opcode"는 perl 소스에서 이미 다른 의미를 갖고 있으므로, 정규식 프로그램의 노드를 "regop"이라고 부를게요.
프로그램은 regnode 구조의 배열로 표현되는데, 그 중 하나 이상이 프로그램의 단일 regop을 나타내요. regnode 구조는 필요한 가장 작은 구조이고, 다른 모든 더 큰 구조와 공유되는 필드 구조를 가져요. (이 문서 밖에서 "regnode"라는 용어가 "regop"을 의미하는 데 쓰이기도 하는데, 혼란스러울 수 있어요.)
BRANCH를 제외한 모든 regop의 "next" 포인터는 연결(concatenation)을 구현해요. 양쪽 끝에 BRANCH가 있는 "next" 포인터는 두 대안을 연결해요. [여기에는 미묘한 문법 의존성이 하나 있어요. 연산자 우선순위 때문에 개별 BRANCH(모음과 반대로)는 어떤 것과도 결코 연결되지 않아요.]
일부 유형의 regop의 피연산자는 리터럴 문자열이고, 다른 것들은 하위 프로그램으로 이어지는 regop이에요. 특히 BRANCH 노드의 피연산자는 브랜치의 첫 번째 regop이에요.
참고: 철도 비유가 시사하듯, 이것은 트리 구조가 아니에요. 브랜치의 꼬리는 BRANCH 집합 다음에 오는 것에 연결돼요. 역(驛)이나 철도 야드로 들어가면서 갈라지고 반대쪽으로 나오면서 다시 합치는 단일 철도 선로와 같아요.
Regops
regop의 기본 구조는 regexp.h 에 다음과 같이 정의돼 있어요:
struct regnode {
U8 flags; /* Various purposes, sometimes overridden */
U8 type; /* Opcode value as specified by regnodes.h */
U16 next_off; /* Offset in size regnode */
};
다른 더 큰 regnode-유사 구조는 regcomp.h 에 정의돼 있어요. 그것들은 거의 하위 클래스 같아서 regnode와 같은 필드를 갖고, 구조에 추가 필드가 뒤따를 수 있으며, 어떤 경우에는 기본 필드 일부의 특정 의미(와 이름)가 재정의돼요. 다음은 더 완전한 설명이에요.
regnode_1, regnode_2
regnode_1 구조는 같은 헤더 다음에 단일 4바이트 인자를 갖고, regnode_2 구조는 대신 두 개의 2바이트 인자를 포함해요:
regnode_1 U32 arg1;
regnode_2 U16 arg1; U16 arg2;
regnode_string
리터럴 문자열에 쓰이는 regnode_string 구조는 헤더 다음에 1바이트 길이, 그다음 문자열 데이터를 가져요. 문자열은 노드의 총 길이가 4바이트의 배수가 되도록 끝에 0바이트로 패딩돼요:
regnode_string char string[1];
U8 str_len; /* overrides flags */
regnode_charclass
브래킷 문자 클래스는 regnode_charclass 구조로 표현되는데, 4바이트 인자 다음에 Latin1 범위에서 클래스에 포함된 문자를 나타내는 32바이트(256비트) 비트맵이 와요.
regnode_charclass U32 arg1;
char bitmap[ANYOF_BITMAP_SIZE];
이름이 ANYOF_로 시작하는 다양한 플래그가 특수 상황에 쓰여요. Latin1 위의 매치와 런타임까지 알 수 없는 것들은 "Perl's pprivate structure"에 저장돼요.
regnode_charclass_posixl
또한 /l 매치 아래에서 POSIX 문자 클래스를 나타내는 데 쓰이는 더 큰 형태의 문자 클래스 구조가 있어요. regnode_charclass_posixl이라고 하는데, 어떤 POSIX 문자 클래스가 포함됐는지 나타내는 추가 32비트 비트맵을 가져요.
regnode_charclass_posixl U32 arg1;
char bitmap[ANYOF_BITMAP_SIZE];
U32 classflags;
regnodes.h 는 PL_regnode_arg_len[]이라는 배열을 정의하는데, 각 opcode의 크기를 size regnode(4바이트) 단위로 줘요. 매크로는 EXACT 노드의 크기를 str_len 필드에 기반해 계산하는 데 쓰여요.
regop은 regcomp.sym 에서 regcomp.pl 이 생성하는 regnodes.h 에 정의돼 있어요. 현재 가능한 서로 다른 regop의 최대 수는 256으로 제한돼 있고, 약 1/4이 이미 사용됐어요.
필드에 접근을 더 쉽고 일관성 있게 만드는 매크로 집합이 있어요. regnode-유사 구조의 유형을 결정하는 OP(), 다음 노드로의 오프셋인 NEXT_OFF()(이건 나중에 더), ARG(), ARG1(), ARG2(), ARG_SET()과 인자를 읽고 설정하는 동등물, 문자열과 regop 보유 유형을 조작하는 STR_LEN(), STRING(), OPERAND()가 그것이에요.
다음 regnode는 무엇인가? (What regnode is next?)
정규식 엔진에는 "다음 regnode"라는 두 가지 서로 다른 개념이 있고, 많은 곳에서 개념적으로 겹치므로 머릿속에 구분해 두는 게 중요해요. 겹치지 않는 곳에서는 그 차이가 결정적이에요. 대부분의 regnode 유형에서 두 개념은 실무상 (거의) 동일해요. 두 유형은 컴파일 중에 많이 쓰이고 실행 중에는 가끔 쓰이는 REGNODE_AFTER와, 실행 중에 많이 쓰이고 컴파일 중에는 가끔 쓰이는 regnext예요.
"REGNODE_AFTER"
이것은 컴파일된 정규식 프로그램에서 "위치상 다음 regnode"예요. 더 작은 regnode 유형에서는 내부적으로 regnode_ptr+1이지만, regnode 크기가 다양하고 시간이 지나며 바뀔 수 있으므로 세부 사항을 숨기는 매크로를 제공해요.
컴파일러 단계에서 많이 쓰이지만 실행 단계에서는 몇 개의 선택된 regnode 유형만 써요. 정규식 프로그램을 디버깅용으로 덤프하는 코드에서도 많이 쓰여요.
상황에 따라 이것을 가능한 한 효율적으로 계산하는 데 쓸 수 있는 선택된 매크로가 있어요. 정식 매크로는 REGNODE_AFTER()인데, 가장 강력하고 우리가 가진 어떤 경우든 처리해야 하지만 잠재적으로 가장 느릴 수도 있어요. 현재 regnode 크기가 일정하다는 것을 알고 있고, 그 유형·opcode를 안다면 특수한 경우를 위한 추가 매크로 두 개가 있어요. 그 경우 REGNODE_AFTER_opcode() 또는 REGNODE_AFTER_type()을 쓸 수 있어요.
정규식 엔진의 옛 버전에서는 REGNODE_AFTER()가 NEXTOPER라고 불렸지만 혼란스럽다는 걸 발견해 이름이 바뀌었어요. REGNODE_BEFORE()도 있지만 안전하지 않아 새 코드에서는 쓰면 안 돼요.
"regnext"
이것은 regnode의 NEXT_OFF() 멤버 값만큼 앞으로 점프하거나, 몇몇 더 긴 점프의 경우 regnode_1 구조의 arg1 필드로 도달할 수 있는 regnode예요. regnext() 서브루틴이 이것을 투명하게 처리해요. 대부분의 경우 regnode의 regnext는 현재 것이 성공적으로 매치된 후 실행되어야 할 regnode지만, 어떤 경우에는 그렇지 않을 수 있어요. 루프 제어·브랜치 제어 regnode 유형에서 regnext는 특별한 것을 의미할 수 있어요. BRANCH 노드의 경우 regnext는 현재 것이 실행에 실패하면 실행되어야 할 다음 BRANCH이고, 일부 루프 제어 regnode는 현재 반복이 매치에 실패하면 정리로 점프할 수 있게 regnext를 루프의 끝으로 설정해요.
대부분의 regnode 유형은 실행 흐름에 브랜치를 만들지 않고, 최적화를 제외하면 "next"의 두 개념은 같아요. 예를 들어 SBOL opcode의 regnext와 REGNODE_AFTER는 컴파일 단계에서 같아요. 이것이 사실이 아닌 주요 장소는 BRANCH regnode로, 여기서 REGNODE_AFTER는 브랜치의 패턴 시작을, regnext는 이 것이 매치 실패 시 연결할 다음 BRANCH를(마지막 브랜치면 0) 나타내요. 수량자의 루프 논리도 두 유형의 구분을 비슷하게 활용하는데, REGNODE_AFTER가 루프 구조의 안쪽이고 regnext가 루프 끝을 가리켜요.
컴파일 중에 엔진은 주어진 노드의 regnext를 모를 수 있으므로, 컴파일 중 regnext는 반드시 쓰여야 하고 올바르다고 알려진 곳에서만 쓰여요. 컴파일 단계의 맨 끝에 정규식 프로그램을 걸으며 regnext 데이터를 적절히 수정하고, 또한 여러 최적화를 수행해요. 이 최적화는 구축 중에 필요했던 regnode가 중복이 되게 하거나, 큰 regnode를 훨씬 작은 것으로 바꾸고 그 틈을 OPTIMIZED regnode로 채울 수도 있어요. 그래서 이런 것에서 시작해서:
BRANCH
EXACT "foo"
BRANCH
EXACT "bar"
EXACT "!"
이런 것으로 교체할 수 있어요:
TRIE foo|bar
OPTIMIZED
OPTIMIZED
OPTIMIZED
EXACT "!"
TRIE 노드의 REGNODE_AFTER는 OPTIMIZED regnode이고, 이론상 regnext는 REGNODE_AFTER와 같을 거예요. 하지만 OPTIMIZED regnode를 noop으로 세 번 실행하는 건 비효율적이므로, 최적화기가 regnext를 고쳐 실행 단계에서 그런 노드가 건너뛰게 해요.
실행 단계에서는 거의 전적으로 regnext()를 쓰고, REGNODE_AFTER는 주어진 regnode 유형에 잘 정의된 의미를 갖는 특수한 경우에만 써요. 예를 들어 /x+/은 결과적으로:
PLUS
EXACT "x"
END
PLUS regnode의 regnext는 END regnode이고, PLUS regnode의 REGNODE_AFTER는 EXACT regnode예요. EXACT regnode의 regnext와 REGNODE_AFTER는 END regnode예요.
프로세스 개요 (Process Overview)
대략적으로 말해, 문자열을 패턴에 대해 매치하는 것은 다음 단계를 포함해요:
- A. 컴파일(Compilation)
-
- 파싱(Parsing)
-
- Peep-hole 최적화와 분석(Peep-hole optimisation and analysis)
-
- B. 실행(Execution)
-
- 시작 위치와 무-매치 최적화(Start position and no-match optimisations)
-
- 프로그램 실행(Program execution)
-
이 단계들이 실제 perl 프로그램 실행에서 어디서 일어나는지는 패턴이 어떤 문자열 변수를 보간(interpolate)하는지에 따라 결정돼요. 보간이 일어나면 컴파일은 런타임에 일어나요. 그렇지 않으면 컴파일은 컴파일 타임에 수행돼요. (/o 수정자가 이것을 바꾸고, qr//도 어느 정도 바꿔요.) 엔진은 그다지 신경 쓰지 않아요.
컴파일 (Compilation)
이 코드는 주로 regcomp.c 에, 헤더 파일 regcomp.h , regexp.h , regnodes.h 와 함께 상주해요.
컴파일은 pregcomp()로 시작하는데, 대부분 초기화 래퍼로, 무거운 일을 위해 두 개의 다른 루틴으로 작업을 나눠줘요. 첫 번째는 파싱의 시작점인 reg(), 두 번째는 최적화를 담당하는 study_chunk()예요.
pregcomp()의 초기화는 대부분 특수 구조 RExC_state_t(regcomp.c 에 정의)의 생성과 데이터 채우기를 포함해요. regcomp.h 의 거의 모든 내부 사용 루틴은 이 구조 중 하나에 대한 포인터를 첫 번째 인자로 받는데, 이름은 pRExC_state예요. 이 구조는 컴파일 상태를 저장하는 데 쓰이고 많은 필드를 포함해요. 이 변수에 대해 동작하는 매크로도 많아요. RExC_xxxx처럼 보이는 것은 이 포인터/구조에 대해 동작하는 매크로예요.
reg()는 파싱 프로세스의 시작이에요. 문자열 끝이나 패턴에서 만난 첫 번째 닫는 괄호까지 임의의 패턴 덩어리를 파싱하는 책임이 있어요. 이것은 최상위 정규식이나 그룹 괄호 안의 어떤 섹션이든 파싱할 수 있음을 의미해요. 또한 perl 정규식이 가진 "특수 괄호"도 처리해요. 예를 들어 /x(?:foo)y/를 파싱할 때 reg()는 어떤 지점에서 "?" 기호부터 ")"를 포함해 그까지 파싱하도록 호출될 거예요.
추가로 reg()는 패턴에서 하나 이상의 브랜치를 파싱하고, next 포인터를 올바르게 설정해 "마무리"하는 책임이 있어요. 파싱을 위해 반복적으로 regbranch()를 호출하는데, 이것은 만나는 첫 번째 | 기호까지 처리하는 책임이 있어요.
regbranch()는 차례로 수량자가 뒤따르는 "것들(things)"을 처리하는 regpiece()를 호출해요. "것들"을 파싱하기 위해 regatom()이 호출돼요. 이것은 상수 문자열, 문자 클래스, $ 같은 다양한 특수 기호를 파싱하는 가장 낮은 레벨의 루틴이에요. regatom()이 "(" 문자를 만나면 차례로 reg()를 호출해요.
파싱에 관여하는 두 개의 주요 패스가 예전엔 있었는데, 첫 번째는 컴파일된 프로그램의 크기를 계산하고, 두 번째는 실제로 컴파일했어요. 하지만 이제는 단일 주요 패스만 있고, 입력 패턴 길이에 기반한 초기 대략 추정으로 시작해 파싱이 진행되면서 필요하면 늘리고, 그 후에 실제 사용량으로 정리해요.
하지만 파싱이 도중에 다양한 상황이 발생하면 처음부터 다시 시작해야 할 수 있어요. 예를 들어 프로그램이 너무 커서 점프가 정상 16비트에 맞지 않게 됐을 때예요. 더 큰 점프 대상을 담을 수 있는 특수 regop 두 개, BRANCHJ와 LONGBRANCH가 있어요. 파싱이 재시작되고, 정상적이고 더 짧은 것 대신 이것들이 사용돼요. 파싱 재시작이 필요할 때마다 함수는 실패를 반환하고 무엇을 해야 하는지 플래그를 설정해요. 이것은 적절한 조치를 취하고 처음부터 다시 시작하는 최상위 루틴으로 전달돼요. 더 긴 점프가 필요하면 브랜치를 어떻게 할지 결정하기 전에 함수들이 검사한다는 것을 아는 RExC_state_t 구조에 RExC_use_BRANCHJ 플래그가 설정돼요.
대부분의 경우 문제를 발견한 함수가 인과 플래그를 설정하고 즉시 실패를 반환해요. "Parsing complications"에는 이것이 어떻게 동작하는지의 명시적 예시가 있어요. 번호가 매겨진 괄호 그룹에 대한 전방 참조 같은 다른 경우에는, 그 번호가 매겨진 그룹이 패턴에 실제로 나타나는지 알려면 파싱을 끝내야 해요. 그런 경우 파싱은 그 안에 얼마나 많은 그룹이 있는지 아는 상태로 끝에서 그냥 다시 수행돼요.
regtail() 루틴은 "꼬리 포인터(tail pointer)"를 올바르게 설정하기 위해 reg()와 regbranch() 둘 다에서 호출돼요. 실행할 때 브랜치 끝에 도달하면 그룹 괄호 다음의 노드로 가야 해요. 하지만 파싱할 때는 거기 도달할 때까지 끝이 어디인지 모르므로, 도달했을 때 돌아가 오프셋을 적절히 업데이트해야 해요. regtail은 이것을 쉽게 하기 위해 쓰여요.
파싱 프로세스의 미묘함 때문에 /foo/ 같은 정규식은 원래 단일 브랜치를 가진 교체(alternation)로 파싱돼요. 그 후에야 최적화기가 단일 브랜치 교체를 더 단순한 형태로 변환해요.
파싱 호출 그래프와 문법 (Parse Call Graph and a Grammar)
호출 그래프는 이렇게 생겼어요:
reg() # parse a top level regex, or inside of
# parens
regbranch() # parse a single branch of an alternation
regpiece() # parse a pattern followed by a quantifier
regatom() # parse a simple pattern
regclass() # used to handle a class
reg() # used to handle a parenthesised
# subpattern
....
...
regtail() # finish off the branch
...
regtail() # finish off the branch sequence. Tie each
# branch's tail to the tail of the
# sequence
# (NEW) In Debug mode this is
# regtail_study().
문법 형태는 이럴 수 있어요:
atom : constant | class
quant : '*' | '+' | '?' | '{min,max}'
_branch: piece
| piece _branch
| nothing
branch: _branch
| _branch '|' branch
group : '(' branch ')'
_piece: atom | group
piece : _piece
| _piece quant
파싱 합병증 (Parsing complications)
위 설명이 함의하는 것은 중첩 괄호를 포함한 패턴은 reg(), regbranch(), regpiece(), regatom(), reg(), regbranch() 등 을 가장 깊은 중첩 레벨에 도달할 때까지 여러 번 순환하는 호출 그래프를 낳는다는 거예요. 위의 모든 루틴은 보통 프로그램에 추가된 마지막 regnode인 regnode 포인터를 반환해요. 하지만 한 가지 합병증은 reg()가 내장 수정자를 위한 (?:) 문법을 파싱할 때 NULL을 반환해 TRYAGAIN 플래그를 설정한다는 거예요. TRYAGAIN은 어떤 경우 regatom()이, 그 외에는 무조건 regbranch()가 잡을 때까지 위로 전파돼요. 그래서 regbranch()가 reg()에 그것을 절대 반환하지 않을 거예요. 이 플래그는 (?i)+ 같은 패턴이 오류로 탐지되게 해요(Quantifier follows nothing in regex; marked by <-- HERE in m/(?i)+ <-- HERE /).
또 다른 합병증은 프로그램에 쓰이는 표현이 Unicode를 저장해야 하는지에 따라 달라진다는 거예요. 하지만 그것이 필요한지 확실히 아는 게 항상 가능한 건 아니고, 파싱 도중에만 알 수 있어요. 프로그램의 Unicode 표현은 더 크고, 그렇게 효율적으로 매치될 수 없어요. (왜 그런지 더 자세한 내용은 아래 "Unicode and Localisation Support"를 보세요.) 패턴에 리터럴 Unicode가 포함돼 있으면 프로그램이 Unicode를 저장해야 하는 건 명백해요. 그렇지 않으면 파서는 더 효율적인 표현을 쓸 수 있다고 낙관적으로 가정하고, 이 기준으로 크기를 매기기 시작해요. 하지만 그 후 문자 리터럴을 나타내는 \x{...} 이스케이프 시퀀스처럼 Unicode로 저장해야 하는 것을 패턴에서 만나면, 이전에 계산된 모든 크기를 Unicode 표현에 적합한 값으로 다시 해야 한다는 뜻이에요. 이것은 파싱을 다시 시작해야 하는 또 다른 예시이고, 가능하고 즉시 수행돼요. 함수는 실패를 반환하고 RESTART_UTF8 플래그(REQUIRE_UTF8 매크로로 캡슐화)를 설정해요. 이 재시작 요청은 Perl_re_op_compile()에서 "잡힐" 때까지 호출 체인을 따라 비슷한 방식으로 전파되는데, 거기서 패턴에 Unicode가 포함됨을 표시하고 크기 조정 패스를 다시 시작해요. 또한 런타임 코드 블록 내의 구조가 Unicode 표현을 필요로 하는 것으로 판명될 수도 있는데, S_compile_runtime_code()가 Perl_re_op_compile()에 false를 반환해 신호를 보내요.
재시작은 이전에 regatom()의 longjmp가 Perl_re_op_compile()의 setjmp로 돌아가는 방식으로 구현됐지만, 후자가 많은 자동 변수를 포함한 큰 함수여서 setjmp의 발현적 제어 흐름과 나쁘게 상호작용해 문제가 되는 것으로 드러났어요.
디버그 출력 (Debug Output)
perl 5.9.x 개발 버전부터 use re Debug => 'PARSE'로 파싱 과정에 대한 추적 정보를 볼 수 있어요. 몇 가지 단순한 패턴으로 시작해 더 복잡한 패턴으로 만들어 볼게요.
/foo/를 파싱하면 다음과 같은 표가 보여요. 왼쪽은 무엇이 파싱되는지, 숫자는 다음 regop이 갈 곳을 나타내요. 오른쪽은 그래프의 추적 출력이에요. 이름들은 화면을 덜 빽빽하게 만들기 위해 짧게 고른 거예요. 'tsdy'는 추가 분석을 하는 regtail()의 특수 형태예요.
>foo< 1 reg
brnc
piec
atom
>< 4 tsdy~ EXACT <foo> (EXACT) (1)
~ attach to END (3) offset to 2
결과 프로그램은 이렇게 생겼어요:
1: EXACT <foo>(3)
3: END(0)
보시다시피, 브랜치와 piece를 파싱했지만 결국 atom 하나였어요. 최종 프로그램이 어떻게 동작하는지 보여줘요. EXACT regop 다음에 END regop이 있어요. 괄호 안의 숫자는 노드의 regnext가 가는 곳을 나타내요. END regop의 regnext는 사용되지 않는데, END regop은 성공적으로 매치했음을 의미하거든요. 왼쪽 숫자는 regnode 배열에서 regop의 위치를 나타내요.
이제 더 어려운 패턴을 시도할게요. 수량자를 추가해서 이제 패턴은 /foo+/예요. regbranch()가 regpiece()를 두 번 호출하는 걸 볼 수 있어요.
>foo+< 1 reg
brnc
piec
atom
>o+< 3 piec
atom
>< 6 tail~ EXACT <fo> (1)
7 tsdy~ EXACT <fo> (EXACT) (1)
~ PLUS (END) (3)
~ attach to END (6) offset to 3
그리고 프로그램으로 끝나요:
1: EXACT <fo>(3)
3: PLUS(6)
4: EXACT <o>(0)
6: END(0)
이제 특수한 경우가 있어요. EXACT regop의 regnext는 0이에요. 매치되면 자기 자신을 다시 매치해야 하기 때문이에요. PLUS regop은 EXACT regop의 실제 실패를 처리하고 적절히 행동해요(EXACT가 한 번 이상 매치했으면 regnode 6으로 가고, 그렇지 않으면 실패).
이제 훨씬 더 복잡한 것: /x(?:foo*|b[a][rR])(foo|bar)$/
>x(?:foo*|b... 1 reg
brnc
piec
atom
>(?:foo*|b[... 3 piec
atom
>?:foo*|b[a... reg
>foo*|b[a][... brnc
piec
atom
>o*|b[a][rR... 5 piec
atom
>|b[a][rR])... 8 tail~ EXACT <fo> (3)
>b[a][rR])(... 9 brnc
10 piec
atom
>[a][rR])(f... 12 piec
atom
>a][rR])(fo... clas
>[rR])(foo|... 14 tail~ EXACT <b> (10)
piec
atom
>rR])(foo|b... clas
>)(foo|bar)... 25 tail~ EXACT <a> (12)
tail~ BRANCH (3)
26 tsdy~ BRANCH (END) (9)
~ attach to TAIL (25) offset to 16
tsdy~ EXACT <fo> (EXACT) (4)
~ STAR (END) (6)
~ attach to TAIL (25) offset to 19
tsdy~ EXACT <b> (EXACT) (10)
~ EXACT <a> (EXACT) (12)
~ ANYOF[Rr] (END) (14)
~ attach to TAIL (25) offset to 11
>(foo|bar)$< tail~ EXACT <x> (1)
piec
atom
>foo|bar)$< reg
28 brnc
piec
atom
>|bar)$< 31 tail~ OPEN1 (26)
>bar)$< brnc
32 piec
atom
>)$< 34 tail~ BRANCH (28)
36 tsdy~ BRANCH (END) (31)
~ attach to CLOSE1 (34) offset to 3
tsdy~ EXACT <foo> (EXACT) (29)
~ attach to CLOSE1 (34) offset to 5
tsdy~ EXACT <bar> (EXACT) (32)
~ attach to CLOSE1 (34) offset to 2
>$< tail~ BRANCH (3)
~ BRANCH (9)
~ TAIL (25)
piec
atom
>< 37 tail~ OPEN1 (26)
~ BRANCH (28)
~ BRANCH (31)
~ CLOSE1 (34)
38 tsdy~ EXACT <x> (EXACT) (1)
~ BRANCH (END) (3)
~ BRANCH (END) (9)
~ TAIL (END) (25)
~ OPEN1 (END) (26)
~ BRANCH (END) (28)
~ BRANCH (END) (31)
~ CLOSE1 (END) (34)
~ EOL (END) (36)
~ attach to END (37) offset to 1
프로그램으로 끝나요:
1: EXACT <x>(3)
3: BRANCH(9)
4: EXACT <fo>(6)
6: STAR(26)
7: EXACT <o>(0)
9: BRANCH(25)
10: EXACT <ba>(14)
12: OPTIMIZED (2 nodes)
14: ANYOF[Rr](26)
25: TAIL(26)
26: OPEN1(28)
28: TRIE-EXACT(34)
[StS:1 Wds:2 Cs:6 Uq:5 #Sts:7 Mn:3 Mx:3 Stcls:bf]
<foo>
<bar>
30: OPTIMIZED (4 nodes)
34: CLOSE1(36)
36: EOL(37)
37: END(0)
여기서 다양한 최적화가 작동 중인 훨씬 더 복잡한 프로그램을 볼 수 있어요. regnode 10에서 하나의 문자만 있는 문자 클래스가 EXACT 노드로 바뀐 예시를 볼 수 있어요. 전체 교체가 TRIE-EXACT 노드로 바뀐 것도 볼 수 있어요. 결과적으로 일부 regnode는 최적화되어 제거된 것으로 표시됐어요. $ 기호가 EOL regop으로 변환된 걸 볼 수 있는데, \n이나 문자열 끝을 찾는 특수 코드 조각이에요.
BRANCH의 next 포인터는 브랜치가 실패하면 실행이 가야 할 곳을 가리킨다는 점에서 흥미로워요. 실행할 때 엔진이 브랜치에서 브랜치가 아닌 regnext로 횡단하려고 하면, 엔진은 전체 브랜치 집합이 실패했음을 알게 돼요.
Peep-hole 최적화와 분석 (Peep-hole Optimisation and Analysis)
정규표현식 엔진은 다루기 무거운 도구일 수 있어요. 긴 문자열과 복잡한 패턴에서는 매치를 찾으려고 많은 일을 해야 하고, 매치가 불가능하다고 결정하는 데는 더 많은 일을 해야 해요. 다음 패턴 같은 상황을 생각해 보세요.
'ababababababababababab' =~ /(a|b)*z/
(a|b)* 부분은 문자열의 매 문자에서 매치할 수 있고, 문자열에 z가 없으므로 매번 실패해요. 그래서 분명히 문자열에 z가 없으면 정규식 엔진 사용을 피할 수 있어요. 마찬가지로 이런 패턴에서:
/foo(\w+)bar/
이 경우 문자열이 foo를 포함하고 그 다음에 bar가 와야 한다는 걸 알아요. fbm_instr()에 구현된 Fast Boyer-Moore 매칭을 사용해 이 문자열들의 위치를 찾을 수 있어요. 그것들이 존재하지 않으면 훨씬 더 비싼 정규식 엔진에 의존할 필요가 없어요. 더 좋게는, 존재한다면 그 위치를 사용해 전체 패턴이 매치되는지 결정하기 위해 정규식 엔진이 커버해야 할 검색 공간을 줄일 수 있어요.
이런 방향으로 최적화를 촉진하는 데 쓸 수 있는 패턴의 다양한 측면이 있어요:
- 고정 문자열 앵커(anchored fixed strings)
- 부동 고정 문자열(floating fixed strings)
- 최소·최대 길이 요구사항
- 시작 클래스(start class)
- 줄 시작/끝 위치(Beginning/End of line positions)
발생할 수 있는 또 다른 형태의 최적화는 파싱 후 "peep-hole" 최적화로, 비효율적 구조를 더 효율적인 구조로 교체해요. 파싱 중에 브랜치 끝과 그룹 끝을 표시하는 TAIL regop이 이 예시예요. 이 regop은 구축 중 자리 표시자로 쓰이고 "항상 매치"하므로, TAIL을 가리키는 것들이 TAIL이 가리키는 것을 가리키게 만들어 "건너뛸" 수 있어 노드를 "최적화 제거"할 수 있어요.
발생할 수 있는 또 다른 최적화는 "EXACT 병합"으로, 두 개의 연속 EXACT 노드가 단일 regop으로 병합되는 거예요. 더 공격적인 형태는 EXACT BRANCH ... EXACT 형태의 브랜치 시퀀스가 TRIE-EXACT regop으로 변환될 수 있다는 거예요.
이 모든 것은 study_chunk() 루틴에서 발생하는데, 특수 구조 scan_data_t로 수행한 분석을 저장하고 진행하면서 "peep-hole" 최적화를 해요.
study_chunk()에 관여하는 코드는 극도로 난해해요. 조심하세요. :-)
실행 (Execution)
정규식 실행은 일반적으로 두 단계를 포함해요. 첫 번째는 문자열에서 매치해야 할 시작 지점을 찾는 것이고, 두 번째는 regop 인터프리터를 실행하는 거예요.
유효한 시작 지점이 없다는 것을 알 수 있으면 인터프리터를 아예 실행하지 않아요. 마찬가지로 분석 단계에서 시작 위치로의 지름길을 감지할 수 없다는 걸 안다면, 바로 인터프리터로 가요.
두 진입점은 re_intuit_start()와 pregexec()예요. 이 루틴들은 기능이 겹쳐 다소 근친 관계를 갖고 있고, pregexec()는 스스로 re_intuit_start()를 호출할 수도 있어요. 그럼에도 perl 소스 코드의 다른 부분은 둘 중 하나 또는 둘 다를 호출할 수 있어요.
인터프리터 실행 자체는 예전에는 재귀적이었지만, 5.9.x 개발 트랙에서 Dave Mitchell의 노력 덕분에 바뀌었어요. 이제 내부 스택이 힙에 유지되고 루틴은 완전히 반복적이에요. 이것은 코드가 어떤 상태를 저장하는지에 대해 꽤 보수적이라 까다로울 수 있는데, 결과적으로 코드의 두 연속 줄이 시뮬레이션된 재귀로 인해 완전히 다른 문맥에서 실제로 실행될 수 있어요.
시작 위치와 무-매치 최적화 (Start position and no-match optimisations)
re_intuit_start()는 study_chunk()가 수행한 분석 결과(그리고 "Peep-hole Optimisation and Analysis"에서 설명된)에 의해 결정된 시작 지점과 무-매치 최적화를 처리하는 책임이 있어요.
이 루틴의 기본 구조는 패턴이 매치할 수 있는 시작·끝 지점을 찾으려 하고, 문자열이 패턴을 매치하기에 충분히 긴지 확인하려고 해요. 덜 효율적인 방법보다 더 효율적인 방법을 쓰려 하고, 문자열에서 매치되는 곳을 찾기 위해 제약을 상당히 교차 검증할 수 있어요. 예를 들어 주어진 고정 문자열이 존재할 뿐만 아니라 문자열 끝에서 특정 문자 수만큼 앞에 있어야 한다는 걸 결정하려 할 수 있어요.
여러 다른 루틴을 호출하는데, Fast Boyer Moore 매칭을 하는 fbm_instr()과 프로그램에서 첫 번째 필수 regop을 사용해 시작을 찾는 책임인 find_byclass() 같은 것들이에요.
최적화 기준이 충족되면 reg_try()가 호출되어 매치를 수행해요.
프로그램 실행 (Program execution)
pregexec()는 정규식을 실행하는 주 진입점이에요. 정규식 인터프리터 상태 초기화 지원, 필요시 re_intuit_start() 실행, 필요에 따라 문자열의 다양한 시작 위치에서 인터프리터 실행을 포함해요. 정규식 인터프리터를 사용할 필요가 있을 때 pregexec()는 regtry()를 호출해요.
regtry()는 정규식 인터프리터로의 진입점이에요. 인자로 regmatch_info 구조 포인터와 문자열 포인터를 기대해요. 성공 시 정수 1, 실패 시 0을 반환해요. 기본적으로 regmatch() 주위의 설정(set-up) 래퍼예요.
regmatch는 인터프리터의 주요 "재귀 루프"예요. 기본적으로 상태 머신을 구현하는 거대한 switch 문인데, 가능한 상태는 regop 자체와 더불어 여러 추가 중간·실패 상태예요. 상태 중 몇 개는 서브루틴으로 구현되지만 대부분은 인라인 코드예요.
기타 (MISCELLANEOUS)
Unicode와 지역화 지원 (Unicode and Localisation Support)
8비트 문자 집합으로 나타낼 수 없는 문자를 포함한 문자열을 다룰 때 perl은 Unicode의 UTF-8 인코딩의 관대한 버전인 내부 표현을 써요[2]. 이것은 ASCII 문자 집합의 문자를 나타내는 데 단일 바이트를, 다른 모든 문자에는 두 개 이상의 바이트 시퀀스를 써요. (UTF-8과 perl의 인코딩 utf8의 관계에 대한 더 많은 정보는 perlunitut를 보세요. 그 차이는 이 논의에서 중요하지 않아요.)
어떻게 보든 Unicode 지원은 정규식 엔진에서 골칫거리가 될 거예요. 256개의 가능한 문자가 있을 때 괜찮은 트릭은 UTF-8 문자 집합의 크기를 처리하도록 확장되지 않는 경우가 많아요. ASCII에서 당연하게 여길 수 있는 것들이 Unicode에서는 사실이 아닐 수 있어요. 예를 들어 ASCII에서는 sizeof(char1) == sizeof(char2)라고 가정하는 게 안전하지만, UTF-8에서는 그렇지 않아요. Unicode case folding은 ASCII의 단순 규칙보다 훨씬 복잡하고, Unicode를 쓰지 않고 지역화된 단일 바이트 인코딩만 쓸 때도 까다로울 수 있어요(예: LATIN SMALL LETTER SHARP S(U+00DF, ß)는 지역화된 대소문자 구분 없는 매치에서 'SS'와 매치해야 해요).
더 나쁘게 하려고, UTF-8 지원은 정규식 엔진에 (perl에도 그랬듯) 늦게 추가됐고, 이것은 필연적으로 많은 것을 훨씬 더 복잡하게 만들었어요. 처음부터 Unicode 지원을 염두에 두고 정규식 엔진을 설계하는 것이 그렇지 않은 것에 개조하는 것보다 쉬운 건 분명해요.
입력 문자열을 보는 것과 관련된 거의 모든 regop에는 두 가지 경우가 있어요. UTF-8용과 아닌 것용이요. 사실 패턴도 UTF-8일 수 있어서, 종종 그것보다 더 복잡해요.
문자열과 패턴이 불일치할 때를 포함해 컴파일 타임과 실행 타임 모두에서 UTF-8을 제대로 처리하도록 변경할 때 주의를 기울여야 해요.
기본 구조 (Base Structures)
perlreapi에 설명된 regexp 구조는 모든 정규식 엔진에 공통이에요. 그 필드 중 두 개는 패턴을 컴파일한 정규식 엔진의 개인적 사용을 위한 것이에요. 그것들은 intflags와 pprivate 멤버예요. pprivate는 임의 구조에 대한 void 포인터로, 그 사용과 관리는 컴파일 엔진의 책임이에요. perl은 이 두 값 중 어느 것도 절대 수정하지 않아요. 기본 엔진의 경우 pprivate가 가리키는 구조는 regexp_internal이라고 불러요.
그 pprivate와 intflags 필드는 각 엔진에 특정한 데이터를 담아요.
컴파일된 정규식을 저장하는 데 쓰이는 두 구조가 있어요. 하나는 perlreapi에 설명된 regexp 구조로, 현재 사용 중인 엔진이 채우고 일부 필드는 qr//의 문자열화 같은 것을 구현하기 위해 perl이 읽어요.
다른 구조는 regexp 구조의 pprivate가 가리키는 것인데, 같은 구조의 intflags와 더불어 정규식을 컴파일한 정규식 엔진의 속성으로 간주돼요.
regexp 구조는 perl이 정규식과 제대로 동작하기 위해 알아야 할 모든 데이터를 포함해요. perl이 정규식 엔진을 정말 써야 하는지 결정하는 데 쓸 수 있는 최적화에 대한 데이터와, 여러 문맥에서 패턴을 제대로 실행하는 데 필요한 다양한 제어 정보(패턴이 어떤 식으로든 앵커됐는지, 컴파일 중 어떤 플래그가 쓰였는지, 프로그램이 perl이 알아야 할 특수 구조를 포함하는지 같은)를 포함해요.
추가로 패턴을 컴파일한 정규식 엔진의 개인적 사용을 위한 두 필드를 포함해요. 이들은 intflags와 pprivate 멤버예요. pprivate는 사용·관리가 컴파일 엔진의 책임인 임의 구조에 대한 void 포인터예요. perl은 이 두 값 중 어느 것도 절대 수정하지 않아요.
앞서 언급했듯, 기본 엔진의 경우 pprivate는 컴파일된 프로그램과 정규식 엔진 구현에 개인적인 추가 데이터를 보유한 regexp_internal 구조에 대한 포인터일 거예요.
Perl의 pprivate 구조 (Perl's pprivate structure)
다음 구조는 perl의 정규식 엔진이 pprivate 구조로 사용해요. perl에 특정하므로 다른 엔진 구현에는 단지 호기심 가치만 있어요.
typedef struct regexp_internal {
regnode *regstclass;
struct reg_data *data;
struct reg_code_blocks *code_blocks;
U32 proglen;
U32 name_list_idx;
regnode program[1];
} regexp_internal;
속성 설명은 다음과 같아요.
regstclass
re_intuit_start()가 패턴이 특정 위치에서 매치할 수 있는지 확인하는 데 쓰는 특수 regop이에요. 예를 들어 정규식 엔진이 패턴이 'Z'로 시작해야 한다는 걸 안다면, 하나를 찾을 때까지 문자열을 스캔한 다음 거기서 정규식 엔진을 시작할 수 있어요. 이것을 처리하는 루틴은 find_by_class()라고 불러요. 때로 이 필드는 프로그램에 포함된 regop을 가리키고, 때로 최적화기가 구축한 독립적인 합성 regop을 가리켜요.
data
이 필드는 다음과 같이 정의된 reg_data 구조를 가리켜요:
struct reg_data {
U32 count;
U8 *what;
void* data[1];
};
이 구조는 정규식 엔진이 컴파일된 결과물에 대한 clone이나 free 연산 중에 특별히 처리해야 하는 데이터 구조를 다루는 데 쓰여요. data 배열의 각 요소는 what 배열에 대응 요소가 있어요. 컴파일 중 특수 구조를 저장해야 하는 regop은 add_data() 루틴으로 각 배열에 요소를 추가한 다음 그 인덱스를 regop에 저장해요.
현대 perl에서 이 구조의 0번째 요소는 예약돼 있고 무엇을 저장하는 데도 결코 쓰이지 않아요. 이것은 이 배열로 인덱싱해야 하는 것들이 "값 없음"을 나타내게 하기 위함이에요.
code_blocks
이 선택적 구조는 패턴의 (?{}) 구조를 관리하는 데 쓰여요. 다음 구조들로 이루어져 있어요.
/* record the position of a (?{...}) within a pattern */
struct reg_code_block {
STRLEN start;
STRLEN end;
OP *block;
REGEXP *src_regex;
};
/* array of reg_code_block's plus header info */
struct reg_code_blocks {
int refcnt; /* we may be pointed to from a regex
and from the savestack */
int count; /* how many code blocks */
struct reg_code_block *cb; /* array of reg_code_block's */
};
proglen
컴파일된 프로그램의 길이를 regop 단위로 저장해요.
name_list_idx
이것은 data 배열로의 인덱스로, 패턴에 있는 이름 붙은 캡처 버퍼의 이름을 포함한 AV가 저장된 곳이에요(있다면). 이것은 정규식 엔진의 디버깅 버전에서만, 그리고 RXp_PAREN_NAMES(prog)가 true일 때만 사용돼요. 그런 데이터가 없으면 0일 거예요.
program
컴파일된 프로그램이에요. 전체 구조가 단일 blob으로 취급될 수 있도록 구조에 인라인돼 있어요.
더 알아보기 (SEE ALSO)
perlreapi, perlre, perlunitut.