1. 정규표현의역사정규표현 (regular expression) 은문자열검색에있어서아무개문자 (wild card) 의기능을최대한도로확장시킨것이라고할수있다. 정규표현의역사는 1940년대로거슬러올라간다. 신경생리학자인 Warren McCulloch와 Walter Pitts가신경세포들이상호작용하는방식을모델링했는데, 몇년뒤수학자인 Stephen Kleene이모델을수학적으로형식화하여 regular set 이라불렀고, 이 regular set을표현하는표기법을고안해냈는데이것이바로정규표현 (regular expression) 의시초이다. 50년대와 60년대에수학자들사이에서정규표현에대한이론적논의가있었지만, 이것이컴퓨터시스템에서실용화된것은 60년대말의일이다. Ken Thompson은 1968년 Regular Expression Search Algorithm 이라는논문을발표하면서정규표현컴파일러를제시하였고, 이연구로부터만들어진정규표현엔진이유닉스에디터인 qed, ed에탑재되어많은사람들이이용하게되었다. ed에탑재된명령어중 Global Regular Expression Print 라는것이특히애용되었고, 이로부터 grep이라는이름이생겨났으며, 이기능은아예별도의유틸리티로독립되게되었다. 한편 Alfred Aho는 grep의기능을보완하여 egrep을만들었고, 비슷한시기에정규표현을지원하는 awk, lex, sed, Tcl, Emacs, vi 등의도구도만들어졌다. 그런데이렇게다양한도구들이정규표현을지원하게되면서, 프로그램마다정규표현의표기법이라든지특정기호의의미, 검색방식등에차이가생기게되었다. 그리고 1987년 Larry Wall이개발한스크립트언어 Perl은정규표현을가장풍부하게지원하여, 텍스트처리를위한프로그래밍언어로서각광을받게되었다. 90년대에들어와만들어진스크립트언어 Python도정규표현을지원한다. 1986년에는 Henry Spencer가 C 언어로정규표현엔진을구현하여공개함으로써, C 언어개발자들이자신의응용프로그램을만들때정규표현엔진을자유로이탑재할수있게되었다. 최근에는유니코드의대두에따라유니코드문자열까지도처리할수있는정규표현라이브러리가나오게되었다. 대표적인것으로 John Maddock이만든 Boost.Regex 라이브러리와 Eric Niebler가만든 Greta 및 Boost.Xpressive라는라이브러리등이있다. 2. 정규표현의기초프로그램에따라정규표현기호를사용하는방식에약간의차이가있다. 모든프로그램들을다살펴볼수는없으므로, 여기서는 cygwin 패키지에포함되어있는 grep과 pcregrep, 그리고 EmEditor를중심으로살펴보기로한다. 1) 2.1. dot 정규표현에서는몇개의메타문자 (metacharacter) 를정해놓고일정한의미를나타내게하고있다. 예를들어마침표 (dot). 는임의의하나의문자를의미한다. 이해를돕기위해 EmEditor를이용해서정규표현검색을직접해보자. EmEditor로 이상한나라의앨리스 1) 예전의 cygwin 패키지에는 grep 과 egrep, fgrep 이있었다. frep 은속도는빠르지만사용할수있는정규표현에심한제약이있고, egrep 은속도는약간느리지만풍부한정규표현을사용할수있고, grep 은이둘의중간쯤된다. 그런데 cygwin 의최근버전에서는 fgrep 과 egrep 이빠지고대신 pcregrep 이란것이들어갔다. pcre 는 Perl Compatible Regular Expressions 의약자로서, Philip Hazel 이 Perl 의정규표현 syntax 를본따서 C 언어로구현한정규표현라이브러리이다. pcregrep 은이 pcre 엔진을이용해서만든 grep 인셈이다. 예전의 egrep 보다더풍부한정규표현을제공하므로 pcregrep 을이용하는것이좋다.
파일을연다음 Ctrl-F 를눌러서찾기대화상자를띄운다. 대소문자구분 및 정규표현사 용 에체크를한다. 그리고 찾을문자열 입력란에 e.e 라고입력하고 찾기 버튼을눌러보 자. < 그림 1> 그림을보면, 검색결과매치된문자열들이다른색깔로표시된다. 여기서볼수있듯이 e.e 라는정규표현은 e 라는문자뒤에임의의문자가하나오고그뒤에 e 라는문자가온 것을의미한다. 두 e 사이에어떤문자가오든상관없다. 2.2. character class 각괄호 ([ ]) 안에복수의문자들을적어주면이전체는 각괄호안에적은문자들중어느 하나 를의미하게된다. 예를들어 [aeiou]s 라고하면 s 앞에 a, e, i, o, u 중어
느것이와도된다. < 그림 2> 반면에각괄호안에서맨앞에 ^ (caret) 을써주고그뒤에문자들을나열하면그것은나열된문자를제외한임의의하나의문자를의미하게된다. < 그림 3> 에서보듯이 s 앞에 a, e, i, o, u 5개의문자를제외한임의의문자가온경우매치되었다. s 앞에공백이온경우도매치되었음에유의하기바란다. 공백문자도어엿한하나의문자인것이다. 탭문자, 줄바꿈문자도마찬가지이다. 이셋을합쳐서 white space라고한다. character class의효용성을보여주기위해예를하나더들어보자. 영어의동사 fall의쓰임에대해알아보고싶다고하자. 문제는동사 fall의활용형이 falls, falling, fallen, fell로다양하게나타난다는것이다. 문자열 fall 을찾으면 falls, falling, fallen도함께검색되므로이들은별문제가없지만 fell은검색되지않을것이다. 문자열 fell 을따로검색하면물론되기야하지만, fell까지한번에찾을수있으면더좋을것이다. 이럴때 f[ae]ll 이라고하면 fall과 fell이함께검색된다. 그런데이렇게할경우 fellow까지함께검색된다. fellow를배제하고싶으면 f[ae]ll[^o] 와같이하면된다.
< 그림 3> < 그림 4>
2.3. anchor 찾고자하는문자열이라인의맨처음에있는경우만골라내고자할때에는 ^ 를사용하고라인의맨끝에있는경우만골라내고자할때에는 $ 를사용한다. 예를들어 ^th 라고하면 th 라는문자열이라인의맨처음에온경우만매치된다. ( 그림 4) 반면에 to$ 라고하면 to 라는문자열이라인의맨끝에온경우에만매치된다 ( 그림 5). 2) < 그림 5> 2.4. alternation 하나의문자에대해 x라는문자도좋고 y라는문자도좋다고할경우에는 character class를사용하면되지만, 문자열 a도좋고문자열 b도좋다고할경우에는 alternation을사용해야한다. alternation은수직바 (vertical bar) 로나타낸다. 예를들어 (to in) 이라고하면공백앞에 to 가오거나 in 이온경우를찾아준다. 2) ^ 와 $ 의의미가각각라인의시작과끝인가, 아니면검색대상문자열의시작과끝인가하는문제가있다. grep 이나 egrep 등정규표현을지원한초기의도구들은입력파일을한라인한라인불러와서처리를하기때문에이문제가발생하지않았다. 하나의라인이항상검색대상문자열이되기때문이다. 그러나복수의라인이검색대상문자열이될때에는이문제가제기된다. EmEditor 에서는두 anchor 기호의의미를라인의시작과끝으로규정하고있다. 만약검색대상문자열의시작과끝이라는의미였다면, 파일의맨처음에 th 가온경우, 파일의맨끝에 to 가온경우만매치되었을것이다.
여기서괄호는 alternation 연산자의힘의미치는범위를한정하는역할만한다. 실제로괄호가포함된문자열을찾아주는것은아니다. 괄호역시정규표현에서특별한의미를갖는메타문자인것이다. 그럼실제로괄호나마침표가들어있는문자열을찾고싶을때에는어떻게하나? 그럴때에는 escape 문자인역슬래시 \ 를그앞에첨가해준다. < 그림 6> 만약 to in 을둘러싸고있는괄호를뺀다면어떻게될까? 그러면 to 또는 in 이검색 대상이된다. (to) (in ) 과같은의미로해석되는것이다. 3) 2.5. repetition 영어단어 colour 는 u 를생략하고쓰기도한다. u 를포함한 colour 든지 u 를생략 한 color 든지상관없이다뽑아내고싶을때는어떻게할까? 물론 colour color 와같이 할수도있다. 그러나이보다더간단한방법이있다. colou?r 과같이하면된다. 기호? 는그앞의표현이없거나 1 개있음을나타낸다. 정규표현 colou?r 의의미를곧이곧대로 해석하자면문자열 colo 이오고그뒤에문자 u 가없어도되고 1 개있어도되고그뒤에 문자 r 이오는것을의미한다. 즉기호? 는 0 또는 1 개 의의미로이해하면된다. 이에 반해, 기호 + 는 1 개이상 을의미하고기호 * 는 0 개이상을의미한다. 4) 3) grep 의경우 앞에역슬래시를해줘야한다.? 나 + 같은반복기호도마찬가지이다. 4) * 는흔히 Kleene star 또는 Kleene closure 라불린다. 정규표현을수학적으로형식화한수학자 Kleene 의이름이기념되고있는것이다. 한편 + 는 positive closure 라고불린다.
< 그림 7> 위그림에서보듯이 a+ 라고하면 a 가 1개든 2개든몇개든연속해있는것은다매치된다. 그럼위그림에서주어진정규표현과매치된문자열은모두몇개일까? 눈에보이는대로헤아려서 14개라고답하는사람이많을것이다. 그러나 EmEditor에서커서를문서의맨처음에두고 (Ctrl-Home) Find Next 버튼을누르거나 F3을눌러서다음매치된문자열이무엇인지추적해보자. 그럼매치된문자열이 14개가아니라 22개임을알수있을것이다. aaaaa 에걸쳐있는색깔강조가하위문자열을덮어버려서드러나지않은것이지, 사실 aaaaa 의끝 4개의 a 로이루어진 aaaa, 끝의 3개의 a 로이루어진 aaa, 끝의 2개의 a 로이루어진 aa, 끝의 1개의 a 로이루어진 a 등의하위문자열도매치된것이다. 그렇다면제기될수있는의문은 aaaaa 의처음 4개의 a 로이루어진 aaaa, 처음 3개의 a 로이루어진 aaa 등은매치되는것으로볼수없는가하는것이다. 답은 매치되지않는다 이다. 그이유는정규표현의반복기호?, +, * 가기본적으로 greedy search를하기때문이다. 즉주어진정규표현에매치될수있는어떤문자열 A가있고, A와시작을공유하지만그보다먼저끝나는하위문자열 B가있을때, 정규표현은항상긴문자열 A를선택한다는것이다. 예를들어 bbaaaazaaaazcc 라는검색대상문자열이있고 A.*Z 라는정규표현이있을때, AaaaZaaaaZ 도이정규표현에매치될수있고이문자열의하위문자열인 AaaaZ 도매치될수있는데, 이둘중보다긴쪽인전자를선택한다. 반복기호가 greedy search를하지않고가능한한최소의문자열을선택하도록하기위해서는반복기호뒤에? 를붙인다. 5) 다음두그림을비교해보기바란다. < 그림 8> 5) 여기서기호? 은반복기호로서의의미와는다른의미를나타내는셈이다.
< 그림 9> 반복기호가하나의문자에만적용되는것은아니다. 복잡한정규표현전체가반복의대상이될수있다. 예를들어 (ab)+ 는문자열 ab 가 1개이상반복된것을의미한다. 이렇게반복기호를복합표현전체에적용할때에는반복기호의힘이적용되는범위를괄호로묶어준다. alternation의경우와마찬가지로이때의괄호는메타문자로서범위를지정해주는기능만할뿐, 검색대상문자열의괄호와매치되지는않는다. character class에도반복기호가적용될수있다. 예를들어 z[abc]+ 는 z 뒤에 a, b, c 셋중의어느것이든 1개이상반복된것을의미한다. 똑같은문자가반복될필요는없다. a, b, c 셋이뒤섞여서나와도상관없다. < 그림 10> 반복되는횟수를정확히지정해줄수도있다. 어떤표현이정확히몇번이상, 몇번이하반복된경우를찾고싶을때에는 {n,m} 과같은표기법을사용한다. 예를들어 a{3,4} 라고하면 a 가 3번이상 4번이하반복된것을의미한다. < 그림 11> {n,} 와같이쓰면반복횟수의하한선만 n 번으로정해지고상한선은없다. 즉 n 번이상 을 의미한다. 반면에 {n} 은정확히 n 번반복된것을의미한다.
2.6. backreference backreference는정규표현내에서앞에나온부분을뒤에서지칭할때사용하는것이다. 예를들어 (ed es)[^\n]*\1 라고하면 ed 또는 es 가하나의라인내에서반복된경우를찾아준다. 앞에나온것이 ed 이면뒤에도 ed 가나와야하고, 앞에나온것이 es 이면뒤에도 es 가나와야한다. 이점에서 (ed es)[^\n]*(ed es) 와차이가있다. 이것은앞에는 ed 가나오고뒤에는 es 가나와도매치된다. backreference할부분은반드시괄호로묶어주어야한다. 하나의정규표현내에서괄호로묶은부분이둘이상일경우, 왼쪽부터세어서여는괄호가먼저나오는것부터 \1, \2, \3 하는식으로지칭한다. 이상한나라의앨리스 파일에서 (ed es)[^\n]*\1 을실제로찾아보자. grep이나 pcregrep은정규표현에의해매치되는부분이정확히어디서어디까지인지가금방드러나지않는단점이있다. 그래서 Eric Niebler의 Greta라는정규표현라이브러리를이용하여필자가만든유틸리티를이용해서찾아보자. 라인번호가앞에붙어있고, 정규표현에의해매치되는부분의시작과끝이까만삼각형으로표시되어있다. < 그림 12>
< 그림 13> backreference는찾기뿐아니라바꾸기에서도유용하다. e.e 뒤에나오는공백을 # 으로바꾸고싶다고하자. 이때 e 와 e 사이에는임의의문자가올수있다. 그렇기때문에대치해넣을문자열을하나로지정해줄수가없다. 이럴때 backreference를이용하면편리한것이다. 찾을문자열을 (e.e) 로하고대치해넣을문자열을 \1# 이라고하면된다. \1 이찾을문자열에서괄호로묶은부분을가리키기때문이다. 3. 정규표현의응용 3.1. 영어사전이제정규표현을이용해서실제로유용한작업을해보자. 染谷泰正 (Someya Yasumasa) 라는일본의영어학자가만든영어단어목록을가지고예시하겠다. 파일을열어보면표제어, 등급 ( 난이도 ), 품사의세필드로이루어져있다. 우선 tion 으로끝나는표제어들을추출해보자. 각필드는공백으로구분되어있으므로 pcregrep으로 tion 을찾아보면될것이다.
< 그림 14> 위그림처럼하면 tion 으로끝나는단어들이 tion.txt 라는이름의파일에저장될것이다. 단어의수가 1009개가맞는지확인해보라. 이번에는형용사들을모두추출해보자. 이사전에서형용사는 JJ 로표시되어있다. 그냥 JJ 를찾으면혹시단어내부에 JJ 라는문자열이들어있으면그단어가형용사가아니더라도함께추출되어나올것이므로 JJ 가라인맨끝에나온다는것을명시해주는것이좋겠다. pcregrep JJ$ wrdlvl-2.txt >output_file_name과같이하면될것이다. 이번에는부사중에서등급이 15에서 24 사이인것들을뽑아보자. 이사전에서부사는 RB 로표시되어있다. 그럼정규표현의끝부분이 RB$ 인것은쉽게알겠는데, 그앞부분의등급은어떻게나타내야할까? 이사전에서등급은항상두자리의숫자로표시되어있다. 10 보다작은수는앞에 0을적어주고있는것이다. 그렇다면가장무식한방법은 (15 16 17 18 19 20 21 22 23 24) RB$ 처럼하면될것이다. 그러나이방법은타이핑하기도귀찮을뿐아니라검색시간도상대적으로오래걸린다. 보다좋은방법은 (1[5-9] 2[0-4]) RB$ 와같이하는것이다. 앞에오는숫자가 1일때에는뒤에오는숫자는 5부터 9 사이이고앞숫자가 2일때에는뒤숫자가 0과 4 사이인데, 이두경우를 로연결한것이다. 결과가 578개인지확인해보라. < 그림 15> 3.2. 국어사전 인터넷에올라있는동아국어사전을가지고작업을해보자. 파일을열어보면다음과같은
포맷으로되어있다. < 그림 16> 여기서 가 라는음절이두번이상 ( 인접해있지는않더라도 ) 반복되는표제어들을뽑아보자. 우선찾고자하는문자열을뜻풀이나예문이아니라표제어로제한하기위해맨앞에 ^\* 를붙여주어야할것이다. 이사전에서표제어는라인의맨처음에 * 라는기호뒤에공백을하나두고서나타나기때문이다. * 앞에역슬래시를두는이유는짐작할수있을것이다. 정규표현에서메타문자 * 가갖는특수한의미를없애고진짜 * 라는문자를찾기위해서이다. 그리고두개의 가 사이에콜론 ( : ) 이있으면안될것이다. 콜론이표제어와뜻풀이를구분해주고있는데, 두개의 가 가콜론의경계를넘어서반복되는것을하용하면표제어에 가 가하나나오고뜻풀이에 가 가나오는것까지포함하게되기때문이다. 표제어와한자정보를구분짓고있는괄호도제외해야하지않느냐는질문이나올법하다. 원칙적으로는그렇다. 그러나한자정보구획에한글 가 가나올리는없기때문에괄호까지신경쓸필요는없을듯하다. 그러면답은 ^\* 가 [^:]* 가 와같이된다. 실제로 EmEditor로찾아보면다음과같이 가 가표제어내에서두번이상나온예들을찾아준다.
< 그림 17> 그럼이번에는표제어내에똑같은음절이두개이상연속해서나오는경우를찾아보자. ^\* [^:(]*([^:(])\1 와같이하면될것이다. 라인맨앞에 * 와공백이오고그뒤에콜론과괄호를제외한임의의문자가임의의수만큼오고 ( 없어도무방하고 ), 그뒤에콜론과괄호를제외한임의의한문자가오고그것이바로뒤에다시온다는의미이다. EmEditor로실제로찾아보면, 가가, 가가례, 가가문전, 가가호호, 가가, 가가대소, 까까머리, 깐깐오월, 갈갈, 깔깔, 깔깔웃다, 갈갈이, 깔깔하다 등이제대로찾아진다. 그런데여기서한가지주의할것이있다. 똑같은정규표현을가지고똑같은한글완성형파일에대해 grep이나 pcregrep을가지고찾아보자. 이상하게같은음절이연이어나온경우가아닌데도뽑혀져나오는것이많을것이다. 이런현상의원인은 하나의문자란무엇을의미하는가? 하는문제와관련되어있다. grep이나 pcregrep은 multi-byte 코드체계를고려하지않고만들어졌다. 따라서모든문자는 1 바이트라는전제위에서정규표현의문법도만들어졌다. 그러나한글음절은 KS 완성형코드체계에서 2 바이트에해당한다. grep이나 pcregrep은정규표현에서 dot도 character class도모두 1 바이트로간주한다. 따라서, 위의정규표현은같은음절이연속해서나오는경우를찾는것이아니라같은바이트가연속해서나오는경우를찾는것이다. 납 은코드값이 0xB3B3 이고 만 은 0xB8B8 인데이렇게동일한바이트가연속된음절을다찾아주는것이다. 그리고 -스럽다 의 럽 은 0xB7B4, 다 는 0xB4D9 이므로 럽 의뒤바이트와 다 의앞바이트역시동일바이트의연속인것이다. 이런예도함께추출될것이다. 반면에정작같은음절이반복되더라도동일한바이트의반복이아닌이상정규표현에매치되지않을것이다. 따라서 grep이나 pcregrep 같은도구를가지고한글을처리할때에는이러한점을유의해야한다.
반면에 EmEditor는철저한유니코드기반프로그램으로서, KS 완성형이라든가기타다른나라의로컬코드체계로되어있는파일까지도프로그램내부에서는유니코드로변환해서처리한다. 유니코드에서는 ( 정확히말하면 UCS2에서는 ) 모든문자가 2 바이트를차지한다. 따라서 EmEditor 같은유니코드기반프로그램에서는정규표현엔진도유니코드기반으로, 모든문자가 2 바이트라는전제위에서만든것이다. 한글자료를처리하기위해서는유니코드기반프로그램이유리한점이많다.