형식 문법

형식 문법: 형식 언어를 생성하는 규칙의 집합

어떤 문자열을 만들 수 있는 규칙 체계를 수학적으로 정의한 것

 

형식 문법 -> 크게 두가지 방법

1. production rule 만을 가지고 정의

2. 문법 G={VN, VT, P, S} 정의

 

* 터미널 기호: 실제 문자열을 이루는 문자들

* 논터미널 기호: 문장의 구조를 만드는 기호

 

문법 G={VN, VT, P, S} 정의

1. VN : 논터미널 기호들의 유한 집합

2. VT : 터미널 기호들의 유한 집합

- VN ∩ VT = ∅, VN ∪ VT = V

- 터미널 기호와 논터미널 기호를 문법 기호(grammar symbol)라 하며 보통 V(vocavulary)로 표시

3. P : 생성 규칙 (Productio rule)의 집합으로 다음과 같다

- α → β, α ∈ V+, β ∈ V*

- α를 왼쪽 부분(left-hand side), β를 오른쪽 부분(right-hand side)

- ->는 왼쪽 부분에 있는 기호가 오른쪽 부분에 있는 기호로 단순히 대체

4. S: VN에 속하는 기호로서 다른 논터미널 기호들과 구별하여 시작 기호임 (start symbol)

 

3번 추가 설명

- 문자열을 실제로 만드는 방법을 정의한 규칙임

- 왼쪽에 있는 기호를 오른쪽에 있는 기호로 바꾸는 규칙임

- α ∈ V+: 반드시 하나 이상의 기호를 가져야 함, β ∈ V* -> 0개 이상의 기호

 

앞으로 사용할 기호들의 일반적 표기법

1. A, B, C와 같은 영문자 대문자로 구성된 기호, 시작기호를 나타내는 S는 논터미널 기호

2. <와 >로 묶어서 나타낸 기호도 논터미널 기호

3. a, b, c와 같은 영문자 소문자로 구성된 기호와 +, -와 같은 연산자 기호, 괄호나 쉼표와 같은 구분자, 0, 1, 2와 같은 아라비아 숫자 등은 터미널 기호

4. X, Y, Z와 같은 영문자 끝부분의 대문자는 터미널 기호와 논터미널 기호를 나타냄

5. 영문자 끝부분의 소문자인 u, v, w, x, y, z 등은 터미널 기호들로 이루어진 문자열

6. α, β, γ와 같은 그리스어 소문자는 문법 기호로 구성된 문자열

7. 만약 아무런 언급이 없으면 첫번째 생성 규칙 왼쪽에 있는 기호가 시작 기호

8. 생성 규칙의 왼쪽 부분에 같은 기호로 구성된 생성 규칙이 여러 개일때 축약해서 사용 가능

    - 예를 들어 α → β1, α → β2   ..    α → β1 | β2

 

예시

G = ( {S, A}, {0, 1}, P, S )

P : S -> 0AS | 0     A -> S1A | 10 | SS

---

* 생성 규칙: 말 그대로 규칙

* 유도 : 실제 과정

 

=> : 유도(derivation)

- 형식 문법에서 문장을 만들어내는 과정

- 만약 α → β가 존재하고 γ, δ ∈V* 이면

    - γαδ => γβδ로 표시

    - 한 문자열에서 생성 규칙을 적용해서 다른 문자열로 바꾸는 것을 의미

=>* : 영번 이상의 유도 (zero  or more derivation)

=>+ : 한 번 이상의 유도 (one or more derivation)

 

α1 =>n αn : α1, α2, α3, ... αn이 V*에 속하고 α1 => α2 => α3 => ... => αn이 존재

- α1은 αn을 생성(produce) 혹은 유도(derive)한다고 함

- αn은 α1으로 감축(reduce)된다고 함

 

->는 생성 규칙에서 사용되는 기호, 단일 화살표(single arrow)

=>는 유도 과정을 나타내는 기호, 이중 화살표(double arrow)

 

ex. 유도하기

G = ( {S, A}, {0, 1}, P, S )

S -> 0AS | 0

A -> S1A | 10 | SS

 

1. 문자열 0은 허용되는가?

S => 0 (S->0) 으로 유도에 의해 생성되니 가능

 

2. 문자열 0000은 허용되는 문장인가?

S => 0AS (S->0AS)

=> 0SSS (A->SS)

=> 00SS (생략)

=> 000S

=> 0000 으로 유도에 의해 생성되니 가능

 

3. 001100은?

S => 0AS (S->0AS)

=> 0S1AS (A->S1A)

=> 001AS (S->0)

=> 00110S (A->10)

=> 001100 (S->0) 으로 유도에 의해 생성되니 가능

 

이런 식으로 문자열이 성립되는지 체크 가능

---

 

문장과 문장 형태

S => w1 => w2 => w3 => ... => wn => w와 같은 유도 과정이 있을 때,

S =>* w이고 w가 V*에 속하면 w를 문장 형태(sentential form)라 하고, w가 VT*에 속할 경우 w를 문장(sentence)라 함

- 즉, 문장 형태는 터미널 기호와 논터미널 기호의 조합 / 문장은 터미널 기호들로만 구성

- 우리가 프로그램을 작성할 때 사용하는 터미널 기호로만 구성된 문장을 언어라 함

 

문장과 문장 형태 구하기

이전 예시 유도 과정에 있는 S, 0AS, 0SSS, 00SS, 000S, 0000 등은 문장 형태

터미널 기호로만 구성된 0000은 문장

문장 0000은 시작 기호 S로부터 생성된다고 함

 

문법 G로부터 생성되는 문장의 집합을 언어라 하고 L(G) 로 표기

문법 G로부터 생성되는 언어는 시작 기호에서 유도될 수 있는 모든 문장의 집합

 

L(G)

- 문법 G로부터 생성되는 문장의 집합

- L(G) = { w | S =>* w, w  ∈ VT* }

* VT*는 터미널 기호로 생성된 모든 문자열의 집합, VT랑 다름

 

ex. G = ( {S, A}, {b, d}, P, S )

P : S -> dAd    A -> dAd    A -> b

S => dAd => dbd

S => dAd => ddAdd => ddbdd

S => dAd => ddAdd => dddAddd => dddbddd

...

L(G) = { d^nbd^n | n >= 1 }

---

 

이러한 문법의 개념은 촘스키(Chomsky, N.)에 의해 처음으로 소개

문법을 생성 규칙에 가해지는 제한에 따라 네 종류로 나누었으며 이를 촘스크 계층 구조 라고 부름

유형	생성 규칙의 형태	설명
0	φAψ → φWψ	무제약 문법(unrestricted) 문법 생성 규칙에 어떠한 제한도 두지 않는 경우
1	α → β 단, |α| ≤ |β|, α ∈ V⁺, β ∈ V*	문맥인식(context-sensitive) 문법 생성 규칙에 |α| ≤ |β|의 제한을 가하는 것으로 α는 공문자열이 될 수 없음 (변환 거치니까 공문자열 나와서 줄어들면 안되니까) 치환 규칙의 길이가 줄어들면 안 됨
2	A → β 단, A ∈ VN, β ∈ V*	문맥자유(context-free) 문법 생성 규칙의 왼쪽 부분은 하나의 논터미널 기호, 오른쪽 부분은 문자열 문맥에 상관없이 하나의 비단말기호를 다른 문자열로 바꿀 수 있음
3	A → tB, A → t 또는 A → Bt, A → t 단, t ∈ VT*, A, B ∈ VN	정규 문법(regular) 문법 생성 규칙에 따라 두가지 종류 1. A → tB, A → t와 같은 생성 규칙 .. 우선형(right-linear) 문법 - 논터미널 기호가 항상 오른쪽 끝에 옴 2. A → Bt, A → t .. 좌선형(left-linear) 문법 - 논터미널 기호가 항상 왼쪽 끝에 옴

 

문법 판별 방법

- 우선 문맥 인식 문법인지 판별

- 문맥 인식 문법이 아니라면 무제약 문법

- 문맥 인식 문법이라면 문맥 자유 문법인지 판별

- 문맥 자유 문법이 아니라면 문맥 인식 문법

- 문맥 자유 문법이라면 정규 문법인지 판별

- 정규 문법이 아니라면 문맥 자유 문법

 

ex.

S -> 0AS | 0

A -> S1A | 10 | SS

일단 길이 안줄어드니 문맥 인식 문법

문맥 자유 문법인지 확인하려면 왼쪽 부분이 논터미널 기호 하나인지.. -> 문맥 자유 문법

마지막 S->0AS는 정규 문법에 맞지 않음

- 문맥 자유 문법

 

S -> 0S | 0B

B -> 1C

C -> 0C | 0

문맥 인식이고, 자유이고, 정규 문법..(논터미널이 오른쪽 끝)

- 정규 우선형 문법

 

정규 문법 ⊂ 문맥자유 문법 ⊂ 문맥인식 문법 ⊂ 무제약 문법 

 

형식 언어 이론에서 자주 인용되는 언어들

1. 단순 매칭 언어(simple matching language) : CFL (context-free)

- Lm = { a^nb^n | n >= 0 }

- a가 n개 나오고 b가 n개

 

2. 중복 매칭 언어(double matching language) : CSL (context-sensitive)

- Ldm = { a^nb^nc^n | n>= 0 }

- a, b, c가 n개

 

3. 좌우 대칭 언어(mirror image language) : CFL

- Lmi = {ww^R | w ∈ VT*}

- 중심축 기준 완벽히 대칭 (abba, abccba)

 

4. 회문 언어(pailndrome language) : CFL

- Lr = { w | w = w^R }

- 문자열을 뒤집어도 같은 문자열

 

5. 괄호 언어(parenthesis language) : CFL

- Lp = { w | w는 balanced  parenthesis }

- 괄호가 열리고 닫히는 구조가 올바른 문자열

 

CFL은 스택 1개로 처리 가능, CSL은 스택 1개로는 부족

 

문법	언어	인식기
type 0 (무제약 문법)	재귀 열거 언어	튜링 기계
type 1 (문맥인식 문법)	문맥인식 언어	선형한계 오토마타
type 2 (문맥자유 문법)	문맥자유 언어	푸시다운 오토마타
type 3 (정규 문법)	정규 언어	유한 오토마타

 

* 정규 언어 추가 설명

- 가장 단순한 언어

- 단어를 구성하는 규칙을 정의

- 정규 표현으로 표현 가능

- DFA, NFA로 인식 가능

 

문법의 표기법

- 정규 표현 (Regular Expression)

- 문법 도표 (Syntax Diagram)

- BNF

- EBNF

 

언어의 표현 방식

- 언어는 일반적으로 집합의 표기법으로 표현

- L1 = {a^(2n+1) | n>=0 }

- L2 = {a^nb^nc^n | n >= 0}

- 정규 언어는 정규 표현이라는 특수한 방식으로 표기 가능