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에 대해 알아보았습니다.