The systematic construction of Earley Parsers: Application to the production of an O(n6) Earley Parser for Tree Adjoining Grammars
Bernard Lang · 1990
Using general results on dynamic programming techniques for the evaluation of definite clause programs, we systematically derive an O(n) Earley algorithm for Tree Adjoining Grammars. Though the algorithm produced is original and interesting in its own right, the main contribution of this paper is the collection of independent techniques used to produce it. In particular we show how general results on dynamic programming execution of compiled DC programs can be used to organize the parsing in a strictly left-to-right discipline, even in the presence of discontinuous structures with interleaved constituents. The same techniques can be used to produce parsers with different recognition strategies, e.g. bottom-up, topdown, or predictive bottom-up as Earley’s. They may also be applied to unification based grammatical formalisms, and to the construction of robust parsers (e.g. island parsing).