컴파일러_형식언어

프로그래밍 언어도 형식언어라 할 수 있다.

Basic definitions
1) alphabet : symbol들의 유한집합이다.
꼭 한 문자는 아니다.

• T1 : {ㄱ,ㄴ,ㄷ,..,ㅏ,ㅑ,ㅓ,...ㅡ,ㅣ}
• T2 : {A,B,C,D,E,...,Z}
• T3 : {auto, break,...,while}

2) string(or sentence, word)

• 임의의 T 집합안의 symbol들이 모여 만든 문장이다.

3) length

• string 안의 symbol의 갯수이다.
• denoted by $|\omega|$

4) empty string

• string 안에 symbol이 없다.
• $|\omega|$ = 0
• denoted by $\epsilon$ or 람다

5) T*는 T 집합의 모든 가능한 경우의 string의 집합이다.

T = {a, b}
T* = {a와 b로 이루어진 모든 string} = {aa, ab, ba, bb, $\epsilon$}
T+(dagger) = T* - $\epsilon$

6) Language(L) : T*의 부분집합이면서 문법G의 규칙을 따라야한다.

T = {a, b}
L = {aa, bb, ba, bb} = { w | |w| = 2, w $\in$ T*}

L 집합도 집합 연산이 가능하다.

---

• terminal(Vt) : 정의되어 바뀌지 않는다.
• nonterminal(Vn) : terminal이 아닌 다른 문법적인 symbol들
• grammer symbol(V) : Vn + Vt

Grammer(G) = (Vn, Vt, P, S)

Vn = nonterminal symbols
Vt = terminal symbols
P = production rules
a $\rightarrow$ b : 왼쪽이 오른쪽을 생성해낸다.
이때 a는 무조건 symbol이 있어야 하므로 V+의 원소이다.
S = start symbol, Vn의 원소

---

Derivation

a $\rightarrow$ b일때 둘이 Derivation 하다 라고 한다.

---

L(G) : Language generated by grammer G

언어 L은 그것을 생성하게 하는 문법 G가 존재한다.
형식언어는 문법으로 기술할수 있는 언어를 뜻한다.