入力文の構文構造を明らかにする構文解析手法には，大きく分けて，1)可能な構造をすべて生成する手法と，2)可能な構造に優劣を付け，そのうち最も適切なものだけを，または適切なものから順に生成する手法，の二つがある．前者の手法として，これまでに，一般化LR法\cite{Tomita85}やSAX\cite{Matsumoto86}，LangLAB\cite{Tokunaga88}などの効率の良い手法が数多く提案されている．しかしながら，これらの手法を，機械翻訳システムなどの実用を目指した自然言語処理システムに組み込むことは，必ずしも適切ではない．なぜならば，通常，可能な構文構造の数は膨大なものになるため，それらをすべて意味解析などの構文解析以降の処理過程に送ると，システム全体としての効率が問題になるからである\footnote{文献\cite{Tomita85}には，構文構造の曖昧さをユーザとの対話で解消する方法も示されている．}．意味的親和性や照応関係に関する選好なども考慮に入れて全体で最も適切となる解釈は，最も適切な構文構造から得られるとは限らないので，システム全体で最も適切な解釈を得るためには，最悪の場合，可能な構造をすべて生成しなければならない．しかし，より適切な構文構造がシステム全体で最も適切な解釈の構成要素となる可能性が高いと期待されるので，適切でない構造は生成しなくてもよい可能性が高い．従って，可能な構造のうち最も適切なものだけをまず生成し，構文解析以降の処理からの要請があって初めて，次に適切な構造を生成するための処理を開始する後者の手法のほうが，システム全体の効率の観点からは望ましい．後者の手法を実現するためのアプローチでは，費用が付与された部分構造を状態とする状態空間において，目標状態のうち費用の最も小さいものを発見するという探索問題として構文解析を捉えるのが自然である．このように捉えると，確立された種々の探索戦略を構文解析に応用することができる．本稿では，可能な構造のうち生成費用の最も小さいものだけをまず生成し，必要ならば可能な構造が尽きるまですべての構造を生成費用の昇順に生成する構文解析法を提案する．基本的な考え方は，チャート法のアジェンダ\cite{Kay80}を$\A^*$法の探索戦略\cite{Nilsson80}に従って制御することである\cite{Yoshimi90}．チャート法は，良く知られているように，重複処理を行わない効率の良い構文解析の枠組みである．解析過程において生成されうる部分構造に，構文規則に付与された費用に基づいて計算される生成費用を付与するとともに，その構造を構成要素として持つ全体構造を生成するまでの費用を，$\A^*$法の最適性条件を満たし実際の費用になるべく近くなるように推定して付与し，競合する部分構造のうちその生成費用と推定費用の和が最も小さいものに対する処理を優先的に進めれば，効率の良い構文解析が実現できる．本稿の手法と同じように，適切な構造を優先的に生成する手法として，これまでに，Shieberの手法\cite{Shieber83}やKGW+p\cite{Tsujii88}，島津らの手法\cite{Shimazu89}などが提案されている．これら関連する研究との比較は\ref{sec:comparison}節で行なう．