5 - Regular Language (Regular Expression)

 어휘를 분석하여 토큰을 추출하려면 형식 언어와 정규 언어에 대한 이해가 필요하다.

이번엔 정규 표현에 대해 알아보도록 하자.

 

개념

---

정규 표현 상에서는 + 기호가 or 을 나타낸다.

(0 + 1)* 일 경우 0또는 1로 이루어질 수 있는 모든 집합을 말한다.

 

(aa)*(bb)*b 와 같은 정규 표현이 있다.

위 정규표현은 이와 같은 수학 식으로도 정의할 수 있다.

aa 로 이루어질 수 있는 집합이므로 2n개 만큼이 나오고, 

bb 로 이루어질 수 있는 집합에 마지막 b가 있어야 하므로 2m+1 개가 나와야 한다.

n, m 둘다 입실론(공백)이 될 수도 있으므로 0 보다 크거나 같다고 명시해주어야 한다.

 

 

정규 표현의 방정식

---

저번에 배웠던 Formal Language를 여러 형태로 만들어 보자

그중 새로 배울 개념은 방정식 형태로 만드는것 이다

 

X -> aX | b 라는 식이 있다.

이는 X 가 aX 또는 b가 될 수 있다는 뜻이다.

aX 에서 X 가 b가 안나오고 계속 aX 로 치환된다면 aaa...X 형태가 된다.

언젠간 b가 나오면 형태는 aaaa....b가 되는 것이다.

 

그래서 이 식은 우리가 X = a*b라고 표현할 수 있는 것이다.

a로 나올수 있는 모든 집합에다가 마지막에 b가 나온다는 뜻이기 때문이다. 

더불어 or 기호인 +를 이용하면,

X = aX + b 라는 방정식을 만들 수 있다.

 

 

예제

---

 주어진 식 1 : 

S -> aS | bR | ε
R -> aS

 

이 두식은 S = aS + bR + ε 와 R = aS로 생각할 수 있다.

R 자리에 밑에 식을 넣으면

S = aS + baS + ε 가 된다.

이 식에서 S 끼리 묶으면

S = (a + ba)S + ε 가 된다.

이로 인해 아까처럼 X = aX + b 형태가 완성되었다.

(a + ba)* ε 가 성립하는 것이다.

ε는 공백이기 때문에 최종적으로 a 또는 ba으로 만들 수 있는 모든 집합이다.

라는 식이 되는것 이다.

 

 

주어진 식 2 :

S -> aA | bB | b
A -> bA | ε
B -> bS

이번엔 좀 더 복잡하다.

일단 수식으로 빠르게 변환시킨다.

1) S = aA + bB + b

2) A = bA + ε

3) B = bS

 

여기서 2번을 보아하니, X = aX + b 형태이다.

ε는 생략하여 A = b* 라는 결과를 얻어냈다.

 

이제 바뀐 2번과 3번을 1번식에 대입해보자.

S = a(b*) + b(bS) + b 가 된다.

이제 터미널로 이루어 진건 대문자인 S 하나 뿐이다.

가장 앞으로 빼주고 묶어버리면,

S = bbS + (ab* + b) 가 된다.

이것도 역시 X = aX + b 형태이다.

S = bb* (ab* + b) 라는 식이 최종적으로 도출된다.