Total
1. 형식언어의 기초
•
형식언어
◦
프로그래밍 언어
◦
문자열들의 집합
◦
어떤 알파벳에서 얻은 기호들로 구성되어있는 문자열들의 집합
•
문자열
◦
알파벳을 구성하는 기호들이 0, 1개 이상 나열
◦
기호가 0개일때 ε 문자열로 표현
•
알파벳
◦
기호들의 유한 집합
•
예시
•
T스타, T클로저
◦
집합(a,b,c)으로 만들어질 수 있는 모든 경우의 수 + 공문자열 (ε)
•
T대거
◦
T스타에서 공문자열(ε)이 없는 집합
•
cf) ε
◦
공문자열; 문자열의 길이가 0인 것
2. 형식문법
2.1. 형식 문법
•
G = (Vn, Vt, P, S)
•
Vn: 논터미널 기호들의 유한집합
◦
{S, A}
◦
종점(터미널)이 아님. 왼편에 위치
◦
언어에서 문자열을 생성하는 데 사용되는 중간과정의 기호로서 보통 대문자로 표시
•
Vt: 터미널 기호의 유한집합
◦
{0, 1}
◦
정의된 언어의 알파벳이나 기호로서 영문자의 소문자나 아라비아 숫자, 연산자 기호 등
•
P: 생성규칙의 집합
•
S: 시작기호
2.2. 예시
•
G=({S,A},{0,1},P,S)
◦
P: Production Rule (생성 규칙)
◦
S: Start (출발기호, 시작 기호)
•
문법 규칙을 적용해서 유도 가능
◦
A → SS로 변경 가능
◦
SS의 S는 0으로 변경가능
◦
0AS → 0000으로 변경가능
3. 문법의 4종류
3.1. chomsky 계층구조
•
type 0
◦
a → b
◦
모든 문법 규칙
•
type 1
◦
a → b, | a | ≤ | b |
◦
크기 = 문자열의 길이 (줄어들지 않음)
◦
비위축성 문법
•
type 2 (CFG)
◦
A → γ, A ∈ Vn
◦
A는 단하나의 기호로 되어있음. Vn: 논터미널 기호
◦
Context Free Grammar
◦
구문분석에 사용
•
type 3 (Regular Grammar)
◦
정규문법
◦
어휘분석에서 사용
◦
t: 터미널 기호
3.2. 타입간의 포함관계
•
chomsky 계층구조 타입간의 포함관계
3.3. 예시
•
type 1 예시
◦
반드시 시작기호(S)에서 유도, 시작해야함.
◦
오른쪽의 길이가 왼쪽의길이보다 같거나 크다
◦
오른쪽이 더 늘어나야함
•
type2 예시
◦
왼편이 단 하나의 non terminal 기호로 되어있음
◦
오른편은 제약이 없음. (줄어들지 않음)
◦
aCa는 터미널이 가운데 껴있음 (좌선형, 우선형 둘다 아님. type3 가 아님)
•
type3 예시
◦
왼편이 단하나의 non terminal로 되어있음 (type2)
◦
오른편을 보면 terminal 기호가 나오다가 non terminal 기호가 딱 하나 나옴 (우선형)
▪
정규문법
4. 문법의 표현 방법
4.1. 문법도표
•
문법을 그림으로 표현한 것
4.2. BNF / EBNF 표기법
•
BNF
◦
특수한 meta symbol을 사용하여 프로그래밍 언어의 구문을 명시하는 표기법
•
EBNF (Extended BNF)
◦
중괄호를 사용하여 반복 기능 추가
▪
반복되는 부분(repetitive part): { }
▪
선택적인 부분(optional part): []
▪
괄호와 택일 연산자(alternative): ( | )
•
예시
4.3. 정규표현
•
a + b = a or b 를 의미
•
예시
5. 정규문법과 정규표현
•
정규문법 → 정규표현
•
정규표현을 터미널기호로만 구성된다
•
공식
•
증명
•
예시 1
•
예시 2
•
예시 3
