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

Mark Johnson; Brian Roark

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

Research output: Chapter in Book/Report/Conference proceeding › Conference proceeding contribution › peer-review

15 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 language	English
Title of host publication	Proceedings of the 18th International Conference on Computational Linguistics
Subtitle of host publication	COLING 2000
Place of Publication	New Brunswick, NJ
Publisher	Association for Computational Linguistics (ACL)
Number of pages	7
Volume	1
ISBN (Print)	1-55860-717-X
Publication status	Published - 2000
Externally published	Yes
Event	International Conference on Computational Linguistics (18th : 2000) - Universität des Saarlandes, Saarbrücken, Germany Duration: 31 Jul 2000 → 4 Aug 2000

Conference

Conference	International Conference on Computational Linguistics (18th : 2000)
Abbreviated title	COLING 2000
Country/Territory	Germany
City	Saarbrücken
Period	31/07/00 → 4/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.

Access to Document

Publisher versionFinal published version, 207 KBLicence: CC BY-NC-SA

https://www.aclweb.org/anthology/C00-1052/Licence: CC BY-NC-SA

Cite this

@inproceedings{4df4af8a4d1d4dcd9fee38c894ea562f,

title = "Compact non-left-recursive grammars using the selective left-corner transform and factoring",

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, itproduces non-left-recursive grammars that are not much larger than the original.",

author = "Mark Johnson and Brian Roark",

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. ; International Conference on Computational Linguistics (18th : 2000), COLING 2000 ; Conference date: 31-07-2000 Through 04-08-2000",

year = "2000",

language = "English",

isbn = "1-55860-717-X",

volume = "1",

booktitle = "Proceedings of the 18th International Conference on Computational Linguistics",

publisher = "Association for Computational Linguistics (ACL)",

}

Johnson, M & Roark, B 2000, Compact non-left-recursive grammars using the selective left-corner transform and factoring. in Proceedings of the 18th International Conference on Computational Linguistics: COLING 2000. vol. 1, Association for Computational Linguistics (ACL), New Brunswick, NJ, International Conference on Computational Linguistics (18th : 2000), Saarbrücken, Germany, 31/07/00. <https://www.aclweb.org/anthology/C00-1052/>

Compact non-left-recursive grammars using the selective left-corner transform and factoring. / Johnson, Mark; Roark, Brian.
Proceedings of the 18th International Conference on Computational Linguistics: COLING 2000. Vol. 1 New Brunswick, NJ: Association for Computational Linguistics (ACL), 2000.

Research output: Chapter in Book/Report/Conference proceeding › Conference proceeding contribution › peer-review

TY - GEN

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

AU - Johnson, Mark

AU - Roark, Brian

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

PY - 2000

Y1 - 2000

N2 - 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, itproduces non-left-recursive grammars that are not much larger than the original.

AB - 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, itproduces non-left-recursive grammars that are not much larger than the original.

M3 - Conference proceeding contribution

SN - 1-55860-717-X

VL - 1

BT - Proceedings of the 18th International Conference on Computational Linguistics

PB - Association for Computational Linguistics (ACL)

CY - New Brunswick, NJ

T2 - International Conference on Computational Linguistics (18th : 2000)

Y2 - 31 July 2000 through 4 August 2000

ER -

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

Abstract

Conference

Bibliographical note

Access to Document

Fingerprint

Cite this