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

fjh@mundook.cs.mu.OZ.AU (Fergus Henderson)
21 Dec 1996 23:07:07 -0500

          From comp.compilers

Related articles
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 ? fjh@mundook.cs.mu.OZ.AU (1996-12-21)
| List of all articles for this month |

From: fjh@mundook.cs.mu.OZ.AU (Fergus Henderson)
Newsgroups: comp.compilers
Date: 21 Dec 1996 23:07:07 -0500
Organization: Comp Sci, University of Melbourne
References: 96-12-140
Keywords: parse

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
--


Post a followup to this message

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