Parsing and empty nodes

Mark Johnson; Martin Kay

Parsing and empty nodes

Research output: Contribution to journal › Article › peer-review

19 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 language	English
Pages (from-to)	289-300
Number of pages	12
Journal	Computational Linguistics
Volume	20
Issue number	2
Publication status	Published - Jun 1994
Externally published	Yes

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.

Access to Document

Publisher version (open access)Final published version, 562 KBLicence: CC BY-NC-SA

https://www.aclweb.org/anthology/J94-2005/Licence: CC BY-NC-SA

Cite this

@article{6aa166c3ac6d4a41b7d67b5ce0cb6b99,

title = "Parsing and empty nodes",

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. ",

author = "Mark Johnson and Martin Kay",

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. ",

year = "1994",

month = jun,

language = "English",

volume = "20",

pages = "289--300",

journal = "Computational Linguistics",

issn = "0891-2017",

publisher = "MIT Press Journals",

number = "2",

}

TY - JOUR

T1 - Parsing and empty nodes

AU - Johnson, Mark

AU - Kay, Martin

N1 - 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.

PY - 1994/6

Y1 - 1994/6

N2 - 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.

AB - 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.

M3 - Article

SN - 0891-2017

VL - 20

SP - 289

EP - 300

JO - Computational Linguistics

JF - Computational Linguistics

IS - 2

ER -

Parsing and empty nodes

Abstract

Bibliographical note

Access to Document

Fingerprint

Cite this