Re: [boost] Re: Experiment in Automata syntax

From: Douglas Gregor (gregod_at_[hidden])
Date: 2001-06-20 08:39:15

On Wednesday 20 June 2001 09:00, you wrote:
> On Monday 18 June 2001 19:05, Douglas Gregor wrote:
> > > > -----------------DFA Creation Syntax-------------------
> > > > The syntax follows the theoretical syntax as closely as possible.
> > > > [snip]
> > > > typedef boost::automata::dfa<ABAlphabet> DFA;
> > > > DFA dfa;
> > > >
> > > > DFA::state q0 = dfa.add_state(false);
> > > > DFA::state q1 = dfa.add_state(true);
> > > >
> > > > (q0, 'a') = q0;
> > > > (q0, 'b') = q1;
> > > > (q1, 'a') = q1;
> > > > (q1, 'b') = fa.trap();
> > > > q0.set_initial();
> > >
> > > I have two points:
> > > 1) I'm a little concerned about q0.set_initial(). In your
> > > dfa_state_handle both pointer to dfa and state index is stored.
> > > How extra memory consumption due to dfa pointer will affect performace?
> > > Is alternative implementation possible? Maybe, DFA::state should have
> > > no operations at all?
> >
> > The "(q0, 'a') = q0" syntax also requires both the pointer and the state
> > index. I haven't done performance tests, but I believe it is reasonable
> > for a compiler to merge all of those dfa pointers so they do not affect
> > performance.
>
> Those pointers will still consume memory. Also, suppose you have a stack of
> states. In this case compiler must be very smart in order to understand
> that all dfa pointers in all the states are equal.

They don't necessarily have to consume memory. You can split the structure 
into two registers, then copy propagation will make for a lot of dead 
registers that contain the DFA pointer. 

As soon as you stick those pointers into a data structure, no compiler is 
going to handle it, I agree. 

> > > 2) I never thought about trap() state. Are complete automatons used
> > > often enough to justify special method for their support?. Even if they
> > > are usefull, they are likely to demand considerably more memory.
> >
> > They would be useful for a scanner/lexer for sure. When you hit the trap
> > state you know you can't possibly hit another match, so you backtrack to
> > the last match.
>
> When automaton is not complete, you backtrack when you can't make a
> transition.

"can't make a transition" is no different from "transition to the symbolic 
trap state", except that it is safe to use the symbolic trap state.

> > I believe the cost is minimal. The trap state is always located at index
> > 0, so any undefined transition defaults to the trap state. No extra
> > memory is wasted for transitions to the trap state than for undefined
> > transitions. The cost of having a trap state is the cost of the size of a
> > state with all transitions undefined.
>
> Agree. So, in this case
> (q1, 'b') = fa.trap();
> is essentially no-op? I find it somewhat strange, but maybe it's ok.

Yes, it is essentially a no-op.

        Doug