Re: Is there a lookahead definite-clause grammar parsing algorithm ?

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 [1] or as part of partial evaluation / partial
deduction.


[1] 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 <fjh@cs.mu.oz.au>
WWW: <http://www.cs.mu.oz.au/~fjh>
PGP: finger fjh@128.250.37.3
--

Return to the comp.compilers page.
Search the comp.compilers archives again.