|Is there a lookahead definite-clause grammar parsing algorithm ? Hai.Doan-Nguyen@imag.fr (haidoan) (1996-12-20)|
|Re: Is there a lookahead definite-clause grammar parsing algorithm ? email@example.com.OZ.AU (1996-12-21)|
|From:||firstname.lastname@example.org.OZ.AU (Fergus Henderson)|
|Date:||21 Dec 1996 23:07:07 -0500|
|Organization:||Comp Sci, University of Melbourne|
haidoan <Hai.Doan-Nguyen@imag.fr> writes:
>Is there a definite-clause grammar parsing technique augmented with
>lookahead to reduce time for backtracking ?
For a discussion of how to avoid unnecessary backtracking in DCGs by
(manual) lookahead, see the DCG chapter of Richard O'Keefe's book "The
Craft of Prolog".
If you were looking for an automatic method, I don't know of anything
related specifically to DCGs, but I do know of quite a bit of work
about minimizing nondeterminism in logic programs, e.g. using
determinism analysis  or as part of partial evaluation / partial
 See for example "Determinism analysis in the Mercury compiler",
Fergus Henderson, Thomas Conway, and Zoltan Somogyi.
Available from <http://www.cs.mu.oz.au/mercury/papers>.
Fergus Henderson <email@example.com>
PGP: finger firstname.lastname@example.org
Return to the
Search the comp.compilers archives again.