Path: utzoo!attcan!uunet!cs.utexas.edu!usc!snorkelwacker.mit.edu!ira.uka.de!rusux1!mark From: mark@adler.philosophie.uni-stuttgart.de (Mark Johnson) Newsgroups: comp.lang.prolog Subject: Re: Efficiency of DCGs and chart parsers Message-ID: Date: 24 Jan 91 11:20:00 GMT References: <8014@castle.ed.ac.uk> Sender: zrf80385@rusux1.rus.uni-stuttgart.de Organization: IMS, University of Stuttgart Lines: 33 In-reply-to: jmcn@castle.ed.ac.uk's message of 23 Jan 91 16:15:57 GMT Regarding the use of a chart in a DCG parsers implemented in Prolog; Pereira and Shieber themselves note that the constant factors involved when the chart is stored by asserting it into the database outweigh the speedup obtained. One of the things that the chart does is cache intermediate results (lemmas) of the computation in such a way that no computation is ever performed twice. But as Ken Church first pointed out to me, it may be more expensive to actually store in and look up the cache than it is to just redo the original calculation again. Since asserting is a very expensive process in Prolog, in most cases it will be more efficient not to use an assert-based cache. (There is one case where there is a win, of course. Left-recursive clauses cause an infinite number of essentially identical goals with the top-down proof procedure of prolog, and an approach in which a computation is performed at most once clearly wins here. There are other approaches to left-recursion, including left-corner parsing, which can handle left recursion and doesn't need caching). I have implemented a couple of chart parsers in Prolog, and to get half-way acceptable performance I had to do the following: - Pass around the chart as an argument, rather than store it in the database. This means that the parser itself never backtracks, and that edges must be copied before they are used (assuming that the categories in the edges are not always ground). - Build efficient indexing into the chart (edges must be indexed on their left-hand string position, etc). Mark Johnson