Context Free Grammar

Context free grammar(CFG)

• $G = (V_N, V_T, P,S)$
  • $V_N$ : non-terminal symbols들의 집합
  • $V_T$ : terminal symbols들의 집합
    • $V_N \cap V_T = \varnothing, V_N \cup V_T = V$
  • $P$ : productions
    • $\alpha \rightarrow \beta, \alpha \in V^+, \beta \in V^*$
    • $\alpha \in V_N, \beta \in V^*$
  • $S$ : 시작 기호(non-terminal symbol)

Context free language(CFL)

• context free grammar에 의해 생성된 언어
• $L(G) = \{w|w \in V_T^*\space and\space S\overset{*}\Rightarrow w\}$
• $L = L(G)$이면 $L \subseteq \Sigma^*$는 context free language

Derivation

• 왼쪽부터 변환 or 오른쪽부터 변환

Parse trees(Derivation tree)

• 특정 CFG의 기호들로 라벨 된 트리
  • 단말노드 : terminal symbol 또는 $\varepsilon$
  • 중간노드 : non-terminal symbol
  • Root노드 : Start symbol

Leftmost (rightmost) derivation

• leftmost derivation
  • $\underset{lm}\Rightarrow \subseteq V^* \times V^*$
  • $\alpha = uA\rho, \beta = u\gamma\rho$
    $u \in \Sigma^*, \rho \in V^*, (A\rightarrow \gamma) \in P$이면
    모든 $\alpha, \beta \in V^*$에 대하여, $\alpha \underset{lm}\Rightarrow \beta$
  • 가장 왼쪽의 not-terminal 기호를 계속해서 대체
• rightmost derivation
  • $\underset{rm}\Rightarrow \subseteq V^* \times V^*$
  • $\alpha = \lambda Av, \beta = \lambda\gamma v$
    $v \in \Sigma^*, \lambda \in V^*, (A\rightarrow \gamma) \in P$이면
    모든 $\alpha, \beta \in V^*$에 대하여, $\alpha \underset{rm}\Rightarrow \beta$
  • 가장 오른쪽의 not-terminal 기호를 계속해서 대체

모호한 문법

• 같은 문자열에 대해 두 개 이상의 다른 leftmost(rightmost) derivation 존재
  → 2개 이상의 parse tree 존재
  ⇒ 모호함
• 모호함을 증명하려면 2개 이상의 parse tree를 생성

Parsing and membership problem

• 파싱 하는 것은 w가 L(G)에 포함되는지 찾고 그렇다면 w를 derivation
• membership problem(인식 문제)
  • 주어진 문자열 w와 언어 L에 대하여 w가 L에 포함되는지 결정

모호한 context free grammar

• context free grammar는 어떤 문자열 w에 대해 두 개 이상의 derivation이 존재할 경우 모호하다
• context free grammar는 본질적으로 모호함
• 문법이 모호한지 여부는 파싱의 복잡성에 영향을 줌
• 모호하지 않은 문법이면 더 쉽게 파싱이 가능
• context free grammar를 모호하지 않게 만드는 것은 불가능
  • 몇 가지 CFL에 대해 모호함을 제거하면 가능할 수도
  • 모호한 문법을 모호하지 않게 자동으로 변환하는 것은 불가능

CFG and Backus-Naur Form(BNF)

• 프로그래밍 언어는 재귀적 구조를 가짐
• 이런 재귀적 구조를 위한 표기법
• 프로그래밍 언어의 구문
• Backus-Naur Form
  • <expr>::=<expr>+<term>|<term>
  • <term>::=<term>+<factor>|<factor>
• 모호함
  • 결과는 다를 수 있음

Grammar transform( 문법 변환)

Context-free grammar equivalence

• 같은 언어를 생성하면 $G_1 = G_2$

문법 변환을 해야 하는 이유

• 많은 문법은 같은 언어를 생성
• CFG에서 w가 L(G)에 속하는지 확인하는 데 걸리는 시간 복잡도
  • CKY 알고리즘 : $O(|w|^3)$
• 파싱 알고리즘은 어떤 문법에서 더 효율적
  • 사용하지 않는 production, $\varepsilon$-production rule, 단일 production rule 제거
• ⇒ 효율적인 파싱 알고리즘을 위해 문법 변환

필요 없는 productions

• CFG에서 필요 없는 rule을 포함하고 있을 수 있음
• terminal symbol로 변환되지 않는 non terminal symbol
• 사용되지 않는 non-terminal symbol

필요 없는 productions을 제거하는 방법

• $T(G)$ : terminal symbol로 변환되는 non terminal symbol들의 집합
  ${A \in V_N | \exists w \in V_T, A\overset{+}\Rightarrow w}$
  • $T_1 = {A \in V_N | \exists (A\rightarrow w) \in P, with \space w \in V_T}$
    바로 terminal symbol로 가는 non terminal symbol
  • $T_{n+1} = T_n \cup {A \in V_N | \exists (A\rightarrow \beta) \in P, with \space \beta \in (T_n\cup V_T)^*}$
    $T_n$이나 불필요한 non-terminal symbol로 가는 non-terminal symbol
  • $T_{n+1} = T_n, T(G) = T_n$
• $S\notin T(G)$이면, $L(G) = \varnothing$
• $S\in T(G)$이면, $U(G) = \{A \in T(G) | \exists\alpha,\beta \in (T(G) \cup V_T)^*, S \overset{*}\Rightarrow \alpha A \beta\}$
  필요한 non terminal symbol 집합
• $U(G)$ : 시작 기호에서 도달할 수 있는 nonterminal symbol들의 집합
  • $U_1 = {A \in T(G) | \exists(S \rightarrow \alpha A\beta) \in P, \space with \space \alpha,\beta \in (T(G) \cup V_T)^*}$
  • $U_{n+1} = U_n \cup {B \in T(G) | \exists(A \rightarrow \alpha B\beta) \in P, \space with \space A \in U_n, \alpha,\beta \in (T(G) \cup V_T)^*}$
  • $U_{n+1} = U_n, U(G) = U_n \cup {S}$

1. T(G)를 구하고 T(G)에 해당하지 않는 non-terminal symbol을 사용하는 rule 제거
2. U(G)를 구하고 U(G)에 해당하지 않는 non-terminal symbol을 사용하는 rule 제거

축소된 CFG(Reduced CFG)

• 모든 non terminal이 사용되는 CFG
  • 필요 없는 rule이 제거되지 않으면 어떤 파서들은 loop를 돌 것이다.

$\varepsilon$-production rules 제거

• $\varepsilon$-production rules : A → $\varepsilon$
• $E(G)$ : 한 번 이상 derivation 해서 $\varepsilon$이 되는 non-terminal symbol
  (제거해도 되는 non-terminal symbol들의 집합)
  ${A \in V_N | \ A \overset{+}\Rightarrow \varepsilon}$
• $E_0 = { A \in V_N | (A\rightarrow \varepsilon) \in P}$
• $E_{i+1} = E_i \cup {A | \exists(A\rightarrow B_1,...,B_j,...,B_k) \in P, \space with \space B_j\in E_i, i\le j\le k}$
• $E_0 \subseteq E_1 \subseteq ... \subseteq E_i \subseteq E_{i+1} \subseteq ... \subseteq V_N$

$\varepsilon$-free grammar

• $G = (V_N, V_T, P,S)$로 $G' = (V'_N, V_T, P', S')$ 생성
• $L(G') = L(G)$
• $P'$ 는 $S' \rightarrow \varepsilon, \space and \space S' \rightarrow \varepsilon \in P' \space iff \space \varepsilon \in L(G)$를 제외하고는 $\varepsilon$-rule을 가지지 않음
• $S'$는 production에서 오른쪽에 나타나지 않음
• $G'$이 $\varepsilon$-free grammar

$\varepsilon$-free grammar로 변환

1. E(G)를 구한다
2. $\varepsilon$을 대입한 rule을 구함
3. S가 E(G)에 포함되면 S’ → S | $\varepsilon$

Single production rule 제거

• single production rule : $A \rightarrow B, A,B \in V_N$
  non terminal symbol이 non-terminal symbol로 가는 것 → 사이클 형성
• chain rule을 제거해야 함
• $I_A : {B \in V_N | A \overset{+}\Rightarrow B} \space for A \in V_N$
  non-terminal symbol에서 한번 이상 derivation 해서 non-terminal symbol로 가는 것
  • $I_{A,0} = {B\in V_N | (A \rightarrow B) \in P}$
  • $I_{A, i+1} = I_{A,i} \cup {C \in V_N | \exists(B \rightarrow C) \in P, \space with \space B \in I_{A,i}}$
  • $I_{A,0} \subseteq I_{A,1} \subseteq ... \subseteq I_{A,i} \subseteq I_{A,i+1} \subseteq ... \subseteq V_N$
  • $I_{A,i_0} = I_{A,i_{(0+1)}}$

Cycle-free grammar

• $G = (V_N, V_T, P,S)$로 $G' = (V'_N, V_T, P', S')$ 생성
• $L(G') = L(G)$
• $P'$ 에 있는 모든 rule은 $A\rightarrow \alpha$ 형태 ($|\alpha|\ge2 \space or \space \alpha \in \Sigma \space or \space S' \rightarrow \varepsilon$ 일 때)
• $S'$는 production에서 오른쪽에 나타나지 않음
• $G'$이 cycle-free grammar

Cycle free grammar로 변환

1. $P' = P - {A \rightarrow B | A, B \in V_N}$
   P에서 한번 non-terminal symbol에서 단일 non-terminal symbol로 가는 rule 제거
2. 모든 non-terminal symbol에 대해 $I_A$구하기
3. $P'$에 위에서 구한 $I_A$ 에 해당하는 rule 붙여주기

적절한 CFG

• 축소된 CFG
• $\varepsilon$-free CFG
• cycle-free CFG