Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!uunet!mcsun!ukc!canon!wachtel From: wachtel@canon.co.uk (Tom Wachtel) Newsgroups: comp.lang.prolog Subject: Re: Efficiency of DCGs and chart parsers Message-ID: <1991Jan29.133529.8862@canon.co.uk> Date: 29 Jan 91 13:35:29 GMT References: <8014@castle.ed.ac.uk> <1549@gufalet.let.rug.nl> <1991Jan28.131922.727@canon.co.uk> <1991Jan28.235755.7827@agate.berkeley.edu> Organization: Canon Research Europe, Guildford, UK Lines: 33 stolcke@ICSI.Berkeley.EDU (Andreas Stolcke) writes: >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. [...] >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. I'm not sure what domain restrictions you have in mind, but I'd be glad to hear about them. I'm assuming that you never want to have to explicitly compare or manipulate feature values, but only unify or fail to unify feature matrices. I'm also assuming you use a compiler to get from whatever high-level representation you favour down to the prolog code. The thing I like most about it is that you are really unifying (or failing to unify) entire feature matrices rather than specific features, which I think is an important notion in unification-based grammars. It's true that you waste a lot of space for empty slots. The biggest problem I have come across, however, is the limit on the number of registers, so that if you have more than 32 non-anonymous variables (i.e. unified feature values) in the head of a rule, then it all falls over. You can code around that at compile time, but it is a bit messy. What you get is matrix unification as =/2 at parse time, without losing high-level expressiveness, since the compiler handles things for you. I think it's worth it. Tom Wachtel (wachtel@canon.co.uk)