CFG (Context Free Grammar)

프로그래밍 언어는 CFG (Context Free Grammar) 로 나타낼 수 있어요

오늘은 C언어의 문법을 BNF 로 나타내볼거에요. BNF 는 CFG의 한 갈래로 일단 여기서는 이 둘은 같다라고 생각해도 될거같아요.

 

세상에 "규동" 이라는 언어가 있어서 이 언어는 "규"와 "동" 이 두 글자만 사용할 수 있는 언어에요.

규칙은 모든 "규"는 "동" 보다 앞에 있어야 한다.

즉 모든 "규"가 "동" 보다 앞에있는 세상 모든 문자열은 "규동" 언어로 표현됐다. 라고 말할 수 있어요

예를 들면 "규동", "규규동", "규동동동", "규", "동" 이 이런 경우에요.

그럼 "규동" 언어가 아닌건 뭐가 있을까요?

"규동규", "동규", "규규규규규규동규" 이런 경우겠죠

 

이렇게 어떤 언어를 말로 표현하는것도 가능은 하지만 C언어처럼 복잡한 언어를 말로 표현하려면 하루 종일 말 해도 부족할거에요

그래서 언어를 표현하는 방법 중 BNF를 사용해볼겁니다.

 

기본적으로 <A> => s

이런 꼴을 갖고 있는데 <> 안에 있는 문자는 변수, 그렇지 않은 문자는 상수(terminal) 이라고 해요

=> 는 변환을 의미해서

<A> => s 는 <A> 라는 변수는 s라는 상수로 변환될 수 있다. 라는 뜻이에요

변환의 정확한 용어는 derivation 에요.

derivation은 모든 변수가 terminal 이 되었을 때 끝나게돼요. 그럼 규동 언어를 표현하는 언어를 정의해볼게요

 

<KyooDong> => <Kyoo><Dong>

<KyooDong> => <Kyoo>

<KyooDong> => <Dong>

<Kyoo> => 규<Kyoo>

<Kyoo> => 규

<Dong> => 동<Dong>

<Dong> => 동

 

자 어떤가요? 이해가 되시나요?

<KyooDong> => <Kyoo><Dong>

<KyooDong> => <Kyoo>

<KyooDong> => <Dong>

 

<KyooDong>이 세 개나 되서 당황스럽겠지만 이건 셋 중에 아무거나로 변할 수 있다! 라는 뜻이에요

이걸 짧게쓰면 다음과 같아요

<KyooDong> => <Kyoo><Dong> | <Kyoo> | <Dong>

<Kyoo> => 규<Kyoo> | 규

<Dong> => 동<Dong> | 동

 

이게 규동 언어를 적절히 표현했는지 확인해볼게요

"규규규동동" 을 만들어보죠

<KyooDong> => <Kyoo><Dong>

    => 규<Kyoo><Dong>

    => 규규<Kyoo><Dong>

    => 규규규<Dong>

    => 규규규동<Dong>

    => 규규규동동

 

"규" 를 만들어볼까요?

<KyooDong> => <Kyoo>

    => 규

 

이 언어가 틀렸음을 보이려면 "규동규" 같이 규동 언어에 속하지 않은 문자열을 만들 수 있음을 하나라도 보이면 돼요

규동규를 만들어 볼까요?

<KyooDong> => <Kyoo><Dong>

    => 규<Dong>

    => 규동

 

불가능하죠? 이런식으로 하나씩 하면서 안되는걸 하나라도 발견하게 된다면

<KyooDong> => <Kyoo><Dong> | <Kyoo> | <Dong>

<Kyoo> => 규<Kyoo> | 규

<Dong> => 동<Dong> | 동

 

는 규동 언어를 잘못 표현했다 라고 말할 수 있어요.

잘못된 문자열을 찾지못했다면 위 규칙을 규동 언어를 CFG로 표현했다. 말할 수 있는거죠

 

지금까지 CFG에 대해 알아보았습니다.