Technical Reports

The ICICS/CS Reading Room

UBC CS TR-87-32 Summary

Generalized LL(K) grammars for Concurrent Logic Programming Languages, October 1987 Harvey Abramson

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.

If you have any questions or comments regarding this page please send mail to