형식언어와 형식문법
형식언어의 기초
문법의 예(식별자)
ABC := E * 3.14 + ABC / E;
식별자 : ABC, E
문법 : 식별자의 첫 글자는 영문자 + 숫자, 8자 이내
BNF 표기
<식별자> ::= <영문자> {<영문자> | <숫자>}07
알파벳 : 기호들의 유한 집합
T = {a, b, c}
문자열 : 기호들이 0, 1개 이상나열
w = ε, a, ca, abc, ...
ε 공문자열 : 기호들이 0개 나열. 이론적으로 정의한 내용.
aε = εa = a
T*(ε를 포함한 T로 만들 수 있는 모든 문자열) = (ε, a, aa, aaa, abc, abbbc, ...)
T+(ε를 포함하지 않는 T로 만들 수 있는 모든 문자열) = (a, aa, aaa, abc, abbbc, ...)
형식언어 : 문자열들의 집합
형식문법
G : Grammer, 문법, G = (Vn, Vt, P, S)
Vt : 터미널 기호. 더이상 유도할 수 없는 기호 ex) 0, 1
Vn : 논터미널 기호. 유도 할 수 있는 기호 ex) S, A
S : Start, 시작기호
P : Production Rule, 규칙
예)
G = ({S, A}, {0, 1}, P, S)
P : S -> 0 | 0AS
A -> SS | 10 | S1A
S -> 0
S -> 0AS -> 0SSS -> 0000 (터미널 기호까지 와서 종료됨
S -> 0AS -> 0S1AS -> 0S110S -> 001100
S -> 0,0000,001100 (S가 될 수 있는 터미널 기호의 모음)
문법의 4종류
type0 : a -> b
모든 문법을 의미함.
위축형도 포함한다.
type1 : a -> b, | a | ≤ | b |
type0에서 b는 a보다 크다는 규칙을 추가함.(비위축형)
ex)
G1 = ({S,A,B,C}, {a,b,c}, P, S)
P: S -> A, A -> abC | aABC, bB -> bb, CB -> BC, bC -> bb
S -> abC -> abb
S -> aABC -> aabCBC -> aabbbb
S -> abb, aabbbb
∴ S = a^n * b^2n
type2(CFG, Context Free Grammar, 구문분석) : A -> c, A ∈ Vn
type1을 만족하면서 왼쪽은 논터미널, 오른쪽은 제약이 없다.
ex)
G2 = ({S,C}, {a,b}, P, S)
P: S-> aCa, C-> b, C -> aCa
S -> aCa -> aba
S -> aaCaa -> aabaa
S -> aba, aabaa
∴ S = a^n * b * a^ntype3(Regular Grammar, 어휘분석)
type2를 만족하면서 오른쪽은 우선형 또는 좌선형이다.
우선형 : A -> tB, 터미널 기호가 왼쪽에 나옴. B가 오른쪽으로 확장되기 때문에 우선형
자선형 : A -> Bt, 터미널 기호가 오른쪽에 나옴. B가 왼쪽으로 확장되기 때문에 좌선형
ex)
G3 = ({S,B,C}, {a,b}, P, S)
P: S -> aS | aB, B -> bC, C -> a | aC
S -> aB -> abC -> aba
S -> aB -> abC -> abaC -> abaaC -> ... -> aba^m
S -> aS -> aaS -> aaaS -> ... -> a^nS
S -> a^nS -> a^nba
S -> a^nS -> a^nba^m
∴S -> a^nba^m문법의 표현 방법
P : V₀ -> aV₁, V₁ -> bV₀ | a
V₀ -> (ab)^m * aa
정규문법과 정규표현
정규표현
1. 공집합 : ⏀
2. 공문자열 : ε
3. 터미널 기호로 이루어짐 : a ∈ Vt
4. P+Q : a+b
P∙Q : ab
P* : a*, (ab)*, (a+b)*
5. 이 밖의 정규표현은 없다.
정규문법을 정규표현으로 변환
a, b : 정규표현 a는 ε을 포함하지 않음.
X = aX + b의 유일해는 X = a*b 이다.
X -> aX
X -> b
X -> aX | b -> aX + b ( | 를 + 로 표현)
X -> b
X -> aX -> ab
X -> aaX -> aab
...
∴ X = a*b
a*인 이유는 εb의 경우도 포함하기 때문이다.
ex1)
G = ({S}, {a,b}, P,S)
S = aS | bS | b
= (a+b)S + b
= (a+b)*b
ex2)
G = ({S,A}, {a,b}, P,S)
S -> aA | bS
A -> aA | bA | b
A = (a+b)A + b
= (a+b)*b
S = aA + bS
= a(a+b)*b + bS
= bS + a(a+b)*b
= b*a(a+b)*b
ex3)
G = ({S,A,B}, {a,b}, P,S)
S -> aA | bS
A -> aS | bB
B -> aB | bB | ε
S = aA + bS
B = aB + bB + ε = (a+b)B + ε = (a+b)*
A = aS + bB = aS + b(a+b)*
S = aA + bS
= aaS + bS+ ab(a+b)*
= (aa+b)S + ab(a+b)*
= (aa+b)*ab(a+b)*
와우..