[컴파일러] 11. 정규언어

  type 3: regular Language

 

정규 문법과 정규 언어

정규 문법 이론: 컴파일러 어휘 분석 과정에서 모형을 만드는데 사용

 

Type 3 문법

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

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

여기서 A, B ∈Vn이고, t∈VT*

우선형 형태의 규칙과 좌선형 형태의 규칙이 혼합되어 있으면 정규 문법이 아님.

 

정의

• 각 생성규칙이 다음과 같을 때 정규문법이라 한다.
  • A->aB, A->a, 여기서 a∈VT, A,B ∈VN
  • S->ε∈P 이면, S는 오른쪽에 나타나지 않아야 한다.
• 정규 문법에 의해 생성된 A언어는 정규 언어(rl)이다.
  • L = {a^nb^m|n, M>=1}은 정규언어
  • S->aS|aA
  • A->bA|b
• 정규 문법의 생성 형태는 우선형 문법으로부터 유도할 수 있다.

동치관계(Equivalence)

다음 3가지는 모두 같으며 정규언어이다.

1. 언어 L은 우선형 문법에 의해 생성
2. 언어L은 좌선형 문법에 의해 생성
3. 언어 L은 정규 문법에 의해 생성

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

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

2) context-free 문법보다는 정규 문법으로부터 효율적인 인식기를 쉽게 구현 가능

3) 컴파일러의 전반부를 모듈러하게 나누어 구성할 수 있다.(스캐너+파서)

문법G(정규문법)에서 언어의 표현을 체계적으로 구하여 정규표현 L로 나타낼 수 있다.

 

정규 표현

: 정규 언어를 표현하기 위한 하나의 방법

: 정규 언어를 상세화하기 위한 방법

1)regular grammar

2)regular expression

3)finite (state) automata

위의 3개는 equivalence

정의

• 기본 소자: ∅, ε, a ∈T
  • ∅: 공집합을 나타내는 정규표현
  • ε: 집합 {ε}를 나타내는 정규표현
  • a ∈T: 집합 {a}를 나타내는 정규 표현
• 순환식: +, ●, *. P와 Q가 정규언어 Lp와 Lq를 나타내는 정규표현이라면
  • (P+Q)는 Lp∪Lq를 나타내는 정규표현(union)
  • (P●Q)는 Lp●Lq를 나타내는 정규표현(concatenation)
  • (P)*은 다음을 나타내는 정규표현(closure): {ε}∪Lp∪Lp2∪Lp3∪Lp4..∪Lpn
  • 우선순위 +<●<*
• 이외의 어떤 것도 정규표현이 될 수 없다.

정의: α가 정규표현일 때, L(α)는 α가 나타내는 언어정의: 두개의 정규 표현이 같은 언어를 표현할 때 그 정규표현은 같다.공리<img>

 

정규표현식: 계수가 정규 표현인 식을 정규 표현이라 한다.X = αX+β(여기서 X는 우측 식이 그 비단말 기호를 생성하는 언어임을 나타냄)(해): 식의 양변에 X=α*β를 대입할 때 각 변이 같은 언어를 나타냄)모든 정규 표현이 유일해를 가지진 않음.

• ε이 α에 속하지 않을 때, X=α*β은 유일해
• ε이 α에 속할 때 X=α*(β+L)는 어떤 언어 L에 대해 유한한 해를 가진다.

 

주어진 정규 문법 G가 생성하는 언어 L(G)를 나타내는 정규 표현

• L(A)여기서 A ∈VN는 A에 의해 생성된 언어를 나타냄.
• 정의에 따라 S가 시작심벌이면 L(G)=L(S)
• 2STEP
  • G로부터 연립방정식을 만들면
  • 이식을 풀면 된다.