[컴파일러] 문법

21 Oct 2018

Reading time ~4 minutes

BNF

BNF는 프로그래밍 언어의 구문을 정의하는 방법으로 논 터미널(함수)과 터미널(상수)로 구성됩니다. 그리고 이러한 확장 방식으로 EBNF가 있습니다. EBNF는 ‘extended’ BNF를 의미하며 optional(선택 가능한), selection(~중에 선택), repetition(반복)을 표현하는 메타 기호가 존재합니다. 또한, 동치(equivalence)라는 개념이 있습니다. 이 말은 표현력이 가지고 있는 힘이 같다는 것입니다. 즉, 모든 EBNF의 \(E\)에 대해서, 어떤 BNF \(B\)에 대해서 \(E\), \(B\)에 대한 언어 표현인 \(L(E)\), \(L(B)\)가 \(L(E) = L(B)\)를 만족하는 것을 의미합니다.

BNF의 내용을 EBNF로 변경을 해보도록 하겠습니다.

OPTIONAL

사각형 꺾쇠(bracket)를 사용하면 그 내용은 선택적으로 사용할 수 있는 내용임을 의미합니다.

[BNF]
<number> ::= "0" | "1" | "+" "1" | "-" "1" | "+" "0" | "-" "0"
[EBNF]
<number> ::= ["+"|"-"]("0"|"1")

SELECTION

막대기(bar)는 대체 부분을 구분하는 데 사용합니다. 이는 BNF하고 EBNF에 둘 다 있는 내용입니다.

REPETITION

중괄호(brace)를 사용해서 내용의 반복을 나타낼 수 있습니다.

[BNF]
<E> ::= <E> "+" <F> | <E> "-" <F> | <F>
<F> ::= "0"|"1"|"2"|"3"|"4"|"5"|"6"|"7"|"8"|"9"
[EBNF]
<E> ::= <F>{"+" <F>|"-" <F>}

유도

이전에 변수(non-terminal)와 상수(terminal)에 관한 규칙을 생성규칙이라 부르거나 생성이라고 했었습니다. 여기서 유도(Derivation)라고 하는 것이 있습니다. 이는 규칙의 응용으로 \(\Rightarrow\)으로 표현 할 수 있습니다. 예를 들어, \(\alpha \Rightarrow^* \beta\)는 \(\alpha\)에서 \(\beta\)까지 0번 이상의 과정을 통해서 유도됨을 의미하며, \(\alpha \Rightarrow^+ \beta\)는 \(\alpha\)에서 \(\beta\)까지 1번 이상의 과정을 통해서 유도됨을 의미합니다. 이러한 유도과정 이후에는 상수 집합을 얻을 수 있습니다.

규칙 생성 예제

먼저 BNF를 사용해서 직접 규칙을 만들어 보도록 하겠습니다. 먼저 규칙은 이진수에 대해서 덧셈과 뺄셈을 하는 규칙입니다. 이것에 대한 첫 번째 접근은 아래와 같이 할 수 있습니다.

<expression> ::= <number> + <number>
			 | <number> - <number>
<number>	::= "0" | "1"

하지만 생각해봅시다. 십진법 \(2+1\)을 위의 규칙이 받아들일 수 있을까요? 불가능합니다. \(2+1\)은 이진수로 \(10_2 + 1_2\)인데 우리의 규칙은 1개의 이진수(“0” 또는 “1”)밖에 받을 수 없습니다. 이를 더 개선하면 아래와 같이 개선 할 수 있습니다.

<expression> ::= <number> + <number>
			 | <number> - <number>
			 | <number>
<number>     ::= <number> <digit>
	          | <digit>
<digit>      ::= "0" | "1"

이렇게 하면 우리가 원하는 이진법 덧셈 및 뺄셈에 대한 규칙이 완성되게 됩니다. 근데 위는 좀 많이 복잡합니다. 이번에는 EBNF를 사용해서 좀 더 개선하면 아래와 같이 나옵니다.

<expression> ::= <number> {+ <number>|- <number>}
<number>	::= <digit> {<digit>}
<digit>		::= "0" | "1"

형식 언어

형식 언어를 이해하기 위해서는 알파벳과 문자열에 관해서 알아야 합니다. 알파벳은 기호의 집합입니다. 알파벳을 \(A\)라고 하면 \(A = \{0, 1, +, -\}\)와 같이 기호의 집합으로 정의할 수 있습니다. 이에 반해, 문자열은 알파벳의 일련(一連)이라고 할 수 있습니다. 예를 들어, 아까 정의된 \(A\)의 문자열을 만들면 “\(10 + 1 - 0\)“과 같이 제작할 수 있습니다. 여기서 문자열들의 집합을 보고 형식 언어라고 합니다. 이러한 언어는 문법에 따라서 표현될 수 있습니다.

이러한 형식 언어의 예를 보여주면 아래와 같이 작성될 수 있습니다.

알파벳: \(\Sigma = \{0, 1\}\)
문자열: \(101\)
언어: \(L = \{1, 11, 101, 111\}\)

이 형식 언어는 홀수에 대한 형식 언어라고 볼 수 있습니다.

형식 문법

형식 문법은 BNF의 개념을 일반화하기 위해서 만들어진 것으로 4가지 형태의 문법을 정의했습니다.

정규(regular) 문법 → Type 3
문맥 자유(context-free) 문법 → Type 2
문맥 의존(context-sensitive) 문법 → Type 1
무제한(unrestricted) 문법 → Type 0

문맥 자유 문법

형식 문법은 수학적으로 다음과 같이 표현할 수 있습니다. \(G = (N, T, P, S)\) 이고 여기서 각각의 의미는 다음과 같습니다.

\(N\): 논 터미널(non-terminal)로 문자열들의 집합을 나타내는 구문 변수입니다.
\(T\): 터미널(terminal)을 의미하며 \(\Sigma\)로도 표현되며 기본 기호를 지칭합니다.
\(P\): 생성규칙(관계)을 의미하며 이러한 생성규칙은 아래를 만족해야 합니다.
1. 생성규칙의 왼쪽은 머리(head) 또는 좌변(left side)이라 불리는 논 터미널로 구성된 것이 있습니다. 이들은 생성규칙에서 정의되는 쪽에 해당합니다.
2. 기호는 \(\to\) 또는 \(::=\)를 사용합니다.
3. 생성규칙의 오른쪽은 몸체(body) 또는 우변(right side)이라 불리는 0개 이상의 터미널과 논 터미널로 구성된 것이 있습니다. 이들은 생성규칙에서 정의되는 내용에 해당합니다.
\(S\): 이는 시작기호를 의미하며 문법에서는 이러한 한 개의 논 터미널 시작기호에 의해서 구분이 됩니다.

이러한 문법 \(G\)에 의해서 정의되는 언어 \(L(G)\)는 아래와 같이 표현할 수 있습니다.

\[L(G) = \{w \mid S\Rightarrow^{+} w\}\in T^*\]

그리고 이러한 문법을 예제를 통해서 좀 더 알아보겠습니다.

<expression> ::= <expression> + <term>
<expression> ::= <expression> - <term>
<term> ::= <term> * <factor>
<term> ::= <term> / <factor>
<term> ::= <factor>
<factor> ::= id

여기서 논 터미널은 <expression>, <term>, <factor>이고 터미널은 id, +, -, *, /에 해당하며, <expression>이 시작기호가 됩니다.

이에 따른, 문맥 자유 문법의 정의는 다음과 같습니다. 만약 논 터미널 \(A\)와 문법 기호들의 문자열인 \(x\)의 모든 생성규칙이 \(A \to x\)의 형태를 하고 있으면 그 문법을 문맥 자유(Type 2)라고 합니다. 이러한 문맥 자유 문법은 보통 프로그래밍 언어를 정의할 때 많이 사용합니다. 즉, 위에서 정의한 문법 예제도 문맥 자유 문법의 예제라고 할 수 있습니다.

compiler