Context-free 문법

이 글은 <컴파일러 입문> (저자: 오세문)을 참고하여 만들어졌습니다.

프로그래밍 언어의 구문 구조를 명시하는데 context-free 문법이 널리 사용되어 왔다.

또한 context-free 문법은 효율적이고 잘 정의된 구문 분석 알고리즘을 가지기 때문에 프로그래밍 언어의 문법적인 표현이나 번역에 매우 중요하다.

 

정규 문법은 프로그래밍 언어의 구문 구조를 표현하기에는 너무 제약이 많아 부적합하다.

대부분의 경우 토큰의 구조는 정규 표현으로 나타내지만 프로그래밍 언어의 구조는 context-free 문법을 사용한다.

 

장점

1. 간단하고 이해하기가 쉽다.

2. 표현된 문법으로부터 자동적으로 인식기를 구현할 수 있다.

3. 입력된 프로그램의 구조를 생성 규칙에 의해 분해할 수 있으므로 번역에 유용하다.

 

context-free 문법은 촘스키 분류에 따르면 형태 2에 해당하며, 모든 생성 규칙은 A->a의 형태를 갖는다.

여기서 A는 하나의 nonterminal이며 a는 V*에 속하는 스트링이다. 

따라서 유도 과정의 문장 형태(sentential form)에서 A를 문맥에 관계없이 a로 대체할 수 있기 때문에 context-free(문맥 자유 또는 문맥 무관)이라 부른다.

 

문법 표기에서 사용하는 문법 심벌들의 일반적인 표기법은 다음과 같다.

1. Terminal 심벌:

(1) a, b, c와 같은 알파벳 시작 부분의 소문자와 숫자 0, 1, 2, ...., 9

(2) + - 와 같은 연산자 기호와 콤마, 세미콜론, 괄호와 같은 구분자

(3) 'if' 또는 'then'과 같이 '과' 사이에 표기된 문법 심벌

 

2. Nonterminal 심벌:

(1) A, B, C와 같은 알파벳 시작 부분의 대문자;

(2) S는 보통 시작 심벌(start symbol)을 나타낸다.

(3) <exp>나 <statement>와 같이 <와 >로 묶어서 나타낸 문법 심벌

 

3. 만약 아무런 언급이 없다면, 첫 번재 생성 규칙의 왼쪽에 있는 nonterminal이 시작 심벌이다.

4. A -> a1, A -> a2,  .... , A -> an과 같이 생성 규칙의 왼쪽이 모두 A인 경우 => A에 대한 택일(alternation) 규칙

 

각 심벌의 의미는 다음과 같다

• X, Y, Z와 같은 알파벳 끝 부분의 대문자는 nonterminal 심벌 혹은 terminal 심벌을 나타낸다.
• 알파벳 끝 부분의 소문자, 주로 u,v, ...., z는 terminal들로 이루어진 스트링을 나타낸다. w(omega) 역시 terminal 스트링을 나타내는 대표적인 문자이다.

<if_statement> -> 'if' '(' <expression> ')' <statement>에서 <>안에 기술된 심벌은 nonterminal이고 '(quote)와 '사이에 기술된 심벌은 terminal이다.

 

5.2 유도와 유도 트리

5.2.1 유도

Context-free 문법에서 문장의 생성은 문장 형태의 스트링에서 생성 규칙을 연속적으로 적용하여 nonterminal을 확장함으로써 얻을 수 있다.

 

Context-free 문법에서는 생성 규칙의 오른쪽에 nonterminal이 여러 개 나올 수 있기 때문에 같은 문장을 유도하는 여러 가지 방법이 있을 수도 있다.

즉, 문장 형태에서 유도시 대치해야 할 nonterminal을 선택하는데 여러 가지 경우가 있을 것이다.

 

정의 5.1

유도 과정의 각 단계에서 문장 형태의 가장 왼쪽에 있는 nonterminal을 대치하는 경우, 이를 좌측 유도(leftmost derivation)라 하며 =>으로 표기한다.  

가장 오른쪽에 있는 nonterminal 심벌을 대치하는 경우를 우측 유도(rightmost derivation)라 하며 =>으로 표기한다.

 

5.2.2 유도 트리

Context-free 문법에서, 문장이 유도되는 과정을 트리 형태로 표현할 수 있는데, 이를 유도 트리(derivation tree)라 한다.

유도 트리는 루트 노드(root node), 중간 노드(interior node), 단말 노드(terminal node 또는 leaf node)로 구성

생성 규칙에 의해 적용되는 문장의 계층적 구조를 나타낸다.

 

유도 트리는 문장 형태에서 대치되는 심벌의 순서에 관계없이 그릴 수 있다.

따라서 생성 규칙의 적용 순서에 따라 달라지는 유도 과정은 어떤 특정한 유도 과정을 사용함으로써 고정시킬 수 있다. 

그러나, 어느 한 가지 유도 방법을 이용하더라도 구성되는 유도 트리가 유일하다는 것을 확증하지 못할 뿐만 아니라, 실제로 두 개 이상의 유도 트리가 만들어지는 경우도 존재한다.

 

5.2.3 모호성

문법 G에 의해 생성되는 어떤 문장이 2개 이상의 유도 트리를 갖는다면, 문법 G는 모호하다(ambiguous)고 한다.

구문 분석기의 출력으로 유도 트리를 낼 경우, 문장의 유도 트리를 결정적으로 구성하기가 어렵기 때문에 모호하지 않은(unambigous) 문법이 필요하다.

따라서, 결정적인 파싱을 하기 위해서는 일반적으로 모호하지 않은 문법으로 바꾸어야 한다.

하지만 모호한다는 것은 문법의 속성이며 언어의 속성은 아니다.

그러므로, 모호한 문법을 모호하지 않은 동등한 문법으로 바꿀 수 있다.

 

일반적으로 연산 순위나 결합 법칙의 정보를 이용해서 생성 규칙을 추가하여 모호성을 제거한다.

이때 새로운 nonterminal을 도입하게 된다.

다음은 모호한 문법을 모호하지 않은 문법으로 변환시키는 과정을 설명한 것이다.

 

이제부터 연산 순위를 고려하여 동등한 문법으로 바꾸는 과정을 생각해보자.

먼저, 가장 기초적인 피연산자를 F(factor)라 두면 이것은 괄호로 묶인 산술식이나 a가 될 수 있다. 

 

한 context-free 언어를 생성하는 모든 문법이 모호하다면, 이 언어를 본질적으로 모호하다(inherentlyu ambigous)고 한다.

 

 

5.3 문법 변환

• 한 문법을 다른 형태의 동등한 문법으로 변환하는데 사용되는 기법에는 대입(substitution)과 확장(expansion)이 있다.
• 대입이란 특정한 생성 규칙을 제거하고 그에 해당하는 생성 규칙들을 추가하는 방법으로 제거된 생성 규칙의 오른쪽 부분에 있는 nonterminal 심벌 대신에 그 생성 규칙들의 오른쪽을 대입함으로써 문법을 변환하는 방법이다.

확장이란 새로운 nonterminal 심벌을 도입하여 한 개의 생성 규칙을 쪼개는 방법이다.

유도 과정에서 생성 규칙을 확장한 효과는 유도 과정의 횟수를 한 번 늘인 결과가 된다.

 

5.3.1 필요 없는 생성 규칙 제거

한 문법이 생성하는 언어는 시작 심벌로부터 유도할 수 있으며 모두 terminal 심벌들로 이루어진 스트링의 집합이다.

따라서 문장을 생성하는데 적용할 수 없는 생성 규칙들은 모두 제거할 수 있으며 필요 없는 생성 규칙(useless production)이라 부른다.

 

문장을 생성하는 유도 과정에 나타날 수 있는 심벌을 필요한 심벌(useful symbol)이라 하며 그렇지 않은 심벌을 필요 없는 심벌(useless symbol)이라 한다.

 

다시 말해서, X가 필요 없는 심벌이라는 의미는 X가 teminal 스트링을 생성할 수 없는 nonterminal 심벌이거나, 또는 시작 심벌로부터 도달할 수 없는 심벌이라는 것이다.

역으로, 필요한 생성 규칙들은 모두 terminating nonterminal과 도달 가능한 심벌들만으로 이루어져 있다고 생각할 수 있다.

 

필요 없는 생성 규칙을 제거하는 방법은 다음과 같이 단계적으로 처리하여야 한다.

1. terminating nonterminal을 구하여 terminal 스트링을 생성할 수 없는 nonterminal들을 구별해 내서 이 심벌들을 갖고 있는 모든 생성 규칙들을 제거한다. 

2.  도달 가능한 심벌들을 구하여 도달 불가능한 심벌들을 구별해 내서 이 심벌들을 갖고 있는 모든 생성 규칙들을 제거해야 한다.

 

Terminating nonterminal을 구하는 방법

생성 규칙의 오른쪽이 모두 terminal만으로 이루어진 생성 규칙의 lhs는 당연히 terminal 스트링을 유도하는 nonterminal이다.

또한 이 nonterminal들과 terminal들로 이루어진 생성 규칙의 lhs가 terminal을 생성할 수 있는 nonterminal에 속하게 된다.

이런 과정을 새로운 nonterminal이 더 추가되지 않을 때까지 반복한다.

 

다음으로 도달 가능한 심벌을 구하는 방법을 생각해 보자.

시작 심벌로부터 도달할 수 있는 심벌을 차례로 마크(mark)해 나가고 또 마크된 심벌로부터 유도할 수 있는 심벌은 도달할 수 있기 때문에 마크한다.

더 이상 마크되는 심벌이 나타나지 않을 때 마크된 모든 심벌들이 도달 가능한 심벌들의 집합이다.

 

주어진 문법으로부터 필요 없는 생성 규칙을 제거하기 위해서는 먼저 [알고리즘 5.1]을 적용하고 그 다음에 [알고리즘 5.2]를 적용한다.

 

문법을 입력으로 받아 그에 해당하는 파싱 테이블을 생성하는 파서 제작 시스템(PGS)에서는 필요 없는 생성 규칙을 가려내어 사용자에게 알려주는 일도 한다.

 

5.3.2 ε- 생성 규칙 제거

ε-생성 규칙을 제거함으로써 구문 분석 시간을 줄일 수 있다.

아래의 알고리즘은 context-free 문법을 ε-free한 문법으로 바꾸는 방법을 기술한 것이다.

 

여기서 P'이 ε-생성 규칙을 제거한 집합

VNε는 ε을 유도할 수 있는 nonterminal의 집합이다.

그리고 P'의 각 생성 규칙에 대하여 VNε에 속하는 nonterminal을 가질 경우, 이 nonterminal에 대하여 ε을 대입하여 만든 새로운 생성 규칙을 추가하며,

또한 이 nonterminal이 ε 이외의 다른 생성 규칙을 가진다면 이 생성 규칙도 포함시킨다.

그리고 시작 심벌이 VNε에 속하면 새로운 시작 심벌 S'을 도입하여 S' -> ε | S의 생성 규칙을 P'에 추가한다. 

 

VNε을 구하는 방법

 

5.3.3 단일 생성 규칙의 제거

생성 규칙의 형태가 A -> B와 같이 생성 규칙의 오른쪽에 한 개의 nonterminal만이 나오는 생성 규칙을 단일 생성규칙(single production)이라 한다. 

이것으로 인하여 불필요한 유도 과정이 생기며 파싱 속도가 느려진다. 

따라서, 효율적인 파싱을 위하여, 만약 단일 생성 규칙이 의미 정보를 갖고 있지 않으면 제거하는 것이 바람직하다.

앞에서 언급했듯이 cycle과 ε-생성 규칙을 가지는 문법은 cycle-free하고 ε-free한 문법보다 구문 분석하기가 힘들며 필요 없는 심벌을 가지는 경우 크기가 너무 커지게 된다.

 

5.3.4 문법의 기본적인 형태

Context-free 문법을 이용하여 일반적인 프로그래밍 언어를 기술하고 그것으로부터 인식기를 구현하려는 많은 시도와 알고리즘이 개발

모든 context-free 문법은 촘스키 정규 형태로 바꿀 수 있고 표기법(notation)을 간소화하는데 유용하다

다음은 context-free 문법을 촘스키 정규 형태로 바꾸는 방법이다.

 

5.4 CFG 표기법

먼저 BNF => Extended BNF

BNF 표기법으로 모든 프로그래밍 언어의 문법을 기술할 수 있지만,

이보다 읽기 쉽고 간결하게 프로그래밍 언어를 나타내기 위해 확장된 BNF(EBNF)를 도입하게 되었다.

EBNF는 반복되는 부분이나 선택적인 부분을 간결하게 표현할 수 있는 방법으로

이를 위해 특수한 의미를 갖는 메타 심벌(meta symbol)을 사용한다.

=> 메타 심벌은 표현하려는 언어의 일부분이 아니라 그 언어를 표현하려고 사용된 특수 심벌이다.

 

반복되는 부분(repetitive part)를 기술하기 위해 메타 심벌 {}를 사용한다.

즉, {a}는 a가 0번 이상(zero or more) 반복될 수 있다는 것을 나타낸다.

 

EBNF는 반복되는 최대 횟수와 최소 횟수를 나타낼 수 있다.

선택적인 부분(optional part)를 기술할 때에는 메타 심벌 []로 나타낸다.

즉 [x]가 나타나지 않거나 한번만 나타날 수 있음을 의미한다.

 

* EBNF에 사용되어지는 메타 심벌들을 teminal 심벌로 사용하는 경우 혼돈이 생기는데, 이를 피하기 위해 terminal 심벌을 ''을 묶어 표현한다.

 

표준 C언어의 문법으로부터 줄여서 만든 Mini C 문법은 프로그래밍 언어의 의미에 정확히 맞는 형태(exact form)는 아니다.

특히 <declaration>과 <expression> 부분은 의미분석에서 많은 작업을 해야만 한다.

 

문법 흐름도는 EBNF 표기법의 사고 방식과 유사하므로 문법이 EBNF로 쓰여져 있을 경우, 쉽게 문법 흐름도로 바꿀 수 있다.

 

5.5 푸시다운 오토마타

유한 오토마타는 보조 기억장치를 갖고 있지 않기 때문에 지나간 입력의 유례 알수 x

따라서 입력 심벌의 일정한 개수를 셀 수 있는 능력이 없는 것이다.

푸시다운 오토마타(PDA: Push-Down Automata)는 인식기의 한 종류로 유한 상태 제어(finite state control), 입력 테이프(input tape), 그리고 스택(stack)으로 구성되어 있다.

입력 테이프는 입력 스트링을 유지하고 있으며 스택은 보조 기억장치로 보통 푸시다운 리스트(push-down list)라고 부른다.

 

=> 나머지 설명은 책 참조

 

5.6 Context-free 언어와  PDA 언어

지금까지의 내용을 기초로 PDA 언어가 정확히 context-free 언어라는 것을 보일 수 있다.

즉 CFG가 주어졌을 때, 그에 해당하는 PDA를 구성할 수 있고, 역으로 PDA가 주어졌을 때, PDA가 인식하는 언어를 생성하는 CFG를 만들 수 있다.

 

상태는 하나만 필요하고 그것이 시작 상태도 된다.

그리고 입력 심벌은 항상 terminal 심벌이 되고 스택에는 terminal 심벌이나 nonterminal 심벌이 들어갈 수 있다.

스택 시작 심벌은 문법의 시작 심벌이 되며, 입력 스트링을 모두 보고 스택이 비어 있을 때만 인식하기 때문에 종결 상태는 없다.

 

PDA의 δ 함수는 G의 생성 규칙으로부터 만든다.

1. 확장(expand) => ε-이동을 하면서 스택의 내용만 A를 a로 바꾼다.

2. pop => 입력 심벌과 스택 top 심벌이 같은 경우에 스택의 top 심벌은 스택에서 제거하고 입력 심벌은 입력 스트링에서 제거한다.

- 이와 같은 방법으로 PDA를 만들 경우, δ 함수의 개수는 생성 규칙의 개수에다 terminal 심벌의 개수를 더한 것이 된다.

 

시작 심벌로부터 아래로 내려가면서  스트링을 만들기 때문에 이와 같은 방법을 top-down 구문 분석 방법이라 한다.

CFG에서 우측 유도를 역으로 적용함으로써 bottom-up 파서로 작동하는 확장된 PDA를 만들 수 있다.

 

주어진 스트링을 bottom-up 방법으로 인식하기 위한 과정은 다음과 같다. 

생성 규칙의 rhs가 스택 top 부분에 나타날 때까지 shift를 하다가 rhs가 모아지면 reduce를 한다.

즉, shift와 reduce 행동을 반복하여 주어진 입력 스트링이 시작 심벌에 다다르면 올바른 문장이라고 인식하는 방법이다.

 

P가 인식하는 모든 스트링을 생성할 수 있는 문법을 고안해야 한다.