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$
- $T_1 = {A \in V_N | \exists (A\rightarrow w) \in P, with \space w \in V_T}$
- $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}$
- T(G)를 구하고 T(G)에 해당하지 않는 non-terminal symbol을 사용하는 rule 제거
- 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로 변환
- E(G)를 구한다
- $\varepsilon$을 대입한 rule을 구함
- 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로 변환
- $P' = P - {A \rightarrow B | A, B \in V_N}$
P에서 한번 non-terminal symbol에서 단일 non-terminal symbol로 가는 rule 제거 - 모든 non-terminal symbol에 대해 $I_A$구하기
- $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 |