Preliminary Analysis of a Breadth-First Parsing Algorithm: Theoretical and Experimental Results

摘要

We will trace a brief history of context-free parsing algorithms and then describe some representation issues. The purpose of this paper is to share our philosophy and experience in adapting a well-known context free parsing algorithm (Earley's algorithm and variations thereof) to the parsing of a difficult and wide ranging corpus of sentences. The sentences were gathered by Malhotra in an experiment which fooled businessmen users into thinking they were interacting with a computer, when they were actually interacting with Malhotra in another room. The Malhotra corpus is considerably more difficult than a second collection published by the LADDER Group. Both collections are given in the appendices. Section 4 compares empirical results obtained from these collections against theoretical predictions. (Author)