제 5 장 Context-Free 문법 상지대학교컴퓨터정보공학부고광만 (kkman@mail.sangji.ac.kr)
Contents 5.1 서론 5.2 유도와유도트리 5.3 문법변환 5.4 CFG 표기법 5.5 Push Down Automata; PDA 5.6 Context-free 언어와 PDA 언어 제 5 장 : Context-Free Grammar 2
서론 정규문법 간단한패턴기술에적합 프로그래밍언어의구문구조표현에부적합 토큰구조 정규표현 프로그래밍언어문법구조 Context-Free Grammar; CFG Context-Free Grammar 의장점 간단하고이해하기용이 표현된문법으로부터자동적으로인식기구현 입력된프로그램의구조를생성규칙에의해분해, 번역이유용 제 5 장 : Context-Free Grammar 3
Context-Free Grammar A α생성규칙 A : Nonterminal, α : V * A를문맥에관계없이 α로대치 context-free( 문맥-자유또는문맥-무관 ) 제 5 장 : Context-Free Grammar 4
표기법 (Notational Convention) Terminal 심볼 알파벳소문자 (a, b, c,... ), 숫자 ( 0,1,2,...,9) 연산자기호 (+, -,...) 구분자 ( 세미콜론, 콤마, 괄호 ) ' 와 ' 사이에표기된문법심볼 Nonterminal 심볼 알파벳대문자 S, 시작심볼 (start symbol) < 와 > 로묶어서나타낸문법심볼 <stmt>, <expr> 제 5 장 : Context-Free Grammar 5
A α 1, A α 2,..., A α k 생성규칙의왼쪽이모두 A 인경우 A α 1 α 2... α k, 택일 (alternation) 규칙 예. E EOE (E) -E id O + - * / <if_statement> -> 'if' <condition> 'then' <statement> < > 안에기술된심볼, Nonterminal 사이에기술된심볼, Terminal 제 5 장 : Context-Free Grammar 6
유도및유도트리 문장생성, In Context-free Grammar 문장형태의스트링에생성규칙반복적용 Nonterminal 확장 산술식 E E+E E*E (E) -E id 문장을얻기위해시작심볼 E 로부터반복적으로생성규칙적용 E -E - ( E ) - ( id ) 제 5 장 : Context-Free Grammar 7
생성규칙오른쪽, Nonterminal 이존재 같은문장을유도하는여러가지방법이가능 유도시대치해야할 Nonterminal을선택?? 여러가지경우가존재 예. A B C D 제 5 장 : Context-Free Grammar 8
좌측유도 v.s 우측유도 좌측유도 (Left derivation) 문장형태의가장왼쪽에있는Nonterminal을대치 좌문장형태 (Left-sentential form) 우측유도 (Right derivation) 문장형태의가장오른쪽에있는 Nonterminal 을대치 우문장형태 (Right-sentential form) 제 5 장 : Context-Free Grammar 9
문장 -(id+id) 가유도되는과정 좌측유도 E -E -(E) -(E+E) -(id+e) -(id+id). 우측유도 E -E -(E) -(E+E) -(E+id) -(id+id). 제 5 장 : Context-Free Grammar 10
좌파스 (left parse) 좌파스 vs. 우파스 좌측유도에서적용된일련의생성규칙순서. top-down parsing 시작심볼로부터터미널생성 ( 확장, expansion) 우파스 (right parse) 우측유도에서적용된생성규칙번호의역순. bottom-up parsing 터미널로부터넌터미널로축약하여시작심볼에도착 ( 축약, reduce) 제 5 장 : Context-Free Grammar 11
예, a+a*a 의좌파스와우파스 1. E E + T 2. E T 3. T T * F 4. T F 5. F (E) 6. F a E E + T E E + T 1 1 T + T E + T * F 2 3 F + T E + T * a 4 6 a + T E + F * a 6 4 a + T * F E + a * a 3 6 a + F * F T + a * a 4 2 a + a * F F + a * a 6 4 a + a * a a + a * a 6 6 좌파스 : 1 2 4 6 3 4 6 6. 우파스 : 6 4 2 6 4 6 3 1. 제 5 장 : Context-Free Grammar 12
유도트리 유도트리 (Derivation Tree) 문장유도과정을트리형태로표현 생성규칙에의해적용되는문장의계층적구조 CFG G = {V N, V T, P, S} 유도트리 노드 : 문법심볼 루트 (root) 노드 : 시작심볼 S Nonterminal 심볼 최소한하나이상의자노드를가지는노드 생성규칙 A A 1 A 2... A k A 1 A 2... A k 노드 : 노드 A의자노드 제 5 장 : Context-Free Grammar 13
A XYZ 의유도트리, 순서트리 (Ordered tree) internal(nonterminal) node V N external(terminal) node V T {ε} 예 6, 교재 166 A X Y Z 제 5 장 : Context-Free Grammar 14
유도트리 문장형태에서대치되는심볼의순서에관계없이구성 생성규칙의적용순서에따라다른유도과정이존재 두개이상의유도트리가가능 a+a*a 에대한좌측유도, 그림 5.2 E E + E E E * E a + E E + E * E a + E * E a + E * E a + a * E a + a * E a + a * a a + a * a 제 5 장 : Context-Free Grammar 15
모호성 (Ambiguity) 모호성 (Ambiguity) 문법 G 에의해생성되는문장이두개이상의유도트리가존재 모호한문법 어떤문장이 2 개이상의유도과정이존재 예 7, 모호한문법 S if C then S else S S if C then S S a C b 제 5 장 : Context-Free Grammar 16
구문분석기의출력, 유도트리 문장의유도트리를결정적으로구성 모호하지않은문법 (Unambiguous Grammar) 결정적파싱 (Deterministic Parsing) 모호하지않은문법구성 모호한문법을모호하지않은문법으로변환. 제 5 장 : Context-Free Grammar 17
모호한문법 ( 일반적인경우 ) 생성규칙 : A AαA 문장형태 : AαAαA 트리형태 : A A A α A A α A A α A A α A 제 5 장 : Context-Free Grammar 18
모호하지않은문법으로변환 연산우선순위, 결합법칙 생성규칙추가 새로운 Nnonterminal 도입 제 5 장 : Context-Free Grammar 19
정의 5.6 5.3 문법변환 L(G 1 ) = L(G 2 ), 문법 G 1 과G 2 는동등 문법이생성하는언어가같음. 예 9, CFG G 1, G 2 는동일. G 1 : A 1B G 2 : X Y1 A 1 X 1 B 0A Y X0 L(G 1 ) = L(G 2 ) = 1(01) * 제 5 장 : Context-Free Grammar 20
문법변환 다른형태의동등한문법으로변환 대입 (substitution), 확장 (expansion) 대입 (substitution) 특정생성규칙을제거하고그에해당하는생성규칙추가. if A αbγ, B β 1 β 2 β 3 β n P, then P' = ( P - {A αbγ } ) {A αβ 1 γ αβ 2 γ... αβ n γ }. 제 5 장 : Context-Free Grammar 21
확장 (expansion) 새로운 Nonterminal 심볼을도입. 한개의생성규칙을쪼개는방법 생성규칙 A αβ 에대해 A αx, X β 혹은 A Xβ, X α X, 새로운 Nonterminal 심볼 확장의효과 유도과정의횟수를한번늘인결과 제 5 장 : Context-Free Grammar 22
불필요한생성규칙제거 불필요한생성규칙 (Useless production rule) 문장을생성하는데적용할수없는생성규칙 [ 정의 5. 7] CFG G = (V N, V T, P, S) S wxy wxy (w, x, y V T *) 형태의유도과정이존재하지않으면, 심볼 X 는불필요 (useless) 불필요한생성규칙 불필요한심볼 (useless symbol) 을갖고있는생성규칙 제거 (elimination) 제 5 장 : Context-Free Grammar 23
불필요한심볼, X 시작심볼로부터도달할수없는심볼 X가스트링을생성할수없는 Nonterminal 심볼 생성규칙 A α Α w, w V * T, A :Terminating Nonterminal S uxw, u,w V * : X, 도달가능한심볼 (accessible symbol) 필요한생성규칙 도달가능한심볼 + Terminating Nonterminal 제 5 장 : Context-Free Grammar 24
불필요한생성규칙제거방법 terminating nonterminal 을구함 스트링을생성할수없는 nonterminal을포함하고있는생성규칙제거 도달가능한심볼들을구성 도달불가능심볼을포함하고있는생성규칙제거 알고리즘 5.1 예제 11, 12, 13번참조 제 5 장 : Context-Free Grammar 25
ε- 생성규칙제거 (ε-free) A ε, ε- 생성규칙 생성규칙의형태가 A ε, 제거. CFG G=(V N, V T, P, S), ε-free. 생성규칙 P 가 ε- 생성규칙을갖지않음 S 는 ε- 생성규칙을갖지만다른생성규칙의오른쪽에 S 가나타나지않음. ε- 생성규칙제거 구문분석시간감소 ε-free 문법 제 5 장 : Context-Free Grammar 26
단일생성규칙제거 단일생성규칙 (single production rule) A B 생성규칙의오른쪽에한개의 nonterminal만존재 불필요한유도과정이발생, 파싱속도증가 의미없는단일생성규칙, 제거 제 5 장 : Context-Free Grammar 27
Proper 문법 : CFG G = ( V N, V T, P, S ) Cycle-free if there is no derivation of the form A + A ε-free 불필요한심볼을갖지않음 제 5 장 : Context-Free Grammar 28
문법표기법 5.4 CFG 표기법 BNF(Backus-Naur Form) 확장된 BNF(EBNF, Extended-BNF) 문법흐름도 (Syntax diagram) 제 5 장 : Context-Free Grammar 29
BNF 프로그래밍언어의형식적정의 Nonterminal 심볼 : < 와 > Terminal 심볼 : 문자 명칭 (Identifier) 에대한표현 <id> ::= <letter> <id> <letter> <id> <digit> <letter> ::= a b c... y z <digit> ::= 0 1 2... 8 9 ::= : : 택일 (alternation) 교재 PP. 184, 예 17 제 5 장 : Context-Free Grammar 30
EBNF 반복, 선택적인부분을간결하게표현 특수한의미를갖는메타심볼 (meta symbol) 도입 메타심볼 (Meta Symbol) 언어의일부분이아니라언어를표현하려고사용된특수심볼. 제 5 장 : Context-Free Grammar 31
반복부분 (repetitive part) 표현 { } {a} a가영번이상반복 정규표현 a * 와같은의미 콤마로구분되는명칭리스트 : BNF 및 EBNF BNF <id_list> ::= <id_list>, <id> <id> EBNF <id_list> ::= <id> {, <id> } 제 5 장 : Context-Free Grammar 32
혼합문에대한 BNF 및 EBNF 표현 BNF 표현 <compound_statement> ::= begin <statement_list> end <statement_list> ::= <statement_list> ; <statement> <statement> EBNF 표현 <compound_statement> ::= begin <statement> { ; <statement> } end 제 5 장 : Context-Free Grammar 33
반복되는최대회수와최소회수지정 <external_name> ::= <alphabet> {<alphanumeric>} 7 <alphanumeric> ::= <alphabet> <digit> <alphabet> ::= a b c y z <digit> ::= 0 1 2 9 0 중괄호뒤의 0 은최소회수, 7 은최대회수 제 5 장 : Context-Free Grammar 34
선택적인부분 (optional part) [ ] [x] x가나타나지않거나한번만나타날수있음 [x] 는 {x} 1 예 <if_st> ::= if <cond> then <stat> [else <stat>] 제 5 장 : Context-Free Grammar 35
단순변수, 일차원배열변수 BNF 및 EBNF 표현 BNF 표현 : <variable> ::= <id> <id> '[' <exp> ']' EBNF 표현 : <variable> ::= <id> [ '[' <exp> '] ] 제 5 장 : Context-Free Grammar 36
괄호와택일기호 : ( ) 여러개의생성규칙을간단히표현 <exp> ::= <exp> + <exp> <exp> - <exp> <exp> * <exp> <exp> / <exp> <exp> ::= <exp> ( + - * / ) <exp> 제 5 장 : Context-Free Grammar 37
EBNF 메타심볼 vs. terminal 심볼 terminal 심볼을 ' 와 ' 로묶어표현 <BNF_rule> ::= <left_part> '::=' <right_part> <right_part> ::= <right_part_element> { ' <right_part_element> } 제 5 장 : Context-Free Grammar 38
문법흐름도 (Syntax diagram) 문법을도식화하여표현 초보자가프로그래밍언어의문법을쉽게이해 구성 사각형 :Nonterminal 타원 : Terminal 지시선 : 문법이움직이는경로 (path) 제 5 장 : Context-Free Grammar 39
Nonterminal A 사각형안을 A terminal의경우와같이지시선 사각형의내용은그안의이름에의해참조 A Terminal a 타원안을 a 지시선으로연결 a 제 5 장 : Context-Free Grammar 40
생성규칙 A ::= X 1 X 2 X i 가 Nonterminal 인경우... X n X 1 X 2 X 3... X n X i 가 terminal 인경우 x1 x2 x3... x n 제 5 장 : Context-Free Grammar 41
A ::= α 1 α 2... α n α 1 A α i α n 제 5 장 : Context-Free Grammar 42
EBNF A ::= {α} A α EBNF A ::= [ α ] A α 제 5 장 : Context-Free Grammar 43
EBNF A ::= ( α1 α2 ) β α 1 A β α 2 제 5 장 : Context-Free Grammar 44
푸시다운오토마타 푸시다운오토마타 (Push-Down Automata; PDA) 보조기억장치를가진인식기. Context-Free Grammar 인식기. 구성 유한상태제어 (finite state control) 전체의행동제어 현재의입력심볼, 스택의 top 심볼에따라행동 입력테이프 (input tape) 입력스트링유지 스택 (stack) 보조기억장치, 푸시다운리스트 (push-down list) 제 5 장 : Context-Free Grammar 45
Push Down Automata, PDA Input tape a 1 a 2... a n Finite state control Z 1 Z 2 Z n stack 제 5 장 : Context-Free Grammar 46
PDA P = (Q, Σ, Γ, δ, q 0, Z 0, F) Q : 상태의유한집합 Σ : 입력알파벳의유한집합 Γ : 스택심볼의유한집합 δ : 사상함수 Q (Σ {ε} ) Γ Q Γ * q 0 Q : 시작상태 (start state) Z 0 Γ: 스택의시작심볼 F Q : 종결상태 (final state) 의집합 제 5 장 : Context-Free Grammar 47
사상함수 ( 전이함수 ) : δ, delta δ(q, a, Z) = { (p 1,α 1 ), (p 2,α 2 ),...,(p n,α n ) } 현재의상태 : q 입력심볼 : a 스택 Top 심볼 : Z (p i,α i ) 선택 현재의 q 상태에서입력 a 를본다음상태 : p i 스택 top 심볼 Z 를 α i 로대치. 제 5 장 : Context-Free Grammar 48
PDA 형태 (configuration) : P 어떤시점에서 PDA P 의현재상태표현방법 Q Σ * Γ * => Triple(q, ω, α) q : 현재상태 ω: 읽지않은입력부분 α: 스택의내용 ω= ε 인경우, 모든입력심볼이읽혀졌음 P 에의한상태이동 (move) : -- (q, aω, Zα) -- (q', ω,υα) 제 5 장 : Context-Free Grammar 49
a=ε; ε- 이동 (ε-move) 현재의입력심볼변화없음 모든입력심볼이읽혀졌을때발생 스택이빈경우, 어떤이동도발생하지않음. * : 영번이상, + : 한번이상이동 P 시작형태 Σ * 에속하는 ω, (q 0,ω,Z 0 ) P 의종결형태 (q, ε, α), q F, α Γ* 제 5 장 : Context-Free Grammar 50
P 의이동 (move)ː 1) a ε: (q, aω, Zα) ( q', ω, γα) 2) a = ε : (q, ε, Z) (q', ε, γ) <===> ε-move * : zero or more moves + : one or more moves 제 5 장 : Context-Free Grammar 51
L(P) : PDA P 에의해언어인식 (accept). 입력스트링 ω 를다본상태가종결상태 시작상태 : (q 0, ω, Z 0 ) 종결상태 : (q, ε, α), where q F, α F* L(P) = {ω (q 0, ω, Z 0 ) * (q, ε, α), q F, α Γ* }. 제 5 장 : Context-Free Grammar 52
인식 (accept) 시작상태에서입력스트링 ω 를다본상태가종결상태에도달 "ω 는 P 에의해인식 (accept)" P 에의해정의되는언어 푸시다운오토마타언어 : L(P) P 에의해인식되는스트링의집합 L(P) = {ω ( q 0,ω, Z 0 ) -- (q, ε, α), q F, α Γ*} 제 5 장 : Context-Free Grammar 53
예 26. 언어 L = {0 n 1 n n 1} 을인식하는 PDA P = ( {q 0, q 1, q 2 }, {0, 1}, {Z, 0}, δ, q 0, Z, {q 0 } ) δ(q 0, 0, Z) = { (q 1, 0Z) } δ(q 1, 0, 0) = { (q 1, 00) } δ(q 1, 1, 0) = { (q 2, ε) } δ(q 2, 1, 0) = { (q 2, ε) } δ(q 2, ε, Z) = { (q 0, ε) } 0 에대하여차례로스택에모두이동 1 에대하여스택에있는 0 을하나씩팝 (pop) 제 5 장 : Context-Free Grammar 54
입력스트링 0011 에대하여 P 가인식하는과정 (q 0, 0011, Z) -- (q 1, 011, 0Z) -- (q 1, 11, 00Z) -- (q 2, 1, 0Z) -- (q 2, ε, Z) -- (q 0, ε, ε) 제 5 장 : Context-Free Grammar 55