BNF

고급 프로그래밍 언어로 작성된 프로그램은 결국 기계어로 변환되어야만 컴퓨터에서 실행될 수 있다. 이 변환 작업을 하는 별도의 프로그램이 컴파일러compiler이다. 안타깝게도 컴파일러는 융통성이 없다. 프로그램을 대충 작성하더라도, 알아서 기계어로 변환해주는 컴파일러는 아직까지 없다. 문법에 맞게 작성한 프로그램만 기계어로 변환될 수 있다.

어떤 언어의 문법을 설명하기 위해서는 구구절절이 글로 적는 방법이 있다. 예를 들어 한국어를 생각해보자. 다음과 같이 문법을 설명할 수 있다.

문장은 주어, 동사의 순서이다. 또는,
문장은 주어, 목적어, 동사의 순서이다. 또는,
문장은 주어, 부사구, 동사의 순서이다. 또는,
문장은 목적어, 동사의 순서이다. 또는, ...

프로그래밍 언어도 마찬가지로 이렇게 문법을 기술할 수 있다. 가능한 경우를 모두 고려하여 일일이 설명하는 식이다. 하지만 존 배커스는 프로그래밍 언어의 문법을 체계적으로 정리하고 싶었다. 그래서 알골 언어 설계에 참여했을 때, 문법을 정리하기 위한 표기법을 만들어 제안했다. 그의 표기법은 처음에는 Backus Normal Form의 약자로 불렸으나 후에 Backus-Naur Form의 약자로 수정되었다. 아래의 것은, 알골 60 언어의 문법을 BNF로 표현한 것 중 일부이다.

<identifier> ::= <letter>|<identifier><letter>|<identifier><digit>
<letter> ::= A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z
<digit> ::= 0|1|2|3|4|5|6|7|8|9

< >로 표기된 것은 문법에 의해 정의되는 것임을 의미한다. 위에서 볼 수 있듯이 알파벳과 숫자는 본래 존재하는 것이므로 < >로 둘러싸여 있지 않다. | 기호는 선택지or를 의미한다. 따라서 위의 표기는 다음과 같이 해석된다.

명칭(identifier)은 문자(letter)이거나, 명칭에 문자가 바로 붙어 있는 것이거나, 명칭에 숫자(digit)가 바로 붙어있는 것이다. 문자(letter)는 A부터 Z까지의 알파벳 중 하나이다. 숫자(digit)는 0부터 9까지 중 하나이다.

그렇다면 A는 명칭인가? 그렇다. 0은 명칭인가? 그렇다. K4는 명칭인가? 그렇다. AB12Z는 명칭인가? 그렇다. 3PY는 명칭인가? 그렇지 않다. 위의 문법을 따른다면 절대로 명칭은 숫자로 시작할 수 없다. a2z는 명칭인가? 그렇지 않다. 알파벳 소문자는 위에서 정의한 문자<letter>에 포함되어 있지 않다.

A -> <letter> -> <identifier>
0 -> <digit> -> <identifier>
K4 -> <letter><digit> -> <identifier><digit> -> <identifier>
AB12Z -> <letter><letter><digit><digit><letter>
      -> <identifier><letter><digit><digit><letter>
      -> <identifier><digit><digit><letter>
      -> <identifier><digit><letter>
      -> <identifier><letter>
      -> <identifier>
3PY -> <digit><letter><letter>
    -> <digit><identifier><letter>
    -> <digit><identifier>
    -> ?
a2z -> ?<digit>?

BNF 표기법은 프로그래밍 언어의 문법을 군더더기 없이 완벽하게 기술할 수 있었기 때문에 알골 언어 이후에 등장하는 많은 프로그래밍 언어들에서 적극적으로 도입되었다. 특히, BNF로 표현된 문법을, 컴파일러의 중요한 단계에 해당되는 파서parser로 자동 변환해주는 yacc 프로그램이 등장하면서 BNF 표기법의 효용은 더욱 커졌다.

1 2 3 4 5