컴파일러 입문 제 5 장 Context-Free 문법

목 차 5.1 서론 5.2 유도와 유도 트리 5.3 문법 변환 5.4 CFG 표기법 5.5 푸시다운 오토마다(PDA) 5.1 서론 5.2 유도와 유도 트리 5.3 문법 변환 5.4 CFG 표기법 5.5 푸시다운 오토마다(PDA) 5.6 context free 언어와 PDA언어 Context-free Grammar

5.1 서론 정규표현 : 토큰의 어휘구조 프로그래밍 언어의 구문 구조를 CFG로 표현할 경우의 장점: 정규표현 : 토큰의 어휘구조 인식기 : FA( scanner) id = l(l + d)* , sc = ´(c + ´´)*´ CFG : 프로그래밍 언어의 구문 구조 인식기 : PDA( parser) 프로그래밍 언어의 구문 구조를 CFG로 표현할 경우의 장점: 1. 간단하고 이해하기 쉽다. 2. CFG로부터 인식기를 자동으로 구성할 수 있다. 3. 프로그램의 구조를 생성규칙에 의해 구분할 수 있으므로 번역시에 유용하다. Context-free Grammar

문법 심벌들의 일반적인 표기법 Terminal 심벌 Nonterminal 심벌 a, b, c와 같은 알파벳 시작 부분의 소문자와 숫자 0,1,2,…,9; +, -와 같은 연산자 기호와 세미콜론, 콤마, 괄호와 같은 구분자 ‘if’또는 ‘then’과 같이 ‘과 ’사이에 표기된 문법 심벌 Nonterminal 심벌 A, B, C와 같은 알파벳 시작 부분의 대문자; S는 보통 시작 심벌(start symbol)을 나타낸다. <stmt>나 <expr>과 같이 <와 >로 묶어서 나타낸 문법 심벌 만약 아무런 언급이 없으면 첫번째 생성 규칙의 왼쪽에 있는 것이 시작 심벌이다. Aa1, Aa2, …, Aak와 같이 생성 규칙의 왼쪽이 모두 A인 경우에, Aa1|a2|…|ak로 간단히 표기 할 수 있다. 이것을 A에 대한 택일 규칙이라 부른다. Context-free Grammar

CFG의 형태 : N. Chomsky의 type 2 문법 A  , where A  VN and   V*. 재귀적 구성 ex) E  E OP E | (E) | -E | id OP   |  |  | / VN : <와 >사이에 기술된 symbol. VT : ' 와 ' 사이에 기술된 symbol. VN =  E, OP  VT =  (, ), , id, , , / ex) <if_statement>  'if' <condition> 'then' <statement> Context-free Grammar

5.2 유도와 유도 트리 정의 : 1  2 시작 심벌로부터 문장을 생성하는 과정에서 nonterminal 을 이 nonterminal로 시작되는 생성 규칙의 right hand side로 대 치하는 과정. (1)  : derives in one step. if A    P, ,   V* then A  . (2)  : derives in zero or more steps. 1.   V*,    2. if    and    then    (3)  : derives in one or more steps. * + * Context-free Grammar

L(G) : G에 의해서 생성된 언어 정의 : 대치될 nonterminal의 선택 * = { | S  ,  ∈ VT*} 정의 : 문장 : S  ,   VT*  모두 terminal로만 구성. 문장의 형태 : S  ,   V*. 대치될 nonterminal의 선택 문장형태에서 어느 nonterminal을 선택할 것인가 ? A   , where   V*. 좌측 유도: 가장 왼쪽에 있는 nonterminal을 대치해 나가는 방법. 우측 유도: 가장 오른쪽에 있는 nonterminal을 대치. * Context-free Grammar

parse : parser의 출력 형태 중에 한가지. 유도순서 유도과정의 각 단계에서 문장형태의 가장 왼쪽에 있는 nonterninal을 대치하는 경우 이를 좌측유도(leftmost derivation)라한다 0  1  ...  n in i for all i, 0  i  n-1. i  i+1 : 가장 왼쪽에 있는 nonterminal을 차례로 대치. parse : parser의 출력 형태 중에 한가지. left parse : leftmost derivation에서 적용된 생성 규칙 번호. top-down parsing start symbol로부터 sentence를 생성 right parse : rightmost derivation에서 적용된 생성 규칙 번호의 역순. bottom-up parsing sentence로부터 nonterminal로 reduce되어 결국엔 start symbol로 reduce. Context-free Grammar

유도 트리 ::= 문장이 유도되는 과정을 트리형태표현. ::= 문법에 적용되는 문장의 계층적구조 정의 : 유도트리 CFG G = (VN,VT,P,S) &   VT*  a derivation tree. 1. nodes: symbol of V(VN  VT) 2. root node: S(start symbol) 3. if A  VN, then a node A has at least one descendent. 4. if A  A1A2...An  P, then A가 subtree의 root가 되고 좌로부터 A1,A2,...,An가 A의 자 노드가 되도록 tree를 구성 Context-free Grammar

순서 트리 - child node들의 위치가 순서를 갖는 트리, 따라서 유도트리는 순서트리이다. 유도트리의 노드 내부(nonterminal) 노드  VN 외부(terminal) 노드  VT  {} 순서 트리 - child node들의 위치가 순서를 갖는 트리, 따라서 유도트리는 순서트리이다. Context-free Grammar

예) G : E → E + T | T T → T * F | F F → ( E ) | a  : a + a * a ※ 각각의 유도 방법에 따라 derivation tree 모양은 변하지 않는다. 즉, 한 문장에 대한 tree 모양은 unique하다. Context-free Grammar

nondeterministic Ambiguous(모호한) 문법 문법G에 의해 생성되는 어떤 문장이 두개 이상의 유도 트리(nondeterministic)를 갖는다면 문법 G는 모호하다. 설명: 같은 문장를 생성하는 트리가 2개 이상 존재할 때 이 문법를 모호하다고 하며, 결정적인 파싱을 위해 nondeterministic한 문법을 deterministic하게 변환해야 한다. nondeterministic Context-free Grammar

“G: ambiguous 증명”  하나의 sentence로 부터 2개 이상의 derivation tree 생성. ex) dangling else problem: G: S  if C then S else S | if C then S | a C  b : if b then if b then a else a Context-free Grammar

일반적으로 다음과 같은 형태의 생성규칙이 있다면 모호성이 나타난다. ※ else : 일반적으로 right associativity를 만족한다. if 문장의 경우 자신과 가장 가까운 if와 결합함으로 두개의 트리 중 일반적으로 2)를 만족. 일반적으로 다음과 같은 형태의 생성규칙이 있다면 모호성이 나타난다. 생성형태 : A  AA 문장형태 : AAA 트리형태 : Context-free Grammar

모호한 분명한 1) 새로운 nonterminal을 도입해서 분명한 문법으로 변환. 2) 이 과정에서,우선순위 & 결합법칙 규칙을 이용. 비결정적  결정적 예) G : E  E  E | E + E | a  : a  a + a 우선순위 방법을 적용 Context-free Grammar

새로운 nonterminal의 도입 G : E  E + T | T T  T * F | F F  a ※ 그런데 , 문법 의 모호성 을 검사 할 수 있는 알고리즘 이 존재하지 않으며 분명 하게 바꾸는 형식적인 방법도 않는다 . Context-free Grammar

(Unambiguous)분명한 문법으로 바꾼 예: ┃ expression - term ┃ term G : expression  expression + term ┃ expression - term ┃ term term  term * factor ┃ term / factor ┃ factor factor  primary ↑ factor ┃ primary primary  - primary ┃ element element  ( exp ) ┃ id 유도트리가 하나이므로 위 문법은 분명하다. Context-free Grammar

id * id + id의 유도트리: 유도트리가 하나 이므로 위 문법은 분명하다. Context-free Grammar

5.3 문법 변환 5.3.1 필요 없는 생성 규칙 제거 5.3.2 -생성 규칙제거 5.3.3 단일 생성 규칙 제거 5.3.1 필요 없는 생성 규칙 제거 5.3.2 -생성 규칙제거 5.3.3 단일 생성 규칙 제거 5.3.4 문법의 기본적인 형태 Context-free Grammar

모든 문장은 대입과 확장기법을 통하여 동등한 문법으로 변환 할 수 있다. 정의 :만약 L(G) = L(G2) 이면 문법 G1과 G2 는 동등하다. 두가지 문법 변환 방법 대입 : if A  B, B  1 | 2 | 3 … | n P, then P' = ( P - {A  B } )  {A  1 | 2 | ... | n }. 확장 : A   <=> A  X, X   or A  X, X   ex) P : S  aA | bB A  bB | b B  aA | a 모든 문장은 대입과 확장기법을 통하여 동등한 문법으로 변환 할 수 있다. Context-free Grammar

5.3.1 필요 없는 생성규칙 제거 문장을 생성하는데 적용할 수 없는 생성규칙들은 모두 제거할 수 5.3.1 필요 없는 생성규칙 제거 문장을 생성하는데 적용할 수 없는 생성규칙들은 모두 제거할 수 있으며 필요 없는 생성 규칙이라 한다.  eliminated 의 정의 정의 : 문법심볼에 대하여 다음과 같은 형태가 존재하지 않으면 x는 필요 없는 심볼이다. ∃S  Xy  xy, ,x,y  VT*. 두가지 제거 방법 Terminating nonterminal : A   ,   , where A  VN and   VT*. Accessible symbol : S  X, 　where X ∈ V and ,  V*. Context-free Grammar

Terminating nonterminal을 구하는 방법: Algorithm terminating; begin VN':= { A | A   ∈ P,  ∈ VT* }; repeat VN' := VN' ∪ { A | A   ∈ P, ∈ (VN' U VT )* } until no change end. Accessible symbol을 구하는 방법: Algorithm accessible; V ' := { S }; (* initialization *) V ' := V ' { X | some A  X ∈ P, A ∈ V ' } Context-free Grammar

ex) S  A | B A  aB | bS | b B  AB | BB C  AS | b 필요없는 생성규칙 제거 : Terminating nonterminal 알고리즘 적용. Accessible symbol 알고리즘 적용. ex) S  A | B A  aB | bS | b B  AB | BB C  AS | b Context-free Grammar

5.3.2 -생성규칙 제거 (2) S 하나만이 -생성규칙을 가지며, 다른 생성규칙의 오른쪽 에 S가 나타나지 않아야 한다. 정의 : 다음과 같은 생성규칙을 -생성규칙이라 한다. 생성규칙의 형태가 A ->  인 경우 정의 : CFC G=(VN,VT,P,S)가 다음과 같은 조건을 가질 때 -free라한다. (1) P가 -생성규칙을 갖지 않거나, (2) S 하나만이 -생성규칙을 가지며, 다른 생성규칙의 오른쪽 에 S가 나타나지 않아야 한다. Context-free Grammar

-free 문법으로 변환: Algorithm  -free; begin VN := { A | A =>  , A  VN }; (* nullable nonterminal *) P' := P – { A   | A  VN }; for A  0B11B2... Bkk ∈ P' , where i ≠ and Bi  VN do if Bi   ∈ P' then P' = P' ∪ { A  0X1 1X2... Xkk | Xi = Bi or Xi = } else P' = P' ∪ { A  0X1 1X2... Xkk | Xi = } end if end for if S  VN then P ' := P ' ∪ { S'   | S } end. ex1) A  AaA | ε ex2) S  aAbB A  aA | ε B  ε + Context-free Grammar

5.3.3 단일 생성 규칙의 제거 정의 : 생성규칙의 형태가 A  B와 같이 생성규칙의 오른쪽에 5.3.3 단일 생성 규칙의 제거 정의 : 생성규칙의 형태가 A  B와 같이 생성규칙의 오른쪽에 한 개의 nonterminal이 나오는 생성규칙. Algorithm Remove_Single_Production; begin P' := P – { A  B | A, B  VN}; for each A  VN do VNA = { B | A  B } ; for each B  VNA do for each B    P' do (* not single production *) P' := P' ∪ { A  α} end for end.  main idea : grammar substitution. + Context-free Grammar

과정을 갖지 않을 때 cycle-free하다고 한다. 만약 G가 cycle-free하고 ex) S  aA | A A  bA | C C  c S  aA | bA | c A  bA | c 정의 : Context-free 문법 G = ( VN , VT, P, S )가 어떤 AVN 에 A A 형태의 유도 과정을 갖지 않을 때 cycle-free하다고 한다. 만약 G가 cycle-free하고 -free, 그리고 필요 없는 심벌을 가지지 않을 때 proper하다고 한다. * Context-free Grammar

5.3.4 문법의 기본적인 형태 정의 : CFG G = ( VN , VT, P, S )의 생성규칙이 다음과 같은 형태로 이루어져 있을 때, G를 정규 형태(normal form) 혹은 촘스키 정규 형태 (CFN : Chomsky Normal Form)라 한다. A  BC 여기서 A,B,C  VN A  a 여기서 a  VT 만약  L(G)라면 S   이고 S는 생성규칙의 오른쪽에 나타나지 않는다. Conversion to CNF Context-free Grammar

Definition : CFG G = (VN, VT,P,S)가 -free이고 -생성 규칙 이 존재하지 않는 A  a, a  VT,   VN* 형태의 생성 규칙을 갖는다면 표준 형태(standard form) 혹은 Greibach 정규 형태(GNF : Greibach Normal Form)이라 한다. Context-free Grammar

5.4 CFG 표기법 ☞ BNF(Backus-Naur Form), EBNF(Extended BNF), Syntax Diagram BNF 특수한 meta symbol을 사용하여 프로그래밍 언어의 구문을 명시하는 표기법. meta symbol : 새로운 언어의 구문을 표기하기 위하여 도입된 심벌들. terminal symbol : ‘ ’ grammar symbol : VN ∪ VT nonterminal symbol < >  ::= (치환) nonterminal symbol의 rewriting | (또는) Context-free Grammar

P = {S  AB, A  aA, A  a, B  Bb, B  b}  BNF 표현: 예1) VN = {S, A, B}, VT = {a, b} P = {S  AB, A  aA, A  a, B  Bb, B  b}  BNF 표현: <S> ::= <A> <B> <A> ::= a <A> | a <B> ::= <B> b | b 예2) Compound statement (복합문) <compound_statement> ::= ‘{’<statement_list> ‘}’ <statement_list> ::= <statement_list> <statement> | <statement> <S> ::= <A> <B> <A> ::= ' a ' <A> | ' a ' <B> ::= <B> ' b ' | ' b ' Context-free Grammar

반복되는 부분(repetitive part): { } 선택적인 부분(optional part): [ ] Extended BNF(EBNF) 특수한 의미를 갖는 meta symbol을 사용하여 반복되는 부분이나 선택적인 부분을 간결하게 표현. meta symbol 예1) <compound_statement> ::= ‘{’ <statement> {<statement>} ‘}’ 예2) <if-st> ::= 'if' ‘(’ <expression> ‘)’ <statement> [‘else’ <statement>] 예3) <exp> ::= <exp> + <exp> | <exp> - <exp> | <exp>  <exp> | <exp> / <exp> <exp> ::= <exp> (  |  |  | / ) <exp> 반복되는 부분(repetitive part): { } 선택적인 부분(optional part): [ ] 괄호와 택일 연산자(alternative): ( | ) Context-free Grammar

Syntax dlagram (문법흐름도,구문 도표) 초보자가 쉽게 이해할 수 있도록 구문 구조를 도식화하는 방법 syntax diagram에 사용하는 그래픽 아이템: 원 : terminal symbol 사각형 : nonterminal symbol 화살표 : 흐름 경로 syntax diagram을 그리는 방법: 1. terminal a 2. nonterminal A Context-free Grammar

(1) Xi가 nonterminal인 경우: 3. A ::= X1X2... Xn (1) Xi가 nonterminal인 경우: (2) Xi가 terminal인 경우: 4. A ::= 1┃2┃...┃ n Context-free Grammar

5. EBNF A ::= {} 6. EBNF A ::= [] 7. EBNF A ::= (1┃2) Context-free Grammar

(예) A ::= a | (B) B ::= AC C ::= {+A} Context-free Grammar

Context-free Grammar

5.5 푸시다운 오토마타 PDA(Push Down Automata)는 인식기의 한 종류로 유한 상태 제어, 입력 테이프 그리고 스택으로 구성되어있다. Context-free Grammar

CFG의 인식기 push-down list(stack), input tape, finite state control Context-free Grammar

 : Q  ( ∪ {})    Q  * 정의 : PDA P = (Q, , , , q0, Z0, F), where, Q : 상태 심벌의 유한 집합.  : 입력 알파벳의 유한 집합.  : 스택 심벌의 유한 집합.  : 사상 함수 Q  ( ∪{})    Q  *, q0 ∈ Q : 시작 상태(start state), Z0 ∈ F : 스택의 시작 심벌, F ⊆ Q : 종결 상태(final state)의 집합이다.  : Q  ( ∪ {})    Q  * (q,a,Z) ={(p1, 1), (p2, 2), ... ,(pn, n)} 의미: 현재 상태가 q이고 입력 심벌이 a이며 스택 top 심벌이 Z일 때, 다음 상태는 n개 중에 하나이며 만약 (pi, i)가 선택되었다면 그 의미는 다음과 같다. 현재의 q 상태에서 입력 a를 본 다음 상태는 pi이다. 스택 top 심볼 Z를 i로 대치한다. Context-free Grammar

L(P) : 시작상태에서 를 다 본 상태가 종결 상태에 속하면 는 P에 의해 인식. P의 형태 : (q, , ) where, q : 현재 상태  : 입력 심볼  : 스택의 내용 P의 이동(move)ː┣ a   : (q, a, Z) ┣ ( q', , ) a =  : (q, , Z) ┣ (q', , ) <===> -move ※ ┣ : zero or more moves, ┣ : one or more moves L(P) : 시작상태에서 를 다 본 상태가 종결 상태에 속하면 는 P에 의해 인식. 시작 : (q0, , Z0) 종결 : (q, , α), where q ∈ F,  ∈ * L(P) = {ω | (q0, , Z0) ┣ (q, , ), q ∈ F,  ∈ * }. * + Context-free Grammar

ex) P = ({q0, q1, q2}, {0, 1}, {Z, 0}, , q0, Z, {q0}), where, (q0, 0, Z) = {(q1, 0Z)} (q1, 0, 0) = {(q1, 00)} (q1, 1, 0) = {(q2, )} (q2, 1, 0) = {(q2, )} (q2, , Z) = {(q0, )} 스트링 0011의 인식 과정: (q0, 0011, Z) ┣ (q1, 011, 0Z) ┣ (q1, 11, 00Z) ┣ (q2, 1, 0Z) ┣ (q2, , Z) ┣ (q0, , ) 스트링 0n1n(n≥1)의 인식 과정: (q0, 0n1n, Z) ┣ (q1, 0n-11n, 0Z) ┣ n-1 (q1, 1n, 0nZ) ┣ (q2, 1n-1, 0n-1Z) ┣ n-1 (q2, , Z) ┣ (q0, , ) ∴ L(P) = {0n1n | n  1}. Context-free Grammar

확장된 PDA δ : Q × (∪{}) × * → Q × * (q, a, ) ┣ (q', , ) 한번의 move로 stack top 부분에 있는 유한 길이의 string을 다른 string으로 대치. (q, a, ) ┣ (q', , ) stack이 empty일 때도 move가 발생 예) PDA = ({q0, qf}, {a, b}, {a, b, S, Z}, , q0, Z, {qf}) where, (q0, a, ) = {(q0, a)} (q0, b, ) = {(q0, b)} (q0, , ) = {(q0, S)} ※ S : center mark (q0, , aSa) = {(q0, S)} (q0, , bSb) = {(q0, S)} (q0, , SZ ) = {(qf, )} Context-free Grammar

스트링 aabbaa의 인식 과정: ∴ L = { R |  ∈ {a, b}+}. (q0, aabbaa, Z) ┣ (q0, abbaa, aZ) ┣ (q0, bbaa, aaZ) ┣ (q0, baa, baaZ) ┣ (q0, baa, SbaaZ) ┣ (q0, aa, bSbaaZ) ┣ (q0, aa, SaaZ) ┣ (q0, a, aSaaZ) ┣ (q0, a, SaZ) ┣ (q0, , aSaZ) ┣ (q0, , SZ) ┣ (qf, , ) ∴ L = { R |  ∈ {a, b}+}. Context-free Grammar

Le(P) : stack을 empty로 만드는 PDA에 의해 인식되는 string의 집합 Le(P) : stack을 empty로 만드는 PDA에 의해 인식되는 string의 집합. 즉, 입력 심벌을 모두 보고 스택이 empty일 때만 인식되는 string의 집합. ∴ Le(P) = {  ┃ (q0, , Z0) ┣ (q, , ), q ∈ Q} . Le(P’) = L(P)인 P’의 구성: (text p. 202) P = (Q, , , , q0, Z0, F) ===> P’ = (Q∪{qe, q’},  , ∪{Z’}, ’, q’, Z’,  ), where ’ : 1) 모든 q ∈ Q, a ∈ ∪{}, Z ∈  에 대해, ’(q, a, Z) = (q, a, Z). 2) ’(q’, , Z’) = {(q0, Z0Z’)}. Z’ : bottom marker 3) 모든 q ∈ F, Z ∈ ∪{Z’}에 대해, ’(q, , Z)에 (qe, )를 포함. 4) 모든 Z ∈ ∪{Z’}에 대해, ’(qe, , Z) = {(qe, )} * Context-free Grammar

5.6 Context-free 언어와 PDA 언어 PDA언어가 Context free 언어이다. CFG <===> PDA CFG ===> PDA (for a given context-free grammar, we can construct a PDA accepting L(G).) Top-Down Method leftmost derivation, A   Bottom-Up Method rightmost derivation,  ==>A PDA ===> CFG Context-free Grammar

Top-Down Method CFG G로부터 Le(R)=L(G)인 PDA R의 구성 For a given G = (VN, VT, P, S), construct R = ({q}, VT, VN∪ VT, , q, S,  ), where  : 1) if A  ∈ P, then (q,,A)에 (q,)를 포함. 2) a ∈ VT에 대해, (q, a, a) = {(q, )}. ex) G = ({E, T, F}, {a, , +, (, )}, P, E), P : E  E + T | T T  T  F | F F  (E) | a ===> R = ({q}, , , , q, E, ) where  : 1) (q, , E) = {(q, E + T), (q, T)} 2) (q, , T) = {(q, T  F), (q, F)} 3) (q, , F) = {(q, (E)), (q, a)} 4) (q, t, t) = {(q, )}, t∈{a, +, , (, )}. Context-free Grammar

(q, a + a  a, E) ┣ (q, a + a  a, E + T) ┣ (q, a + a  a, T + T) ┣ (q, a + a  a, F + T) ┣ (q, a + a  a, a + T) ┣ (q, + a  a, + T) ┣ (q, a  a, T) ┣ (q, a  a, T  F) ┣ (q, a  a, F  F) ┣ (q, a  a, a  F) ┣ (q,  a,  F) ┣ (q, a, F) ┣ (q, a, a) ┣ (q, , ) ※ 스택 top은 세 번째 구성 요소의 왼쪽. Context-free Grammar

Bottom-Up Method CFG ===> extended PDA(rightmost derivation) ex) G = ({E, T, F}, {a, , +, (, )}, P, E), P : E  E + T | T T  T  F | F F  (E) | a ===> R = ({q, r}, VT, VN ∪ VT∪{$}, , q, $, {r})  : 1) (q, t, ) = {(q, t)}, t ∈{a, +, , (, )}  shift 2) (q, , E + T) = {(q, E)} (q, , T) = {(q, E)} (q, , T * F) = {(q, T)} (q, , F) = {(q, T)} (q, , (E)) = {(q, F)} (q, , a) = {(q, F)} 3) (q, , $E) = {(r, )} Context-free Grammar

스트링 a + a  a의 인식 과정 (q, a + a  a, $) ┣ (q, + a  a, $ a) ┣ (q, + a  a, $ F) ┣ (q, + a  a, $ T) ┣ (q, + a  a, $ E) ┣ (q, a  a, $ E +) ┣ (q,  a, $ E + a) ┣ (q,  a, $ E + F) ┣ (q,  a, $ E + T) ┣ (q, a, $ E + T ) ┣ (q, , $ E + T  a) ┣ (q, , $ E + T  F) ┣ (q, , $ E + T) ┣ (q, , $ E) ┣ (r, , ) ※ 스택 top은 세 번째 구성 요소의 오른쪽. Context-free Grammar

Given PDA P = (Q, , , , q0, Z0, F) PDA P로부터 L(G) = Le(P)인 CFG G의 구성 ===> Construct cfg G = (VN, VT, P, S) where (1) VN = {[qZr] | q, r∈Q, Z∈}∪{S}. (2) VT = . (3) P : ① (q, a, Z)가 k  1 에 대해 (r, X1... XK)를 가지면 [qZsk]  a[r X1s1][s1X2s2] ... [Sk-1Xksk]를 P에 추가. s1, s2, ..., sk ∈ Q. ② (q, a, Z)가 (r, )를 포함하면 생성규칙 [qZr]  a를 P에 추가. ③ 모든 q ∈ Q에 대해 S  [q0Z0q]를 P에 추가. (4) S : start symbol. Context-free Grammar

결론 L은 CFG G에 의해 생성되는 언어 L(G)이다. L은 PDA P에 의해 인식되는 언어 L(P)이다. L은 PDA P에 의해 인식되는 언어 Le(P)이다. L은 extended PDA에 의해 인식되는 언어 L(P)이다. Context-free Grammar