Re: [boost] Interest in automa(parser) building library?

From: Douglas Gregor (gregod_at_[hidden])
Date: 2001-05-24 14:53:46

On Thursday 24 May 2001 11:50 am, you wrote:
> Douglas Gregor wrote:
> > On Thursday 24 May 2001 08:32, you wrote:
> > > Vladimir Prus wrote:
>
> ...skipping
>
> > > I'd be interested, especially in one that allowed inheritance of
> > > grammars, as in antlr, and allowing the lex part of the parser being
> > > another parser. I've currently got some smalltalk around somewhere that
> > > did analysis of grammers to rm left recursion an some other ops on
> > > grammars.  So, yes I'm interested.
> >
> > One interface I had considered for automata was an "Acceptor" interface.
> > The Acceptor concept refines the Output Iterator concept. You output
> > symbols until you are finished, and then output an end-of-stream symbol.
> > Then there is an "accepted" function that specifies whether or not the
> > input string was in the language.
> >
> > Sample usage:
> >
> > DFA::acceptor a = myDFA.start();
> > copy(istream_iterator(cin), istream_iterator(), a);
> >
> > if (accepted(a)) { cout << "accepted" << endl; }
> >
> > Automata that transform a string of tokens into another string of tokens
> > (i.e., a lexer) could be created as an output iterator adaptor:
> >
> > HighParser::acceptor h = myHighParser.start();
> > TokenParser::acceptor t = tokenParser.start();
> > Lexer::acceptor l = lexer.start();
> >
> > copy(istream_iterator(cin), istream_iterator(), l(t(h)));
> > finalize(l); // Send the end-of-stream token through
> >
> > if (h) { cout << "accepted" << endl; }
> >
> > The idea is that any of these transforming acceptors are a function
> > object that takes another acceptor and returns an acceptor that emits
> > tokens to the acceptor it contains. So whenever "l" matches a token it
> > outputs that token to "t" and, likewise, when "t" matches a token it
> > outputs it to "h".
>
> This maybe close to what I want.  To make it clearer, let me refer you to
> the attached pccts grammar, cflowCmmPmsZomSafe.g.   I would like to
> replace the TOK_SLC and TOK_PRED instances of the input language
> with the output from a parser which parsed Straight Line Code
> and PREDicate expressions.  The reason why I want to do this is to
> test a control flow normalizer with a simple language which just contained
> the syntax needed for the normalizer (after all, expressions and straight
> line code do not affect the control flow).  After the normalizer is
> verified with the simple language, I can test it on the full language by
> replacing the TOK_SLC and TOK_PRED with some non-terminals.
>
> I hope that's clear.

I believe so, and I think that the abovementioned transforming acceptors 
would handle this nicely - you are just adding or modifying a step prior to 
your grammar.

        Doug