An Efficient Stochastic Context-Free Parsing Algorithm
一种有效的概率上下文无关文法分析算法*

The research of parsing is important in the field of natural language processing. An efficient stochastic context free parsing algorithm is described in this paper. In order to implement a stochastic context free parser, the authors rebuild a GLR algorithm like parsing table so that derivation probabilities can be computed efficiently by making use of the parsing control structure, and add indices to each state in parsing period as identifiers of different parsing paths. Based on the techniques above, the forward and inner probabilities of states are introduced in this paper. With these two probabilities, the probabilities of all parsing trees of the input sentence can be computed to select an optimal parsing result. The experiment shows that the proposed algorithm is efficient.