This paper describes a method for ensuring the termination of parsers using grammars that freely posit empty nodes. The basic idea is that each empty node must be associated with a lexical item appearing in the input string, called its sponsor. A lexical item, as well as labeling the node for the corresponding word, provides labels for a fixed number, possibly zero, of empty nodes. The number of nodes appearing in the parse tree is thus bounded before parsing begins. Termination follows trivially. The technique is applicable to any standard parsing algorithm.
|Number of pages||12|
|Publication status||Published - Jun 1994|