컴파일러
문법 : Grammer
생각없는 개발자
2022. 9. 19. 00:26
언어는 스트링들을 원소로 갖는 집합이다. 유한 언어의 경우에는 그 집합에 속한 모든 스트링을 열거함으로써 쉽게 표현 할 수 있지만, 무한 언어는 그 언어의 유한 표현을 찾아야 한다. 이러한 유한 표현의 방식으론 다음과 같이 세가지가 존재한다.
- 조건제시법
- 문법
- 인식기
이 중에서도 문법을 다루고자 한다. 문법은 다음과 같이 네가지 요소로 정의 할 수 있다.
G = (Vn, Vt, P, S)
- Vn : nonterminal 심벌의 유한 집합
- Vt : terminal 심벌의 유한 집합
- P : 생성 규칙(production rule)의 유한집합
- S : Vn에 속하는 심벌로서 다른 nonterminal들과 구별하여 시작 심벌(start symbol) 또는 문장 심벌(sentence symbol)이라 한다
처음에는 "이게 무슨 말이지?" 싶다 차근차근 알아가 보자. 다음은 문법의 예시이다. 생성규칙 A → B는 A구조를 B구조로 정의한다는 것이며, A를 B로 대체할 수 있다는 것을 의미한다.

생성 규칙의 왼쪽이 같은 경우에는 '|'를 활용하여 간단히 나타낼 수 있다. 예를 들어 A → B1, A → B2 가 있을때 A → B1 | B2로 표기 가능하다는 것을 의미한다. 즉 위 생성규칙을 간단히 표현하면 다음과 같다.

문법은 생성규칙에 따라 4가지 종류로 나뉜다.
- Type 0 문법(unrestricted grammer) : 생성 규칙에 어떤 제한도 두지 않는다. 다만, 문법의 정의에 따라 생성 규칙 A → B에서 A는 empty 스트링이 될 수 없다는 것이다.
- Type 1 문법(context-sensitive grammer) : 생성 규칙 A → B에서 B의 길이가 A의 길이보다 길다.
- Type 2 문법(conetxt-free grammer) : 모든 생성 규칙은 A → a의 형태를 갖는다. 여기서, A는 하나의 nonterminal 심벌이며, a는 V*에 속하는 스트링이다. 즉, 생성 규칙의 좌측은 하나의 nonterminal이며 우측은 terminal과 nonterminal로 이루어진 스트링이다.
- Tyep 3 문법(regular grammer) : 정규 문법의 생성 규칙은 두가지 형태로 표현 될 수 있는데 첫 번째 형태를 우선형 문법, 두 번째를 좌선형 문법이라고 한다.
- A → tB 혹은 A → t, 여기서 A,B ∈ Vn이고, t ∈ Vt*이다.
- A → Bt 혹은 A → t, 여기서 A,B ∈ Vn이고, t ∈ Vt*이다.