A Context-Free Parsing Algorithm using Heuristic

This paper presents a heuristic parsing algorithm for general stochastic context-free grammars (SCFG). The method is based on the formulation of the parsing problem as a search on the state-space representing legal phrases generated by the grammars. An extension of the state-space search algorithm A* to stochustzc gruphs is applied to solve the parsing problem. Simple, grammar independent, heuristics are described that ensure convergence to the solution and guarantee the choice of the most probable parsing in case of ambiguous grammars. The method is compared with Earley's algorithm and with a related heuristic recognizer (AE*). Several test grammars are used as examples, showing that the proposed algorithm outperforms both methods in many situations. grammars (A*-p). Terniination conditions for the algorithm are discussed in section 2.4. Admissibility of the second heuristic is demonstrated (section 2.5). Section 3 shows results of parsing on three different grammars. Results are compared with Earley's algorithm [5] and with a related heuristic recognizer (AE") [SI in terms of average and worst case time complexity.