Path: utzoo!utgpu!news-server.csri.toronto.edu!bonnie.concordia.ca!thunder.mcrcim.mcgill.edu!snorkelwacker.mit.edu!usc!sdd.hp.com!uakari.primate.wisc.edu!aplcen!aplcomm!uunet!mcsun!ukc!edcastle!jmcn
From: jmcn@castle.ed.ac.uk (J McNicol)
Newsgroups: comp.lang.prolog
Subject: Efficiency of DCGs and chart parsers
Summary: Is an efficient Prolog chart parser possible?
Keywords: natural language, DCG, grammar, chart parser
Message-ID: <8014@castle.ed.ac.uk>
Date: 23 Jan 91 16:15:57 GMT
Organization: Scottish Crop Research Institute
Lines: 18

I'm attempting to make DCG parsing more efficient by using a chart,
using (approximately) Pereira and Shieber's method.  However I find
that my new parser takes at least twice as long as standard Prolog 
since it has to do so much housekeeping.

It seems a shame to abandon it having got as far as a DCG-compatible 
translator; does anyone have any comments about chart parsing and Prolog, 
such as 'chart parsing can't be done efficiently enough in Prolog'?

The relative efficiency for the grammar I tested is twice as long 
if finding all solutions, three times as long if only finding the 
first solution.

Thank you for any comments!

Julian Smart

EMAIL jmcn@castle.ed.ac.uk