CFG(Context Free Grammar)
문맥 자유 문법에 대해 간단하게 말하자면 문맥에 따라, 앞뒤 단어에 따라 의미가 달라지지 않는 문법을 말한다.
대부분의 프로그래밍 언어는 CFG를 사용한다.
문맥 자유 문법은 다음과 같이 정의한다
G = (V,T,P,S)
V - 변수 혹은 비단말(non Terminal)
T - 단말(Terminal)의 집합, 앱실론 ε을 포함
P - 생성(Productions) 규칙 집합
S 는 시작 변수(start variable)
Terminal과 Non terminal의 개념이 있다
Terminal
- 단말 기호 집합
- 다른 기호로 유도가 불가능함
Non terminal
- 비단말 집합, 언어 안에서 다른 문자를 만드는 중간 과정
- 다른 기호로 유도할 수 있음
다시 CFG의 정의로 돌아가자면
문법 G는 모든 생성 규칙이
A -> a
를 따르는 문법을 말한다
A는 V의 원소(non Terminal)
a는 V 혹은 T의 원소이다
BNF를 통해서 이해해보자
BNF(Backus–Naur form)
문맥 자유 문법(CFG)을 나타내기 위한 표기법
위에 A -> a 를 따르기 때문에
LHS(Left Hand Side)는 non terminal이고 RHS(Right Hand Side)는 terminal과 non terminal의 문자열이다
-> : Production rule
<> : Non terminal
| : Or
좌측 유도에 의해 <program>을 유도한 과정이다.
<stmts>는 자기 자신으로 재귀적으로 정의되는 모습을 볼 수 있다.
컴파일러 또한 재귀 파서를 통해 파서 트리를 생성한다.
위의 과정은 이런 parse tree로 그려볼 수 있는데
여기서 리프 노드의 값
a = b + const
유도된 sentence이다
유도(Derivation)
시작 심볼부터 시작해 Non Terminal X에 생성 규칙(productions)를 적용해 Y1, Y2... Yn으로 대치하는 과정이다
S는 aS혹은 b로 정의되기 때문에 재귀적으로
ab, aab, aaab.. 등으로 정의할 수 있지만
aba로 정의될 수는 없다.
E -> E * E | E + E | (E) | N
N -> N D | D
D -> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
좌측 유도(좌측 non terminal 먼저 terminal로 유도)
E
E + E
N + E
D + E
3 + E
를 통해 좌측의 E를 terminal D의 3으로 유도하고
비슷한 원리도
3 + E
3 + E * E
3 + N * E
3 + 4 * E
.
.
3 + 4 * 5
로 유도할 수 있다
Ambiguous
위의 식을 우측 유도 해도 똑같은 문장이 유도되겠지만
파스 트리를 만들었을 때 다른 모양이 만들어진다
유도한 3 + 4 * 5로 보았을 때
좌측유도 시 좌측의 트리처럼
3의 깊이가 더 얕다 즉 3이 앞에 온다
우측유도 시 우측의 트리 모양이 된다.
연산자 우선순위로 봤을 때 *가 +의 앞에 와야 하기 때문에 파서 입장에서 좌측의 트리는 잘못됐다.
이처럼 좌측 유도, 우측 유도 중 하나만 써도 두개 이상의 트리를 가지는 문법은 Ambiguous, G는 모호하다
라고 표현한다.
해당 BNF를 각각 우측유도 | 좌측유도를 통해 트리로 바꾸면
모호한 상태인데
<OP>를 / 혹은 - 로 정의하여 연산자 간 우선순위를 모호하게 정의한 위의 예시와 달리
<term>에서 / 연산자가 상수(const)와 직접 연결된 구조이고,
- 를 상수로 유도하기 위해서는 term을 한번 더 참조하게 한다.
이를 통해 / 연산자에 -보다 높은 우선순위를 부여할 수 있고 모호성을 해소할 수 있다.