Publication Search Form




We found publication with these paramters.

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

Marc Dymetman
We present in easily reproducible terms, a simple transforrnatiomm for offline-parsable grammars which results in a provably terminatiing parsing program directly top-down interpretable in Prolog. The transformation consists in two steps: (1) removal of empty-productions, followed hy: ( 2 ) left-recursionr elimination. It is related both to left-corner parsing (where the grammar is compiled rather thani interpreted through a parsing program, and with the advantage of guaranteed termination in tine presence of empty productions) and to the Generalized Greibach Normal Form for DCGs (with the advantage of implementation simplicity ).
COLING'94, Aug. 5 - 9 Kyoto, Japan, Vol. I., pp. 1226-1230