[Compiler]Regular_Expression(정규 표현식)

본 내용은 아래의 출처에서 본것이고 허락을 맡고 포스트한다.

 

출처 : https://talkingaboutme.tistory.com/category/About%20Study/Compiler

 

Lexical Analysis(구문을 Token별로 잘라주는 방법)를 위한 특정 pattern이 필요 -> 정규식 방식을 사용해서 처리

 

구문이나 단어라고 하는 String을 나누는 예를 들어보자

ex) 'compiler'

 

접두사(prefix) : c로 시작하는 모든 String,  -- {ε,c, co, com, ...}
접미사(suffix) : 마지막 단어를 포함하는 모든 부분 문자열, -- {ε,r, ler, compiler, ....}

substring : {ε, com, omp, ...} 

subsequence : {ε, cmplr, cpe, ...}

*empty string : ε*

 

위의 내용을 정리하면, 'compiler'를 구하성하는 'c','o','m','p'...같은 Symbol을 알파벳이라고 알고 이들이 모인 집합체가 String이라고 알고 있다. 위의 'cmplr' 혹은 전혀 상관없는 'sss'도 하나의 String이지만, 우리가 원하는 건 'compiler' 하나 밖에 없다. 이 같이, 무언가로 정의될 수 있는 String중에서도 따로 Language를 구분할 수 있다.

 

결론 : 어떤 규칙으로 구분지을 수 있는 것들이 Language이다.

 

드래곤 책에서의 Alphabet, String, language 정의

 

Alphabet : any finite set of Symbol

 

String : a finite sequence of Symbol drawn from the alphabet

 

Language : any countable set of strings over some fixed alphabet

 

이제 우리가 알아가고 있는 어떤 규칙으로 구분하고 나열되어 있는것이 Language이다. 이것을 4가지로 표현할 수 있다. 이 4가지를 적절히 조합하면 원하는 단어를 찾을수도 뽑아낼 수도 있다.

 

1. Union (합집합)

ex) L = {A,B,C ...}  D ={a,b,c ...}   L ∪ D 를 통해 모든 알파벳 찾을 수 있다.

 

2. Concatenation : 연속된 단어를 찾기 위해 집합을 이어줌

ex) LD = {Aa, Ab, Ac .... Zy, Zz}

 

3. L* (Kleene Star) : 같은 단어가 연속해서 나오는 경우 ex) Ahhhhhhhhhhhhhhhhhhh

  언어 L을 0번이상 접합함으로써 얻는 스트링의 집합

 

4. L+ (Positive Closure) : L*와 같지만, 공집합(ε) 제외 

 

위의 방식을 통해 주어진 subset에서 하나의 단어를 찾을수도 표현할 수도 있다.

이러한 것이 Regular Expression이다.