형식 언어

형식 언어와 형식 문법

형식 언어(formal language)는 문장의 집합입니다. 문장은 기호(symbol)로 구성된 기호열로 볼 수 있으며, 그 중 어떤 기호열이 그 언어에 속하는지는 형식 문법(formal grammar)에 의해 결정됩니다.

형식 문법을 표기하는 데에는 네 가지 요소가 필요합니다.

비단말 기호(nonterminal symbol)의 집합 $V_N$
단말 기호(terminal symbol)의 집합 $V_T$
생성 규칙(production rule)의 집합 $P$
시작 기호(start symbol) $S$

참고로 기호와 기호열을 표현할 때 흔히 사용되는 관례가 있는데, 이 글에서도 이 관례를 따르겠습니다.

비단말 기호는 로마자 대문자($A$, $B$, $C$, …)로 표현합니다.
단말 기호는 로마자 소문자($a$, $b$, $c$, …)로 표현합니다.
기호열은 그리스 문자 소문자($\alpha$, $\beta$, $\gamma$, …)로 표현합니다.
빈 기호열은 $\epsilon$으로 표현합니다.
때때로 문장의 맨 끝을 나타내는 특수한 단말 기호 $$$를 사용하기도 합니다.

생성 규칙

생성 규칙은 형식 문법으로 새로운 문장을 생성해내는 규칙입니다. 생성 규칙은 다음과 같은 형태를 가집니다.

\[ \alpha \to \beta \]

이는 문장 내에서 $\alpha$를 $\beta$로 치환할 수 있다는 뜻입니다. 예를 들어 어떤 형식 언어가 생성 규칙 $xA \to xBy$를 가지고, 문장 $wxAz$가 형식 언어에 포함되면 생성 규칙을 적용한 문장 $wxByz$도 형식 언어에 포함됩니다.

여러 생성 규칙이 동일한 좌변을 가지면 하나로 합쳐 쓸 수 있습니다. 예를 들어 두 생성 규칙

\begin{align*} A &\to aAb \\ A &\to Bb \end{align*}

은 다음과 같이 하나로 합칠 수 있습니다.

\[ A \to aAb \mid Bb \]

치환을 통해 문장을 변환하는 것을 유도(derivation)라고 합니다. 치환을 한 번 하여 $\alpha$에서 $\beta$를 얻을 수 있으면 $\alpha \Rightarrow \beta$로 표기합니다. 치환을 한 번 이상 하는 것은 $\alpha \stackrel{+}{\Rightarrow} \beta$로 표기하고, 비슷하게 치환을 0번 이상 하는 것은 $\alpha \stackrel{*}{\Rightarrow} \beta$입니다. 반대로 유도 과정을 역으로 추적하는 것은 축약(reduce)이라고 합니다.

비단말 기호와 단말 기호

비단말 기호는 생성 규칙을 통해 치환할 수 있는 기호입니다. 단말 기호는 그 반대가 되겠죠.

\begin{align*} A &\to aAb \\ A &\to Bb \\ aB &\to ac \\ \end{align*}

위 문법에서 $A$와 $B$는 비단말 기호이고, $a$, $b$, $c$는 단말 기호입니다.

시작 기호

시작 기호는 형식 언어의 문장을 생성하기 위한 출발점입니다. 모든 문장은 시작 기호로부터 유도를 통해 만들어집니다. 시작 기호는 비단말 기호에 속합니다.

촘스키 위계

언어학자 놈 촘스키(Noam Chomsky)는 형식 문법을 표현 가능한 범위에 따라 네 수준으로 나누었습니다. 상위 문법은 하위 문법을 포함합니다.

무제약 문법

무제약 문법(unrestricted grammar)은 생성 규칙에 아무런 제약이 없는 문법입니다. 즉, 어떤 기호열이든지 다른 기호열로 치환할 수 있습니다. 단, 빈 기호열은 치환할 수 없습니다. 무제약 문법을 사용하는 언어는 재귀적 열거 가능 언어(recursively enumerable language)라고 합니다.

문맥 의존 문법

문맥 의존 문법(context-sensitive grammar)은 생성 규칙이 다음과 같은 형태를 가집니다.

\[ \alpha A \beta \to \alpha \gamma \beta \]

한 마디로 비단말 기호 $A$를 다른 기호열 $\gamma$로 치환하되, $A$의 앞뒤 문맥($\alpha$와 $\beta$)을 고려하여 치환해야 한다는 것입니다.

문맥 자유 문법

문맥 자유 문법(context-free grammar)은 생성 규칙이 다음과 같은 형태를 가집니다.

\[ A \to \alpha \]

문맥 의존 문법의 생성 규칙과 비교하면 $A$를 치환할 때 앞뒤 문맥을 고려하지 않아도 된다는 점에서 다릅니다. 대부분의 프로그래밍 언어는 문맥 자유 문법을 따르는 언어입니다. 때문에 형식 언어론에서 가장 많이 다루는 문법이기도 하고요.

정규 문법

정규 문법(regular grammar)은 생성 규칙이 다음 둘 중 하나의 형태를 가집니다.

좌선형(left-linear) 문법

\[ A \to Bt \quad \text{or} \quad A \to t \]

우선형(right-linear) 문법

\[ A \to tB \quad \text{or} \quad A \to t \]

좌선형 문법과 우선형 문법은 동일한 문법을 표현하는 다른 형태일 뿐입니다. 좌선형 문법과 우선형 문법은 항상 서로 변환할 수 있습니다.

형식 문법의 다른 분류

촘스키 위계 외에도 형식 문법을 분류하는 방법이 더 있습니다.

좌재귀와 우재귀

어떤 비단말 기호 $A$에 대해 $A \stackrel{+}{\Rightarrow} A\alpha$가 가능하면 형식 문법이 좌재귀(left-recursive)라고 합니다. 반대로 $A \stackrel{+}{\Rightarrow} \alpha A$가 가능하면 우재귀(right-recursive)라고 합니다. 생성 규칙 자체가 $A \to A\alpha$ 또는 $A \to \alpha A$를 포함하는 경우에는 직접(direct) 좌재귀 또는 우재귀라고 부릅니다. 그 외에는 간접(indirect) 좌재귀 또는 우재귀입니다.

좌재귀 또는 우재귀인 형식 문법은 문법을 분석할 때 큰 문제를 일으킬 수 있습니다. 보통은 한쪽만 문제가 되기 때문에 좌재귀를 우재귀로 변환하거나 그 반대로 변환하는 작업을 합니다. 문맥 자유 문법에서 직접 좌재귀를 제거하는 방법은 다음과 같습니다.

먼저 $A$에 대한 생성 규칙을 좌재귀인 것과 좌재귀가 아닌 것으로 나눕니다.

\begin{align*} A &\to A\alpha_1 \mid A\alpha_2 \mid \cdots \mid A\alpha_n \\ A &\to \beta_1 \mid \beta_2 \mid \cdots \mid \beta_m \end{align*}

여기서 각 $\beta$는 $A$로 시작하지 않는 기호열입니다. 그리고 새로운 비단말 기호 $A’$을 추가하여 $A$에 대한 생성 규칙을 다음과 같이 변환합니다.

\begin{align*} A &\to \beta_1A' \mid \beta_2A' \mid \cdots \mid \beta_mA' \\ A' &\to \alpha_1A' \mid \alpha_2A' \mid \cdots \mid \alpha_nA' \mid \epsilon \end{align*}

문맥 자유 문법의 간접 좌재귀는 생성 규칙의 우변에 있는 비단말 기호를 치환하여 직접 좌재귀로 바꿀 수 있습니다.

\begin{align*} A &\to Bb \\ B &\to Cc \\ C &\to Aa \mid d \end{align*}

위 예시에서는 첫째로 비단말 기호들을 $A$, $B$, $C$ 순서로 정렬합니다. 그 다음 각 생성규칙에 대해 좌변의 비단말 기호보다 순서가 앞인 비단말 기호가 우변에 올 경우 그 비단말 기호를 생성 규칙에 따라 치환합니다. 마지막 생성 규칙의 우변에 $A$가 등장하므로 치환해봅시다.

\begin{align*} A &\to Bb \\ B &\to Cc \\ C &\to Bba \mid d \end{align*}

한 번 더 치환하면

\begin{align*} A &\to Ba \\ B &\to Cb \\ C &\to Ccba \mid d \end{align*}

이제 직접 좌재귀를 앞서 설명한 방법으로 제거하면 됩니다.

\begin{align*} A &\to Ba \\ B &\to Cb \\ C &\to dC' \\ C' &\to cbaC' \mid \epsilon \end{align*}

우재귀는 좌재귀와 비슷한 방법으로 제거할 수 있습니다.

모호한 문법

모호한 문법(ambiguous grammar)은 하나의 문장에 대해 두 가지 이상의 유도가 가능한 문법입니다. 다음 문법은 매우 모호한 문법의 예시입니다.

\begin{align*} S &\to a \mid SS \mid SSS \end{align*}

이 문법은 $a$를 하나 이상으로 구성된 문장을 생성할 수 있는데, $a$가 많아지면 너무나도 많은 유도 방법이 존재하게 됩니다.

Compiler