제5장 문맥 자유 문법(CFG)

컴파일러 구성론

강 승 식

5.1 서론

∙ 정규문법 : token 인식에 적합, 언어의 syntax 기술하기에는 부적합

∙ CFG(type 2) : A →[eqn: alpha]

∙ P.L.의 구조는 CFG로 기술하는 장점

① 간단하고 이해하기가 쉽다

② 문법으로부터 자동적으로 인식기를 구현 가능

③ 입력된 program의 구조를 생성규칙에 의해 분석

∙ 문법기호들의 notational convention

1. Terminal symbol

(1) a, b, c 등 알파벳 시작부분의 소문자와 숫자 0, 1, 2, ⋯

(2) +, - 연산자와 semi-colon, comma, 괄호 등 delimiter

(3) ‘if’, ‘then’과 같이 인용부호 사이에 표기된 문법기호

2. Nonterminal symbol

(1) A, B, C 등 알파벳 시작부분의 대문자

(2) S는 보통 시작기호로 사용

(3) <stmt>, <expr>과 같이 <와 >로 묶어서 나타낸 문법기호

3. 만약 아무런 언급이 없으면 첫번째 생성규칙의 LHS 기호가 시작기호임.

4. A →[eqn: alpha]1, A →[eqn: alpha]2, ⋯, A →[eqn: alpha]k와 같이 생성규칙의 LHS가 모두 A인 경우에

A →[eqn: alpha]1 |[eqn: alpha]2 | ⋯ |[eqn: alpha]k로 간단히 표기할 수 있다.

( A에 대한 택일(alternation) 규칙 )

∙ 형식언어 이론에서 사용하는 각 기호들의 의미

1. X, Y, Z와 같은 알파벳 끝부분의 대문자는 보통 문법기호, 즉 nonterminal 혹은 terminal 기호를 나타낸다(X,Y,Z∈V).

2. 알파벳 끝부분의 소문자, 주로 u, v, ⋯, z는 terminal들로 이루어진 string을 나타낸다. [eqn: omega] 역시 terminal string을 나타내는 대표적인 문자이다([eqn: omega]∈V*).

3. [eqn: alpha, beta, gamma]와 같은 그리스체 소문자는 문법기호로 구성된 string을 나타낸다([eqn: alpha, beta, gamma]∈V*).

예1) 일반적인 표기법에 따라 문법기호를 분류해 보자.

E → EOE | (E) | -E |a

O → + | - | * | /

E, O : nonterminal

E : start symbol

그외 : terminal symbol

생성규칙의 수는 8개

예2) <if_statement> → 'if' <condition> 'then' <statement>에서 <>안에

기술된 기호는 nonterminal이고 '과 '사이에 기술된 기호는 terminal이다.

5.2 유도와 유도트리(derivation tree)

5.2.1 유도(derivation)

∙ CFG에서 문장의 생성 : 유도 과정

sentential form의 string에서 생성규칙을 반복 적용하여 nonterminal을 확장

예3) 산술식을 나타내는 문법

E → E+E | E*E | (E) | -E | a

-(a)의 유도 : E ⇒ -E ⇒ -(E) ⇒ -(a)

※ CFG에서는 생성규칙의 RHS에 nonterminal이 여러 개 올 수 있으므로 같은 문장을 유도하는 과정이 여러 개 있을 수 있다. 즉, 문장형태에서 유도시 대치해야 할 nonterminal을 선택하는데 여러 가지 경우가 있을 수 있다.

[정의 5.1] 좌단유도와 우단유도

- 좌단유도(leftmost derivation)

: 유도 과정의 각 단계에서 sentential form의 가장

lm

왼쪽에 있는 nonterminal을 대치. ⇒으로 표기.

- 우단유도(rightmost derivation)

: 유도 과정의 각 단계에서 sentential form의 가장

rm

오른쪽에 있는 nonterminal 을 대치. ⇒으로 표기.

※ 좌단유도에 의한 sentential form을 left-sentential form,

우단유도에 의한 sentential form을 right-sentential form이라 한다.

예4) 문장 (a+a)가 예3의 문법에 의해 유도되는 과정

E → E+E | E*E | (E) | -E | a

(1) 좌단유도

E ⇒ (E) ⇒ (E+E) ⇒ (a+E) ⇒ (a+a).

(2) 우단유도

E ⇒ (E) ⇒ (E+E) ⇒ (E+a) ⇒ (a+a).

[정의 5.2] left parse와 right parse

left parse -- 좌단유도에서 적용된 생성규칙의 순서

right parse -- 우단유도에서 적용된 생성규칙의 역순

예5) 문장 a+a*a의 left parse와 right parse를 구하시오.

1. E → E+T	2. E → T

3. T → T*F	4. T → F

5. F → (E)	6. F → a

left parse: 1 2 4 6 3 4 6 6.	right parse: 6 4 2 6 4 6 3 1.

E ⇒ E+T   (1)	E ⇒ E+T   (1)

⇒ T+T   (2)	⇒ E+T*F (3)

⇒ F+T   (4)	⇒ E+T*a (6)

⇒ a+T   (6)	⇒ E+F*a (4)

⇒ a+T*F (3)	⇒ E+a*a (6)

⇒ a+F*F (4)	⇒ T+a*a (2)

⇒ a+a*F (6)	⇒ F+a*a (4)

⇒ a+a*a (6)	⇒ a+a*a (6)

5.2.2 유도트리(derivation tree)

∙ 유도 트리

- 문장이 유도되는 과정을 tree형태로 표현한 것.

- 생성규칙에 의해 적용되는 문장의 계층적 구조를 나타냄.

[정의 5.3] CFG G=(VN, VT, P, S)에 대한 유도 tree

1. 각 node는 문법기호를 label로 갖는다.

2. root label은 시작기호이다.

3. 어떤 node가 하나 이상의 children node를 가지면, 이 node는

nonterminal symbol을 label로 가진다.

4. 왼쪽부터 순서대로 label이 A1A2⋯Ak인 node들이 어떤 node A의

children node라면, 생성규칙 A→A1A2⋯Ak가 존재한다.

예) 어떤 유도 과정에서 생성규칙 A→XYZ가 적용되었다면 유도 tree는

다음과 같은 subtree를 갖는다.

A

↙↓↘

X Y Z

※ 유도 tree는 children node의 위치 순서가 생성규칙의 오른쪽에 나타난 symbol의 순서와 반드시 일치한다. 따라서 유도 tree는 순서 트리(ordered tree)가 된다.

예6) <예4> (1)의 유도 과정에 대하여 각 단계에 따라 유도 트리를 만들어 보자.

( 좌단유도, 우단유도 모두 같은 모양의 tree로 구성됨 )

E → E+E | E*E | (E) | -E | a

※ 문장 a+a*a를 이 문법에 의해 좌단 유도를 하면 두 가지의 유도 과정 발생

□□□ 이런 문법을 모호한(ambiguous) 문법이라고 한다.

5.2.3 모호성(ambiguity)

[정의 5.4] 문법의 모호성

문법 G에 의해 생성되는 어떤 문장이 두 개 이상의 유도 트리를 갖는다면, 문법 G는 모호하다(ambiguous)고 한다. 즉, 모호한 문법은 어떤 문장에 대해 좌단유도나 우단유도 중 어느 한 가지를 이용하더라도 두 개 이상의 유도 과정이 존재하는 경우이다. 따라서 어떤 문법이 모호함을 증명하려면 그 문법에 속하는 임의의 문장을 선택하여 두 개 이상의 유도 트리를 구성하면 된다.

예7) 다음 문법은 모호한 문법이다.

S → if C then S else S

S → if C then S

S → a

C → b

증명: if b then if b then a else a에 대해 두 개의 유도 트리

※ 구문분석기(parser)의 출력 : parse tree

어떤 문장에 대한 parse tree가 모호성(ambiguity)을 가지면 어떤 object code를 생산할지 알 수 없다.

⇒ 모호하지 않은 문법으로 변환 가능, 모든 경우에 변환이 가능하지는 않음

※ 생성규칙의 형태가 A → A[eqn: alpha]A, A →[eqn: beta]이면 ambiguous하다.

∵ A[eqn: alpha]A[eqn: alpha]A와 같은 문장에 대하여 2개의 tree가 생성 가능

⇒ 모호성 제거

① [eqn: alpha]가 좌측결합(left associative) 연산자인 경우

A → A[eqn: alpha]A' | A'

A' →[eqn: beta]

② [eqn: alpha]가 우측결합(right associative) 연산자인 경우

A → A'[eqn: alpha]A	| A'

A' →[eqn: beta]

예) 다음 문법을 unambiguous grammar로 변환

E → E+E | E*E | (E) | a

E → E+T | T

T → T*F | F

F → (E) | a

E → E+E | E-E | E*E | E/E | E↑E | -E | (E) | id

- 연산자의 우선순위

+, - ≺ *, / ≺ ↑ ≺ -(unary)

① 우선순위가 가장 높은 것부터

<element> → (<expression>) | id

② 다음으로 높은 우선순위

<primary> → -<element> | <element>

③ 연산자 ↑는 우측결합(right associative)이므로

<factor> → <primary>↑<factor> | <primary>

④ 연산자 *, /는 좌측결합(left associative)이므로

<term> → <term> * <factor> | <term> / <factor> | <factor>

⑤ 연산자 +, -는 좌측결합(left associative)이므로

<expr> → <expr> + <term> | <expr> - <term> | <term>

[정의 5.5] 언어의 모호성

어떤 CFL을 생성하는 모든 문법이 모호하면, 이 언어는 본질적으로 모호하다.

예8) L={aibjck | i=j 또는 j=k} 는 본질적으로 모호한 CFL이다.

<이유>

i=j인 스트링을 생성하려면 j=k인 경우의 유도과정과 다른 과정을 거쳐야 한다. 마찬가지로, j=k인 스트링을 생성하려면 i=j인 경우의 유도과정과 다른 과정을 거쳐야 한다. 그런데, i=j=k의 경우는 두 유도과정이 모두 가능하기 때문이다.

5.3 문법 변환

[정의 5.6] L(G1) = L(G2)이면 문법 G1과 G2는 동등하다(equivalent)고 말한다.

예9) 다음 CFG G1과 G2는 동일하다.

G1 : A → 1B	G2 : X → Y1

A → 1	X → 1

B → 0A	Y → X0

∴ L(G1) = L(G2) = 1(01)*

※ 문법 변환 방법

① 대입(substitution) : 특정 생성규칙을 제거하고 그에 해당하는 생성규칙 추가

A →[eqn: alpha]B[eqn: gamma]와 B →[eqn: beta_1~ |~ beta_2~ |~ ...~ |~ beta_n]에 대하여

A →[eqn: alphabeta_1 gamma~ |~ alphabeta_2 gamma~ |~ ...~ |~ alphabeta_n gamma]

② 확장(expansion)  : 새로운 생성규칙을 도입하여 한 개의 생성규칙을 분해

A →[eqn: alpha][eqn: beta] 에 대하여 A →[eqn: alpha]X 와 X →[eqn: beta]

예10) S → aT | bT, T → S | Sb | c 에서 생성규칙 T를 제거하시오.

□□□ T를 S에 대입

5.3.1 불필요한 생성규칙 제거

- 문장을 생성하는데 적용될 수 없는 생성규칙들은 모두 제거

[정의 5.7] nonterminal X가 유도과정에서 전혀 사용되지 않는다면 X는 불필요한 symbol이다. 이 때, X를 포함한 모든 생성규칙을 제거해도 된다. 불필요한 symbol에는 non-terminating symbol과 inaccessible symbol이 있다.

[정의 5.8]

terminating nonterminal: terminal string을 생성할 수 있는 nonterminal

(알고리즘 5.1)

accessible symbol: 시작기호로부터 도달할 수 있는 symbol (알고리즘 5.2)

[알고리즘 5.1] Terminating nonterminal 구하는 방법

Algorithm terminating

begin

VN' : = { A | A→[eqn: omega]∈P, [eqn: omega]∈VT* };

repeat

VN' := VN' ∪ { A | A→[eqn: alpha]∈P, [eqn: alpha]∈(VN'∪VT)* }

until no change

end.

[알고리즘 5.2] Accessible symbol을 구하는 방법

Algorithm accessible

begin

V' := { S };

repeat

V' := V' { X | some A→[eqn: alpha X beta]∈P, A∈V' }

until no change

end.

예11) P = { S → A, S → B, B → a } 에서 terminating nonterminal 집합은?

{ S, B }

예12) P = { S → aB, A → aB, A → aC, B → C, C → b } 에서 도달가능한 symbol 집합은?

알고리즘 5.2에 따라 구하면 : { S, a, B, C, b }

예13) P = { S → aS, S → A, S → B, A → aA, B→a, C→aa } 에서 불필요한 생성규칙 제거.

5.3.2 [eqn: epsilon]-생성규칙 제거 --- [정의 5.9] [eqn: epsilon]-free 문법

생성규칙의 형태가 A → [eqn: epsilon] 인 것 제거 --- 알고리즘 5.3

[알고리즘 5.3] [eqn: epsilon]-free 문법으로 변환하는 방법

예14) S → aSbS | bSaS |[eqn: epsilon]

① 각 생성규칙에 대하여 [eqn: epsilon] 제거

S → aSbS  ⇒  S → aSbS | aSb | abS | ab

S → bSaS  ⇒  S → bSaS | bSa | baS | ba

② 시작기호가 [eqn: epsilon]으로 생성되면 S' → S |[eqn: epsilon]를 추가

5.3.3 단일 생성규칙 제거 --- 알고리즘 5.5

A → B 와 같이 생성규칙의 오른쪽에 한 개의 nonterminal만 오는 경우

⇒ 불필요한 유도과정이 생기며 parsing 속도가 느려진다.

예15) 아래 문법에 대해 단일 생성규칙을 제거해 보자.

E → E+T | T

T → T*F | F

F → (E) | a

E → E+T | T*F | (E) | a

T → T*F | (E) | a

F → (E) | a

[정의 5.10] cycle-free이고 [eqn: epsilon]-free인 문법을 proper하다고 한다.

cycle-free 문법 : A⇒...⇒A 형태의 유도과정이 존재하지 않는 문법

5.3.4 문법의 기본적인 형태(Canonical Forms of Grammar)

[정의 5.11] Chomsky Normal Form : CNF

CFG G=(VN, VT, P, S)의 생성규칙이 다음 형태로 이루어져 있을 때

G를 정규형태(normal form) 혹은 CNF라 한다.

(1) A→ BC, 여기서 A,B,C∈VN

(2) A→ a, a∈VT

(3) 만약 [eqn: epsilon]∈L(G)라면, S →[eqn: epsilon]이고 S는 생성규칙의 RHS에 나타나지 않음

※ 모든 CFG는 CNF로 바꿀 수 있다.

방법 : ① CFG를 [eqn: epsilon]-free 문법으로 변환

② A→[eqn: alpha], |[eqn: alpha]|>2인 생성규칙의 RHS를 두 개의 symbol을 갖도록 변환

A→X1X2⋯Xk, k>2

⇒ A→X1'<X2⋯Xk>

<X2⋯Xk>→X2'<X3⋯Xk>

⋯

<Xk-1Xk>→Xk-1'Xk'

※ <Xi⋯Xk>는 nonterminal이고,

Xi'은 nonterminal이면 Xi', terminal이면 생성규칙 Xi'→Xi가 추가된다.

예16) 다음 문법을 CNF로 변환하시오.

S→ aAB | BA

A→ BBB | a

B→ AS | b

S→ aAB에 대하여

S→ a'<AB>

a'→ a

<AB>→AB

[정의 5.12] 표준형태(standard form) 또는 Greibach 정규형태

CFG G=(VN, VT, P, S)가 [eqn: epsilon]-free이고 [eqn: epsilon]-생성규칙이 존재하지 않는

A→a[eqn: alpha], a∈VT, [eqn: alpha]∈VN* 형태의 생성규칙을 갖는 문법

5.4 CFG 표기법 : BNF와 EBNF

∙ 명칭의 정의

<id> ::= <letter> | <id><letter> | <id><digit>

<letter> ::= a | b | c | ⋯ | y | z

<digit> ::= 0 | 1 | 2 | ⋯ | 8 | 9

∙ comma로 구분되는 명칭의 정의

① BNF

<id_list> ::= <id_list>, <id> | <id>

② EBNF --- 반복되는 부분을 {}로 표현

<id_list> ::= <id> {, <id> }

예18) compound statement의 CFG 표현

① BNF

<compound_statement> ::= begin <statement_list> end

<statement_list> ::= <statement_list>; <statement> | <statement>

② EBNF --- 반복되는 부분을 {}, 선택은 []로 표현

<compound_statement> ::= begin <statement> {; <statement>} end

※ EBNF : 반복횟수 표현 [eqn: left{right}_0^7] --- 최소 0번, 최대 7번

[x] ---[eqn: left{ x right}_0^1]과 같은 의미

예) if 문 : <if_stmt> ::= if <condition> then <statement> [else <statement>]

예19) 단순변수와 1차원 배열에 대한 BNF와 EBNF

① BNF

<variable> ::= <id> | <id> '[' <exp> ']'

② EBNF

<variable> ::= <id> [ '[' <exp> ']' ]

※ EBNF에서 사용되는 meta symbol들을 terminal로 사용할 때는 ‘’로 묶어 표현

※ 괄호와 택일기호 |를 사용하여 여러 개의 생성규칙들을 묶어서 간단히 표현

예) <exp> ::= <exp>+<exp> | <exp>-<exp> | <exp>*<exp> | <exp>/<exp>

⇒ <exp> ::= <exp> ( + | - | * | / ) <exp>

예20) BNF의 정의

※ CFG는 syntax diagram(구문 도표)으로 표현하기도 한다.

5.5 pushdown automata (PDA)

∙ finite automata의 제약

기억장소가 없으므로 처리된 input symbol의 수를 헤아릴 수 없음

∙ PDA

finite-state control, input tape, stack으로 구성 ( 그림 5.3 )

[정의 5.13] PDA는 7개 요소로 구성된다.

P = (Q, [eqn: SIGMA], [eqn: GAMMA], [eqn: delta], q0, Z0, F)

Q : finite set of states

[eqn: SIGMA] : finite set of input alphabets

[eqn: GAMMA] : finite set of stack symbols

[eqn: delta] : 상태전이함수 Q×([eqn: SIGMA]∪{[eqn: epsilon]})×[eqn: GAMMA] → Q×[eqn: GAMMA]*

q0∈Q : start state

Z0∈[eqn: GAMMA] : stack의 start state

F∈Q : set of final states

- 상태전이 함수 [eqn: delta]는 다음과 같은 형태를 갖는다.

[eqn: delta](q, a, Z) = {(p1,[eqn: alpha]1), (p2,[eqn: alpha]2), ⋯, (pn,[eqn: alpha]n)}

- 현재상태 q, input symbol a, stack의 top symbol Z에서 (pi,[eqn: alpha]I)가

선택되었다면,

(1) next state는 pi

(2) stack의 top symbol Z를[eqn: alpha]i로 대치

[정의 5.14] PDA의 작동 상태 : (q,[eqn: omega],[eqn: alpha]) ⇐ Q×[eqn: SIGMA]*×[eqn: GAMMA]*의 triple

q : 현재 상태

[eqn: omega] : 읽지 않은 input 부분

[eqn: alpha] : stack의 내용 ([eqn: alpha]의 왼쪽 1-st symbol이 stack의 top symbol )

∙ 상태전이의 예

(q, a[eqn: omega], Z[eqn: alpha]) ⊢ (q',[eqn: omega],[eqn: gamma alpha])  ---  [eqn: delta](q, a, Z) = {(q',[eqn: gamma]), ⋯ }에 대하여

⊢*, ⊢+

- q에서 q'으로 상태전이

- input head가 한 칸 이동

- stack의 top Z가 [eqn: gamma]로 대치 ([eqn: gamma]가 [eqn: epsilon]이면 pop )

- a가 [eqn: epsilon]이면 [eqn: epsilon]-move

- PDA P의 시작 형태 : [eqn: omega]∈[eqn: SIGMA]*일 때 (q0, [eqn: omega], Z0)

- PDA P의 종결 형태 : (q,[eqn: epsilon],[eqn: alpha]),  q∈F이고 [eqn: alpha]∈[eqn: GAMMA]*

[정의 5.15] PDA P에 의해 accept되는 언어 L(P)

・ input string [eqn: omega]를 다 본 상태가 [eqn: epsilon]이고 final state에 있으면,

string [eqn: omega]는 P에 의해 인식된다고 말한다.

・ L(P) = {[eqn: omega]| (q0, [eqn: omega], Z0) ⊢* (q, [eqn: epsilon], [eqn: alpha]), q∈F, [eqn: alpha]∈[eqn: GAMMA]*}

예26) 언어 L = { 0n1n | n≥1 }을 인식하는 PDA

P = ({q0, q1, q2}, {0, 1}, {Z, 0}, [eqn: delta], q0, Z, {q0})

[eqn: delta](q0, 0, Z) = { (q1, 0Z) }

[eqn: delta](q1, 0, 0) = { (q1, 00) }

[eqn: delta](q1, 1, 0) = { (q2, [eqn: epsilon]) }

[eqn: delta](q2, 1, 0) = { (q2, [eqn: epsilon]) }

[eqn: delta](q2, [eqn: epsilon], Z) = { (q0, [eqn: epsilon]) }

・ input string 0011에 대하여 P가 인식하는 과정

(q0, 0011, Z) ⊢ (q1, 011, 0Z)

⊢ (q1, 11, 00Z)

⊢ (q2, 1, 0Z)

⊢ (q2, [eqn: epsilon], Z)

⊢ (q0, [eqn: epsilon], [eqn: epsilon])

・ input string 0n1n에 대하여 인식하는 과정

(q0, 0n1n, Z) ⊢ (q1, 0n-11n, 0Z)

⊢n-1 (q1, 1n, 0nZ)

⊢ (q2, 1n-1, 0n-1Z)

⊢n-1 (q2, [eqn: epsilon], Z)

⊢ (q0, [eqn: epsilon], [eqn: epsilon])

※ stack이 empty이면 더 이상 move가 발생하지 않는다.

[정의 5.16] Extended PDA

P = (Q, [eqn: SIGMA], [eqn: GAMMA], [eqn: delta], q0, Z0, F)

[eqn: delta] : 상태전이함수 Q×([eqn: SIGMA]∪{[eqn: epsilon]})×[eqn: GAMMA]*→Q×[eqn: GAMMA]*

예27) L = {[eqn: omega][eqn: omega]R | [eqn: omega]∈{a,b}+ }를 인식하는 확장된 PDA를 정의해 보자.

P = ({q}, {a, b}, {a, b, S, Z}, [eqn: delta], q, Z, {q})

[eqn: delta](q, a, [eqn: epsilon]) = { (q, a) }

[eqn: delta](q, b, [eqn: epsilon]) = { (q, b) }

[eqn: delta](q, [eqn: epsilon], [eqn: epsilon]) = { (q, S) }

[eqn: delta](q, [eqn: epsilon], aSa) = { (q, S) }

[eqn: delta](q, [eqn: epsilon], bSb) = { (q, S) }

[eqn: delta](q, [eqn: epsilon], SZ) = { (q, [eqn: epsilon]) }

・ input string aabbaa에 대하여 인식하는 과정

(q, aabbaa, Z) ⊢ (q, abbaa, aZ)

⊢ (q, bbaa, aaZ)

⊢ (q, baa, baaZ)

⊢ (q, baa, SbaaZ)

⊢ (q, aa, bSbaaZ)

⊢ (q, aa, SaaZ)

⊢ (q, a, aSaaZ)

⊢ (q, [eqn: epsilon], aSaZ)

⊢ (q, [eqn: epsilon], SZ)

⊢ (q, [eqn: epsilon], [eqn: epsilon])

[정의 5.17] stack을 empty로 만드는 확장된 PDA P에 의해 인식되는 언어

Le(P) = {[eqn: omega] | (q0, [eqn: omega], Z0) ⊢+ (q, [eqn: epsilon], [eqn: epsilon]), q∈Q }

[정리 5.1] PDA P = (Q, [eqn: SIGMA], [eqn: GAMMA], [eqn: delta], q0, Z0, F)에 의해 인식되는 언어 L(P)를 L이라 할 때, Le(P') = L인 PDA P'을 만들 수 있다.

5.6 Context-free 언어와 PDA 언어

[정리 5.2] 문법 G = (VN, VT, P, S)가 CFG일 때, G로부터

Le(R) = L(G)인 PDA R을 만들 수 있다.

∙ 좌단유도를 행하는 PDA R을 구성

R = ( {q}, VT, VN∪VT, [eqn: delta], q, S,[eqn: phi] )

(1) A→[eqn: alpha] ∈ P 이면, [eqn: delta](q,[eqn: epsilon], A)에 (q,[eqn: alpha])를 추가

(2) 모든 a∈VT에 대하여, [eqn: delta](q, a, a) = { (q, [eqn: epsilon]) }

(증명) A⇒[eqn: omega]와 (q,[eqn: omega], a) ⊢n (q,[eqn: epsilon],[eqn: epsilon])이 서로 필요충분 조건이 됨을 증명.

예28) 문법 G에 대하여 좌단유도를 행하는 PDA R을 구성.

G = ( {E, T, F}, {a, *, +, (, )}, P, E )

P : E → E+T | T

T → T*F | F

F → (E) | a

(1) [eqn: delta (q, epsilon], E) = { (q, E+T), (q, T) }

(2) [eqn: delta (q, epsilon], T) = { (q, T*F), (q, F) }

(3) [eqn: delta (q, epsilon], F) = { (q, (E)), (q, a) }

(4) [eqn: delta (q,]x, x) = { (q, [eqn: epsilon]) }, 여기서 x∈{ a, +, *, (, ) }

・ input string a+a*a에 대한 PDA R의 인식 과정

(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,    [eqn: epsilon], [eqn: epsilon])

∙ 우단 역유도(reverse derivation)를 행하는 PDA R을 구성

R = ( {q, r}, VT, VN∪VT, [eqn: delta], q, $, {r} )

(1) A→[eqn: alpha] ∈ P 이면, [eqn: delta](q,[eqn: epsilon],[eqn: alpha])에 (q, A)를 추가

(2) 모든 a∈VT에 대하여, [eqn: delta](q, a, [eqn: epsilon]) = { (q, a) }

(3) [eqn: delta](q,[eqn: epsilon], $S) = { (r,[eqn: epsilon]) }

예29) 예28의 문법에 대하여 우단 역유도를 행하는 PDA R을 구성.

(1) [eqn: delta (q,]x,[eqn: epsilon]) = { (q, x) }, 여기서 x∈{ a, +, *, (, ) }

(2) [eqn: delta (q, epsilon], E+T) = { (q, E) }

[eqn: delta (q, epsilon], T) = { (q, E) }

[eqn: delta (q, epsilon], T*F) = { (q, T) }

[eqn: delta (q, epsilon], F) = { (q, T) }

[eqn: delta (q, epsilon], (E)) = { (q, F) }

[eqn: delta (q, epsilon], a) = { (q, F) }

(3) [eqn: delta (q, epsilon], $E) = { (r,[eqn: epsilon]) }

・ input string 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,    [eqn: epsilon], $E+T*a)

⊢ (q,    [eqn: epsilon], $E+T*F)

⊢ (q,    [eqn: epsilon], $E+T)

⊢ (q,    [eqn: epsilon], $E)

⊢ (r,    [eqn: epsilon], [eqn: epsilon])

※ top-down parsing vs. bottom-up parsing

top-down parsing : 좌단유도

bottom-up parsing : 우단 역유도

[정리 5.3] R = (Q, [eqn: SIGMA], [eqn: GAMMA], [eqn: delta], q0, Z0, F)가 PDA라면 L(G) = Le(R)인 CFG를 만들 수 있다.

※ 다음은 모두 동등한 의미를 갖는다.

(1) CFG G에 의해 생성되는 언어 L(G)

(2) PDA P에 의해 생성되는 언어 L(P)

(3) PDA P에 의해 생성되는 언어 Le(P)

(4) Extended PDA P에 의해 생성되는 언어 L(P)

※ 연습문제 풀이