프로그래밍언어론 - BNF

 갓구글에 검색해도 많은 정보가 나오지 않는다니, 구글에 BNF와 EBNF에 대한 내용을 추가하려고 적고 있다. 학교 후배님들이 보고서 공부를 조금 더 수월하게 하셨으면 좋겠습니다. 😂

  BNF는 우리가 평소에 사용하는 프로그래밍 언어의 문법을 만들어놓은 규칙이라고 보면 된다. 말이 조금 어려운데, 간단하게 생각하면 "int num = 0;"이다 이런 하나의 문장을 컴파일러가 해석하기 위해서 어떠한 규칙을 가지고 있어야 한다. BNF(Backus-Naur Form)는 <assgin> ::= <ident> = <exp>;와 같은 BNF 생성 규칙 예를 가질 수 있다. 방금 적은 "int num = 0;"와 동일하다. 이 생성 규칙의 예의 ::= 기호는 ->와 같은 뜻으로, 왼쪽에서 오른쪽으로 기호를 정의한다는 뜻을 가진다. 하지만 이렇게 말하면 또 어렵다. 예를 한번 볼까?

 위 BNF 생성 규칙을 파스트리로 그린다면 위 그림과 같이 그릴 수 있다. assign이 <id> = <expr>를 정의한다는 것을 쉽게 알 수 있다. 처음 본다면 프로그래밍 언어 문장이 저렇게 파스 트리로 표현된다는 사실 자체가 신선하다.

 이런 생성 규칙이 하나만 있을까? 우리가 사용하는 문법이 많음으로 당연하게 많을 것이다. 현재 <assign>에 대한 유명한 예(검색하면 이 예만 나오는 ...)를 알아보자.

간단한 BNF 예제

 위와 같은 프로그래밍 언어론을 배우지 않았다면, 처음 보는 광경을 보게 된다. 처음보면 어질어질하지만, 이 글이 끝나면 어느정도 친숙해질 것이라고 믿고 있다. 위와 같은 보기 힘든 BNF를 당연히 최적화를 했을 것이다. |(or) 를 사용하여 <exp>와 같이 같은 생성 규칙들은 or 처리를 할 수 있다.

 < >로 둘러쌓인 기호를 논터미널 기호라고 부른다. 어휘 항목(lexeme)은 소스 코드 내에서 의미있는 문자열, 식별자 숫자, 키워드를 의미한다. 터미널 기호는 터미널이라고 부르며 규칙에 포함된 어휘 항목을 말한다.

 이제 한번 생각해봐야한다. 생성 규칙만 있다고 하여 끝일까? 우리가 사용하고 있는 문법, 즉 문장은 저 규칙을 통해 어떻게 나올 수 있을까?(어떻게 유도할 수 있을까?)

 만약 다음과 같은 생성 규칙이 있다고 가정해보자.

 그리고 다음과 같은 문장을 생성 규칙을 유도하여 만들고 싶다고 가정한다.

A = B * ( A + C )

 유도를 하는 방법은 왼쪽 유도, 우측 유도가 있으면 보통 왼쪽 유도를 한다.  아래 예는 왼쪽 유도를 하는 방법이다.

<assign> => <id> = <exp>
             => A = <exp>
             => A = <id> * <exp>
             => A = B * <exp>
             => A = B * ( <exp> )
             => A = B * ( <id> + <exp> )
             => A = B * ( A + <exp> )
             => A = B * ( A + <id> )
             => A = B * ( A + C )
 이와 같이 왼쪽부터 유도를 할 수 있다. 중간에 나오는 ( )는 터미널 기호로 알 수 있다. 이제 유도된 결과를 가지고 Parse tree를 그릴 수 있다. 정확한 의미는 "왼쪽 유도의 결과를 트리 형태로 기술한다"이다.

  <assgin>에 대한 규칙은 우리가 가진 문장에 대해 하나의 파스트리를(하나의 유도 결과를) 가지기 때문에 모호하지 않다고 할 수 있다. 모호하다? 실제로 유도를 해보지 않고 모호하다란 이야기를 쉽게 이해할 수 없다. 유념하고 아래를 따라와보자. 우리가 사용하는 소스코드(문장)에서 모호한 경우가 무엇이 있을까? A = B * A + C의 경우 우리는 자연스럽게 *가 먼저 실행된다는 것을 알 수 있다. 하지만 생성 규칙을 모호하게 짠다면 B*A가 먼저, A+C가 먼저 실행되는 2가지 경우가 나타난다. 먼저 파스 트리를 보자.

 이렇게 하나의 문법에 2개의 파스 트리가 나온다면, 모호하다고 할 수 있고, 생성 규칙이 모호하다는 것이다. 이제 위 파스트리의 생성 규칙을 살펴보자.

어는 부분에서 모호할까? exp가 +으로도 *으로도 갈 수 있기 때문에 모호하다. 이제 이 생성 규칙을 모호하지 않도록 바꿔보자.

 먼저 짚고 넘어가야하는 부분은 모호하지 않는 문법을 만들기 위해서는 좌재귀, 좌인수분해와 같은 지식을 가지고 있다면 더 수월하게 할 수 있다. 이 내용은 BNF와 EBNF의 문법 이후 조금 더 이후에 나오는 내용이다. 그럼으로 현 상황에서 저 생성 규칙을 끌어내기 위해서는 눈치껏 할 수 밖에 없다. 

 눈치껏 바꾸는 방법에 대해서 알기 위해선 왜 이전 생성 규칙이 문제인지 다시 보자. 이전 문제는 두 갈래길이 있기 때문에 *가 먼저 실행되도록 강제할 수 없다. 그렇기 때문에 눈치껏 갈래길을 하나로 강제해야한다. 위는 exp는 +만 있고 또는 term으로 간다. term은 *와 factor로 간다. focotr는 ( <exp> )와 <id>를 가진다. 이렇게 계속 타고 가니 헷갈릴 것이다.

다시 강제하기 위해선 새로운 논 터미널을 가지게 되고 식은 하나만 들어간다. exp도 그렇고, term도 그렇다. 눈치껏이기 때문에 한번 직접 해보면 조금 힘들겠지만 알 수 있을 것이다.