Efficient syntactic parsing with beam search

Abstract

Implementing a Vietnamese syntactic parser is a difficult task due to the complexity of Vietnamese language. Most existing Vietnamese syntactic parsers are limited by types of sentences they can analyze. This paper introduces a syntactic parser that can analyze a larger range of Vietnamese sentences in a reasonable time. The proposed parser uses a probabilistic Head-Driven Phrase Structure Grammar that can control syntactic and semantic constraints of words in order to produce accurate results. The system uses a parsing algorithm that combines an improved version of the CYK algorithm and the idea of beam search in order to reduce the search space. Our experimental results achieved precision and recall of 82% and 74%, respectively. ©2010 IEEE.