2. 형식언어와 형식문법

주요용어

1. 형식언어(formal language) : 어떤 알파벳(alphabet)에서 얻은 기호(symbol)들로 구성되는 문자열(string)의 집합
2. context-free 문법 : A → γ (단, A는 논터미널 기호이고, γ는 V*에 속하는 문자열이다.)
3. 촘스키 계층구조 : 생성규칙의 형태에 가해지는 제한에 따라 미국의 영문학자 촘스키가 4종류로 나눈 형식문법
4. context-sensitive 문법 : γ → β (단, |γ|≤|β| γ∈V+, β∈V*)
   생성규칙에 |γ|≤|β|의 제한을 가하는 것으로 비위축형(noncontracting) 문법에 속함
5. 공문자열 : 문자열의 길이가 0인 것, ε 혹은 λ로 표시
6. 정규문법 : A → tB A → t 또는 A → Bt A → t (단, t ∈ A, B ∈ VN)
   생성규칙에 따라 두 가지 종류가 있다.
   A → tB, A → t 와 같은 생성규칙을 갖는 것을 우선형(right-linear)문법이라 하고 A → Bt, A → t와 같은 생성규칙을 갖는 것을 좌선형(left-linear)문법이라 함.
7. 형식문법 : 형식언어를 생성하기 위한 규칙
8. 논터미널 : 언어에서 문자열을 생성하는 데 사용되는 중간과정의 기호로서 보통 대문자로 표시
9. 터미널 : 정의된 언어의 알파벳이나 기호로서 영문자의 소문자나 아라비아 숫자, 연산자 기호 등이 속함
10. 문법기호 : 터미널과 논 터미널 기호를 문법기호(grammar symbol)라 하며 보통 V(vocabulary)로 표시
11. 튜링기계(turing machine) : unrestricted 언어를 받아들이는 인식기
12. 유도(derivation) : 한 문자열에서 생성규칙을 한 번 적용해서 다른 문자열로 바뀌는 것
13. 정규표현(regular expression) : 정규문법을 가장 잘 표현할 수 있는 방법

---

정리하기

1. 2강에서는 컴파일러의 설계를 위한 형식언어(formal language)와 이 언어를 생성하는 형식문법에 대해 알아보았다.
2. 형식언어란 어떤 알파벳(alphabet)에서 얻은 기호(symbol)들로 구성되는 문자열들의 집합을 말하며 이러한 형식언어를 생성하기 위해 여러 규칙들을 이용하는데 이것을 형식문법이라 한다.
3. 형식문법은 논터미널 기호들의 유한집합 VN , 터미널 기호들의 유한집합 VT, 생성규칙(production rule)의 집합 P, 시작기호 S 로 구성되며 G ＝ (VN, VT, P, S) 로 표현한다.
4. 형식문법에서 터미널(terminal) 기호는 정의된 언어의 알파벳이나 기호로서 영문자의 소문자나 아라비아 숫자, 연산자 기호 등이 여기에 속하고, 논터미널(non－terminal) 기호는 언어에서 문자열을 생성하는 데 사용되는 중간과정의 기호로서 보통 대문자로 표시한다.
5. 생성규칙의 형태에 가해지는 제한에 따라 미국의 영문학자 촘스키(Chomsky, N.)는Type0, Type1, Type2(= CFG), Type3(= 정규문법)등의 4종류로 형식문법을 나누었으며, 이를 촘스키 Chomsky 계층구조(hierarchy)라고 부른다.
6. 형식문법을 표현하기 위해 정규표현(regular expression), 문법도표(syntax diagram), BNF(Backus-Naur From), EBNF(Extended BNF) 등의 방법을 사용한다.