Parsing and empty nodes

Mark Johnson, Martin Kay

Research output: Contribution to journalArticlepeer-review

4 Downloads (Pure)

Abstract

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.
Original languageEnglish
Pages (from-to)289-300
Number of pages12
JournalComputational Linguistics
Volume20
Issue number2
Publication statusPublished - Jun 1994
Externally publishedYes

Bibliographical note

Copyright the Publisher 1994. Version archived for private and non-commercial use with the permission of the author/s and according to publisher conditions. For further rights please contact the publisher.

Fingerprint

Dive into the research topics of 'Parsing and empty nodes'. Together they form a unique fingerprint.

Cite this