An heuristic-based context-free parsing algorithm

A heuristic-based parsing algorithm for general stochastic context-free grammars is presented. The algorithm is basically a top-down parser that combines an extension of the A* search paradigm with a constraint satisfaction procedure. Heuristics are used to increase the likelihood of making a correct choice while constraint satisfaction eliminates states that cannot lead to a solution. Two simple heuristics are introduced ensuring convergence to the solution and guaranteeing the choice of the most probable parsing in the case of ambiguous grammars. A comparison of the proposed parser with J. Earley´s (1986) algorithm on four different grammars is presented. The efficiency of the proposed method relies on three main aspects: guidance of the search through promising paths, pruning of the state space, based on elimination criteria, and restriction of the number of solutions encountered to the best or the n-best. The last two aspects cannot be met by Earley´s algorithm.