컴파일러 - 정규 언어

목차

1. 정규문법과 정규 언어

2. 정규 표현

 

1. 정규 문법과 정규 언어

정규 문법이란?

노엄 촘스키가 생성 규칙 형태에 분류한 네가지 문법 중 가장 간단한 레벨에 해당하는 문법

 

형태

생성 규칙의 오른쪽에 위치한 논-터미널 심볼의위치에 따라 구분됨.

우선형 문법

L -> tB, L->t

좌선형 문법

L ->Bt, L->t where L,B  Vn and t Vt*

정규문법에서 우선형 문법과 좌선형 문법의 속성

- 모든 우선형 문법은 동등한 좌선형 문법을 만들수 있고, 그 역도 가능

- 단 한 문법의생성 규칙이 우선형, 좌선형 형태 규칙이 혼합되어 있으면, 정규문법이 아님

 

정규문법의 활용

컴파일러의 어휘 분석 단계에서 입력 프로그램을 구성하는 토큰의 구조를 정의하는데 주로 사용됨

1. 토큰의 구조는 간단하므로 정규 문법으로도 표현 가능

2. 효율적으로 토큰 인식기 구현

3. 프로그램의 크기를 분할하여 모듈화하는데 용이함

 

G가 정규문법인 경우 L(G)를 구하려면?

문법 G를 정규문법으로 변환후 이것으로부터 구할수 있다.

 

2. 정규 표현

정규 표현

정규 표현의 기본 소자는 ε, 𝝅, terminal 심볼이다. 

 -  𝝅 은 공집합을 나타내는 정규 표현

 - ε 은 집합 영스트링을 나타내는 정규 표현

 - 터미널 심볼은 집합 {a}를 나타내는 정규 표현

e1과 e2가 정규언어 L1, L2를 나타내는 정규표현이면

 - e1+e2는 L1과 L2의 합집합, e1+e2는 e1|e2로 표시가능

 - e1 e2 concatnation은 L1L2 concatnation, e1e2concatnation은 e1e2로 표시가능

 - (e1)*은 L1*을 나타내는 정규표현

 

a가 정규 표현이면, L(a)는 a가 나타내는 언어. a,b 언어이면 아래를 만족 - L(a+b) = L(a) + L(b) - L(ab) = L(a)L(b) - L(a*) = L(a)*

 

두개의 정규표현이 같은 언어를 표현하면 그 정규 표현은 같다고 표현한다.

 

정규 표현의 대수적 공리

a + b = b + a

(ab)r = a(br)

(a+b) + r = a + (b+r)

a(b+r) = ab + ar

a+a = a

a+공집합 = a

a*공집합 = 공집합

a* + a = a*

(a*)* = a*

a* + a+ = a*

a* + a = a*

(a+b)* = (a*b*)*

 

a b가 정규 표현이고, 영스트링이 a의 언어에 포함되지 않으면, X= aX+b의 유일해는 X=a*b이다.

 

정규언어 구하는 로직

1. 정규 문법이 X -> a|b|r 이면 X = a+b+r으로 변환 가능하다.

2. X = aX+b는 X=a*b형식으로 푼다.

3. X 대신에 a*b를 대입하고, 정규 표현의 공리를 이용하여 X=aX+b 꼴로 변환하고 2-3을 반복한다.

4. 더 변환할수 없을때까지 반복하면 그것이 정규언어 L(G)가 된다.

 

정규문법과 정규 표현은 같은 종류의 언어를 나타낸다.

정규 표현은 유한 오토마타를 이용하여 시각화 가능하다.