1. 문맥 종속 문법, 문맥 자유(무관) 문법 이란?
ㅇ 문맥 종속 문법 (Context Dependent Grammer) : 例) 자연어
ㅇ 문맥 자유/무관 문법 (Context Free/Independent Grammar) : 例) 형식언어 (프로그래밍 언어 등)
※ 1950년대 Noam Chomsky(노엄 촘스키,1928~)가 문맥 무관 문법(Context-free Grammer,CFG)을 제안함
- 1957년 `통사의 구조(Syntatic Structure)`를 발표하여, 언어학 연구에 혁명을 일으킴
- 문맥적인 의미를 따로 떼어 놓고서도, 형식화된 문법에 대한 표기법이 가능하다고 함
. 즉, 문법과 의미를 서로 분리시킬 수 있다는 아이디어를 내고,
. 전후 문맥과 무관하게 문법을 간추릴 수 있어서, 구문을 형식화시켜,
. 이를 간명하게 서술 가능한 방법이 있다고 함
- 따라서, 대개의 프로그래밍 언어는,
. 문맥 무관 문법(Context-free Grammer, CFG)의 구조로 제한시켜,
. 기계의 효율적인 번역이 가능하도록,
. 충분히 단순한 구조를 유지시켜 만들어짐
2. 문맥 자유 문법 (Context-Free Grammar), 문맥 독립(무관) 문법 (Context Independent Grammar)
ㅇ 특정 자연 언어의 구문을, 명확하게/엄격하게 기술하는 표기법
ㅇ 용도 : 자연 언어의 이론적인 본질 규명 등
ㅇ 구성
- 비단말(non-terminal) 기호 : 정의할 대상으로, 대문자 (A,B,C,S 등) 사용
- 단말(terminal) 기호 : 해당 언어에서 직접 사용되는 표현으로, 소문자 (a,b,c 등) 사용
- 시작 비단말 기호 : 언어에서 독립적으로 사용되는 단위
- 생성 규칙 : 화살표(→)가 아니라 함수적 표기법을 사용
. 규칙의 오른쪽에는 기호들의 문자열이 올 수 있음
. 비단말 기호를 구체적으로 정의하게 됨
. 각 규칙은 하나의 비단말 기호를 단말 기호와 비단말 기호의 조합으로 정의됨
※ 사실상, 촘스키의 `문맥 자유 문법(CFG)`과 아래 3.항의 `Backus-Naur 형식(BNF)` 이 둘은,
- 표기법 만 다르고, 기능/개념은 동일함
. 촘스키의 표기법은, 보다 수학적인 함수형 접근을 사용한 반면,
. BNF는, 프로그래밍 언어의 구문(syntax) 기술에 특화된 표기법으로 발전되어 널리 사용됨
3. BNF 표기법 (Backus-Naur Form)
ㅇ 프로그래밍 언어의 구문을 서술할 수 있는 표기법
ㅇ 용도 : 프로그래밍 언어의 구문 문법, 통신 프로토콜 동작에 대한 구문 문법 등의 엄격한 정의
ㅇ 역사
- John Backus가 Peter Naur의 도움으로 개발
. John Backus가 1959년 ALGOL의 문법을 정의하기 위해 처음 사용했고,
. 이후 Peter Naur가 1960년대에 이를 정리하며 널리 보급됨
- 1963년, ALGOL 60 언어 구문을 기술할 때 사용
- 이후, Ada, Pascal, C, Java 등 대부분의 프로그래밍 언어의 구문에 대한 표기법으로도 사용됨
ㅇ 규칙
- Symbol ::= Expression (심볼 ::= 표현식)
ㅇ 메타 기호
- ::= ⇒ 정의를 뜻함 (좌변을 우변으로써 정의함)
- | ⇒ 선택/택일(or)을 뜻함
- < > ⇒ 비단말 기호를 뜻함
4. 확장 BNF, 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 표기법