[컴파일러] 구문을 나타내는 방법, Context Free Grammar (CFG, 문맥자유문법)
▶ 서론 겸 사전지식
세상 언어를 표현하는 문법은 네단개로 표현할 수 있다 (by Chomsky)
recursively enumerable ⊃ context-sensitive ⊃ context-free ⊃ regular
이때 가장 오른쪽의 regular, 정규언어는 세상의 모든 언어를 표현할 수 없다.
흔한 예를 들어, 괄호 구조(), {}는 열린괄호와 닫힌괄호의 수가 동일해야 한다. 하지만 정규표현식을 통해서는 특정 요소의 개수를 파악할 방법이 없다. 즉, 정규표현식으로는 괄호와 같은 nested 구조를 표현할 수 없다.
+ 또한 FSA로 나타낼 수도 없다는 것도 중요하다.
한편 regular language를 포괄하는 context-free language는 nested 구조를 표현할 수 있다.
즉 세상의 더 많은 언어를 표현할 수 있다는 것이다.
context-free 언어는 regular 언어처럼 regular expression으로 나타내는 것이 아닌, terminal symbol과 non-terminal symbol의 관계로 언어를 표현하는 방식이다.
오늘 이 context-free language에 대해 공부할 것이고,
그럼 가장 먼저 terminal symbol과 non-terminal symbol이 무엇인지 먼저 알아야겠다.
- 간단한 참고: regular과 context free 차이
예를 들어 if (a == b) then c = 4 else c = 5 라는 문장이 있다고 하자.
regular language는 if, a, ==, b 등 토큰을 표현하는 것이고,
context free language는 if ~~ then ~~ else 구조라는 것을 표현하는 것이다.
즉, 문장은 context free 문법으로 기술할 수 있다.
문장을 context free 문법으로 기술하면 여러 심볼들로 기술하게 되는데,
terminal 심볼이랑 non-terminal 심볼이 있다. 이게 뭔지는 아래서 보자.
▶ 참고: CFG를 공부하게 된 계기
컴파일러개론을 공부하면서다.
컴파일러 전반부의 구조를 보면, 컴파일 대상 source는 "어휘분석 / 구문분석 / 의미분석"의 3가지 분석 과정을 거쳐 추상구문트리를 만들게 된다.
그 중 어휘분석은 지난 주차에 공부했고, 지금은 구문분석을 배우고 있다.
구문분석에서 던져야 할 질문은 다음과 같다.
1. 문법을 기술하는 방법 (언어제작자 책임)
2. 주어진 input이 기술된 문법에 맞는지 판별하는 방법 (컴파일러 제작자 책임)
그 중 1번질문인 '문법을 기술하는 방법'이 바로 context free grammar다. 그래서 공부하고 있다.
참고로 2번은 CFG로 기술된 문장들을 판별해내는 방법, 즉 구문분석의 핵심에 대한 이야기다.
다음 포스팅에 작성하겠다.
▶ CFG, context free grammar, 문맥자유문법
개요
∨ 자연어를 표현하기 위해 도입된 문법
: 간단 & 이해 쉬움
∨ 비효율적 부분들이 존재하며, 이러한 것들은 제거 대상이다.
: 모호한 문법, 불필요한 생성규칙(ε-생성규칙, 단일생성규칙), 백트래킹, left-recursion
: 제거 방법은 뒤에서 알아보도록 하자.
Context Free Grammar
context free grammar는 다음과 같은 요소들로 구성된다.
문법 G = (N, T, P, S)
N : Non-terminal symbol
T : Terminal symbol
P : 생성규칙
S : 시작(Start)심볼 (non-terminal임)
- 생성규칙 P
어떤 문법을 생성규칙들로 기술하는데,
그 모든 생성 규칙이 N -> x로 표현될 때 그 문법을 context free grammar라고 한다.
※ N은 nonterminal symbol
※ x는 nonterminal OR terminal이 0번이상 나타난 표현, 즉 x ∈ (N∪T)*
예를 들어 다음 문법은 context free grammar다.
S -> E
E -> E+E | E*E | (E) | a
- Non-terminal symbol
: 대문자로 나타낸다. (예시에서 S, E)
: 시작 심볼은 특히 S로 표기한다.
: 중간 과정 심볼이다.
- Terminal symbol
: 소문자 (예시에서 a)
: 숫자 '0'~'9'
: 구분자 ; () 등
: 연산자기호 + - 등
: 따옴표 사이의 문법 심볼 'if' 'then' 등
: 어휘분석할 때 배운 token이랑 같은 개념이다.
++ plus ++
구문분석시 non-terminal을 하나씩 없애가며 최종적으로 terminal symbol만 남기게 된다.
다시말해, terminal symbol 'a'가 어떤 언어(문장)라면, 기술된 context free grammar에 따라 a를 남길 수 있다면 그 언어(문장)는 CFG에 따라 잘 작성된 것이다.
여기선 이렇게만 언급하고 좀 더 자세한 구문분석 방법에 대해서는 다음 포스팅에 정리하겠다.
++ plus ++
시작 심볼 S는 Non-terminal이고, 생성 규칙(N -> P)들은 시작 심볼로부터 파생되어간다.
파생되는 심볼은 x ∈ (N∪T)* 이 된다.
다시 말해서 Teminal, Non-terminal, Empty String들이 파생된다.
예를들어 구문 S->(S), S->ε 를 보자. 생성규칙은 P = {S->(S), S->ε}이다.
S -> (S)에서 (S)를 보면, S는 non-terminal이고 ( )는 terminal symbol이다.
ε는 empty string이다.
이렇게 "구문을 나타내는 방법, Context Free Grammar (CFG, 문맥자유문법)"을 간단히 이해해보았다.
참조: https://talkingaboutme.tistory.com/entry/Study-Context-Free-Grammar-CFG