[컴파일러] 03. 정규 언어 (Regular Language)

• 정규 문법과 정규 언어 (Regular Grammar & Regular Language)

• 정규언어 : 토큰의 형태를 기술하는데 사용하는 언어
• The methods for specifying the regular languages

1) regular grammar (rg) 정규 문법

2) regular expression (re) 정규 표현

3) finite automata (fa) 유한 오토마타

 

 

1. 정규문법 : 정규 언어를 기술하는 형식 문법

 - 생성 규칙에 따라 분류한 네가지 문법 형태 중 가장 간단한 형태인 Type 3 문법

 - 어휘 분석 과정에서 인식되는 토큰 구조를 표현하는데 이용

 

Type 3 Grammar (N.Chomsky)

- RLG (Right Linear Grammar) : A->tB, A->t

- LLG (Left Linear Grammar) : A->Bt, A->t

where A,B ∈ VN and t ∈ VT *

 

- 모든 RLG(LLG)는 그와 동등한 LLG(RLG)를 만들 수 있다.

- LLG 형태의 규칙과 RLG 형태의 규칙이 혼합되어 있으면 정규문법이 아니다.

 

* 정규언어 : 정규문법에 의해 생성된 언어

 

• 토큰의 구조를 정의하는데 정규 언어를 사용하는 이유

- 토큰의 구조는 간단하기 때문에 정규 문법으로 표현할 수 있다.

- Context-free 문법보다는 정규 문법으로부터 효율적인 인식기를 구현할 수 있다.

- 컴파일러의 전반부를 모듈러하게 나누어 구성할 수 있다. (Scanner + Parser)

 

2. 정규 표현 (Regular Expression)

- 특정한 규칙을 가진 문자열의 집합을 표현하는데 사용하는 형식 언어