[Compiler] 7. Context Free Grammar

Context Free Grammar (CFG)

context free grammar G = (VN, VT, P, S)로 구성되어있다.

• V_N : non-terminal symbol의 유한개 집합
• V_T : terminal symbol의 유한개 집합
  • VN ∩ VT = ø
  • VN ∪ VT = V
• P : productions 유한 집합
  • a -> v, a ∈ V+, b ∈ V*
  • a ∈ VN, b ∈ V*
• S : start symbol

 

Context free language (CFL)

grammar로부터 생성된 Language

• context free grammar G=(VN, VT, P, S)가 주어졌을 때, G에 의해 생성된 언어는 집합이다.
• L(G) = {w | w ∈ VT* and S =*> w}
  => S에서 시작해 0번이강 derivation 수행해 w에 도착하는 집합

language L ⊆ ∑*는 context-free grammar G의 경우 L = L(G)인 경우에만 context-free language다.

 

Examples of context free grammar

G1 = ({S}, {a, b}, P, S)

P : S -> aSb | ab

• L(G1) = {(a^i)(b^i) | i>= 1}
• S -> ab
• S -> aSb -> aabb

 

Derivation

G2 = ({E}, {+, *, (, ), a}, P E)

P: E -> E + E | E * E | (E) | a

Derivations of the string : a + a * a

• E => E * E => E + E * E => a + E * E => a + a * E => a + a * a
• E => E + E => a + E => a + E * E => a + a * E => a + a * a
• E => E * E => E * a => E + E * a => E + a * a => a + a * a
• E => E + E => E + E * E => E + E * a => E + a * a => a + a * a

 

Parse trees (Derivation tree)

Parse trees는 특정 CFG의 기호로 label이 지정된 tree다.

• Leaves : terminal symbol || ε이 될 수 있다. 즉, 단말 노드
• Interior nodes : non-terminal symbol
• Root : start symbol
  
  
• Tree 생성시 root로 도달 가능 => Token에 문제 없다는 의미

ex)

• G2 = ({S}, {(, )}, P, S)
• P : S -> SS | (S) | ()
• S => SS => (S)S => (())S => (())()

 

Leftmost derivations

context-free grammar G가 주어졌을 때, leftmost derivation relation은 binary relation이다. (leftmost = lm)

즉, 가장 왼쪽의 Non-terminal 기호를 계속해서 derivation 하는 것

• a,b ∈ V*가 있을 때, a =>(lm) b는 u ∈ ∑*, p ∈ V*, (A -> y) ∈ P이라면
• a = uAp -> b = uyp

Rightmost derivations

가장 오른쪽의 Non-terminal 기호를 계속해서 derivation 하는 것

• a =>(rm) b
• a = uAv -> b=uyv

ex)

Leftmost

• E => E * E => E + E * E => a + E * E => a + a * E => a + a * a
• E => E + E => a + E => a + E * E => a + a * E => a + a * a

Rightmost

• E => E * E => E * a => E + E * a => E + a * a => a + a * a
• E => E + E => E + E * E => E + E * a => E + a * a => a + a * a

 

Ambiguous grammar

ex)

• G = ({E}, {+, *, (, ), a}, P, E)
• P : E -> E + E | E * E | (E) | a
• 같은 문자열인데, 서로 다른 leftmost(rightmost) derivation이 존재한다. -> 위의 예시 참조
  • E => E * E => E + E * E => a + E * E => a + a * E => a + a * a
  • E => E + E => a + E => a + E * E => a + a * E => a + a * a

• parse tree도 서로 다른게 존재한다.

위의 예시와 같이 서로 다른 leftmost(rightmost) derivaion가 존재할 경우, 이 문법을 모호하다고 한다.

 

Ambiguous context free grammar

context free grammar G가 ambiguous하다는 것은

어떤 문자열 w ∈ L(G)가 서로 다른 2개의 leftmost(rightmost) derivation이 존재한다는 것이다.

• unambiguous하다는 것은 어떤 문자열에 도달하는 derivation이 하나만 존재하는 것이다.
  이는 증명하기 쉽지 않다.
• Context-free language는 본질적으로 애매하다.
  -> 모든 CFG G가 모두 ambiguous하기 때문 => L를 생성하는 G가 여러개 있을 수 있기 때문이다.

 

Parsing and membership problem

CFG G = (VN, VT, P, S)가 주어졌을 때, 어떤 문자열 w가 L(G)에 속하는지 속하지 않는지 판단하는 문제가 parsing이다.

• parsing에 성공 -> L(G)에 속한다.
• Parsing에 실패 -> L(G)에 속하지 않는다.

 

Grammar가 모호하다는 것을 증명하는 방법

=> 하나의 문자열에 대해 서로 다른 Parse Tree를 만든다.

*** 서로 다른 Parse Tree를 그릴 때, left || right 중 하나로만 derivation을 해야한다.

ex)

G = ({S}, {a, b}, P, S)

P : S -> aSb | SS | ε

• S => aSb => aaSbb => aabb
• S => SS => aSbS => aaSbbS => aabbS => aabb
• leftmost로 진행시 하나의 문자열에 대해 서로 다른 leftmost derivation이 나타났기 때문에 이 문법은 모호하다.

 

Unambiguous grammars

unambiguous 하다면 더 빠르게 인식 가능하다.

ex)

• G' = ({E, T, F}, {+, *, (, ), a} P', E)
• P' =
  E -> E + T | T
  T -> T * F | F
  F -> (E) | a
• 앞의 예시에선 *와 +가 같은 level에 있어 문제가 발생했다. 따라서 rule을 변경해 우선순위가 다르게 표현했다.

 

Ambiguous context free grammar

grammar가 ambiguous한지 아닌지는 parsing의 복잡성에 영향을 준다.

• parsing의 복잡성은 시간을 줄이기 위해 중요하다.
• 어떤 문자열 w가 L(G)에 속하는지 확인하기 위해선 |w| = n이라면 O(n)의 시간이 걸린다.
• unambiguous한 grammar에 대한 Parsing algorithms은
  ambiguous한 grammar에 대한 parsing algorithm보다 더 효율적이다.
• context-free grammar를 수정하는 것이 항상 가능한 것은 아니다.
  • 일부 CFL에 대한 ambiguity를 제거할 수 있다.
  • ambiguous grammar를 unambiguous하게 자동변환할 수 없다.

 

Grammar transform (문법 변환)

context-free grammar equivalence

서로 다른 Grammar가 서로 같은 Language를 생성시 equivalent하다고 정의된다.

ex)

• G1 = ({S, A}, {1, 2, a, b, c}, P, S})
• P :
  S -> 1A2
  A -> a | b | c
  
  
• G2 = ({S}, {1, 2, a, b, c}, P, S)
• P:
  S -> 1a2 | 1b2 | 1c2
  
  
• L(G1) = L(G2) = {1a2, 1b2, 1c2}
• G1과 G2는 equivalent하다.

 

Why we do a grammar transformation

많은 grammar는 같은 language를 생성한다.

CFG G와 문자열 w가 주어졌을 때, w가 L(G)에서 생성됐는지 확인해라

• CKY algorithm : O(|w|^3)

일부 Grammar에 대한 Parsing algorithms은 다른 문법에 대한 parsing algorithm보다 더 효율적이다.

• 이를 위해, grammar를 변환할 수 있다.
  • 예를들어, L(G1) = L(G2)일 때, G1을 parsing 하는 알고리즘이 G2보다 효율적이라면?
    => L(G2) -> L(G1)으로 변환하는게 좋다.

 

Useless productions in context-free grammars

CFG G가 주어졌을 때, Grammar는 사용하지 않는 rule을 포함하고 있을 수 있다.

ex1) 

• G = ({E, A}, {a, b, c}, P, E)
• P :
  E -> aEb | ab | A
  A -> bAa

위의 예시에서 A의 경우 terminal symbol로 derivation할 수 없다.

ex2)

• G = ({E, A}, {a, b, c, d}, P, E)
• P :
  E -> aEb | ab
  A -> cAd | cd

위의 예시에선 E -> A로 derivaion할 수 없다.

이러한 필요없는 rule은 제거해야하한다.

 

How to eliminate useless productions

1.

T(G) : terminal string을 derive할 수 있는 nonterminal의 집합
{A ∈ VN | ∃w ∈ VT, A =>(+) w}

T(G)는 단계별로 정의할 수 있다.
T1 = {A ∈ VN | ∃(A -> w) ∈ P, with w ∈ VT}
T_(n+1) = Tn ∪ {A ∈ VN | ∃(A -> β) ∈ P, with b ∈ (Tn ∪ VT)*}
T_(n+1) = Tn -> 이때까지 반복. 이때의 Tn을 T(G)라고 한다. => T(G) = Tn 

S(start symbol)가 T(G)에 포함되지 않는다면, L(G) = ø

2.

S가 T(G)에 포함된다면,
U(G) : 사용 가능한 non-terminal의 집합
{A ∈ T(G) | ∃α, β ∈ (T(G) ∪ VT)*, S =>(*) αAβ}

3.

U(G)는 단계별로 정의할 수 있다.
U1 = {A ∈ T(G) | ∃(S -> αAβ) ∈ P, with α, β ∈ (T(G) ∪ VT)*}
U_(n+1) = Un ∪ {B ∈ T(G) | ∃(A -> αBβ) ∈ P, with A ∈ Un, α, β ∈ (T(G) ∪ VT)*}
U_(n+1) = Un, -> U(G) = Un ∪ {S}

U(G)를 사용해 G를 모든 non-terminal이 equivalent한 CFG로 변환한다.

ex)

• G = ({S, A, B, C}, {a, b}, P, S)
• P : 
  S -> aS | A | C
  A -> a    B -> aa    C -> aCb

T(G)

• A, B, S (S => A => a)
• Eliminate S -> C, C -> aCb

U(G)

• S, A (S => A)
• Eliminate B -> aa

P :

• S -> aS | A
• A -> a

 

Reduced context-free grammar

context-free grammar G는 모든 non-terminals이 useful하면 reduce하다고 한다.

일부 parser(LR-parsers)는 불필요한 규칙을 제거하지 않으면 루프될 수 있다.

 

ε-production rules and eliminate the rules

ε-production rule : A -> ε

Eliminate ε-production rules

E(G) : 지울 수 있는 nonterminals의 집합

{A ∈ VN | A =>(+) ε}

E(G)는 다음과 같이 계산할 수 있다.

• E0 = {A ∈ VN | (A -> ε) ∈ P}
• E_(i+1) = Ei ∪ {A | ∃(A -> B1, ..., Bk) ∈ P, with Bj ∈Ei, i <= j <= k}
• E0 ⊆ E1 ⊆ ... ⊆ Ei ⊆ E_(i+1) ⊆ ... ⊆ VN (상승 chain을 형성한다.)

 

Find nullable non-terminals

• G = ({S, A, B, C}, {a, b, c}, P, S)
• P : 
  S -> ACA
  A -> aAa | B | C
  B -> bB | b
  C -> cC | ε

E(G) = {C, A, S}

 

ε-free grammar

context-free grammar G = (VN, VT, P, S)가 주어졌을 때, context-free grammar G' = (V'N, VT, P', S')를 다음과 같이 구성할 수 있다.

• L(G') = L(G)
• P'는 ε-rule을 포함하지 않는다. 단, S' -> ε rule은 제외한다. iff ε ∈L(G)
• S'은 어느 production P'의 right-hand side에 나타나지 않는다.

 

Convert the grammar to ε-free grammar

ex1)

• G = ({S}, {a, b}, P, S)
• P : S -> aSbS | bSaS | ε

1. E(G) : {S}

2.

• S -> aSbS | abS | aSb | ab
• S -> bSaS | baS | bSa | ba

3.

S' -> S | ε

4.

• G' = ({S', S}, {a, b}, P', S')
• P' : 
  S' -> S | ε
  S -> aSbS | abS | aSb | ab
  S -> bSaS | baS | bSa | ba

ex2)

• G = ({S, A, B, C, D}, {a, b, d}, P, S)
• P : 
  S -> ABaC
  A -> BC
  B -> b | ε
  C -> D | ε
  D -> d

1. E(G) : {A, B, C}

2.

S -> ABaC | BaC | AaC | ABa | aC | Aa | Ba | a
A -> BC | B | C
B -> b
C -> D
D -> d

3. S'은 만들지 않는다. -> E(G)에 포함되지 않기 때문

4.

• G' = ({S, A, B, C, D}, {a, b, d}, P', S)
• P' : 
  S -> ABaC | BaC | AaC | ABa | aC | Aa | Ba | a
  A -> BC | B | C
  B -> b
  C -> D
  D -> d

 

Single production rule and eliminate the rule

Single production rule : A -> B (A, B ∈ VN)
// non-terminal이 또 다른 non-terminal로 가는 경우 -> 계속 있을 경우 cycle 생성할 수 있따.

Eliminate of chain rules

I_A : {B ∈ VN | A =>(+) B} for A ∈ VN // I_A : A에 대해 구한다.

I_A는 다음과 같이 계산할 수 있다.

• I_(A,0) = {B ∈ VN | (A -> B) ∈ P}
• I_(A,1) = I_(A, 0) ∪ { C ∈ VN, ∃(B -> C)}
• I_(A, i+1) = I_(A,i) ∪ {C ∈ VN | ∃(B -> C) ∈ P, with B ∈I_(A, i)}
• I_(A, 0) ⊆ I_(A, 1) ⊆ ... ⊆ I_(A, i) ⊆ ... ⊆ VN (상승 chain을 형성한다.)

 

cycle-free grammar

context-free grammar G가 주어졌을 때, context-free grammar G' = (V'N, VT, P', S')를 다음과 같이 구성할 수 있다.

• L(G') = L(G)
• P'의 모든 rule은 A -> α, |α| >= 2 || A -> α, α ∈ ∑ || S' -> ε iff ε ∈ L(G)
• S'는 어느 P'에서든 right-hand side에 위치하지 않는다.

ε-free를 입력으로 받아 cycle-free grammar를 만든다.

 

Convert the grammar to cycle-free grammar

ex1)

• G = ({E, T, F}, {+, *, (, ), a}, P, E) // G is context-free grammar
• P : 
  E -> E + T | T
  T -> T * F | F
  F -> (E) | a

1. P' = P - {A -> B | A, B ∈ VN}

• P' :
  E -> E + T
  T -> T * F
  F -> (E)
  F -> a

2. 모든 all-terminals의 경우 I_A를 구한다.

• I_E = {T, F}
• I_T = {F}
• I_F = ø

3. 

E -> E + T | T * F | (E) | a
T -> T * F | (E) | a
F -> (E) | a

ex2)

• G = ({S, A, B}, {a, b, c}, P, S) // G is context-free grammar
• P : 
  S -> aA | A
  A -> bB | B
  B -> C

1. P' = P - {A -> B | A, B ∈ VN}

• P' : 
  S -> aA
  A -> bB
  B -> c

2. 

• I_S = {A, B}
• I_A = {B}
• I_B = ø

3. I_VN의 집합에 있는 rule을 VN에 복사

• S -> aA | bB | c
• A -> bB | c
• B -> c

 

Proper context-free grammar

context-free grammar G는 proper하다는 것은 아래를 만족한다는 것이다.

• Reduced
• ε-free
• cycle-free