제 7 장파싱
파싱의개요 파싱 (Parsing) 입력문장의구조를분석하는과정 문법 (grammar) 언어에서허용되는문장의구조를정의하는체계 파싱기법 (parsing techniques) 문장의구조를문법에따라분석하는과정 차트파싱 (Chart Parsing) 2
문장의구조와트리 문장 : John ate the apple. Tree Representation List Representation N V John ate DET the N apple ( ( (N John)) ( (V ate) ( (DET the) (N apple)) ) ) 의미 (meaning) 는 와 로이루어졌다. 는 NAME 인 John 으로이루어졌다. 는 VERB 인 ate 와다른 로이루어졌다. 는 DET 인 the 와 NOUN 인 apple 로이루어졌다. 3
문맥자유문법 (Context-Free Grammar) 문법의구성요소 단어및품사기호 (terminals) ate, the, apple 등 V, DET, N 등 구문기호 (nonterminals),, 등 문법규칙 (productions) N DET N V V V 4
하향식파싱 하향식파싱 (Top-Down Parsing) 문장기호 로부터입력문장방향으로진행 문법규칙의 LH (left-hand side) 기호를 RH (right-hand side) 기호로대체하는과정의반복 하향식파싱의예 (leftmost derivation) N John John V John ate John ate DET N John ate the N John ate the apple G : N DET N V N John DET the V ate N apple Input entence : John ate the apple 5
하향식파싱과정 Grammar G N DET N V N John V ate DET the N apple N V DET N Input entence John ate the apple John ate the apple 6
상향식파싱 상향식파싱 (Bottom-Up Parsing) 입력문장으로부터문법기호 방향으로진행 문법규칙의 RH 를 LH 로대체하는과정의반복 상향식파싱의예 (reverse rightmost derivation) John ate the apple N ate the apple ate the apple V the apple V DET apple V DET N V G : N DET N V N John DET the V ate N apple Input entence : John ate the apple 7
상향식파싱과정 Grammar G N DET N V N John V ate DET the N apple Input entence John ate the apple N V DET N John ate the apple 8
자연언어의중의성 (1) 구조적중의성 (tructural Ambiguity) 하나의문장이다수의구조로해석될수있는성질 구조중의성의예 G : Input entence : N DET N John saw Mary in the park. V P N V N P DET N John saw Mary in the park N V N P DET N John saw Mary in the park 9
자연언어의중의성 (2) 어휘적중의성 (Lexical Ambiguity) 하나의단어가복수의품사로서사용되는경우 어휘적중의성으로구조적중의성발생 어휘적중의성의예 G : Input entence : D N A N N Time flies like an arrow V P A N V D N Time files like an arrow N V P D N Time files like an arrow 10
차트파싱 차트 (chart) 파싱의진행과정을기록하는테이블 Bookkeeping mechanism Keep track of constituents that were built up during part of parse, but may be used by other rules 차트파싱 (chart parsing) 차트를이용하는파싱 Backtracking 에의해동일한분석을반복하는 overhead 제거 구체적인 parsing strategy 에대해서는 no comments top-down or bottom-up left-to-right, right-to-left, or island-driven 일반적인 CFG parsing algorithm (CYK, Early algorithm 등 ) 이용 11
차트파싱의장점 A Grammar G G : DET N V P entence : The rabbit with a saw nibbled on an orange Traditional Parsing (with backtracking) 규칙을적용하여실패할경우 backtracking 한후, 규칙을적용하여파싱 이규칙에서 와 는 규칙에서분석했던내용과동일한데도처음부터다시분석해야함 ( 비효율적 ) 차트파싱 규칙을적용하여실패하였다고해도, 부분결과로만들어진, 구조를버리지않고 chart 에기록해둠 규칙에서, 는새로분석할필요없이 chart 에기록된내용을그대로이용 12
차트파싱과정 (1) Early algorithm 을이용한차트파싱 시작 tate entence symbol 이 LH 인규칙의 RH 처음에 Dot( ) 를삽입한규칙 Closure 연산 Dot 가 Nonterminal 앞에있으면, 해당 Nonterminal 이 LH 인모든규칙의 RH 처음에 Dot 를첨가하여해당 state 에삽입 파싱방법 Initial tate 현재의입력심볼이 A 이면현재 active 한규칙중에서 A 앞에 dot 가있는규칙의 dot 를 A 의뒤로이동 Dot 가해당규칙의맨오른쪽에있고그규칙의 LH 를 B 라고하면, active 한규칙중에서 B 앞에 dot 가있는규칙의 dot 를 B 뒤로이동 DET N DET N P DET N V P DET N The rabbit with a saw nibbled on an orange 13
차트파싱과정 (2) Next item : DET DET N Next item : N DET N V P DET N P DET N V P DET N The rabbit with a saw nibbled on an orange Next item : P V P DET N Next item : DET V P DET N 14
차트파싱과정 (3) Next item : N V P DET N P DET N P DET N V P DET N The rabbit with a saw nibbled on an orange Next item : V V P DET N P DET N V P DET N The rabbit with a saw nibbled on an orange 15
차트파싱과정 (4) Next item : P P DET N Next item : DET P DET N Next item : N P DET N DET N P DET N V P DET N The rabbit with a saw nibbled on an orange 16
차트표현 DET N P DET N V P DET N The rabbit with a saw nibbled on an orange 0 1 2 3 4 5 6 7 8 9 차트표현의한예 [(start position, end position), Category, (constituents)] 1 [(0,1), DET] 7 [(6,7), P] 13 [(0,5),, (10,12)] 2 [(1,2), N] 8 [(7,8), DET] 14 [(5,6),, (6)] 3 [(2,3), P] 9 [(8,9), N] 15 [(0,6),, (13,14)] 4 [(3,4), DET] 10 [(0,2),, (1,2)] 16 [(7,9),, (8,9)] 5 [(4,5), N] 11 [(3,5),, (4,5)] 17 [(6,9),, (7,16)] 6 [(5,6), V] 12 [(2,5),, (3,11)] 18 [(0,9),, (13,14,17)] 17