Re: [boost] Re: Experiment in Automata syntax

From: Vladimir Prus (ghost_at_[hidden])
Date: 2001-06-20 08:00:42

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.  

> > 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.

> 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.

-- 
Regards,
Vladimir