문맥 자유 언어 (Context

Regular Language는 스트링 a와 b를 쌍으로 표현하는 식에 대해서 표현이 불가능합니다. ex) L = {a^mb^m | m >= 0}

따라서, 정규언어는 한계가 있습니다.

또한, Regular Grammar 같은 경우에도, A → x 의 예시로 들어 넌터미널이 존재하지 않거나 마지막에 한 개만 가능한 제약이 있는데, 이를 없애서 Context - Free Language로 만들어줍니다.

Context - Free Language는 G = (V, T, S, P)로 정의되고, 생성 룰 P를 정의합니다.

위 형식에서 A ∈ V, x ∈ (v ∪ T)* 로 정의합니다.

문맥 자유 언어 (Context - Free Language) L이 있을 때, L = L(G)인 문맥 자유 문법 G가 존재합니다.

모든 Regular Language는 Context - Free Language 입니다. ( RL ∈ CFL)

문법에 따라서 유도할 때, 좌측 우선(Leftmost)과 우측 우선(Rightmost)가 있습니다.

ex) G = ({A,B,S}, {a,b}, S, P)

Rule P = S → AB, A → aaA, A → λ, B → Bb, B → λ 일때,

S ⇒ AB ⇒ aaAB ⇒ aaB ⇒ aaBb ⇒ aab (Leftmost)

S ⇒ AB ⇒ ABb ⇒ Ab ⇒ aaAb ⇒ aab (Rightmost)

컴파일러에서는 Parse Tree 라고 부르며, 문법의 생성 룰을 기준으로 트리를 형성합니다.

root Node는 시작 넌터미널로 하고, 각 자식 노드는 루트 룰의 오른쪽 부분의 기호들로 형성됩니다.

leaf Node들은 터미널로, 그 안쪽 부분은 넌터미널로 구성됩니다.

추후 설명할 문제이지만, 유도 트리가 2개 이상으로 구성될 수 있는 모호성 문제가 발생할 수 있습니다.

ex) 유도 트리는 연산자 우선 순위를 정의하기 어려움.

파싱은 w ∈ L(G)인 스트링의 유도 과정을 표현한 것입니다.

유도 트리는 앞서 포스팅 했던 DP에서 사용한 탑 다운과 바텀 업 방식으로 생성합니다.

유도 트리에서 탑 다운은 시작 넌터미널로 부터 트리를 구성하고, 바텀 업 방식은 주어진 스트링을 leaf node에 위치시키고, 루트 방향으로 트리를 구성해서 올라갑니다.

문맥 자유 문법의 특성상 유도 트리는 모호성을 가질수 있습니다. 따라서, 문맥 자유 문법을 정의할 때, 모호성 문제의 가능성을 염두에 두고 정의하여야 합니다.

모든 프로그래밍 언어의 문법은 CFG로 정의되는데, 그 중 Algol 언어 문법 정의에 이 기법을 사용한 Backus와 Naur의 이름을 따, BNF(Backus Naur Form) 이라고 부릅니다.

BNF의 경우, 스트링을 반복적으로 생성하기 위해 재귀적 표현을 사용하고, 스트링 그룹을 표현하기 위해서 넌터미널을 이용합니다.

EBNF는 여기에 메타 문자를 추가적으로 사용하여 표기합니다.

- { } : 0개 이상의 반복적인 시리즈 (Recursive Expression)

- ( ) : 여러 리스트 중 하나를 선정 (Grouping)

- [ ] : Optional, List 중 한개 OR 0개 선정

Luinesse