Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!sdd.hp.com!zaphod.mps.ohio-state.edu!samsung!think.com!mintaka!bloom-beacon!eru!hagbard!sunic!mcsun!hp4nl!let.rug.nl!gufal02.let.rug.nl!gosse From: gosse@gufal02.let.rug.nl (Gosse Bouma) Newsgroups: comp.lang.prolog Subject: Re: Efficiency of DCGs and chart parsers Message-ID: <1549@gufalet.let.rug.nl> Date: 25 Jan 91 16:09:02 GMT References: <8014@castle.ed.ac.uk> Sender: news@let.rug.nl Organization: Faculty of Arts, Groningen, The Netherlands Lines: 33 Nntp-Posting-Host: gufal02.let.rug.nl In article mark@adler.philosophie.uni-stuttgart.de (Mark Johnson) writes: > >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). How do you pass the chart around? as a list of chart items? I can hardly believe that going through a list with, say, a few hundred elements is more efficient in Prolog than just exploiting the data-base. Also, the copying, which is avoided if you assert items, seems rather expensive. Anyway, in my (sicstus) prolog chart parser for unification grammar, which just asserts items dynamically, I can have up to 300 items (for 20 words) and have a response in 3 secs or so if the grammar isn't too wild. I find that reasonable, given the fact that feature-unification, rather than prolog-unification, has to be performed and that I have made no attempts whatsoever to index chart items efficiently (in fact, the first argument is just the number of the item). Also, given the fact that in unification grammars, the size of the chart items tends to be rather large, using a list of items as additional argument seems practically impossible to me. -- Gosse Bouma, Alfa-informatica, RUG, Groningen gosse@let.rug.nl All we cry, all we contend for, in this world of toil and blood, is beneath the notice of the hacker we call God. (Th. Pynchon)