[Compiler] 2. Formal language and grammar

Computability, Decidability, Undecidability

• 모든 입력에 대해 함수가 정의되어 있는지 결정

 

Automata theory

계산 능력이 있는 추상 기계와 그 기계를 이용해서 풀 수 있는 문제들을 연구하는 컴퓨터 과학

• "장치"는 물리적 하드웨어일 필요가 없다.
• 컴퓨터 과학의 근본적인 질문은
  다양한 모델의 기계가 할 수 있는 것과 없는 것을 알아본다.

 

Motivations

ex)
문자열을 입력하고 다음 두 가지 가능한 답변을 반환하는 일종의 black box를 가정
Black box에 input으로 문자열 w를 입력했을 때
YES -> w는 언어에 속한다.
NO -> w는 언어에 속하지 않는다.

Language로부터 유효한걸 어떻게 기술할 것인가?

• Automaton : 언어를 인식 또는 수용한다.
• Grammar : 언어를 생성한다.

 

Formal language (형식 언어)

Alphabet (알파벳)

알파벳 ∑는 유한하고 공집합이 없는 집합이다.

ex)

• Binary : ∑ = {0, 1}
• All lower-case letters : ∑ = {a, b, c, ..., z}
• Alphanumeric : ∑ = {a-z, A-Z, 0-9}
• DNA molecule letters : ∑ = {A, C, G, T}

 

String (문자열)

문자열 또는 단어는 알파벳에서 선택된 유한개의 집합이다. 

• ε (epsilon) : 빈 문자열

ex)

• ∑ = {a, b, c}
• string : a, ab, ccba, ...
• |string| = 1, 2, 4, ...
  
  
• x = abcd, y = efgh
• xy = abcdefgh
• xε = abcd
  
  
• a^n = aaa...aa (# of a = n)

 

Power of an alphabet (∑*, ∑+)

1. ∑k : k 길이의 문자열 집합

2. ∑* : 0 이상의 길이의 문자열 집합

3. ∑+ : ∑* - {ε} = 1 이상의 길이의 문자열 집합

ex)

• ∑ = {a, b, c}
• ∑2 = {aa, bb, cc, ab, ba, ...}
• ∑* = {ε, a, b, c, aa, bb, cc, ab, ..., aaa, ...}
• ∑+ = {a, b, c, aa, bb, cc, ab, ..., aaa, ...}

 

(Formal) Language (L)

Language L은  ∑*의 부분집합이다. ( L ⊆ ∑* )

ex)

• ∑ = {a, b}
• L1 = {a, ba, bbbb}
• L2 = {aaa, bbb, aba, bba}
• L3 = {(a^n)(b^n) | n >= 1} = {ab, aabb, aaabbb, ...}

 

Membership (recognition) problem

w ∈ ∑* 이 주어졌을 때 Language L에 속하는가?에 대한 문제를 앞으로 풀것이다.

이것을 하는게 컴파일러

 

Grammar

"legal" 문자열 생성을 허용하는 Rules로 Language를 기술하는 것

즉 Language를 생성하는 Rule이다.

ex) Spring Grammar

• Sprint-Sent -> Spring-subj Spring-Verb
• Spring-Subj -> 새가 | 꽃이 | 싹이
• Spring-Verb -> 노래한다 | 핀다 | 난다
  
  
• Spring-Sent -> Spring-subj Spring-Verb -> 새가 Spring-Verb -> 새가 노래한다
• L(Sring Grammar) = { 새가 노래한다, 새가 핀다, 새가 난다, 꽃이 노래한다, 꽃이 핀다, ...}

 

(Formal) Grammar

Grammar는 G = (VN, VT, P, S)로 구성되어 있다.

• VN : non-terminal symbols의 유한집합
• VT : terminal symbols의 유한집합
• V = VN ∪ VT, VN ∩ VT = ø
• P : productions(생성 규칙)의 유한집합
  α → β, α ∈ V+, β ∈ V
  α : left-hand side (lhs)
  β : right-hand side (rhs)

 

Further notation of grammar ( 문법의 추가 표기법)

• VN : upper-case letters
• VT : lower-case letters

ex1)

S -> dingdongA
A -> dengS | deng

• A -> dengS
  A -> deng
  Grouping

ex2)

P: S -> 0AS    S ->0    A -> S1A    A -> 10    A -> SS

• VN : {S, A}
• VT : {0, 1}
• # of production rule : 5
• G = ({S, A}, {0, 1}, P, S)

 

Derivation ( => , 유도)

한 문자열에서 생성 규칙을 한 번 적용해서 다른 문자열로 바꾸는 것을 나타냄

	0번 이상 derivation
	1번 이상 derivation
	n번 derivation

 

L(G), Language Generated by a Grammar G

L(G) = {w | w ∈ VT* and S *=> w}

문법 G = (VN, VT, P, S)가 주어졌을때, L(G)로 표현된 G에 의해 생성되는 language는 집합이다.

 

The Chomsky Hierarchy (춈스키 계층 구조)

Type	Grammar	Production Rules
0	Unrestricted	α → β
1	Context-Sensitive	α → β |α| <= |β|, α ∈ V+, β ∈ V*
2	Context-Free	α → β α ∈ VN, β ∈ V*
3	Regular	α → tβ | t (right linear) α → βt | t (left linear) α, β ∈ VN, t ∈ VT*

ex1)

S -> 0AS | 0
A -> S1A | 10 | SS
=> Context-Sensitive, Context-Free (O), Regular(X)

ex2)

S -> A
A -> aaC | aABC
bB -> bbb
bC -> bb
=> Context-Sensitive (O), Context-Free, Regular(X)

ex3)

S -> 0S | 0B
B -> 1C
C -> 0C | 0
=> Context-Sinsitive, Context-Free, Regular (O)

 

Hierarchy of Languages and recognizer

Grammar	Language	Recognizer
Unrestricted	Recursively enumerable set	Turing machine
Context-Sensitive	Context-Sensitive language	Linear bounded automata
Context-Free	Context-Free language	Pushdown automata
Regular	Regular language	Finite automata