[프로그래밍 언어론] BNF (Backus-Naur Form) 란?

* 이 포스트는 이전에 공부하면서 보고서로 작성한 것을 그대로 포스팅 한 것입니다.
* 참조교재 : 프로그래밍 언어론 (한빛미디어)

BNF란 배커스-나우어 형식(Backus-Naur Form)의 약어로, 컴퓨터 언어에서 언어의 문법을 수학적인 수식으로 나타낼 때 사용하는 언어 도구입니다.

1959년 파리에서 개최된 유네스코 학술회의에서 존 배커스(John Backus)는 ALGOL 58에 대한 논문을 발표하였고, 1년 후에 피터 나우어(Peter Naur)가 그 내용을 보완하여 ALGOL 60을 기술하여 지금의 형태로 만들었습니다.

이것이 중요한 이유는 프로그래밍 언어의 구문을 기술하는 데 매우 자연스러운 표기법으로, C, Java, PHP 등을 포함한 대부분의 프로그래밍 언어의 정의에 가장 널리 사용되기 때문입니다.

한 언어의 구문을 기술하는 BNF는 생성 규칙들의 집합으로, 배정문에 대한 생성 규칙의 예는 다음과 같습니다.

<digit> → 0 | 1 | 2 | … | 9

이는 <digit>가 0 | 1 | 2 | … | 9 로 정의됨을 의미하며, 여기에서 화살표를 기준으로 왼쪽에 위치한 <digit>은 정의되고 있는 구문 구조의 이름으로, LHS(left hand side)라 부르며, 우측에 위치한 0 | 1 | 2 | … | 9 은 RHS(right hand side) 라고 부릅니다.

RHS에서 수의 표기에 사용 된 | 는 논리 OR 을 의미하며, 하나의 구문 구조에서 두 개 이상의 다른 정의를 가질 때 이를 이용하면 하나의 규칙으로 표현하는 것이 가능합니다.

또한, <digit> 와 같이 '<>'로 묶인 기호를 비단말 기호(non-terminal symbol)라 하고, 0, 1, 2와 같이 직접 나타낼 수 있는 기호를 단말 기호(terminal symbol)라 하며, →, | 와 같이 BNF 표기에서 사용되는 특수한 기호들을 메타 기호(meta symbol) 라 합니다.


언어의 문장들은 BNF의 규칙을 적용해가며 생성되는데, 시작 기호(start symbol)라 불리는 비단말 기호에서 시작되며, 이러한 문장 생성 과정을 유도(derivation) 라 합니다.

<number> → <number><digit>    ────── ➀
                  | <digit>               ────── ➁
<digit> → 0 | 1 | 2 | … | 9            ────── ➂

이러한 수에 대한 문법이 있다면, 123 을 다음과 같이 유도할 수 있습니다.

<number> ⇒ <number><digit>                 ─ ➀ 에 의해 <number>를 <number><digit>로 대치
                 ⇒ <number><digit><digit>     ─ ➀ 에 의해 <number>를 <number><digit>로 대치
                 ⇒ <digit><digit><digit>         ─ ➁ 에 의해 <number>를 <digit>로 대치
                 ⇒ 1<digit><digit>                ─ ➂ 에 의해 <digit>를 수 1로 대치합니다.
                 ⇒ 12<digit>                        ─ ➂ 에 의해 <digit>를 수 2로 대치합니다.
                 ⇒ 123                               ─ ➂ 에 의해 <digit>를 수 3으로 대치합니다.

여기에서 시작 기호는 <number> 이며, ⇒ 는 '유도 한다'고 읽습니다.