Re: [boost] Automata builder -- interface

From: Douglas Gregor (gregod_at_[hidden])
Date: 2001-05-28 20:01:50

On Friday 25 May 2001 07:30 am, you wrote:
> Since there seem to be interest in automata building library, I suggest
> some more detailed discussion.
>
> I thinks that the more fundamential classes should be created first: BNF,
> automaton, probably NFA/DFA. Those have foundation in computer science, and
> hopefully will not depend on personal preferences as much as high level
> classes. All the other suggestions can be evaluated later -- e.g. making
> Acceptor interface for existing DFA is better  than making Acceptor
> interface primary.

This depends on what one considers the primary purpose of an automaton. If 
the primary purpose is to take a string an either "accept" or "reject" it, 
then the primary interface we want to define is based on accept/reject. If we 
consider the primary purpose to be something else, then the primary interface 
is built based on that idea.

I mentioned the Acceptor interface because most automata are presented as 
acceptors: DFAs and push down automata accept or reject a given string, a 
Turing machine accepts, rejects, or loops (we couldn't tell when a loop 
occurs anyway, so accept/reject is okay here). 
Or, automata could be classified based on their output. A DFA/NFA outputs 
merely accept/reject, whereas a PDA outputs accept/reject with a parse tree. 

> Now to the point! I have implementation for LALR(1) and SLR(1), which at
> least works, but prefer to discuss interface first. Here's first attempt:

[code snipped]

Some comments:

We probably don't want the user to have to subclass Terminal or Nonterminal 
merely for classification purposes - it would get in the way of allowing 
arbitrary types (i.e., char or std::string) as terminals. A trait and/or 
policy class would likely suffice.

I don't see that the BNF class even needs to exist: the Rule class is enough. 
When you want to generate an automaton for a given grammar, give the 
generator the Rule instance for the start variable. 

LR_parser class: by taking a scanner, the scope of the LR parser is limited 
only to that type of scanner. However, an LR parser is more abstract than 
that: it can take any sequence of symbols and parse it. I think the mechanism 
for getting that sequence of symbols should be as abstract as possible (and 
not bound too early!) so that composing several transformations doesn't 
require the parser to change type. The parser need not know where its input 
comes from.

        Doug