Boost logo

Boost :

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.


Boost list run by bdawes at, gregod at, cpdaniel at, john at