제2장 형식 언어

컴파일러 구성론

강 승 식

∙ Formal language : Well-formed language 또는 well-defined language

‘문장들의 집합’으로 정의, syntax but no semantics

∙ Description of language  :  grammar(문법) 또는 syntax

2.1 언어(language)

∙ language = set of statements  □□□□  자연언어에서는 sentences

∙ statement = set of alphabets   □□□□  자연언어에서는 words

└□□□ 문장을 구성하는 최소단위 : symbol이라고 함

[정의2.1] alphabet의 정의

alphabet T는 symbol들의 유한집합(finite set)이다.

예1) T1 = {ㄱ, ㄴ, ㄷ, ㄹ, ⋯, ㅎ, ㅏ, ㅑ, ㅓ, ㅕ, ⋯, ㅡ, ㅣ}

T2 = {A, B, C, D, ⋯, Z}

T3 = {main, int, char, long, ⋯ }

[정의2.2] string의 정의

Alphabet T에 대한 string은 sequence of one or more symbols이다.

└□□□  언어의 문장

예2) T = {a, b}일 때

a, b, aa, ab, ba, bb, aaa, ⋯ 는 모두 T로부터 생성되는 string이다.

[정의2.3] string length

string의 길이는 string을 구성하고 있는 symbol들의 수이고,

임의의 string [eqn: omega]의 길이는 |[eqn: omega]|로 표기한다.

예3) [eqn: omega] = a1a2a3⋯ak이면 |[eqn: omega]| = k이다.

[정의2.4] string concatenation

- 2개의 string을 연속으로 연결한 것.

- string u, v가 각각 u = a1a2a3⋯an, v = b1b2⋯bm일 때

u・v = a1a2a3⋯anb1b2⋯bm

□□□□  교환법칙 성립 안함 ( u・v ≠ v・u )

u・v는 간단히 uv로 표기하며 u를 prefix, v를 suffix라 한다.

( 이 때, |uv| = |u| + |v| )

[정의2.5] empty string과 reverse string

- 공백 스트링은 [eqn: epsilon] 또는 [eqn: lambda]로 표기

- an = aa⋯a, 그리고 a0 = [eqn: epsilon]

- [eqn: omega]R은 string [eqn: omega]의 역순

(예) [eqn: omega] = v1v2v3⋯vn이면, [eqn: omega]R = vn⋯v3v2v1

[정의2.6] T*와 T+ ( alphabet T에 대하여 )

- T* : empty string을 포함하여 T에 속하는 symbol로 이루어질 수 있는

모든 string들의 집합.

- T+ : empty string을 제외하고 T에 속하는 symbol로 이루어질 수 있는

모든 string들의 집합.

- T+ = T* - {[eqn: epsilon]}

예4) ① T = {0}일 때, T* = {[eqn: epsilon], 0, 00, 000, ⋯}, T+ = {0, 00, 000, ⋯}

② T = {a, b}일 때, T* = {[eqn: epsilon], a, b, aa, ab, ba, bb, aaa, aab, ⋯},

T+ = {a, b, aa, ab, ba, bb, aaa, aab, ⋯}

※ alphabet T는 항상 유한집합, T*는 항상 무한집합

임의의 u, v ∈ T*에 대하여 uv ∈ T*이다.

즉, T*는 alphabet T에 속하는 symbol로부터 생성할 수 있는 전체집합이다.

[정의2.7] 언어 L의 정의

알파벳 T에 대하여 언어 L은 T*의 부분집합이다.

즉, 언어 L은 T*에 속하는 string중에서 특정한 유형만 모아놓은 집합

※ 유한언어(finite language)와 무한언어(infinite language)

□□□□  언어에 속하는 string의 수가 유한 개 or 무한 개

(아래 예5에서 L2만 유한 언어)

예5) T = {a, b}일 때 ①-④는 언어이다.

① L1 = T* = {[eqn: epsilon], a, b, aa, ab, ba, bb, aaa, aab, ⋯},

② L2 = { a, ba, aba }

③ L3 = { ap | p는 소수 }

④ L4 = { anbn | n ≥ 1 }

※ 형식언어는 의미(semantics)를 논하지 않으며, 언어의 syntactic structure만

다르다. 즉, 형식언어 이론은 string 집합의 속성에 관한 이론이다.

[정의2.8] 두 언어 L과 L'의 곱(product)은 L・L'은 L에 속하는 string과 L'에 속하는 string을 접속한 것으로 간단히 LL'으로 나타낼 수 있다.

( 교환법칙 성립 안함 )

LL' = { xy | x ∈ L and y ∈ L' }

예6) L2{a, b} = { aa, ab, baa, bab, abaa, abab}

L3L4 = { ap+nbn | p는 소수, n ≥ 1 }

[정의2.9] 언어 L의 거듭제곱(power)은 순환적(recursive)으로 정의된다.

L0 = {[eqn: epsilon]}

Ln = LLn-1 for n≥1

예7) L = {a, ba, aab}일 때

L0 = {[eqn: epsilon]}

L1 = {a, ba, aab}

L2 = {aa, aba, aaab, baa, baba, baaab, aaba, aabba, aabaab}

[정의2.10] 언어 L의 L*(reflexive transitive closure)는 다음과 같이 정의된다.

L* = L0∪L1∪L2∪⋯∪Ln∪⋯

= [eqn: {smallunion _i=0 ^inf}]Li

[정의2.11] 언어 L의 L+(transitive closure)는 다음과 같이 정의된다.

L+ = L1∪L2∪⋯∪Ln∪⋯ = L*- L0

※ 각 언어마다 고유의 알파벳 T가 존재하며 T로부터 만들 수 있는 string 전체

집합이 T*이다. 언어는 T* 중에서 어떤 규칙에 적합한 string으로 정의된다.

한 언어에 속하는 string을 그 언어의 문장(sentence)이라 한다.

( Given alphabet T and T*,  L = T* ∧ grammar )

2.2 문법(grammar)

• 언어의 기술방법

유한 언어 --- 모든 string 나열

무한 언어 --- 모든 string 나열?  □□□□  finite representation

① 집합 표현 방식으로 조건 제시법

② 언어 생성 시스템인 문법 ( grammar )

③ 언어 인식 시스템 ( recognizer )

[정의2.12] 문법은 다음과 같은 네 가지 항목으로 구성된다.

G = (VN, VT, P, S)

VN : nonterminal symbol의 유한 집합 □□□□ A, B, C 등 대문자 사용

VT : terminal symbol의 유한 집합 □□□□ a, b, c 등 소문자 사용

P : 생성규칙(production rule)의 유한 집합

S : VN에 속하는 symbol로 start symbol 혹은 sentence symbol □□□ 대문자 S

예8) G = ({S,A}, {a,b}, P, S}

P : S → aAS	S → a

A → SbA	A → ba	A → SS

※ 생성 규칙의 축약

[eqn: alpha] →[eqn: beta]1,  [eqn: alpha] →[eqn: beta]2   ⇔  [eqn: alpha] →[eqn: beta]1 | [eqn: beta]2

예8)의 생성 규칙 축약

P: S → aAS | a

A → SbA | ba | SS

예9) P: S → aA | bB | [eqn: epsilon]

A → bS

B → aS

[정의2.13] ‘⇒’는 직접 유도(directly derive)된다는 의미이다.

[eqn: alpha] →[eqn: beta]가 존재하고 [eqn: gamma, delta]∈V*이면, [eqn: gamma~ alpha~ delta] ⇒[eqn: gamma~ beta~ delta] 로 표기한다.

( 생성 규칙 [eqn: alpha] →[eqn: beta]을 한 번 적용하여 다른 스트링으로 변환 )

*

‘⇒’는 0번 이상의 유도된 과정을 나타낸다.

예를 들어, [eqn: alpha]1,[eqn: alpha]2,[eqn: alpha]3,⋯[eqn: alpha]n이 V*에 속하고 [eqn: alpha]1 ⇒[eqn: alpha]2 ⇒[eqn: alpha]3 ⇒ ⋯ ⇒[eqn: alpha]n

*

이 존재한다면 [eqn: alpha]1 ⇒[eqn: alpha]n으로 쓸 수 있다.

이 때 [eqn: alpha]n이 [eqn: alpha]1로부터 유도될 수 있다고 말한다.

+

‘⇒’는 한 번 이상의 유도된 과정을 나타낸다.

※ string [eqn: alpha]가 V*에 속한다([eqn: alpha]∈V*) ≡ [eqn: alpha]는 nonterminal과 terminal로 구성된 string

[정의2.14] sentential form의 정의

*

S ⇒[eqn: omega]이고 [eqn: omega]가 V*에 속하면 [eqn: omega]를 sentential form이라 하고,

[eqn: omega]가 VT*에 속할 경우 [eqn: omega]를 sentence라고 한다.

즉, sentence는 nonterminal을 포함하지 않는 sentential form이다.

예10) 예9의 문법에서 start symbol로부터 abba를 유도하는 과정

S ⇒ aA     ( 생성규칙 S → aA를 적용 )

⇒ abS    ( 생성규칙 A → bS를 적용 )

⇒ abbB   ( 생성규칙 S → bB를 적용 )

⇒ abbaS  ( 생성규칙 B → aS를 적용 )

⇒ abba   ( 생성규칙 S → [eqn: epsilon]를 적용 )

*

S ⇒ abba

sentential form : aA, abS, abbB, abbaS, abba

sentence : abba

[정의2.15] 언어와 문법의 관계

문법 G에 의해 생성되는 언어는 G에 의해 생성되는 문장의 집합

*

L(G) = {[eqn: omega] | S ⇒[eqn: omega], [eqn: omega]∈VT* }

즉, L(G)는 start symbol로부터 유도될 수 있는 모든 문장의 집합.

예11) 문법 G1에 대하여 L(G1)을 구하라.  L(G1) = {an | n≥1}

G1 = ({S}, {a}, P, S),  P: S → a | aS

※ 주어진 문법으로부터 생성되는 언어 발견 과정

1. start symbol로부터 길이가 짧은 순으로 생성규칙 적용

2. 생성된 문장들의 형태를 고려하여 일정한 규칙 발견

예12) 문법 G2에 대하여 L(G2)을 구하라.  L(G2) = {a2n+1 | n≥0}

G2 = ({O,E}, {a}, P, O),  P: O → a | aE, E → aO

예13) 문법 G3에 대하여 L(G3)을 구하라.  L(G3) = {anbncn | n≥1}

G3 = ({A,B,C}, {a,b,c}, P, A),

P: A → abc     A →  aBbc     Bb → bB     Bc →  Cbcc

bC → Cb     aC →  aaB     aC → aa

※ 주어진 언어를 기술하는 문법 발견

예14) L1 = {anbn | n≥1}를 생성하는 문법을 고안해 보자.

S → aSb | ab

예15) L2 = {0i1j | i≠j, i,j≥1}

(1) i>j인 경우 : S → 0A1, A → 0A1 | 0A | 0

(2) i<j인 경우 : S → 0B1, B → 0B1 | B1 | 1

※ 문법 기술 방법

1. embedded rule : S → aSb

2. right-recursive rule : A → aA

3. left-recursive rule : A → Aa

※ nonterminal 기호

<identifier_list> → <identifier>, <identifier_list>

<identifier_list> → <identifier>

※ 한 문법이 어떤 언어 L을 생성한다는 것을 증명.

역으로, L에 속하는 모든 string이 그 문법에 의해서 생성될 수 있음을 증명.

예16) Balanced parenthesis

G = ({S}, {(,)}, {S → (S)S |[eqn: epsilon]}, S)

⇔ L = {[eqn: epsilon] | [eqn: epsilon]는 균형을 이룬 괄호로 구성되어 있다.}

※ 프로그래밍 언어의 문법(syntax)

- syntax : 언어의 구조를 단순-명료하게 기술

- 문법의 의미 : start symbol로부터 몇몇 문장을 유도해 봄

- 부록A 참조 : mini C 언어 syntax 및 예제 프로그램

2.3 문법의 분류 : Noam Chomsky

Chomsky Hierarchy

1. Type 0 문법 ( UG: unrestricted grammar )

생성규칙에 제한을 두지 않는다.

2. Type 1 문법 ( CSG: context-sensitive grammar )

모든 생성규칙 [eqn: alpha~ →~ beta]에서 [eqn: |alpha|~≤~|beta|]이다.

3. Type 2 문법 ( CFG: context-free grammar )

모든 생성규칙은 [eqn: A~ →~ alpha]의 형태를 갖는다.

( A는 하나의 nonterminal이고, [eqn: alpha]는 V*에 속하는 string이다. )

4. Type 3 문법 ( RG: regular grammar )

모든 생성규칙은 2가지 형태로 표현된다.

(1) [eqn: A~→~tB~혹은~A~→~t,] 여기서 t∈VT*이고 [eqn: A,B∈]VN이다.

(2) [eqn: A~→~Bt~혹은~A~→~t,] 여기서 t∈VT*이고 [eqn: A,B∈]VN이다.

※ (1)을 우선형 문법(right-linear grammar),

(2)를 좌선형 문법(left-linear grammar)이라 한다.

[정의2.16] 언어의 유형

1. regular language : 정규 문법(type 3)에 의해 생성되는 언어

2. context-free language : CFG(type 2)에 의해 생성되는 언어

3. context-sensitive language : CSG(type 1)에 의해 생성되는 언어

4. recursively enumerable set : UG(type 0)에 의해 생성되는 언어

예17) (1) <예11>의 문법은 정규 문법이고 언어 {an | n≥1}는 정규언어이다.

G1 = ({S}, {a}, P, S),  P: S → a | aS

(2) <예13>의 문법은 CSG이고 언어 {anbncn | n≥1}는 CSL이다.

예18) <예14>의 언어 L={anbn | n≥1}이 CFL임을 증명.

S → aSb | ab

※ 언어 L(G2) = {anban | n≥1}를 생성하는 CFG를 구하시오.

G2 = ({S,C}, {a,b}, P, S)

P: S → aCa

C → aCa | b

※ 언어 L(G3) = {anbam | n,m≥1}를 생성하는 RG를 구하시오.

G3=({S,B,C}, {a,b}, P, S)

P: S → aS | aB

B → bC

C → aC | a

※ 형식언어 이론에서 자주 예로 드는 언어

1. 단순 일치 언어 ( simple matching language )

Lm = {anbn | n≥0}

2. 중복 일치 언어 ( double matching language )

Ldm = {anbncn | n≥0}

3. 좌우 대칭 언어 ( mirror image language )

Lmi = {[eqn: omega][eqn: omega]R |[eqn: omega]∈VT*}

4. 회문 언어 ( palindrome language )

Lr = {[eqn: omega] |[eqn: omega]=[eqn: omega]R}

5. 괄호 언어 ( parenthesis language )

Lp = {[eqn: omega] |[eqn: omega]는 balanced parenthesis로 구성}

※ 언어의 포함 관계 : RG ⊆ CFL ⊆ CSL ⊆ UL

※ 언어를 인식하는 인식 시스템

1. 정규 언어 : 유한 오토마타 ( finite automata )

2. 문맥 자유 언어 : pushdown automata

3. 문맥 의존 언어 : linear-bounded automata

4. unrestricted 언어 : Turing machine

문법	언어	인식기
type 0 (unrestricted 문법)	recursively enumeratable set	Turing machine
type 1 (context-sensitive 문법)	context-sensitive 언어	Linear-bounded automata
type 2 (context-free 문법)	context-free 언어	Push-down automata
type 3 (정규 문법)	정규 언어	Finite automata

<숙제> 2장 연습문제 풀이 : 연습장에 연습한 내용을 그대로 제출

(타이핑하지 말 것)