type 3

type 3 문법의 형식은 유도 심볼의 오른쪽은 한 문자가 나오고 , 왼쪽에는 넌터미널 터미널 혹은 터미널이 오는 형태이다.

• non-terminal -> non-terminal · terminal
• non-terminal -> terminal · non-terminal
• non-terminal -> terminal

기호 하나의 크기가 문자 하나 즉 1 이라고 할 때 몇 가지 예를 들면 ,

• A -> A · α
• A -> α · A
• A -> α
• ...

type 3 문법을 정규 문법(regular grammar)이라 하고 , 이 문법이 생성하는 언어를 정규 언어(regular language)라 하고 , 이를 컴퓨터로 처리할 수 있도록 인식하는 인식기를 유한 자동(finite automata)이라 한다.

type 3 문법 형태가 어디에 사용되는지를 알아보자. 다음과 같은 if 문이 있다고 할 때 ,

if ( sum > 10) sum = sum + 1;

이를 다음과 같이 구분 구분 나누어서 (이 각각을 token 이라 함)

if ( 변수 > 숫자 ) 변수 = 변수 + 숫자 ;

이와 같이 일련의 스트링을 받아서 token 으로 나누는 일을 스캐너(scanner) 가 하고, 이 스캐너의 출력으로 token 이 나오고, 이 일련의 token 을 입력으로 받아서 이 형식이 if 문 문법에 맞나를 검사하는 작업을 파서(parser) 가 한다.

스캐너가 정규 문법 형태를 인식하는 유한 오토마타를 이용하고 , 파서가 context free 문법 형태를 인식하는 푸시다운 오토마타를 이용한다.