7.6 Best-First Parsing

• $B:GNI$N(B parse $B$r9bB.$K9T$& $BDc$$3NN($N2DG=@-$rGS=|$7$J$,$i(Bparse
• Chapter 3 $B$N(B buttom-up Chart Parse $B$N(B agenda $B$r(B priority queue($BM%(B $B@h=g=x$D$-BT$A9TNs(B)$B$G4IM}(B, $B$b$C$H$b9b$$3NN($NMWAG$r@hF,$KJ]$A$J$,(B $B$i(B agenda $B$r;HMQ(B
• $BLdBjE@(B
  arc $B$r?-$P$9$H$-$K(B, $B$9$G$K$=$l$,(B chart $B$NCf$KF~$C$F$k$+$b$7$l$J$$(B, ($B:G8e$NC18l$,9b$$3NN($r;}$A(B,$B$9$G$K(B chart $B$KF~$C$F$k$3$H$,$"$j$&$k(B)
• $BC1=c$K(B active arc $B$r(B chart $B$K2C$($F$k$3$H$,LdBj(B,$B2~A1$9$kI,MW$"$j(B,
  Figure 7.22

  1.

  C $B$r(B p₁,p₂ $B$N(B chart $B$K2C$($k(B

  2.

  $X \rightarrow X_1 \cdots \circ C \cdots X_n$ $B$N7A$r$7$F$$$k(B p₀ $B$+$i(B p₁$B$^$G$N(B active arc $B$KBP$7$F(B $B0J2<$K$7$?$,$C$F?7$7$$(B active arc $X\rightarrow X_1 \cdots C \circ \cdots X_n$ $B$r2C$($k(B
  
  $B$3$3$G(B active arc $X \rightarrow X_1 \cdots C \circ C' \cdots X_n$ $B$r(B $B2C$($k$K$O(B

  (a)

  C $B$,:G8e$NMWAG$G$"$k;~$O?7$7$$MWAG(B X $B$r(B agenda $B$K(B $B2C$($k(B

  (b)

  $B$=$&$G$J$$>l9g(B, category C' $B$KB0$9$k9=@.AG$,4{$K(B chart $B$NCf$K$"$l$P(B
  $X \rightarrow X_1 \cdots C\ C'\circ \cdots X_n$ $B$H$$$&(B active arc $B$r(B p₀ $B$+$i(B p₃ $B$^$G2C$($k(B

• $B8zN($N2~A1(B
  3$B>O$N(B buttom-up chart parser $B$G2r@O$7$?>l9g(B 158 $B$N9=@.AG$,(B chart $B$K$J$k(B, $B0lJ}$3$N(B algorithm $B$rE,MQ$9$k$H(B 65$B$K8:$k(B ($B7k2L$OF1$8(B)
• $B3NN(:GBg$N2r(B
  $B$3$N(B algorithm $B$O3NN(:GBg$N2r$r=PNO$9$k$3$H$,J]>Z$5$l$F$$$k(B
  ($B>ZL@(B)

  1.

  S₁ $B$r$3$N(B algorithm $B$GF@$i$l$?2r$H$9$k(B ($B2>Dj(B)

  2.

  S₁ $B$h$j3NN($N9b$$(B S₂ $B$,$"$k$H2>Dj(B

  3.

  S₂ $B$N9=@.AG$O(B,S₁$B$N$=$l$h$j9b$$(B

  4.

  S₁ $B$h$j@h$K(B chart $B$KF~$k(B

  5.

  $B2>Dj$HL7=b(B

• $BLdBjE@(B
  $B3NN($NI>2A$K3NN($N@Q$rMQ$$$F$$$k(B,$B$9$k$HD9$$9=@.AG$N3NN($,5^7c$K(B $B8:$k$?$a(B,$B7k2L$H$7$FC;$$9=@.AG$P$+$j$,(B agenda $B$KDI2C$5$l$k(B,$B$=$3$G(B $B3NN($NI>2A$r0J2<$N$h$&$KJQ99$9$k(B
  
  $$\begin{eqnarray*}Score(C) = MIN(Score(C \rightarrow C_1\cdots C_n),Score(C_1),\cdots,Score(C_n)) \end{eqnarray*}$$
  
  (P221$B$N<0$HHf$Y$F$_$h(B)
  
  $B$3$Nl9g$K$=$l$,A4BN$NI>2A(B $BCM$K$J$C$F$7$^$&7gE@$,$"$k$,(B,$B8=