Context-Free Grammar 그리고 CFG의 반대말

Context-Free Grammar 줄여서 흔히 CFG라고 부르고 우리나라 말로는 문맥 자유 문법이라고 하는 친근해지기 어려운 용어에 대해 알아 본다.

일단 Context-Free의 의미에 익숙해져야 한다. 이걸 문맥 자유라고 해석하니 쉽게 와닿지 않는다. 하지만, 카페인-프리, 슈가-프리 이런 단어들을 떠올려 보자. 카페인 자유, 슈가 자유가 아니다. 카페인이 없음, 설탕이 없음 이란 뜻이다.
즉, CFG의 Context-Free는 말그대로 'Context가 아예 없다' 는 뜻으로 이해하면 된다.

이제 이게 실질적으로 무엇을 의미하는지 코드로 설명하겠다.

break;

for( ; ; )
{
  break;
}

if(1 < 5)
{
  continue;
}

 

이 C 코드는 에러 투성이다. break; 가 코드 시작하자마자 나오고, continue는 if 블럭에 있다.

하지만!!! CFG 상으로는 하나도 틀린 곳이 없다.

그렇다. break, continue가 반복문 내에 있어야 한다는 제약은 CFG 관점에선 존재하지 않는다. 그저, break, continue를 오타 없이 잘 썼냐만 보는 것이다.

 

인간의 언어, 즉 자연어에도 이 규칙은 똑같이 적용된다. CFG 자체가 언어이론에서 나온 것이기도 한데, 짧은 영어 대화를 살펴보자.

• Do you want some coffee?
• I'm a little boy.

전혀 맥락이 맞지 않아서 대화가 성립이 안된다.
하지만!!! CFG 상으로는 하나도 틀린 곳이 없다.

 

컴파일러 분야에서 CFG는 구문분석(Syntax Analysis, 간단히 Parsing) 단계에 깊숙하게 쓰인다. 그냥 파서는 CFG 기계를 만든 것으로 봐도 된다. 그렇다면 위의 코드에서 break / continue 에러를 뱉어낼 때는 언제인가?

일반적으로는 의미분석(Semantic Analysis) 단계에서 문맥 오류를 짚어낸다(물론 컴파일러도 소프트웨어이기에 정답은 없음).

의미분석단계에서 break / continue가 for문이나 while 문 바깥에 있다면 즉각적으로 에러를 발생시킨다.

 

CFG와 달리 맥락을 보는 단계를 지칭하는 표준 용어는 아쉽지만 존재하지 않는다. 그저 컴파일러 서적이나 문서에서 Context-sensitive Rules, Context-dependent, Context-sensitive Constraints 등 다양하게 불리고 있는 것 같다. 즉, CFG의 반대말은 딱히 존재하진 않는다.

개인적인 생각으로는 아마도 자연어 이론에서 맥락에 대한 룰을 집대성하는 것은 화성을 테라포밍하는 것만큼 어려운 일이라서 특별히 정의를 내리지 못한 것이 아닐까 한다. 당장 우리의 일상대화에서 나타나는 맥락을 체계화할 수 있다고 자신하는 사람이 있을까? AI도 인간만큼 맥락을 파악할 수 있으려면 얼마나 시간이 필요할지 모르는데...

어쨌든 컴퓨터 언어가 context를 규칙화 할 수 있는 이유는 자연어와 달리 컴퓨터 언어 명세에 의한 표현 밖에 할 수 없기 때문이다. 정해진 틀 안에서 한정된 방식으로만 코딩을 해야 하기 때문에 가능하다는 뜻이다.

 

여기서 한가지 궁금한 점이 생길 수 있다. 컴파일러에서 문맥무관분석(구문분석)과 문맥의존분석(의미분석)을 함께 처리하면 좋을텐데 굳이 왜 나누는 걸까? 라는 궁금증이다. 마지막으로 이 부분을 짚고 끝마치도록 한다.

구문분석, 의미분석 이 두 단계는 모두 어렵다. 물론, 의미분석이 훨씬 어려운 단계지만 구문분석도 언어가 방대해지면 꽤 어렵다. 어려운 것끼리 합치면 더 어려워지기 때문에 분리한 것이다. 요즘 말로는 관심사 분리(Separation of Concerns, SoC)라고 생각하면 편하다.

게다가, 구문분석은 컴파일러 분야의 석학들 덕분에 자동화가 가능해졌다. Yacc나 Bison 등의 도구가 구문분석 자동화 이론을 체현한 것이다. C, Java, Python, JavaScript 등등 유수의 언어들도 자체적인 자동화 도구를 보유하고 있다. 그렇기 때문에 더더욱 구문분석과 의미분석은 정확하게 분리되어 있다.

같은 의미로 CFG-문맥 자유 문법에 대한 검사는 자동화가 충분히 가능한 영역이라고 보면 된다.