[Compiler] Regular Expression

지난 포스트에서 했던 이야기를 다시 해보자면 컴파일러가 하는 역할은 사람이 작성한 코드를 컴퓨터가 인지할 수 있게끔 번역해주는 역할이며, 가장 먼저 선행되어야 할 기능이 구문을 Token별로 잘라주는 Lexical Analysis이었다. 이를 위해서는 구문을 잘라내기 위한 특정 Pattern이 필요한데 보통 이걸 Regular Expression 방식을 사용해서 처리한다고 언급했었다. 이번 포스트에서는 그 Regular Expression에 대해서 조금 정리해보고자 한다.

 우선 String의 구성요소에 대해서 알아볼 필요가 있을 듯 하다. 보통은 구문 또는 단어라는 말로 다들 알고 있다. 그럼 이 String을 잘게 쪼갤 수 있을까 한번 Compiler라는 단어를 예로 들어보자

우선 첫번째 구성요소는 접두사(prefix)가 포함된 형태이다. 이 경우는 당연히 c로 시작하는 String들이 전부 들어간다. 예를 들면 c란 단어 하나도 compiler를 의미할 수 있는 것이고, 어쩌면 com이라는 단어도 compiler를 표현할 수 있다. 이건 정하기 나름일 것이다. 반면 이 반대로 접미사(suffix)가 포함된 형태도 생각해볼 수 있다. 그렇게 되면 compiler를 구성하는 요소는 r, ler, compiler, ... 등으로 분해해볼 수 있을 것이다. 여기서 한가지 빠진 요소들이 있는데 바로 Ɛ (Empty String)이다. Ɛ 이 나타내는 의미는 그냥 빈 글자, NULL 인 상태를 이야기 한다. 집합으로 생각하면 공집합 정도로 보면 될 듯 하다. 

 또 다르게 요소를 나눠볼 수 있는 방법이 substring과 subsequence이다. substring이라면 연속된 string으로 구성된 요소를 나타낸 것이고, subsequence는 어떤 규칙에 의해서 분해된 요소를 나타낸 것이다. 그래서 각 요소별로 나눠보면 나눠보면 다음과 같다.

Prefix -- { Ɛ, c, co, com, comp, ....}

Suffix -- { Ɛ, r, er, ler, iler, ....}

SubString -- { Ɛ, com, omp, iler, ile, }

SubSequence -- { Ɛ, cmplr, cpe, comp, ....}     

 이 모든 요소들이 전부 Complier라는 String을 구성하는 Subset이 될 것이다. 조금 더 정리해보자면 Compiler를 구성하는 c,o,m,p,i,l,e,r, 같은 Symbol을 우리는 Alphabet이라고 알고 있다. 이 alphabet들이 모인 집합체가 String이 되는 것이다. 물론 당연한 이야기이겠지만 String에는 별 의미가 없는 단어들도 포함될 수 있다. ssss같이 Alphabet이 Exponent된 형태도 string이라고 할 수 있고, Subsequence에 들어 있는 comp도 String이 될 수 있다. 하지만 본래 찾고자 하는 의미를 가지는 건 compiler 라는 것 하나밖에 없다. 이렇게 무언가로 정의될 수 있는 것을 String 중에서도 따로 Language로 구분지을 수 있다. 결론적으로 어떤 규칙으로 구분지을 수 있는 것들이 language라고 부를 수 있는 것이다. 

 그런데 사실 이런 구분 자체는 모호하다. 규칙만 가지고 있으면 모두 language라고 할 수 있기 때문에 특별히 그 String에 의미가 담겨있지 않더라고 language로 정의할 수 있다. Dragon book에는 다음과 같이 Alphabet, String, Language를 정의하고 있다.

- Alphabet Σ : any finite set of Symbol

- String s : a finite sequence of symbols drawn from the alphabet

- Language : any countable set of strings over some fixed alphabet Σ 

   

방금전에 이야기 한 것처럼 특정한 규칙을 가지고 나열되어 있는 것이 language라고 언급했는데 크게 4가지로 표현할 수 있다. 이 4가지를 적절히 조합하면 원하는 단어를 찾을 수도 있고, 뽑아낼 수도 있다. 

 첫번째는 Union (Alternation) 이다. Language subset이 하나는 L={A,B,C,D...,Z}로 되어있고, 다른 하나는 D={a,b,c,d,....z}로 되어있다. 만약 A라는 요소만 찾고 싶으면 L에서만 찾을수도 있지만 여기서 b를 찾아야 하는 경우가 발생할 수 있다. 이때는 L뿐만 아니라 D에서도 찾게끔 해줘야 한다. 이때를 위해서 L ∪ D라고 해주면 어떤 alphabet이 나오던지간에 이 subset에서 찾을 수 있게 된다. 그런데 보통 string이라고 하면 위와 같이 한 낱말씩 찾을 수도 있지만 두개이상의 낱말로 구성되어 있는 경우가 있다. 이때는 Union을 통한 subset에도 포함되어 있지 않기 때문에 찾을 수가 없다. 

 이때 적용할 수 있는 방법이 Concatenation이다. 바로 연속된 단어를 찾기 위해서는 집합을 그대로 이어주면 되는 것이다. 즉 LD로 이어주게 되면 subset은 {A,B,C,D...Z}{a,b,c,d,...,z}로 될 것이고 이걸 수학식으로 풀어서 적용하게 되면 {Aa,Ab,Ac,......Ba,Bb,Bc....... ,Ca,Cb,Cc.... Zz} 라는 단어의 조합으로 subset에 포함될 것이다. 세개 이상의 낱말도 똑같이 Concatenation을 세번 취해주면 해당 subset 내에 포함되게 된다. 

 다음 케이스는 같은 단어가 여러번 나오는 경우이다. 만약 Ahhhhhhhhhhhhhhhh 라는 단어를 찾고자 할때는 어떻게 해야 될까? 물론 Concatenation을 연속으로 취해주는 수도 있겠지만 이걸 축약해서 L*라고도 표현할 수 있다. 보통 이런 방식을 이런 방식을 생각해낸 사람의 이름을 따서 Kleene Closure라고 하고 옆에 붙은 별을 Kleene Star라고도 한다. 또 다른 방식으로는 L+(Positive Closure)가 있는데 Kleene 과 Positive의 차이는 Ɛ 가 있느냐 없느냐의 차이이다. 그래서 앞의 Ahhhhhhhhhhhhhhhhhh을 A = {A}과 B = {h}로 표현하면

AB* = {A,Ah,Ahh,Ahhh,Ahhhhh,.....}

AB+ = {Ah,Ahh,Ahhh,Ahhhh,Ahhhhh,.....} 

(왜냐하면 D에 Ɛ 의 유무가 적용되기 때문에..)

로 표현할 수 있는 것이다. 

이렇게 4가지 방식만 잘 활용하면 주어진 subset을 통해서 하나의 단어를 찾을수도 있고 표현할 수도 있다. 바로 이런게 Regular Expression이다. 당연한 이야기이겠지만 이것도 하나의 집합이기 때문에 우리가 수학시간에 배웠던 집합의 연산(교환, 치환 등등)이 적용된다. 다만 유의할 점이라면 위의 4가지 방법 중에도 먼저 적용되는 우선 순위가 존재한다. 그 우선 순위는 다음과 같다.

* or + > Concatenation > Union (Alternation)

all Left - associative

아무튼 들어가면 복잡한데 내가 이해한건 요기까지.. 

더 참고할 만한 자료

- Wikipedia : http://en.wikipedia.org/wiki/Regular_expression

- Stanford cs143 ( compiler) - Lexical Analysis : http://www.stanford.edu/class/cs143/lectures/01/Slides01.pdf