Re: Grammar for optional elements

anton@mips.complang.tuwien.ac.at (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


*****************************************************************************
Chris Clark Internet : compres@world.std.com
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 comp.compilers page.
Search the comp.compilers archives again.