형식언어와 형식문법

 

형식언어의 기초

문법의 예(식별자)

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^n

type3(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)*

 

 

와우..