[PL] CFG, BNF
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을 한번 더 참조하게 한다.
이를 통해 / 연산자에 -보다 높은 우선순위를 부여할 수 있고 모호성을 해소할 수 있다.