제 5장. Context-Free Languages 학습목표 정규언어의 한계를 극복할 수 있는 Context-Free 언어를 Context-Free Grammar를 통해 이해하고 Parsing의 원리 숙지

개요 정규언어 보다 복잡한 언어의 필요성과 처리방법 숙지  할 수 있는 일이 많아진 만큼 모호성/어려움 증가 all languages ≠ regular 예) CF언어와 CF문법 정의 Parsing : see if a given string is derivable from a given grammar 응용 : PL design, efficient compilers construction nested structure PL requires something beyond RL  형식언어 중에서 가장 응용이 활발히 진행되는 language category

Context-Free Grammars RG와 무제약 문법 사이에서 제약을 완화시키며 능력개선! Restrictions in RG left side : single variable right side : special form CFG proper subset 왜 context-free라 하나?  sentential form에 나타난 변수는 상황에 관계없이 rewrite가능

 context-free이자 linear  RG < linear G < CFG

CFG : 예예 조금 복잡한 경우를 볼까요?  set of all properly nested parenthesis structures for PL

CFG : Derivation (1) CFG : a derivation may involve sentential forms with more than one variable  choice in the order where variables are replaced  뭔가 약속된 순서가 있어야겠군!

그런데 2차원 구조를 1차원적으로 보이자니 감이 잘 안 오는군! CFG : Derivation (2) 그래서 순서를 정한 것이… 정의 2: • leftmost derivation if leftmost variable is first replaced • rightmost derivation if rightmost variable is first replaced 그런데 2차원 구조를 1차원적으로 보이자니 감이 잘 안 오는군!

CFG : Derivation Trees (1) 트리구조로 봅시다! CFG : Derivation Trees (1) Derivation tree – ordered tree where nodes are labeled with the left sides of productions and where the children of a node represent its corresponding right side A B b a c

CFG : Derivation Trees (2) = partial derivation tree yield : reading leaves from left→right, omitting λ depth-first manner  p. 132, 그림 5.2 (partial derivation tree), 그림 5.3 (derivation tree)

CFG : Sentential Forms & Derivation Trees Relation btw. sentential forms & derivation trees

CFG : Homework (Exercises 5.1) 7 (b), (d) : 주어진 언어의 CFG 구하기 연습-1 8 (b), (d) : 주어진 언어의 CFG 구하기 연습-2 10 : CFG 구하기 문제 하나 더 14 : 또 다른 CFG 구하기 문제 22 : 메타언어의 CFG는 어떨지…

Parsing and Ambiguity 생성기로서의 문법이 아닌 Accepter로서의 문법의 이용 Grammar usage generative aspect : derivable strings from grammar analytical aspect : whether w∈L(G)? → derivation of w cf) parsing : finding a sequence of productions by which w∈L(G) is derived Exhaustive search parsing method (top-down parsing) systematically construct all possible derivations see whether any of them match w  좀 무식해 보이지만…

Parsing : 예

Parsing : 효율적인 방법 flaws tedious never terminates for strings not in L(G) : nontermination → restriction on the grammar i) A →  : decrease length of successive sentential forms ii) A → B power와 무관

Parsing : 효율적인 방법 증명 Upper bounds on total no. of sentential forms

문법에 약간의 제약을 가하니 엄청나게 효율적인 파싱이 가능해지는군! Parsing : Simple Grammar G: s-grammar → w∈L(G) can be parsed in |w| 문법에 약간의 제약을 가하니 엄청나게 효율적인 파싱이 가능해지는군!

 똑같은 aabb를 생성하는 두개의 derivation tree가능 Parsing : Ambiguity Ambiguity : several different derivation trees may exist  똑같은 aabb를 생성하는 두개의 derivation tree가능 Tip! 형식언어에서 string(즉, 문장)의 구조는 string을 생성하기 위하여 적용되는 rule과 그 순서에 따라 결정된다. 따라서 어떤 string x를 여러 가지 방법으로 생성할 수 있다면, 이는 x의 구조를 여러 가지로 해석할 수 있음을 뜻한다.

Parsing : Ambiguity의 해결 Rewriting grammar in an equivalent unambiguous form 예) PL’s statement has only one interpretation. (p. 143, 그림 5.6) CFG의 ambiguity, equality  no general algorithm

Parsing : Inherent Ambiguity Tip! 임의의 CFG가 ambiguous한지 여부를 밝히거나, 임의의 ambiguous 한 CFG를 unambiguous 한 CFG로 전환하는 일반화된 algorithm은 없다. 그러나 특정한 주어진 CFG 가 ambiguous 한지 여부를 밝히거나, 이를 unambiguous 한 CFG로 전환하는 것은 가능하다.

좌측의 b를 먼저 생성한 다음 우측의 b를 생성하도록 rule을 수정 Parsing : Ambiguity 해결 연습 G3 : S  bSSbc 1) 언어는? {bicbj | i, j  0} 2) Ambiguous한가? S b c 이 언어의 string은 S  bS 를 먼저 적용하여 좌측에 있는 b를 생성한 다음, 우측의 b를 생성하거나, 이와 역순으로 생성할 수 있다. 따라서 ambiguous 하다. 3) 모호성을 제거하는 방법은? 좌측의 b를 먼저 생성한 다음 우측의 b를 생성하도록 rule을 수정 Ambiguous G3 : S  bSSbc Unambiguous G4 : S  bSA A  Abc

Parsing : Homework (Exercises 5.2) 1 : 주어진 언어의 s-grammar 찾기 기초문제 13 : 언어의 ambiguity 보이기 문제

CFG와 PL application of formal language theory PL definition / interpreter, compiler construction convention for specifying grammars for PL : Backus-Naur Form 예) <expression> ::= <term> | <expression> + <term> <term> ::= <factor> | <term> * <factor> 예) s-grammar : easily / efficiently parsed (due to keywords) <if_stmt> ::= if <expression> <then_clause> < else_cause> → LL / LR grammars Syntax vs. Semantics

CFG와 PL: Homework (Exercises 5.3) 이 장의 내용은 따로 연습까지 할만큼 깊이 있게 다루지 않았지만… 5 : 굳이 한번 해보자면…

다음 이야기  CFG의 변환과 정규화 문법을 변환하는 방법들 Useful substitution rule Removing l-productions / unit-productions / useless productions 정규형식 Chomsky normal form : 우측항의 변수의 수 제한 Greibach normal form : 우측항의 변수와 terminal의 위치 제한 CFG를 위한 간단한 Parsing방법 : CYK algorithm membership algorithm : 주어진 string이 문법에 맞는지?