[Automata] Context-free Language ( 문맥 자유 언어 )

Chapter 5의 내용이다!

 

이전 포스팅에서 다뤘듯이 정규언어가 좋긴 한데, 프로그래밍 언어를 다루기에는 조금 부족한 요소들이 있었다. 

 

L = {a^n b^n:  n>=0} 이면, a=(, b=)일 때 프로그래밍에서 괄호가 중첩인지 확인하기 좋지만 얘 역시 정규언어가 아니였다. 

(정규언어가 아님은 펌핑lemma를 통해서 보였다.)

 

따라서 우리는 정규언어보다 더 큰 개념인 '문맥 자유 언어'를 다룬다.

 

정규언어의 큰 단점은, 좌변은 한개의 변수이고 우변은 특정한 형태여야 했다. (정의임)

 

문맥 자유언어는 우변에 특정한 형태 대신 아무거나 올 수 있게 허용해줌으로써 더 강력해진다!!

 

 

정규언어 ⊂ 문맥 자유 언어이다. 

 

* linear grammar?

 

문제들은 주로, 주어진 언어가 문맥자유언어인지 보이라는 유형이 많다. 

언어에 맞는 문법을 유도해서, 문법이 문맥자유문법에 해당하면 맞다는 식으로 풀어내면 된다. 

 

최좌단유도와 최우단유도

linear하지 않은 문법에서는 유도하고 나면 한개 이상의 변수가 포함된 문장 형태가 나올 수 있다. 그런 경우를 방지하기 위해서 어떤 변수가 대체될 지 우선순위를 정해준다. 그리고 최좌단 변수부터, 또는 최우단 변수부터 유도하는 식으로 해서 순서를 정해준다.  (순서를 안정해도 결과는 같긴 하다!)

 

parse tree (derivation tree)

partial derivation tree

parse tree에서 1조건이 없고, 2조건이

 

이면 partial derivation tree이다. 

 

 

Sentential Form과 Derivation Tree의 관계

뭔가 굉장히 거창하게 서술되어있지만 그냥 tree로 문장 유도할 수 있다는 것..

증명이 나와있다 (Theorem 5.1)

 

Theorem 5.1

Grammar G는 quadrople G = (V, T, S, P) 로 정의되는데 이 G가 context-free grammar라고 가정하자. 

 

V: variable의 유한집합

T: terminal symbol의 유한집합

S: start하는 variable, T에 항상 포함되어있어야 한다

P: production의 유한 집합

 

그렇다면 모든 w ⊆ L(G)에 대하여, 항상 yield가 w인 G의 derivation tree가 존재한다. 

역으로, 모든 derivation tree의 yield는 L(G)에 있다. 

또한, t_G는 root가 S인 어떤 partial derivation tree일 때, t_G의 yield는 G의 sentential form이다.

 

 

 

 

 

 

Parsing과 Ambiguity

ambiguity: 하나의 문자열이 여러개의 tree로 생성될 수 있는 경우

만약 프로그래밍 문법이 ambigious하다면 문제가 될 것이므로 가능한 없애려고 한다.

 

L이 모호하지 않은 문법이 하나라도 존재하는 문맥자유언어이면, L은 모호하지 않다. 

L이 만드는 모든 문법이 모호하다면, 언어는 고유적으로 모호하다고 정의한다.  (Definition 5.6)

 

Exhaustive Search Parsing

: G=(V, T, S, P)인 context free grammar 중에서

A->ƛ, A->B의 form이 하나도 없다면 , (A, B ⊆ V)

exhaustive search parsing 방법은 임의의 w ⊆Σ*에 대해서, 파싱이 불가능한지 아니면 w가 생기는 지 알려줄 수 있는 알고리즘이다. 

 

Complexity가 O(|P|^(2|w| + 1))인데, |P|+ |P|^2 + ... + |P|^2|w| 라서 그렇다. 

하지만 이 complexity가 너무 높아서 실제로는 CYK라는 알고리즘을 쓴다고 한다. 얘는 |w|^3, linear한 시간복잡도이다. 

이 내용은 chapter7에서 추가적으로 다룬다. 

Top-down parsing

//WIP

s-grammar(simple grammar)

S->aA도 있고 S->aB도 있으면 단순 문법이 아니다.

 

꽤 많은 프로그래밍 언어가 s-grammar로 정의될 수 있다고 한다. 

 

실제 프로그래밍 언어에서의 활용

C언어에서의 예시를 하나 보자!

<while_statement> := while <expression> <statement>

<expression> := <term> | <expression> + <term>
<term> := <factor> | <term> * <factor>

BNF이긴 한데 사실상 CFG랑 동일한 문법이다. ->가 := 된것 제외하면!

 

while문은 s-grammar라서 쉽게 해석이 가능하다. 

<expression>은 s-grammar아니여서 해석이 좀 더 어렵다. 컴파일러에서는 LL, LR문법을 쓰는데 이는 Chapter6에서 좀 더 다룰거라고 한다.