A Simple Transformation for Offline-Parsable Grammars and its Termination Properties

Simple item page
dc.creatorDymetman, Marc
dc.date1996-05-14
dc.date.accessioned2026-07-07T09:10:17Z
dc.date.available2026-07-07T09:10:17Z
dc.descriptionWe present, in easily reproducible terms, a simple transformation for offline-parsable grammars which results in a provably terminating parsing program directly top-down interpretable in Prolog. The transformation consists in two steps: (1) removal of empty-productions, followed by: (2) left-recursion elimination. It is related both to left-corner parsing (where the grammar is compiled, rather than interpreted through a parsing program, and with the advantage of guaranteed termination in the presence of empty productions) and to the Generalized Greibach Normal Form for DCGs (with the advantage of implementation simplicity).
dc.descriptionLatex. 5 pages. Appeared in Coling-94 Proceedings
dc.identifierhttps://arxiv.org/abs/cmp-lg/9605023
dc.identifierhttp://arxiv.org/abs/cmp-lg/9605023
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/151310
dc.subjectComputation and Language
dc.titleA Simple Transformation for Offline-Parsable Grammars and its Termination Properties
dc.typetext

Files

Collections

arXiv