Generalized LL(K) grammars for Concurrent Logic Programming Languages

ID
TR-87-32
Authors
Harvey Abramson
Publishing date
October 1987
Abstract
We examine the compilation of the LL(k) deterministic context free grammars to Horn clause logic programs and sequential and concurrent execution of these programs. In the sequential case, one is able to take advantage of the determinism to eliminate the generation of unnecessary backtracking information during execution of the compiled logic program. In the concurrent case, grammar rules are simply and directly translated to clauses of Concurrent Prolog, Parlog, or Guarded Horn Clause programs, allowing grammatical processing directly in the setting of committed or ``don't care'' nondeterminism. LL(k) grammar rules are generalized so that grammatical processing of streams involving derivations of infinite length is possible. A top-down analogue of Marcus's deterministic parser is a possible application of these generalized LL(k) grammars.