1. 문맥 무관 문법, 문맥 종속 문법 이란?
※ 1950년대 Noam Chomsky(촘스키)가 문맥 무관 문법(Context-free Grammer)을 제안함
- 1957년 `통사의 구조(Syntatic Structure)`를 발표하여, 언어학 연구에 혁명을 일으킴
- 문맥적인 의미를 따로 떼어 놓고, 형식화된 문법에 대한 표기법이 가능하다고 함
. 즉, 문법과 의미를 서로 분리시킬 수 있다는 아이디어를 내고,
. 전후 문맥과 무관한 문법을 간추릴 수 있어서, 구문을 형식화시켜,
. 이를 간명하게 서술 가능한 방법이 있다고 함
- 따라서, 대개의 프로그래밍 언어는, 문맥 무관 언어(Context-free Language)의 구조로 제한시켜,
. 기계의 효율적인 번역이 가능하도록 충분히 단순한 구조를 유지시켜 만들어짐
ㅇ 문맥 종속 문법 (Context Dependent Grammer) : 例) 자연어
ㅇ 문맥 무관 문법 (Context Independent Grammar) : 例) 형식언어
2. 문맥 자유 문법 (Context-Free Grammar), 문맥 독립(무관) 문법 (Context Independent Grammar)
ㅇ 특정 언어의 구문을, 명확하게/엄격하게 기술하는 표기법
ㅇ 문맥 자유 문법의 용도
- 프로그래밍 언어의 구문 문법, 통신 프로토콜 동작에 대한 구문 문법 등의 엄격한 정의에 사용됨
ㅇ 문맥 자유 문법의 표기법
- BNF, EBNF, 구문 도표(Syntax Diagram) 등을 사용
ㅇ 문맥 자유 문법의 구성
- 비단말 기호 : 정의할 대상
- 단말 기호 : 해당 언어에서 직접 사용되는 표현
- 시작 비단말 기호 : 언어에서 독립적으로 사용되는 단위
- 규칙 : 비단말 기호를 구체적으로 정의하게 됨
. 각 규칙은 하나의 비단말 기호를 단말 기호와 비단말 기호의 조합으로 정의
3. BNF 표기법 (Backus-Naur Form)
ㅇ 프로그래밍 언어의 구문을 서술할 수 있는 표기법
ㅇ 역사
- John Backus가 Peter Naur의 도움으로 개발
- 1963년, ALGOL 60 언어 구문을 기술할 때 처음으로 사용
- 이후에, Ada, Pascal, C, Java 등 대부분의 프로그래밍 언어의 구문에 대한 표기법으로 사용
ㅇ 규칙
- Symbol ::= Expression (심볼 ::= 표현식)
ㅇ 메타 기호
- ::= ⇒ 정의를 뜻함 (좌변을 우변으로써 정의함)
- | ⇒ 선택/택일(or)을 뜻함
- < > ⇒ 비단말 기호를 뜻함
4. EBNF 표기법 (Extended Backus-Naur Form)
ㅇ 원래의 BNF에 추가적인 메타 기호 등을 사용하고 확장한 표기법으로 많은 변종이 있음
- 例) Niklaus Wirth가 BNF를 확장하여 만드는 등
ㅇ 사용 例)
- 만일, Small_Alphabet이라는 기호가, 소문자 a 부터 z 까지의 한 문자를 표현한다면,
. Small_Alphabet ::= [a-z]
- 만일, Number라는 기호가, 숫자 0 에서 9 까지의 한 숫자를 표현한다면,
. Number ::= [0-9]
5. ABNF 표기법 (Augmented Backus-Naur Form)
ㅇ 표준화된 확장 BNF 표기법