A Binary Combinatorial Grammar for Chinese and Its Parsing Algorithm

In order to resolve the problem of low accuracy in Chinese natural language parsing introduced by the lack of complete grammar rules set, a binary combinatorial grammar (BCG) for describing natural language through binary relations between constituents is proposed, which can depict complicated syntactic structures by a very small number of binary relations between head words and their hierarchical combinations. Based on the binary combinatorial grammar, a parsing algorithm for Chinese natural language is proposed which takes operator precedence computing as its basic ideas. Four basic operations and one extended operation are defined in the algorithm. The order of combinatorial operations in parsing is controlled according to the priority between adjacent binary relations, and eventually the recognition of chunks and whole syntactic structures is achieved. The validity of the grammar and the parsing algorithm is proved by the analysis of the space complexity and the time complexity