컴파일러 2강. 형식언어와 형식문법, 오토마타 이론

 

형식언어와 형식문법 

형식언어는 어떤 알파벳에서 얻은 기호 심볼들로 구성되는 문자열 스트림의 집합이고 형식문법은 형식언어를 생성하기 위한 규칙이다.

형식문법은 논터미널 기호들의 유한집합 VN, 터미널 기호들의 유한집합 VT, 생성규칙의 집합 P, 시작기호 S로 구성되며 

 

 

G = (VN, VT, P, S) 로 표현한다.

 

 

형식문법에서 터미널(terminal) 기호는 정의된 언어의 알파벳이나 기호로서 영문자의 소문자나 아라비아 숫자, 연산자 기호 등이 여기에 속하고, 논터미널(non-terminal) 기호는 언어에서 문자열을 생성하는 데 사용되는 중간과정의 기호로서 보통 대문자로 표시한다.

 

 

 

촘스키 계층구조 Chomsky Hierarchy

생성규칙의 형태에 가해지는 제한에 따라 미국의 영문학자 촘스키는 Type0, Type1, Type2(=CFG), Type3(정규문법) 등의 4종류로 형식문법을 나누었으며 이를 촘스키 계층구조라고 부른다. 형식 문법을 표현하기 위해서 정규표현(regular expression), 문법도표(syntax diagram), BNF(Backus-Naur From), EBNF(Extended BNF) 등의 방법을 사용한다. 

 

 

 

형식 (Type)	생성 규칙의 형태	제약 조건	Recognizer
형식 0문법 (Unrestricted Grammar)	생성 규칙에 대한 제한 없음	어떠한 제약조건이 없음	Turing Machine
형식 1문법 (Context-sensitive Grammar)	α → β (단, | α | ≤ | β |)	생성규칙에서 2개 이상의 non-terminal이 terminal 을 생성할 수 없다.	Linear bounded Automata
형식 2문법 (Context-free Grammar)	Α → γ	형식 1문법의 제약조건과 함께 생성규칙의 왼편에는 단 하나의 non-termina만이 사용될 수 있다.	Pushdown Automata
형식 3문법 (Regular Grammar)	(1) Α → tΒ, Α → t (2) Α → Βt, Α → t	형식 1,2문법의 제약조건과 함께 생성규칙에 따라 생성된 결과는 t1At2와 같은 형태를 가질 수 없다.	Finite Automata

 

 

예시)

1. S → aAB, AB → a, A → b, B → AB생성규칙 AB → a에서 2개 이상의 non-terminal이 terminal을 생성하였으므로 형식 1이상의 문법이 안되고 형식 0문법이다.
2. S → aAB, AB → bB, B → b, A → aB생성규칙 AB → bB의 왼편에서 2개 이상의 non-terminal이 사용되었으므로 형식 2이상의 문법은 안되고 형식 1 문법이다.
3. S → aBa, B → aBa, B → b생성규칙 B → aBa의 생성결과는 t1Bt2와 같은 형태를 가지므로 형식 3문법이 될 수 없고 형식 2 문법이다.
4. S → aB, B → bA, B → b, B → a, A → aB, A → a 모든 생성규칙이 A → tA 또는 A → t 형태임으로 형식 3문법이다.

 

 

 

방송대 1학기 이산수학에서 잠시 다루었던 오토마타. 오토마타는 이론상으로는 계산 능력이 있는 자동 기계가 입력을 받아 상태를 전이하여 출력을 내놓는 것과 그 이론을 뜻한다.

 

 

 

 

주요용어

용어	해설
유한 오토마타 (finite automata)	어떤 알파벳 T로부터 만들어지는 문자열의 특별한 것들을 받아들이는 시스템의 수학적 모델로서, 그 시스템이 변화할 수 있는 상태가 유한개인 것
비결정적 유한 오토마타 (NFA)	어떤 상태에서 주어진 하나의 입력기호를 보고, 갈 수 있는 다음 상태가 두개 이상 존재할 수 있는 유한 오토마타
결정적 유한 오토마타 (DFA)	하나의 입력문자열에 대하여 오직 하나의 다음 상태가 결정되는 것
상태전이도 (transition diagram)	오토마타의 각 상태(state)를 노드(node)로 나타내며, 이동함수δ(q,a) =p에 대해서는 상태 q에서 p로 가는 레이블(label)이 a인 지시선(directed arc)으로 표기. 또한 종결상태들은 이중 원(double circle)으로 나타내고, 시작상태는 시작지시선으로 표시하는 유향 그래프(directed graph)
상태	오토마타에서 입력기호에 의하여 전이된 것을 상태라하며 상태전이도에서 원으로 표현한다.

 

 

정리하기

 

(1) 유한 오토마타(finite automata)란 어떤 알파벳 T로부터 만들어지는 문자열의 특별한 것들을 받아들이는 시스템의 수학적 모델로서, 그 시스템의 변화할 수 있는 상태가 유한개인 것이다.

 

(2) 유한 오토마타는 입력으로 문자열을 받아서, 그 문자열의 그 언어의 문장이면 "yes"를 답하고 그렇지 않으면 "no"라고 답하는 프로그램으로 어휘분석기는 유한 오토마타의 대표적인 예이다.

 

(3) 유한 오토마타를 표현하는 방법에는 두 가지가 있다. 먼저, 정의에 따라서 5가지 구성원소들을 형식(formal)에 맞게 정확히 표현하는 방법이 있다. 다음으로는 상태전이도(transition diagram)를 사용하여 비형식적(informal)으로 표현하는 방법인데 그림을 통하여 쉽게 개념이 들어오기 때문에 일반적으로 유한 오토마타를 설명할 때 상태전이도를 많이 사용한다.

 

(4) 유한 오토마타는 결정적 유한 오토마타(Deterministic Finite Automata; DFA)와 비결정적 유한 오토마타(Nondeterministic Finite Automata; NFA)로 나누어진다.

 

(5) 결정적 유한 오토마타(DFA)란 하나의 입력문자열에 대하여 오직 하나의 다음 상태가 결정되는 유한 오토마타이다.

 

(6) 비결정적 유한 오토마타(NFA)란 두 가지가 있는데 먼저, ε에 의한 전이가 있는 경우와 다음으로 어떤 상태에서 주어진 하나의 입력기호를 보고, 갈 수 있는 다음 상태가 두 개 이상 존재할 수 있는 유한 오토마타이다.

 

(7) NFA는 언어의 구조를 쉽게 표현할 수 있지만 DFA보다 프로그램으로 구현하기 힘들다. 반면 DFA는 NFA보다 프로그램으로 구현했을 때 효율면에서 좋다. 이러한 이유로 NFA가 언어의 구조를 표현하고 일반적인 구현은 DFA로 해야 효율적이다. 따라서 DFA에서 NFA로, NFA에서 DFA로의 변환을 필요로 하며 서로 변환 가능하다.

 

(8) DFA는 상태수를 최소로 줄일 수가 있다. 이렇게 해서 컴파일러의 효율을 높이는 것이다.

 

(9) 정규 표현, 정규 문법, 유한 오토마타는 서로 동치관계에 있으며 서로 변환가능하다.