|Grammar for optional elements email@example.com (Mohitz) (2007-06-12)|
|Re: Grammar for optional elements firstname.lastname@example.org (2007-06-14)|
|Re: Grammar for optional elements email@example.com (2007-06-16)|
|Re: Grammar for optional elements bobduff@shell01.TheWorld.com (Robert A Duff) (2007-06-16)|
|Re: Grammar for optional elements cfc@shell01.TheWorld.com (Chris F Clark) (2007-06-16)|
|Re: Grammar for optional elements firstname.lastname@example.org (Karsten Nyblad) (2007-06-17)|
|Re: Grammar for optional elements email@example.com (Tony Finch) (2007-06-17)|
|Re: Grammar for optional elements firstname.lastname@example.org (2007-06-18)|
|Re: Grammar for optional elements cfc@shell01.TheWorld.com (Chris F Clark) (2007-06-19)|
|Re: Grammar for optional elements email@example.com (Tony Finch) (2007-06-19)|
|Re: Grammar for optional elements firstname.lastname@example.org (Lowell Thomas) (2007-06-19)|
|[6 later articles]|
|From:||Chris F Clark <cfc@shell01.TheWorld.com>|
|Date:||Sat, 16 Jun 2007 18:18:45 -0400|
|Organization:||The World Public Access UNIX, Brookline, MA|
|References:||07-06-019 07-06-020 07-06-024|
email@example.com (Anton Ertl) writes:
> If such problems occur often enough (and I think they do), one might
> consider adding a special grammar construct for this kind of stuff.
> Should be relatively easy to implement and use.
However, adding such a feature directly into a traditional NFA/DFA
introduces combinatorial explosion. That said, there is a simple
formalism which does deal well with this problem a "register vector
grammar" described by Glen David Blank around 1985, see
"dli.iiit.ac.in/ijcai/IJCAI-85-VOL2/PDF/013.pdf". There was also an
ACM paper on the topic.
The basic technique is one keeps a "register vector" with bits for
each feature. One then has a FA that can set/clear/and check those
bits as one traverses the input, which is exactly what one wants for
this problem. If one is in a state where one wants to add a unique
attribute, the FA checks that the bit isn't set and then sets it.
Otherwise (if the bit was already set), the FA fails and rejects the
input with the appropriate message. This is clearly the correct
semantics for this problem and isn't hard to program. It even has
nice linear complexity and doesn't even introduce unbounded space. It
solves a whole class of problems that regular FAs don't. I'm not sure
why this technique never caught on and became mainstream.
I suspect the reason is that one can do everything that one can do
with register vector languages with [L-]attributes. However, most
attribute grammar systems seem to be big buy-into systems (or simply
use action code in the target language). The register vector approach
looks like it would mate well with low-overhead lexing and parsing
tools and still give one nice verifiable properties (i.e. it is more
formalized than do whatever you want action code).
Hope this helps,
Chris Clark Internet : firstname.lastname@example.org
Compiler Resources, Inc. Web Site : http://world.std.com/~compres
23 Bailey Rd voice : (508) 435-5016
Berlin, MA 01503 USA fax : (978) 838-0263 (24 hours)
Return to the
Search the comp.compilers archives again.