Re: [boost] Re: Experiment in Automata syntax

From: Douglas Gregor (gregod_at_[hidden])
Date: 2001-06-18 10:05:29

On Monday 18 June 2001 07:11, you wrote:
> Douglas Gregor wrote:
> > Hello,
> >  I've been experimenting with a clean, usable syntax for representing
> > automata. A skeletal implementation is at:
> >
> > http://groups.yahoo.com/group/boost/files/Automata/automata_syntax.zip
> >
> >
> > -----------------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.

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

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.

> > -----------------Acceptor syntax------------------------
> > Acceptors are output iterators that apply the symbols output through them
> > to the automata they are initialized with. For the above automata, we can
> > test acceptance of standard input this way:
> > DFA::acceptor<> a = dfa.start();
> > copy(istream_iterator<char>(cin), istream_iterator<char>(), a);
> > if (a.accept()) {
> >   // accepted
> > }
> > else {
> >   // rejected
> > }
> >
> > Acceptors can, of course, perform other more interesting tasks along with
> > acceptance. Acceptors are parameterized by a visitor type whose
> > enter_state and transition methods are executed when the acceptor enters
> > a state or crosses a transition, respectively.
> >
> > Now an example of using acceptors to create a Mealy machine.
> > [snip]
>
> I find that acceptors are really usefull.
>
> As a closing remark, I'd like to say that I will like automata library to
> be created. The simplest way would be through enhancing ASTL, if
> its authors are still willing to boostify it -- after thinking about ASTL's
> cursors, I find them a good thing to have and the library already has
> several dfa classes and algorithms.

I would also like to see ASTL enhanced, Boostified and submitted. 

        Doug