Functional - Re: Type of a Skip Parser?

Author

Re: Type of a Skip Parser?

Alex Rubinsteyn

2007-05-16, 7:06 pm

On May 16, 12:11 am, George Neuner <gneune...@comcast.net> wrote:
> On 15 May 2007 11:02:08 -0700, Alex Rubinsteyn
>
> <alex.rubinst...@gmail.com> wrote:
>
> I'm not sure you can implement this using just associativity with the
> stream operators (though if I think about it some more I might come up
> with something). To do what you want a composed parser really needs
> to be a container so it can control application of and catch results
> of sub-parsers.

After reading your post I bit the bullet and made the >> operator
construct a Tuple. I then specialized the operator to ignore void
parsers (skipped elements). The tuple size is statically computed and
makes things like function applications easy to implement.

>
> I would recursively chain the parsers, arranging for results to be
> passed from the current parser to the next. Chaining forward this can
> be done by passing the result of the current parse as a parameter to
> the match function of the next parser. Chaining backward, you can
> just use the return value of the previous parser (assuming it is a
> (pointer/reference to a) structure containing all the information).

I'm not completely certain what you mean by chaining the parsers. I
just implemented parser sequences so each application of the >>
operator results in a tuple which is concatenated with the next
application of >>.
PARSER(Tuple<integer, 2> , string) intPair = integer >> skip(ch(','))
parser is excluded
PARSER(Tuple<integer, 3> string) intTriple = intPair >> skip(ch(','))[color=darkred]

Is this what you meant by chaining?
[color=darkred]
>
> The casualty is your nice stream syntax ... composition becomes a
> recursive process of constructing and associating parser objects.
> However, the match function of the outer container could still be
> called in a sequence using the stream syntax.

I'm sorry, I'm not totally following you. Could you explain this a
little more?

>
> Thant's suggestion is equally good although I think passing results
> rather than continuations is a bit easier to implement and understand
> given the intended application.

I really liked Thant's idea (continuations are appealing and would
avoid some of the waste associated with returning void ParseResult for
skips) but I don't know how to reconcile it with the need for skipping
the last parser in a sequence.

> In your example the parentheses are not really being "skipped" but are
> required syntax for the match. This is a semantically different
> situation from, say, a parser matching a comment where the matched
> text is irrelevant. I do understand why you want to refer to it as
> skipping however.

Quite right, we're not skipping the parser (which still must match for
the parse to succeed), just the value it returns. Any ideas for a
better name?

Thanks,
Alex

George Neuner

2007-05-17, 7:07 pm

On 16 May 2007 11:33:18 -0700, Alex Rubinsteyn
<alex.rubinsteyn@gmail.com> wrote:

>On May 16, 12:11 am, George Neuner <gneune...@comcast.net> wrote:
>
>After reading your post I bit the bullet and made the >> operator
>construct a Tuple. I then specialized the operator to ignore void
>parsers (skipped elements). The tuple size is statically computed and
>makes things like function applications easy to implement.

First, let me say that if you have a solution that works and you are
satisfied with it, then don't let the rest of this post confuse you.

>
>I'm not completely certain what you mean by chaining the parsers. I
>just implemented parser sequences so each application of the >>
>operator results in a tuple which is concatenated with the next
>application of >>.

>
>I'm sorry, I'm not totally following you. Could you explain this a
>little more?

You wrote that you were creating a "combinator" library - which meant
to me that you were "composing" the parse functions as in taking two
functions, f:A->B and g:B->C, and creating a function g°f:A->C which
is equal to g(f(x)) for x in A.

Ignoring irrelevant details, the solution I was envisioning was
something like the following:

class Parser
{
private:
Parser* nextParser;
public:
Parser& chain( Parser& p ) { next = &p; return *this; };

Result* match( istream& in, Result* ret = NULL )
{
// do pattern matching here

if ( success )
{
if (!nextParser)
return ret;
else
return (*nextParser)( in, ret );
}
};
}

where the details of pattern matching and creating an actual Result
object depend on what type of parser it is. A "skip" parser object
would not create its own Result and would return or pass through to
the next parser any Result object passed in. A value parser could
inspect a prior Result object passed into it and create a new object
or modify the existing one.

So in my scenario, the int_in_parens parser would be constructed thus:

Parser int_in_parens, // skip matches '('
integer, // value matches integer, produces result
rparen; // skip matches ')'

int_in_parens.chain(integer.chain(rparen));

The result of calling int_in_parens.match() on an input stream would
be the integer token value (assuming everything went to plan).

I hope now it is obvious that top level parsers could use stream
operator syntax by making >> call match() because at the top level the
input Result is always the default NULL. But the calls to the nested
sub-parsers cannot use stream syntax because >> is a binary operator
and can't pass on a Result object.

[color=darkred]
>PARSER(Tuple<integer, 2> , string) intPair = integer >> skip(ch(','))
>parser is excluded
>PARSER(Tuple<integer, 3> string) intTriple = intPair >> skip(ch(','))

This is a fine solution, but it is not "composition". What you have
is just sequential application of match functions with the ability to
reference the results individually. It is not much different from a
yacc-alike parser where you can write:

int_in_parens: '(' INTEGER ')' { $$ = $2; };

George
--
for email reply remove "/" from address

George Neuner

2007-05-17, 7:07 pm

On Thu, 17 May 2007 12:34:44 -0400, George Neuner
<gneuner2/@comcast.net> wrote:

> return (*nextParser)( in,ret );

Oops! Should have been either

(*nextParser).match( in,ret )
or
nextParser->match( in,ret )

Anyway, you get the idea.
George
--
for email reply remove "/" from address

Sponsored Links