[Compiler] 3-2. 형식 문법

형식 문법은 크게 두 가지 방법으로 정의할 수 있다.

• 생성 규칙(Production Rule)만으로 표현
• 항목으로 정의

1. 형식 문법

형식 문법 \(G=(V_N,V_T,P,S)\) 는 다음과 같이 네 가지 항목으로 정의된다.

 

1. \(V_N\): 논터미널 기호의 유한집합
2. \(V_T\): 터미널 기호의 유한집합
   • \(V_N\cap V_T=\varnothing ,V_N\cup V_T=V\)
   • 터미널 기호와 논터미널 기호를 문법 기호(grammer symbol)라 하며 보통 \(V^{vocabulary}\)로 표시한다.
3. \(P\): 생성 규칙의 유한집합
   • \(\alpha \to \beta, \alpha \in V^+, \beta \in V^*\)
   • \(\alpha\)를 왼쪽 부분(left-hand side), \(\beta\)를 오른쪽 부분(right-hand side)라고 부른다.
   • \(\to \): 왼쪽의 기호가 오른쪽의 기호로 단순히 대체되는 것을 나타내는 기호이다.
4. \(S\): \(V_N\)에 속하는 기호로서 다른 논터미널 기호들과 구별하여 시작 기호(start symbol)라고 한다.

• 터미널 기호: 언어를 정의할 때 사용한 알파벳으로 영문 소문자, 아라비아 숫자,연산자 기호 등이 속한다.
• 논터미널 기호: 언어에서 문자열을 생성하는 데 사용되는 중간 과정의 기호로서 보통 대문자로 표시한다.

👉터미널 기호는 다른 기호로 대체되지 않는 기호이고, 논터미널 기호는 다른 기호로 대체되는 기호이다.

기호들의 일반적인 표기법

1. A, B, C와 같은 영문자 대문자로 구성된 기호를 나타내는 \(S\)는 논터미널 기호이다.
2. <와 >로 묶어서 나타낸 기호도 논터미널 기호이다.
3. a, b, c와 같은 영문자 소문자로 구성된 기호와 +, -와 같은 연산자 기호, 괄호나 쉼표와 같은 구분자, 0, 1, 2와 같은 아라비아 숫자 등은 터미널 기호이다.
4. X, Y, Z와 같은 영문자 끝부분의 대문자는 터미널 기호와 논터미널 기호를 나타내는 문법 기호이다.
5. u, v, w, x, y, z와 같은 영문자 끝부분의 소문자는 터미널 기호들로 이루어진 문자열을 나타낸다.
6. \(\alpha , \beta , \gamma \)와 같은 그리스어 소문자는 문법 기호로 구성된 문자열을 나타낸다.
7. 만약 아무런 언급이 없으면 첫 번째 생성 규칙의 왼쪽에 있는 기호가 시작 기호이다.
8. 생성 규칙의 왼쪽 부분에 같은 기호로 구성된 생성 규칙이 여러 개일 때 축약해서 사용할 수 있다. 예를 들어 2개의 생성 규칙 \(\alpha \to \beta _1, \alpha \to \beta _2\)가 있을 때 간단히 \(\alpha \to \beta _1 | \beta _2\)로 표현한다.

예를 들어 보자. 문법과 생성 규칙이 주어졌을 때 논터미널 기호, 터미널 기호, 시작 기호, 생성 규칙의 개수를 구해보자.

• 문법 \(G=(\{ S,A\}, \{ 0,1\} , P, S)\)
• 생성 규칙 \(P:S \to 0AS, S \to 0, A \to S1A, A \to 10, A \to SS\)

 

구해보면 정답은 다음과 같다.

• 터미널 기호는 아라비아 숫자인 0과 1이다.
• 논터미널 기호는 S, A이다.
• 시작 기호는 S이다.
• 생성 규칙의 개수는 P에 나열된 5개이다.

2. 유도(derivation)

정의된 문법으로부터 어떤 언어가 생성되는지, 언어가 문법에 맞는지를 알기 위해 유도가 필요하다.

\(\Rightarrow \)는 유도한다는 뜻이다. 만약 생성 규칙 \(\alpha \to \beta \)가 존재하고, \(\gamma ,\delta \in V^*\)이면 \(\gamma \alpha \delta \Rightarrow \gamma \beta \delta \)와 같이 나타낼 수 있다. 즉 \(\alpha\)가 \(\beta\)로 대체되었음을 의미한다.

또한 \(\Rightarrow ^*\)는 0번 이상의 유도라 하고, \(\Rightarrow ^+\)는 한 번 이상의 유도라 한다.

만약 \(\alpha _1 , \alpha _2 , \alpha _3 , \cdots ,\alpha _n\)이 \(V\)에 속하고, \(\alpha _1 \Rightarrow \alpha _2 \Rightarrow \alpha _3 \Rightarrow \cdots \Rightarrow \alpha _n\)이 존재한다면 \(\alpha _1 \Rightarrow ^n \alpha _n\)으로 쓰며, 이는 \(\alpha _1 \Rightarrow ^* \alpha _n\)이라고도 할 수 있다. 이때 \(\alpha _1\)은 \(\alpha _n\)을 생성한다(produce) 혹은 유도(derive)한다라고 하며, \(\alpha _n\)은 \(\alpha _1\)로 감축(reduce)된다고 한다.

3. 문장과 문장 형태

\(S \Rightarrow w_1 \Rightarrow w_2 \Rightarrow \cdots \Rightarrow w_n \Rightarrow w\)와 같은 유도 과정이 있으면 \(S \Rightarrow ^* w\)이며, \(w\)가 \(V^*\)에 속하면 \(S, w_1, w_2, \cdots , w_n, w\)를 문장 형태(sentential form)라 하고, \(w\)가 \(V_T^*\)에 속하면 \(w\)를 문장(sentence)이라 한다. 즉 문장 형태는 터미널 기호와 논터미널 기호의 조합으로 구성되고 문장은 터미널 기호로만 구성된다.

우리가 프로그램을 작성할 때 사용하는 터미널 기호로만 구성된 문장을 언어라 한다.

4. 문법 G에 의해 생성된 언어 L(G)

문법 \(G\)에 의해 생성되는 언어는 \(G\)에 의해 생성되는 문장의 집합이며 \(L(G)\)로 표기한다.

• \(L(G)=\{ w|S \Rightarrow ^* w, w \in V_T^*\}\)

5. 촘스키 계층 구조

앞에서 정의한 문법의 개념은 촘스키(Chomsky, N.)에 의해서 처음 소개되었다. 그는 문법을 생성 규칙에 가해지는 제한에 따라 네 종류로 나누었으며, 이를 촘스키 계층 구조라고 부른다.

 

네 문법의 포함관계는 다음과 같다.