On Wed, Sep 18, 2002 at 05:01:35PM +0200, Damian Conway wrote:
> Steve Fink wrote:
>
> >What possible outputs are legal for this:
> >
> > "aaa" =~ /( a { print 1 } | a { print 2 })* { print "\n" } x/
>
> Unless Larry specifies a required semantics, there are potentially very
> many acceptable outputs from this, depending on implementation.
>
> Therefore, your implementation must print the superposition of all possible
> outputs. ;-)
It does. In fact, I wrote the superposition of all possible sequences
of outputs in my email. Don't tell me you actually _read_ my question
before answering it? You, of all people, should know the dangers of
observing these things! Just out of curiousity, which one did it
collapse to?
Superpositions don't seem to work that well as a building block for
our irregular expressions. Making a* map to ANY(,a,aa,aaa,...) loses
some rather important ordering information. Let's see... what if you
makes an OANY ("Ordered ANY") so that
R* -> OANY(aaaa..., aaa..., aa..., ...)
R*? -> OANY(,a,aa,aaa,aaaa,...)
R|S -> OANY(R,S)
Then if you "optimize" by converting as many OANY's to ANY's as you
can, would it then be correct to take maximal subtrees of ANY's and
implement them with DFAs?
Bleh. Why bother? The OANY -> ANY decision is no easier than doing it
directly on the parse tree, I think.
Oops, gotta go. The nice men in the white coats are back.
