문맥 자유 문법 (Context Free Grammar, CFG)

개요

브라우저의 동작 과정 중 렌더링 엔진은 사용자에게 요청받은 문서를 파싱해서 화면에 보여주는 역할을 한다. HTML 문서를 파싱할 때 사용되는 파서의 종류는 문법에 따라 크게 두가지로 나뉘는데 이는 HTML을 파싱하는 파서와 CSS 또는 JavaScript를 파싱하는 파서이다. 왜냐하면 HTML은 언어 자체의 너그러운 속성과 사용자의 변경에 의한 재파싱 등 신경써줘야할 부분이 많기 때문에 문맥 자유 문법에 의해 쉽게 정의할 수가 없다. 그렇다면 문맥 자유 문법이란 무엇일까?

문맥 자유 문법

우리가 영어 문장에서 문장의 의미를 이해하기 위해서 영어 문법을 이해하고 있어야 하는 것이 당연하듯이 파서 또한 프로그래밍 언어를 이해하기 위해서는 프로그래밍 언어 정의에 사용된 문법을 이해하고 있어야한다. 대부분의 프로그래밍 언어는 문맥 자유 문법을 기반으로 정의되어 있다. 문맥 자유 문법은 촘스키 위계의 type-2에 해당하는 문법이다.

촘스키 언어 계층은 정규 언어, 문맥 자유 언어, 문맥 의존 언어, 귀납적 가산 언어 4계층으로 형식 언어(특정한 법칙들에 따라 적절하게 구성된 유한한 길이의 문자열의 집합)를 규정한다. 

 

촘스키 위계

문맥 자유 문법 G는 G=(V, T, P, S) 의 순서쌍으로 정의되며, 각 원소의 의미는 아래와 같다.

• V : nonterminal의 유한집합. nonterminal은 언어에 대한 계층적 구조를 부여하는 역할을 한다.
• T : terminal의 유한집합. terminal은 더 이상 다른 terminal이나 nonterminal로 유도가 불가능하다. V와 T는 서로소이다.
• P : production(생성규칙)의 유한집합. 문법의 생성규칙은 nonterminal과 terminal들이 조합되어 문자열을 생성할 수 있는 방법을 명시한다.
• S : 문법에서는 한 개의 nonterminal을 시작 기호(start symbol)로 갖는다. S는 해당 문법의 시작 기호를 나타내며, 문법은 항상 시작 기호로부터 시작된다.

문맥 자유 문법의 정의에서 생성 규칙은 다음과 같이 정의된다. 아래의 생성규칙을 이해하기 위해서는 언어 도메인에서의 연산에 대한 이해가 필요하다. 

 

 

문맥 자유 문법에서 생성규칙의 가장 큰 특징은 생성규칙의 좌변에는 항상 1개의 nonterminal만 올 수 있다는 것이다. 하나의 nonterminal만 고려하여 문자열을 생성하기 때문에 문맥에 자유롭다는 의미에서 문맥 자유 문법이라고 한다.

 

참고:

https://ko.wikipedia.org/wiki/%EB%AC%B8%EB%A7%A5_%EC%9E%90%EC%9C%A0_%EB%AC%B8%EB%B2%95

https://untitledtblog.tistory.com/93