Context Free Grammar

2023. 9. 28. 07:24전공/컴파일러

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

'전공 > 컴파일러' 카테고리의 다른 글

Lex  (0) 2023.09.28
Lexical analysis  (0) 2023.09.28
Finite Automata  (0) 2023.09.28
Regular expression  (0) 2023.09.28
Formal Language, Grammar and Automata  (0) 2023.09.28