Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!uwm.edu!spool2.mu.edu!sdd.hp.com!ucsd!ucbvax!agate!ICSI.Berkeley.EDU!stolcke From: stolcke@ICSI.Berkeley.EDU (Andreas Stolcke) Newsgroups: comp.lang.prolog Subject: Re: Efficiency of DCGs and chart parsers Message-ID: <1991Jan28.235755.7827@agate.berkeley.edu> Date: 28 Jan 91 23:57:55 GMT References: <8014@castle.ed.ac.uk> <1549@gufalet.let.rug.nl> <1991Jan28.131922.727@canon.co.uk> Sender: usenet@agate.berkeley.edu (USENET Administrator) Reply-To: stolcke@ICSI.Berkeley.EDU (Andreas Stolcke) Organization: International Computer Science Institute, Berkeley, CA Lines: 37 In article <1991Jan28.131922.727@canon.co.uk>, wachtel@canon.co.uk (Tom Wachtel) writes: |> gosse@gufal02.let.rug.nl (Gosse Bouma) writes: |> |> >I find that reasonable, given the fact that |> >feature-unification, rather than prolog-unification, has to be performed |> |> The contrast between feature-unification and prolog-unification is |> unnecessary and expensive. Mapping high-level feature matrix notation |> to prolog terms in a controlled way allows you to treat |> feature-unification as prolog-unification, directly on the whole |> feature matrix represented as a prolog term with a known structure. It |> becomes the same thing. For that to work, it seems, you'd have to map features onto argument positions. Unless you want to severely restrict the domains of features at `compile time' I don't see how this could work. You would lose the very flexibility which makes f-structures so popular among, e.g., grammar writers. Also, many Prolog implementations have upper limits on the number of argument positions in terms. In any case you wast a lot of space for keeping argument slots for features not actually used. The approach I'm familiar with is to encode feature-value sets as open-ended lists. This still requires explicit implementation of f-structure unification, but the resulting complexity is no worse than Prolog's unification (linear in the size of the smaller structure), and very acceptable in practice. Also, you can easily add occur checks if need be. Maybe you have something else in mind, in which case I'd like to know more about it. -- Andreas Stolcke stolcke@icsi.berkeley.edu International Computer Science Institute stolcke@ucbicsi.bitnet 1957 Center St., Suite 600, Berkeley, CA 94704 (415) 642-4274 ext. 126