Backus-Naur Form(BNF)의 표현법

    Backus-Naur Form을 알아보기 전에 CFG가 무엇인지 알아야 한다. CFG는 Context-Free Grammar로 단어 그대로 해석해보면 "문맥으로부터 자유롭다"는 것이다. 아래 문장을 봐보자.

 

나는 배를 먹었더니 배가 아프다.

 

    이 문장을 보고 우리는 앞의 배는 먹는 배, 뒤의 배는 우리 신체를 가리키는 것을 문맥을 보고 알 수 있다. "배를 먹는다"로부터 먹는 배를, "배가 아프다"로부터 신체임을 우리는 문맥상으로 파악해야한다. 이러한 언어를 "Context Sensitive 하다"고 한다. 프로그래밍 언어가 이렇게 Context Sensitive하다고 생각해보자. 그렇다면 프로그래밍한 코드를 컴퓨터가 해석하게 만드는 것은 굉장히 어려울 것이다. 그렇기 때문에 프로그래밍 언어는 앞뒤 단어에 따라 의미가 달라지지 않는  CFG를 사용한다.

 

    BNF는 John  Backus가 ALGOL 58언어의 문법을 표기하기 위해 만들었고 이후 Peter Naur가 ALGOL60언어의 내용으로 보완하여 발표하였다. 처음엔 사람들에게 수용되지 않았지만 지금까지도 프로그래밍 언어 구문을 확실하게 표기하는 방법으로 여겨진다. 

    Grammar는 Rule들의 집합이다.  BNF에서 이러한 Rule들은 아래와 같이 3가지 기호로 이루어져 있다.

1. -> : Rule(production)
2. <> : Non-terminal
3. | : Or

    1번째 표현은 규칙을 나타내는 표현으로 rule이나 production으로 불린다. 화살표의 왼쪽은 LHS(Left Hand Side)라고 하며 정의될 개념이 존재한다. 화살표의 오른쪽은 RHS(Right Hand Side)라고 하며 기호와 개념들로 이루어진 정의가 존재한다. 따라서 LHS는 RHS로 정의된다고 할 수 있다.

    2번째 표현은 Non-terminal Symbol로 <>사이에 정의될 원하는 개념을 적는다. nonterminal symbol은 rule의 왼편에 위치하여 lexeme과 token등 terminal이나 또 다른 Non-terminal들에 의해 정의된다. 또한 Non-terminal symbol은 두 개 이상의 정의를 가질 수 있다.

    3번째 표현은 OR로 2번의 Non-terminal이 두 개 이상으로 정의될 때 rule의 오른편에서 이 '|' 기호를 이용해 각 정의들을 구분하여 한 번에 rule을 표현할 수 있게 한다. 예를 들어 아래와 같이 하나의 Non-terminal symbol에 여러 개의 rule이 존재할 경우 아래와 같이 나타낼 수 있다.

<expression> -> <var> + <var>
<expression> -> <var> - <var>
<expression> -> <var> * <var>
<expression> -> <var> / <var>

<expression> -> <var> + <var> | <var> - <var> | <var> * <var> | <var> / <var>

우리가 프로그래밍을 할 때 사칙연산을 사용할 경우 컴파일러는 위의 rule들 중에 동일한 문법이 존재하지 않는지 판단하여 문법이 맞는지 확인할 수 있다. 만약 존재하지 않을 경우 syntax에러를 주며 컴파일 에러가 발생하게 된다.