CFG

Context Free Language

• 대부분의 프로그래밍 언어가 속해있다.
• $\alpha \rightarrow \beta , \alpha \in V^+, \beta \in V^*$
• $\alpha \in V_N, \beta \in V^*$

파스트리

• 문장을 트리 구조로 나타낸것
• CFG의 심볼들로 이루어졌다.

Leftmost derivation

• 심볼의 집합이 있을 때 가장 왼쪽에 있는 논터미널 심볼에 프로덕션 룰 수행
• 똑같이 leftmost derivation을 했는데 두 가지 이상의 경우가 나오면 모호한(Ambguous) 문법이라 한다.
• 문법이 모호하면 파싱이 복잡
• 그래서 모호하지 않은 문법으로 만들어야 한다.
  • 하지만 항상 가능한 것은 아니다.

문법을 효과적인 형태로 변환

• useless 프로덕션
• 엡실론 프로덕션
• 단일 프로덕션
• 위 세가지를 없애야 한다.

useless productions

1. 시작 기호로 부터 도달하지 못하면 제거
2. 논터미널 기호로 변환되지 못하면 제거

모든 논터미널 기호가 useful하면 reduced grammar 이다.

$\epsilon$ production

1. 엡실론으로 유도될 수 있는 기호가 있으면 그 기호를 가지고 있는 프로덕션룰을 수정한다.

• 해당 기호를 하나 이상씩 제거할 수 있는 모든 경우의 수를 나열 후 프로덕션으로 편입

2. 시작기호가 엡실론으로 가면 S'을 도입해
   $S' \rightarrow S|\epsilon$ 추가

single productions

1. 프로덕션룰에 단일 기호로 유도되는 것이 있으면
   $A \rightarrow B$ 이면 제거
2. 기호를 제거하고 B의 프로덕션 룰을 A로 가져온다.

위 세 과정을 거치면 Proper 문법이다.

CNF

• Chomsky normal form
• 파스 트리가 바이너리 트리로 나온다

1. $S \rightarrow \epsilon$
2. $A \rightarrow BC$
3. $A \rightarrow a$

• 문법이 위의 형태로만 존재하게 한다.
  만드는 방법

1. proper grammar로 만든다.
2. 터미널 심볼과 논터미널 심볼이 붙어있으면 터미널 심볼을 논터미널 심볼로 치환
3. 논터미놀 심볼이 3개 이상 있으면 왼쪽에 있는 논터미널 심볼 1개를 제외 하고 하나의 묶음으로 치환