[Compiler] 3. Regular expression (정규 표현)

Regular expressions (정규표현)

정규 표현은 언어(regular languages)를 설명하는 대수적 방법이다.

• e가 정규식이면 L(e)가 정의하는 언어다.

 

Definition of regular expressions

Basic 1 : a가 기호라면, a는 Regular expression이고, L(a) = {a}

• a를 regular expression으로 표현시 bold 체로 정의

Basic 2 : ε은 regular expression, L(ε) = {ε}

Basic 3 : ø은 regular expression, L(ø) = ø

 

Induction 1 : r, s가 regular expression이라면, r+s도 regular expression

• L(r+s) = L(r|s) = L(r) ∪ L(s)

Induction 2 : r, s가 regular expression이라면, rs는 regular expression

• L(rs) = L(r)L(s)

Induction 3 : r이 정규 표현식이라면, r*은 정규표현식이다.

• L(r*) = (L(r))* = {r}* = {ε, r, rr, ...}

 

Precedence of Operators (우선 순위)

우선순위 : *(highest) > concatenation > +(lowest)

가장 높은건 괄호() 다.

ex)

L(0+1) = L(0) ∪ L(1) = {0} ∪ {1} (basic 1) = {0,1}

L(01+0)
-> L(01) = L(0)L(1) = {01}
-> L(01+0) = {01, 0}

L((0+1)*) = {L(0+1)}* = {0, 1}* = {ε, 0, 1, 00, 01, 10, 11, ...}

L((0+10)*(ε+1)) = {0, 10}* = {ε, 0, 00, 001, 10, 101, 010, 0101, ...} = 1이 연속되지 않는 문자열

 

L = {(a^n)b(a^n) | n >= 0} = {b, aba, aabaa, aaabaaa, ...}

• 위 언어는 정규 표현식이라고 할 수 없다.
• 몇 번 반복해라 라고 정의할 수 없다.
• * : 임의의 수의 반복
• a*ba* : b 앞과 뒤에 있는 a의 개수가 같다는 보장이 없다.

regular expressions은 셀 수 없다.

 

Algebraic laws for regular expressions

• +에 대한 결합법칙
• 접속에 대한 결합법칙
• +에 대한 교환법칙
• a + a = a
• 분배 법칙
• 접속 연산의 항등원 : εa = a = aε
• a* = ε + aa*
• (a*)* = a*

 

Language (set expression)	Regular expression
{a, b}*	(a + b)*
{a^i | i >= 0}	a*
{(a^i)(b^j) | i,j >= 0}	a*b*
{xaaybbz | x, y, z ∈ {a, b}*}	(a + b)*aa(a+b)*bb(a+b)*