Compact non-left-recursive grammars using the selective left-corner transform and factoring

Mark Johnson, Brian Roark

Research output: Chapter in Book/Report/Conference proceedingConference proceeding contributionpeer-review

1 Downloads (Pure)

Abstract

The left-corner transform removes left-recursion from (probabilistic) context-free grammars and unification grammars, permitting simple top-down parsing techniques to be used. Unfortunately the grammars produced by the standard left-corner transform are usually much larger than the original. The selective left-corner transform described in this paper produces a transformed grammar which simulates left-corner recognition of a user-specified set of the original productions, and top-down recognition of the others. Combined with two factorizations, it
produces non-left-recursive grammars that are not much larger than the original.
Original languageEnglish
Title of host publicationProceedings of the 18th International Conference on Computational Linguistics
Subtitle of host publicationCOLING 2000
Place of PublicationNew Brunswick, NJ
PublisherAssociation for Computational Linguistics (ACL)
Number of pages7
Volume1
ISBN (Print)1-55860-717-X
Publication statusPublished - 2000
Externally publishedYes
EventInternational Conference on Computational Linguistics (18th : 2000) - Universität des Saarlandes, Saarbrücken, Germany
Duration: 31 Jul 20004 Aug 2000

Conference

ConferenceInternational Conference on Computational Linguistics (18th : 2000)
Abbreviated titleCOLING 2000
CountryGermany
CitySaarbrücken
Period31/07/004/08/00

Bibliographical note

Copyright the Publisher 2000. 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 'Compact non-left-recursive grammars using the selective left-corner transform and factoring'. Together they form a unique fingerprint.

Cite this