[컴파일러] 구문을 나타내는 방법, 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