Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #110924 > unrolled thread

Parser Combinators

Back to article view | Back to comp.lang.c

Contents

  Parser Combinators luser droog <luser.droog@gmail.com> - 2017-05-30 00:34 -0700
    Re: Parser Combinators luser droog <luser.droog@gmail.com> - 2017-06-04 19:34 -0700
      Re: Parser Combinators Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-06-05 12:46 +0100
        Re: Parser Combinators luser droog <luser.droog@gmail.com> - 2017-06-05 07:55 -0700
    Re: Parser Combinators bartc <bc@freeuk.com> - 2017-06-05 15:06 +0100
      Re: Parser Combinators luser droog <luser.droog@gmail.com> - 2017-06-05 08:00 -0700
        Re: Parser Combinators luser droog <luser.droog@gmail.com> - 2017-06-06 21:54 -0700
          Re: Parser Combinators luser droog <luser.droog@gmail.com> - 2017-06-06 22:32 -0700
            Re: Parser Combinators luser droog <luser.droog@gmail.com> - 2017-06-06 23:03 -0700
              Re: Parser Combinators luser droog <luser.droog@gmail.com> - 2017-06-06 23:24 -0700
              Re: Parser Combinators Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-06-07 20:57 +0100
                Re: Parser Combinators Melzzzzz <Melzzzzz@zzzzz.com> - 2017-06-08 00:55 +0000
                Re: Parser Combinators luser droog <luser.droog@gmail.com> - 2017-06-07 20:17 -0700
                  Re: Parser Combinators luser droog <luser.droog@gmail.com> - 2017-06-11 00:29 -0700
                    Re: Parser Combinators Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-06-11 12:11 +0100
                      Re: Parser Combinators luser droog <luser.droog@gmail.com> - 2017-06-11 21:21 -0700
                        Re: Parser Combinators Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-06-12 12:25 +0100
                          Re: Parser Combinators luser droog <luser.droog@gmail.com> - 2017-06-12 13:53 -0700
                            Re: Parser Combinators luser droog <luser.droog@gmail.com> - 2017-06-13 04:43 -0700
                              Re: Parser Combinators luser droog <luser.droog@gmail.com> - 2017-06-16 02:22 -0700
                                Re: Parser Combinators Melzzzzz <Melzzzzz@zzzzz.com> - 2017-06-17 04:04 +0000
                                  Re: Parser Combinators luser droog <luser.droog@gmail.com> - 2017-06-16 23:05 -0700
                                    Re: Parser Combinators Melzzzzz <Melzzzzz@zzzzz.com> - 2017-06-17 06:16 +0000
                                Re: Parser Combinators tkook11@gmail.com - 2017-08-10 06:38 -0700
                                  Re: Parser Combinators Steve Carroll <tmelmosfire@gmail.com> - 2017-08-12 13:07 -0700
                                  Re: Parser Combinators luser droog <luser.droog@gmail.com> - 2017-08-20 18:45 -0700
            Re: Parser Combinators bartc <bc@freeuk.com> - 2017-06-07 12:22 +0100
          Re: Parser Combinators Melzzzzz <Melzzzzz@zzzzz.com> - 2017-06-07 12:43 +0000
            Re: Parser Combinators bartc <bc@freeuk.com> - 2017-06-07 14:43 +0100

Page 1 of 2  [1] 2  Next page →

#110924 — Parser Combinators

cf. https://en.wikipedia.org/wiki/Parser_combinator
& https://groups.google.com/d/topic/comp.lang.postscript/KiEFeJROOcM/discussion

An exercise in using the Parser-Combinator idea in C. Comments welcome.


$ cat pc.c
#include <stdio.h>
#include <stdlib.h>


enum parser_type { TERM, ALT, SEQ };
typedef struct parser *parser;
struct parser {
    enum parser_type type;
    int c;
    parser a, b;
};


parser term( int c );
parser alt( parser a, parser b );
parser seq( parser a, parser b );
int parse( char *input, parser p );

parser
term( int c ){
    parser p = malloc( sizeof *p );
    p->type = TERM;
    p->c = c;
    return  p;
}

int parse_term( char *input, parser p ){
    printf( "%c?\n", p->c );
    return  *input == p->c;
}

parser
alt( parser a, parser b ){
    parser p = malloc( sizeof *p );
    p->type = ALT;
    p->a = a;
    p->b = b;
    return  p;
}

int parse_alt( char *input, parser p ){
    return  parse( input, p->a ) || parse( input, p->b );
}

parser
seq( parser a, parser b ){
    parser p = malloc( sizeof *p );
    p->type = SEQ;
    p->a = a;
    p->b = b;
    return  p;
}

int parse_seq( char *input, parser p ){
    return  parse( input, p->a ) ? parse( input + 1, p->b ) : 0;
}

int
parse( char *input, parser p ){
    switch( p->type ){
    case TERM:  return parse_term( input, p );
    case ALT:   return parse_alt( input, p );
    case SEQ:   return parse_seq( input, p );
    }
}

int
main( void ){
    parser p = seq( alt( term( 'H' ), term( 'h' ) ),
                    seq( term( 'e' ),
                         seq( term( 'l' ),
                              seq( term( 'l' ),
                                   term( 'o' ) ) ) ) );
    printf("%d\n", parse( "hello", p ) );
    printf("%d\n", parse( "Hello", p ) );
    printf("%d\n", parse( "YaMaMa", p ) );
    return 0;
}

$ make pc && ./pc
cc     pc.c   -o pc
H?
h?
e?
l?
l?
o?
1
H?
e?
l?
l?
o?
1
H?
h?
0

[toc] | [next] | [standalone]

#111507

On Tuesday, May 30, 2017 at 2:35:08 AM UTC-5, luser droog wrote:
> cf. https://en.wikipedia.org/wiki/Parser_combinator
> & https://groups.google.com/d/topic/comp.lang.postscript/KiEFeJROOcM/discussion
> 
> An exercise in using the Parser-Combinator idea in C. Comments welcome.
> 
> $ make pc && ./pc
> cc     pc.c   -o pc
> H?
> h?
> e?
> l?
> l?
> o?


Developed further on the postscript side, but no idea
how to translate to C. Too lispy, perhaps.

[toc] | [prev] | [next] | [standalone]

#111535

luser droog <luser.droog@gmail.com> writes:

> On Tuesday, May 30, 2017 at 2:35:08 AM UTC-5, luser droog wrote:
>> cf. https://en.wikipedia.org/wiki/Parser_combinator
>> & https://groups.google.com/d/topic/comp.lang.postscript/KiEFeJROOcM/discussion
>> 
>> An exercise in using the Parser-Combinator idea in C. Comments welcome.
>> 
>> $ make pc && ./pc
>> cc     pc.c   -o pc
>> H?
>> h?
>> e?
>> l?
>> l?
>> o?
>
> Developed further on the postscript side, but no idea
> how to translate to C. Too lispy, perhaps.

I was going to comment but I had no helpful suggestions on first
reading.  I could not see how what you were doing related to combinators
but then I suppose that was the question -- how to do it in C.

C lacks the key components to write a parser in that style, so there
would be so much supporting gubbins that I doubt it would be worth it.
Your post made me want to have a go, but never got round to it.

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#111552

On Monday, June 5, 2017 at 6:46:43 AM UTC-5, Ben Bacarisse wrote:
> luser droog <luser.droog@gmail.com> writes:
> 
> > On Tuesday, May 30, 2017 at 2:35:08 AM UTC-5, luser droog wrote:
> >> cf. https://en.wikipedia.org/wiki/Parser_combinator
> >> & https://groups.google.com/d/topic/comp.lang.postscript/KiEFeJROOcM/discussion
> >> 
> >> An exercise in using the Parser-Combinator idea in C. Comments welcome.
> >> 
> >> $ make pc && ./pc
> >> cc     pc.c   -o pc
> >> H?
> >> h?
> >> e?
> >> l?
> >> l?
> >> o?
> >
> > Developed further on the postscript side, but no idea
> > how to translate to C. Too lispy, perhaps.
> 
> I was going to comment but I had no helpful suggestions on first
> reading.  I could not see how what you were doing related to combinators
> but then I suppose that was the question -- how to do it in C.
> 
> C lacks the key components to write a parser in that style, so there
> would be so much supporting gubbins that I doubt it would be worth it.
> Your post made me want to have a go, but never got round to it.
> 

I think I agree. To to this with C, I think it'll need to be 2 stages.
Generating C-code from the first stage, then compiling and executing
it in the second stage. 

That, or more of this sort of 'simulation' style. Maybe the generator
should be a different language, and just produce a parser in C code.

-- 
good word: gubbins

[toc] | [prev] | [next] | [standalone]

#111541

On 30/05/2017 08:34, luser droog wrote:
> cf. https://en.wikipedia.org/wiki/Parser_combinator
> & https://groups.google.com/d/topic/comp.lang.postscript/KiEFeJROOcM/discussion
> 
> An exercise in using the Parser-Combinator idea in C. Comments welcome.

> enum parser_type { TERM, ALT, SEQ };
> typedef struct parser *parser;
> struct parser {
>      enum parser_type type;
>      int c;
>      parser a, b;
> };
> 
> 
> parser term( int c );

> int
> parse( char *input, parser p ){
>      switch( p->type ){
>      case TERM:  return parse_term( input, p );
>      case ALT:   return parse_alt( input, p );
>      case SEQ:   return parse_seq( input, p );
>      }
> }

No idea about parser-combinators. But the pattern above calls out for a 
function pointer in place of p->type, then it becomes:

   return (p->type)(input, p);

However, gcc couldn't optimise that as well so was slower (when you 
parse the same thing at least 10M times - without the print %c? line).

(Another issue, when you convert to a language that is case-insensitive, 
is that TERM and term clash. But that's the usual C thing. Even looking 
at the C, there was a bit of confusion as to what 'parser' was, as it's 
not just a typedef version of 'struct parser' but a pointer to it.)

-- 
bartc

[toc] | [prev] | [next] | [standalone]

#111553

On Monday, June 5, 2017 at 9:06:08 AM UTC-5, Bart wrote:
> On 30/05/2017 08:34, luser droog wrote:
> > cf. https://en.wikipedia.org/wiki/Parser_combinator
> > & https://groups.google.com/d/topic/comp.lang.postscript/KiEFeJROOcM/discussion
> > 
> > An exercise in using the Parser-Combinator idea in C. Comments welcome.
> 
> > enum parser_type { TERM, ALT, SEQ };
> > typedef struct parser *parser;
> > struct parser {
> >      enum parser_type type;
> >      int c;
> >      parser a, b;
> > };
> > 
> > 
> > parser term( int c );
> 
> > int
> > parse( char *input, parser p ){
> >      switch( p->type ){
> >      case TERM:  return parse_term( input, p );
> >      case ALT:   return parse_alt( input, p );
> >      case SEQ:   return parse_seq( input, p );
> >      }
> > }
> 
> No idea about parser-combinators. But the pattern above calls out for a 
> function pointer in place of p->type, then it becomes:
> 
>    return (p->type)(input, p);
> 
> However, gcc couldn't optimise that as well so was slower (when you 
> parse the same thing at least 10M times - without the print %c? line).

Thanks. I should have thought of that. The function pointer is nicer,
with less code. Not too concerned about efficiency at this point.
 
> (Another issue, when you convert to a language that is case-insensitive, 
> is that TERM and term clash. But that's the usual C thing. Even looking 
> at the C, there was a bit of confusion as to what 'parser' was, as it's 
> not just a typedef version of 'struct parser' but a pointer to it.)
> 

I'll apologize for the typedef'd pointer, but I'm not likely to stop.
'struct parser' is a struct, and 'parser' is the pointer to it. I know
many programmers do not like this. But I do. I try not to "hide it" by
showing the typedef right at the top.

[toc] | [prev] | [next] | [standalone]

#111674

On Monday, June 5, 2017 at 10:00:36 AM UTC-5, luser droog wrote:
> On Monday, June 5, 2017 at 9:06:08 AM UTC-5, Bart wrote:
> > On 30/05/2017 08:34, luser droog wrote:
> > > cf. https://en.wikipedia.org/wiki/Parser_combinator
> > > & https://groups.google.com/d/topic/comp.lang.postscript/KiEFeJROOcM/discussion
> > > 
> > > An exercise in using the Parser-Combinator idea in C. Comments welcome.

> > No idea about parser-combinators. But the pattern above calls out for a 
> > function pointer in place of p->type, then it becomes:
> > 
> >    return (p->type)(input, p);
> > 
> > However, gcc couldn't optimise that as well so was slower (when you 
> > parse the same thing at least 10M times - without the print %c? line).
> 
> Thanks. I should have thought of that. The function pointer is nicer,
> with less code. Not too concerned about efficiency at this point.


Rewritten more tersely. Same functionality but it fits on one screen now.

Norah@laptop ~
$ cat pc2.c
#include <stdio.h>
#include <stdlib.h>

typedef struct parser *parser;
typedef int (*parser_action)( parser p, char *input );

struct parser {
    parser_action test;
    int c;
    parser a,b;
};


int parse( parser p, char *input ){
    return p->test( p, input );
}


int parse_term( parser p, char *input ){
    printf( "%c", p->c );
    return  *input == p->c;
}

int parse_alt( parser p, char *input ){
  //    printf(" ALT\n");
    return  parse( p->a, input ) || parse( p->b, input );
}

int parse_seq( parser p, char *input ){
  //    printf(" SEQ\n");
    return  parse( p->a, input )  ?  parse( p->b, input + 1 )  :  0;
}


parser term( int c ){
    parser p = malloc( sizeof *p );
    return  p? (*p = (struct parser){ .test = parse_term, .c = c }), p : p;
}

parser alt( parser a, parser b ){
    parser p = malloc( sizeof *p );
    return  p? (*p = (struct parser){ .test = parse_alt, .a = a, .b = b }), p : p;
}

parser seq( parser a, parser b){
    parser p = malloc( sizeof *p );
    return  p? (*p = (struct parser){ .test = parse_seq, .a = a, .b = b }), p : p;
}



int main( void ){
    parser p = seq( alt( term( 'H' ), term( 'h' ) ),
                    seq( term( 'e' ),
                         seq( term( 'l' ),
                              seq( term( 'l' ),
                                   term( 'o' ) ) ) ) );
    printf("%d\n", p->test( p, "hello"  ) );
    printf("%d\n", p->test( p, "Hello"  ) );
    printf("%d\n", p->test( p, "YaMaMa" ) );
    return 0;
}


Norah@laptop ~
$ make pc2 CFLAGS+='-std=c99 -g'
cc -std=c99 -g    pc2.c   -o pc2

Norah@laptop ~
$ ./pc2
Hhello1
Hello1
Hh0

[toc] | [prev] | [next] | [standalone]

#111675

On Tuesday, June 6, 2017 at 11:55:02 PM UTC-5, luser droog wrote:
> On Monday, June 5, 2017 at 10:00:36 AM UTC-5, luser droog wrote:
> > On Monday, June 5, 2017 at 9:06:08 AM UTC-5, Bart wrote:
> > > On 30/05/2017 08:34, luser droog wrote:
> > > > cf. https://en.wikipedia.org/wiki/Parser_combinator
> > > > & https://groups.google.com/d/topic/comp.lang.postscript/KiEFeJROOcM/discussion
> > > > 
> > > > An exercise in using the Parser-Combinator idea in C. Comments welcome.
> 
> > > No idea about parser-combinators. But the pattern above calls out for a 
> > > function pointer in place of p->type, then it becomes:
> > > 
> > >    return (p->type)(input, p);
> > > 
> > > However, gcc couldn't optimise that as well so was slower (when you 
> > > parse the same thing at least 10M times - without the print %c? line).
> > 
> > Thanks. I should have thought of that. The function pointer is nicer,
> > with less code. Not too concerned about efficiency at this point.
> 
> 
> Rewritten more tersely. Same functionality but it fits on one screen now.
> 

Slightly improved. New convenience function 'char_class( char * )'.
Norah is my computer's name.

Norah@laptop ~
$ cat pc2.c
#include <stdio.h>
#include <stdlib.h>

typedef struct parser *parser;
typedef int (*parser_handler)( parser p, char *input );

struct parser {
    parser_handler test;
    parser a, b;
    int c;
};

int debug_parse_term = 1;


int parse( parser p, char *input ){    return p->test( p, input ); }

int parse_fail   ( parser p, char *input ){    return  0; }
int parse_succeed( parser p, char *input ){    return  1; }

int parse_term( parser p, char *input ){
    return  debug_parse_term && printf( "%c", p->c ),
            *input == p->c;
}
int parse_alt ( parser p, char *input ){
    return  parse( p->a, input ) || parse( p->b, input );
}
int parse_seq ( parser p, char *input ){
    return  parse( p->a, input )  ?  parse( p->b, input + 1 )  :  0;
}


parser new_parser( struct parser ps ){
    parser p = malloc( sizeof *p );
    return  p  ?  ( *p = ps ), p  :  p;
}

parser fail   (){
    return  new_parser( (struct parser){ .test = parse_fail } );
}
parser succeed(){
    return  new_parser( (struct parser){ .test = parse_succeed } );
}

parser term( int c ){
    return  new_parser( (struct parser){ .test = parse_term, .c = c } );
}
parser alt ( parser a, parser b ){
    return  new_parser( (struct parser){ .test = parse_alt, .a = a, .b = b } );
}
parser seq ( parser a, parser b ){
    return  new_parser( (struct parser){ .test = parse_seq, .a = a, .b = b } );
}

parser char_class( char *str ){
    return *str ? alt( term( *str ), char_class( str + 1 ) )
                : fail();
}


int main( void ){
    parser p = seq( char_class( "Hh" ),
                    seq( term( 'e' ),
                         seq( term( 'l' ),
                              seq( term( 'l' ),
                                   term( 'o' ) ) ) ) );
    printf("%d\n", parse( p, "hello"  ) );
    printf("%d\n", parse( p, "Hello"  ) );
    printf("%d\n", parse( p, "YaMaMa" ) );
    return 0;
}


Norah@laptop ~
$ make pc2 CFLAGS+='-std=c99 -g'
cc -std=c99 -g    pc2.c   -o pc2

Norah@laptop ~
$ ./pc2
Hhello1
Hello1
Hh0

[toc] | [prev] | [next] | [standalone]

#111678

On Wednesday, June 7, 2017 at 12:32:20 AM UTC-5, luser droog wrote:
> On Tuesday, June 6, 2017 at 11:55:02 PM UTC-5, luser droog wrote:
> > On Monday, June 5, 2017 at 10:00:36 AM UTC-5, luser droog wrote:
> > > On Monday, June 5, 2017 at 9:06:08 AM UTC-5, Bart wrote:
> > > > On 30/05/2017 08:34, luser droog wrote:
> > > > > cf. https://en.wikipedia.org/wiki/Parser_combinator
> > > > > & https://groups.google.com/d/topic/comp.lang.postscript/KiEFeJROOcM/discussion
> > > > > 
> > > > > An exercise in using the Parser-Combinator idea in C. Comments welcome.
> > 
> > > > No idea about parser-combinators. But the pattern above calls out for a 
> > > > function pointer in place of p->type, then it becomes:
> > > > 
> > > >    return (p->type)(input, p);
> > > > 
> > > > However, gcc couldn't optimise that as well so was slower (when you 
> > > > parse the same thing at least 10M times - without the print %c? line).
> > > 
> > > Thanks. I should have thought of that. The function pointer is nicer,
> > > with less code. Not too concerned about efficiency at this point.
> > 
> > 
> > Rewritten more tersely. Same functionality but it fits on one screen now.
> > 
> 
> Slightly improved. New convenience function 'char_class( char * )'.
> Norah is my computer's name.
> 

Even better. Usage is now pretty simple.

I thought I would need variadic functions and/or macros. I even
copied and #included ppnarg.h. But then string() just wrote itself.
I imagine it could be done with a macro that builds a compound 
literal array which can then be counted and a function can work
with a pointer and a count pretty easily.

Next feature it needs is attaching callbacks or returning substrings
or something. Building up to something that can substitute for simple 
scanf() uses, perhaps in conjunction with strtol() and strtod().

Perhaps, after very much development, it could even serve as an extensible
scanf() analogous to Tim Rentsch's printx(). maybe? possibly?  ... putting
down the pipe now.... :)


Norah@laptop ~
$ make pc2 CFLAGS+='-std=c99 -g'
cc -std=c99 -g    pc2.c   -o pc2

Norah@laptop ~
$ ./pc2
Hhello1
Hello1
Hh0

Norah@laptop ~
$ cat pc2.c
#include <stdio.h>
#include <stdlib.h>

typedef struct parser *parser;
typedef int (*parser_handler)( parser p, char *input );

struct parser {
    parser_handler test;
    parser a, b;
    int c;
};

int debug_parse_term = 1;


int parse( parser p, char *input ){    return p->test( p, input ); }

int parse_fail   ( parser p, char *input ){    return  0; }
int parse_succeed( parser p, char *input ){    return  1; }

int parse_term( parser p, char *input ){
    return  debug_parse_term && printf( "%c", p->c ),
            *input == p->c;
}
int parse_alt ( parser p, char *input ){
    return  parse( p->a, input ) || parse( p->b, input );
}
int parse_seq ( parser p, char *input ){
    return  parse( p->a, input )  ?  parse( p->b, input + 1 )  :  0;
}


parser new_parser( struct parser ps ){
    parser p = malloc( sizeof *p );
    return  p  ?  ( *p = ps ), p  :  p;
}

parser fail   (){    return  new_parser( (struct parser){ .test = parse_fail } ); }
parser succeed(){    return  new_parser( (struct parser){ .test = parse_succeed } ); }

parser term( int c ){
    return  new_parser( (struct parser){ .test = parse_term, .c = c } );
}
parser alternate( parser a, parser b ){
    return  new_parser( (struct parser){ .test = parse_alt, .a = a, .b = b } );
}
parser sequence ( parser a, parser b ){
    return  new_parser( (struct parser){ .test = parse_seq, .a = a, .b = b } );
}


parser char_class( char *str ){
    return  *str  ?  alternate( term( *str ), char_class( str + 1 ) )
                  :  fail();
}

parser string( char *str ){
    return  *str  ?  sequence( term(*str), string( str + 1 ) )
                  :  succeed();
}


int main( void ){
    parser p = sequence( char_class( "Hh" ), string( "ello" ) );
    
    printf("%d\n", parse( p, "hello"  ) );
    printf("%d\n", parse( p, "Hello"  ) );
    printf("%d\n", parse( p, "YaMaMa" ) );
    return 0;
}

[toc] | [prev] | [next] | [standalone]

#111682

On Wednesday, June 7, 2017 at 1:03:38 AM UTC-5, luser droog wrote:
> On Wednesday, June 7, 2017 at 12:32:20 AM UTC-5, luser droog wrote:
> > On Tuesday, June 6, 2017 at 11:55:02 PM UTC-5, luser droog wrote:
> > > On Monday, June 5, 2017 at 10:00:36 AM UTC-5, luser droog wrote:
> > > > On Monday, June 5, 2017 at 9:06:08 AM UTC-5, Bart wrote:
> > > > > On 30/05/2017 08:34, luser droog wrote:
> > > > > > cf. https://en.wikipedia.org/wiki/Parser_combinator
> > > > > > & https://groups.google.com/d/topic/comp.lang.postscript/KiEFeJROOcM/discussion
> > > > > > 
> > > > > > An exercise in using the Parser-Combinator idea in C. Comments welcome.
> > > 
 
> Even better. Usage is now pretty simple.
> 
> I thought I would need variadic functions and/or macros. I even
> copied and #included ppnarg.h. But then string() just wrote itself.
> I imagine it could be done with a macro that builds a compound 
> literal array which can then be counted and a function can work
> with a pointer and a count pretty easily.
> 
> Next feature it needs is attaching callbacks or returning substrings
> or something. Building up to something that can substitute for simple 
> scanf() uses, perhaps in conjunction with strtol() and strtod().
> 

Now this part I've actually implemented over in the
postscript thread. I won't bore you guys with the 
gory details, but just the usage section, and then
the output which shows a dump of the number parser.
It generates code. The parser is built dynamically
like it was lisp or something. So I keep bragging 
to my rubber ducks...

The usage reads almost like a grammar already, and
has the side effect of parsing the input according
to that description. And optionally, it could convert
the substrings with cvi (ps equivalent of strtol) 
or cvn (converts a string to an interned name object,
ie. an atom or identifier).

Here one defines a parser-action pair in a style similar
to defining a regular postscript function which looks like

/funcname {
    code for function
} def

A parser-action looks like

/parsername  parser-description
{
    parser action code
} def

Then the parser may be invoked or called upon a string and index

  (my string to be parsed) 0 parsername

or to peek at its code and then execute, I sometimes do this

  (my string to be parsed) 0 //parsername == exec

And I'm probably boring anyone still here at this point, so.
Paste.


/digit   << (0) (1) (2) (3) (4) (5) (6) (7) (8) (9) >> def
/alpha   << (a) (b) (c) (d) (e) (f) (g) (h) (i) (j) (k) (l) (m)
            (n) (o) (p) (q) (r) (s) (t) (u) (v) (w) (x) (y) (z)
            (A) (B) (C) (D) (E) (F) (G) (H) (I) (J) (K) (L) (M)
            (N) (O) (P) (Q) (R) (S) (T) (U) (V) (W) (X) (Y) (Z) >> def
/medial <<//digit //alpha>> def
/opt-space <<( ) true>>
{       % (string) i (str)# (str)
    _ 
} build-parser-action def

/number [ %//opt-space
          //digit << //digit true >> ]
{       % (string) i (str) 
    %cvi = / =          % (string) i str#
    4 1 roll
} build-parser-action def

//number ==

/id     [ %//opt-space
          //alpha //alpha //alpha ]
{
    %cvn = / =
    4 1 roll
} build-parser-action def


(22Foo47)    [ zy 0  opt-space number  opt-space id  opt-space number  _ _ ] ==
( 22 Foo47)  [ zy 0  opt-space number  opt-space id  opt-space number  _ _ ] ==
(22 Foo 47 ) [ zy 0  opt-space number  opt-space id  opt-space number  _ _ ] ==

quit




Norah@laptop ~
$ gsnd -q pc2.ps
{++ ++ ++ ++ ++ ++ ++ ++ ++ ++ ++ ++ (0) test 0= {_ (1) test} {ret} ? 0= {_ (2) test} {ret} ? 0= {_ (3) test} {ret} ? 0= {_ (4) test} {ret} ? 0= {_ (5) test} {ret} ? 0= {_ (6) test} {ret} ? 0= {_ (7) test} {ret} ? 0= {_ (8) test} {ret} ? 0= {_ (9) test} {ret} ? 0^ {mov ++ ++ ++ ++ ++ ++ ++ ++ ++ ++ (0) test 0= {_ (1) test} {ret} ? 0= {_ (2) test} {ret} ? 0= {_ (3) test} {ret} ? 0= {_ (4) test} {ret} ? 0= {_ (5) test} {ret} ? 0= {_ (6) test} {ret} ? 0= {_ (7) test} {ret} ? 0= {_ (8) test} {ret} ? 0= {_ (9) test} {ret} ? 0= {_ empty} {ret} ?} {fail} ? 0^ {{} @ ... z # zy 4 1 roll add y # y sub ... 0} {/parser-fail == ps} ?}
[(22) (Foo) (47)]
[(22) (Foo) (47)]
[(22) (Foo) (47)]

Norah@laptop ~
$ 

[toc] | [prev] | [next] | [standalone]

#111751

luser droog <luser.droog@gmail.com> writes:
<snip>
> #include <stdio.h>
> #include <stdlib.h>
>
> typedef struct parser *parser;
> typedef int (*parser_handler)( parser p, char *input );
>
> struct parser {
>     parser_handler test;
>     parser a, b;
>     int c;
> };
>
> int debug_parse_term = 1;
>
>
> int parse( parser p, char *input ){    return p->test( p, input ); }
>
> int parse_fail   ( parser p, char *input ){    return  0; }
> int parse_succeed( parser p, char *input ){    return  1; }
>
> int parse_term( parser p, char *input ){
>     return  debug_parse_term && printf( "%c", p->c ),
>             *input == p->c;
> }
> int parse_alt ( parser p, char *input ){
>     return  parse( p->a, input ) || parse( p->b, input );
> }
> int parse_seq ( parser p, char *input ){
>     return  parse( p->a, input )  ?  parse( p->b, input + 1 )  :  0;
> }
>
>
> parser new_parser( struct parser ps ){
>     parser p = malloc( sizeof *p );
>     return  p  ?  ( *p = ps ), p  :  p;
> }
>
> parser fail   (){    return  new_parser( (struct parser){ .test = parse_fail } ); }
> parser succeed(){    return  new_parser( (struct parser){ .test = parse_succeed } ); }
>
> parser term( int c ){
>     return  new_parser( (struct parser){ .test = parse_term, .c = c } );
> }
> parser alternate( parser a, parser b ){
>     return  new_parser( (struct parser){ .test = parse_alt, .a = a, .b = b } );
> }
> parser sequence ( parser a, parser b ){
>     return  new_parser( (struct parser){ .test = parse_seq, .a = a, .b = b } );
> }
>
>
> parser char_class( char *str ){
>     return  *str  ?  alternate( term( *str ), char_class( str + 1 ) )
>                   :  fail();
> }
>
> parser string( char *str ){
>     return  *str  ?  sequence( term(*str), string( str + 1 ) )
>                   :  succeed();
> }
>
>
> int main( void ){
>     parser p = sequence( char_class( "Hh" ), string( "ello" ) );
>     
>     printf("%d\n", parse( p, "hello"  ) );
>     printf("%d\n", parse( p, "Hello"  ) );
>     printf("%d\n", parse( p, "YaMaMa" ) );

Try:

        parser p = sequence( string( "ab" ), term( 'c' ) );
        printf("%d\n", parse( p, "abc" ) );

>     return 0;
> }

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#111776

On 2017-06-07, Ben Bacarisse <ben.usenet@bsb.me.uk> wrote:
> luser droog <luser.droog@gmail.com> writes:
><snip>
>> #include <stdio.h>
>> #include <stdlib.h>
>>
>> typedef struct parser *parser;
>> typedef int (*parser_handler)( parser p, char *input );
>>
>> struct parser {
>>     parser_handler test;
>>     parser a, b;
>>     int c;
>> };
>>
>> int debug_parse_term = 1;
>>
>>
>> int parse( parser p, char *input ){    return p->test( p, input ); }
>>
>> int parse_fail   ( parser p, char *input ){    return  0; }
>> int parse_succeed( parser p, char *input ){    return  1; }
>>
>> int parse_term( parser p, char *input ){
>>     return  debug_parse_term && printf( "%c", p->c ),
>>             *input == p->c;
>> }
>> int parse_alt ( parser p, char *input ){
>>     return  parse( p->a, input ) || parse( p->b, input );
>> }
>> int parse_seq ( parser p, char *input ){
>>     return  parse( p->a, input )  ?  parse( p->b, input + 1 )  :  0;
>> }
>>
>>
>> parser new_parser( struct parser ps ){
>>     parser p = malloc( sizeof *p );
>>     return  p  ?  ( *p = ps ), p  :  p;
>> }
>>
>> parser fail   (){    return  new_parser( (struct parser){ .test = parse_fail } ); }
>> parser succeed(){    return  new_parser( (struct parser){ .test = parse_succeed } ); }
>>
>> parser term( int c ){
>>     return  new_parser( (struct parser){ .test = parse_term, .c = c } );
>> }
>> parser alternate( parser a, parser b ){
>>     return  new_parser( (struct parser){ .test = parse_alt, .a = a, .b = b } );
>> }
>> parser sequence ( parser a, parser b ){
>>     return  new_parser( (struct parser){ .test = parse_seq, .a = a, .b = b } );
>> }
>>
>>
>> parser char_class( char *str ){
>>     return  *str  ?  alternate( term( *str ), char_class( str + 1 ) )
>>                   :  fail();
>> }
>>
>> parser string( char *str ){
>>     return  *str  ?  sequence( term(*str), string( str + 1 ) )
>>                   :  succeed();
>> }
>>
>>
>> int main( void ){
>>     parser p = sequence( char_class( "Hh" ), string( "ello" ) );
>>     
>>     printf("%d\n", parse( p, "hello"  ) );
>>     printf("%d\n", parse( p, "Hello"  ) );
>>     printf("%d\n", parse( p, "YaMaMa" ) );
>
> Try:
>
>         parser p = sequence( string( "ab" ), term( 'c' ) );
>         printf("%d\n", parse( p, "abc" ) );
>
>>     return 0;
>> }
>
Heh, Haskell version:
data Parser = Term Char | Alt Parser Parser | Seq Parser Parser

parse (Term c) (input:rest) = (c == input,rest)
parse (Alt a b) input = let a' = parse a input
                            b' = parse b input
                        in if fst a' then a' else b'
parse (Seq a b) input = let a' = parse a input
                            b' = parse b (snd a')
                        in if fst a' then b' else a'

string (x:[]) = Term x
string (x:xs) = Seq (Term x) (string xs)

char_class (x:[]) = Term x
char_class (x:xs) = Alt (Term x) (char_class xs)

main = do
    let p = Seq (Alt (Term 'H') (Term 'h'))
                (Seq (Term 'e') (Seq (Term 'l') (Seq (Term 'l') (Term 'o'))))
    let q = Seq (char_class "Hh") (string "ello")
    let r = Seq (string "ab") (Term 'c')
    print $ parse p "helloh"
    print $ parse p "Hello"
    print $ parse p "YaMaMa"
    print $ parse q "hello"
    print $ parse q "Hello"
    print $ parse q "YaMaMa"
    print $ parse r "abc"         

[bmaxa@maxa-pc haskell]$ ./combinator
(True,"h")
(True,"")
(False,"aMaMa")
(True,"")
(True,"")
(False,"aMaMa")
(True,"")

-- 
press any key to continue or any other to quit...

[toc] | [prev] | [next] | [standalone]

#111784

On Wednesday, June 7, 2017 at 2:57:43 PM UTC-5, Ben Bacarisse wrote:
> luser droog <luser.droog@gmail.com> writes:
> <snip>
> Try:
> 
>         parser p = sequence( string( "ab" ), term( 'c' ) );
>         printf("%d\n", parse( p, "abc" ) );
> 
> >     return 0;
> > }
> 

Thanks. That's a bug. I think I've fixed it by change the return
values from 0/1 to -1/num-chars-matched. Then parse_sequence()
can add the length from the left piece before trying the right
piece.

Also added quantifiers and more testing.

Norah@laptop ~
$ cat pc2.c
#include <stdio.h>
#include <stdlib.h>

typedef struct parser *parser;
typedef int (*parser_handler)( parser p, char *input );

struct parser {
    parser_handler test;
    parser a, b;
    int c;
};

int debug_parse_term = 1;


int parse( parser p, char *input ){    return p->test( p, input ); }

int parse_fail   ( parser p, char *input ){    return  -1; }
int parse_succeed( parser p, char *input ){    return  0; }

int parse_term( parser p, char *input ){
    return  debug_parse_term && printf( "%c%c? ", p->c, *input ),
            *input == p->c  ?  1  :  -1;
}
int parse_alternate ( parser p, char *input ){
    int i;
    return  ( i = parse( p->a, input ) ) >= 0  ?  i
                                               :  parse( p->b, input );
}
int parse_sequence ( parser p, char *input ){
    int i;
    return  ( i = parse( p->a, input ) ) >= 0  ?  i + parse( p->b, input + i )
                                               :  -1;
}


parser new_parser( struct parser ps ){
    parser p = malloc( sizeof *p );
    return  p  ?  ( *p = ps ), p  :  p;
}

parser fails   (){    return  new_parser( (struct parser){ .test = parse_fail } ); }
parser succeeds(){    return  new_parser( (struct parser){ .test = parse_succeed } ); }

parser term( int c ){
    return  new_parser( (struct parser){ .test = parse_term, .c = c } );
}
parser alternate2( parser a, parser b ){
    return  new_parser( (struct parser){ .test = parse_alternate, .a = a, .b = b } );
}
parser sequence2 ( parser a, parser b ){
    return  new_parser( (struct parser){ .test = parse_sequence, .a = a, .b = b } );
}

parser many( parser a ){
    parser q = new_parser( (struct parser){ .test = parse_sequence, .a = a } );
    q->b = q;
    return  new_parser( (struct parser){ .test = parse_alternate, .a = q, .b = succeeds() } );
}

parser some( parser a ){
    parser q = new_parser( (struct parser){ .test = parse_sequence, .a = a } );
    q->b = q;
    return  new_parser( (struct parser){ .test = parse_alternate, .a = a, .b = q } );
}

parser n_or_more( int n, parser a ){
    return  n == 0  ?  many( a )  :
            n == 1  ?  some( a )  :
                       sequence2( a, n_or_more( n - 1, a ) );
}

parser char_class( char *str ){
    return  *str  ?  alternate2( term( *str ), char_class( str + 1 ) )
                  :  fails();
}

parser string( char *str ){
    return  *str  ?  sequence2( term(*str), string( str + 1 ) )
                  :  succeeds();
}

parser sequencen( int n, parser *pp ){
    return  n  ?  sequence2( *pp, sequencen( n - 1, pp + 1 ) )
               :  succeeds();
}

parser alternaten( int n, parser *pp){
    return  n  ?  alternate2( *pp, alternaten( n - 1, pp + 1 ) )
               :  fails();
}


int test( parser p, char *str ){
    printf( "%s:", str );
    fflush(0);
    return printf( "%d\n", parse( p, str ) );
}

int main( void ){
  parser p = sequencen( 7, (parser[]){
      char_class( "Hhj" ), string( "ello " ),
        char_class( "Wwm" ), string( "o" ), char_class( "ru" ), string( "ld" ),
        char_class("!.") });
    
    test( p, "hello World." );
    test( p, "jello mould!" );
    test( p, "YaMaMa" );

    parser q = many( term( 'x' ) );
    test( q, "y" );
    test( q, "xy" );
    test( q, "xxy" );
    
    parser r = some( term( 'x' ) );
    test( r, "y" );
    test( r, "xy" );
    test( r, "xxy" );

    parser s = n_or_more( 3, term( 'a' ) );
    test( s, "aa" );
    test( s, "aaa" );
    test( s, "aaaa" );
    test( s, "aaaaa" );
                         
    return 0;
}


Norah@laptop ~
$ make pc2 CFLAGS+='-std=c99 -g'
cc -std=c99 -g    pc2.c   -o pc2

Norah@laptop ~
$ ./pc2
hello World.:Hh? hh? ee? ll? ll? oo?   ? WW? oo? rr? ll? dd? !.? ..? 12
jello mould!:Hj? hj? jj? ee? ll? ll? oo?   ? Wm? wm? mm? oo? ru? uu? ll? dd? !!? 12
YaMaMa:HY? hY? jY? -1
y:xy? 0
xy:xx? xy? 0
xxy:xx? xx? xy? 1
y:xy? xy? -1
xy:xx? 1
xxy:xx? 1
aa:aa? aa? a? a? 1
aaa:aa? aa? aa? 3
aaaa:aa? aa? aa? 3
aaaaa:aa? aa? aa? 3

[toc] | [prev] | [next] | [standalone]

#111955

On Wednesday, June 7, 2017 at 10:18:08 PM UTC-5, luser droog wrote:
> On Wednesday, June 7, 2017 at 2:57:43 PM UTC-5, Ben Bacarisse wrote:
> > luser droog <luser.droog@gmail.com> writes:
> > <snip>
> > Try:
> > 
> >         parser p = sequence( string( "ab" ), term( 'c' ) );
> >         printf("%d\n", parse( p, "abc" ) );
> > 
> > >     return 0;
> > > }
> > 
> 
> Thanks. That's a bug. I think I've fixed it by change the return
> values from 0/1 to -1/num-chars-matched. Then parse_sequence()
> can add the length from the left piece before trying the right
> piece.
> 
> Also added quantifiers and more testing.

This should be my last post so I can focus on other stuff, but I 
fixed the quantifiers. Didn't want to leave the thread dangling
with broken code.

The idea for the Kleene star quantifier combinator is that it's
a sequence

  [ x ]

where x is the input parser. But it could be zero, so wrap the 
sequence in an alternation with succeeds.

  << [ x ]  true >>

Then stitch it up into a loop by putting the alternate inside
the sequence.

  y = << [ x y ]  true >>

This will match 0 or more of x and return the length matched.



Norah@laptop ~
$ cat pc2.c
#include <stdio.h>
#include <stdlib.h>

typedef struct parser *parser;
typedef int (*parser_handler)( parser p, char *input );

struct parser {
    parser_handler test;
    parser a, b;
    int c;
};

int debug_parse_term = 1;


int parse( parser p, char *input ){    return p->test( p, input ); }

int parse_fail   ( parser p, char *input ){    return  -1; }
int parse_succeed( parser p, char *input ){    return  0; }

int parse_term( parser p, char *input ){
    return  debug_parse_term && printf( "%c%c? ", p->c, *input ),
            *input == p->c  ?  1  :  -1;
}
int parse_alternate ( parser p, char *input ){
    int i;
    return  ( i = parse( p->a, input ) ) >= 0  ?  i
                                               :  parse( p->b, input );
}
int parse_sequence ( parser p, char *input ){
  int i,j;
    return  ( i = parse( p->a, input     ) ) >= 0  ?
            ( j = parse( p->b, input + i ) ) >= 0  ?  i + j
                                                   :  -1
                                                   :  -1;
}


parser new_parser( struct parser ps ){
    parser p = malloc( sizeof *p );
    return  p  ?  ( *p = ps ), p  :  p;
}

parser fails   (){    return  new_parser( (struct parser){ .test = parse_fail } ); }
parser succeeds(){    return  new_parser( (struct parser){ .test = parse_succeed } ); }

parser term( int c ){
    return  new_parser( (struct parser){ .test = parse_term, .c = c } );
}
parser alternate2( parser a, parser b ){
    return  new_parser( (struct parser){ .test = parse_alternate, .a = a, .b = b } );
}
parser sequence2 ( parser a, parser b ){
    return  new_parser( (struct parser){ .test = parse_sequence, .a = a, .b = b } );
}

parser many( parser a ){
    parser q = new_parser( (struct parser){ .test = parse_sequence,  .a = a } );
    parser r = new_parser( (struct parser){ .test = parse_alternate, .a = q, .b = succeeds() } );
    q->b = r;
    return r;
}

parser some( parser a ){
    parser q = new_parser( (struct parser){ .test = parse_sequence,  .a = a } );
    parser r = new_parser( (struct parser){ .test = parse_alternate, .a = q, .b = succeeds() } );
    q->b = r;
    return q;
}

parser n_or_more( int n, parser a ){
    return  n == 0  ?  many( a )  :
            n == 1  ?  some( a )  :
                       sequence2( a, n_or_more( n - 1, a ) );
}

parser char_class( char *str ){
    return  *str  ?  alternate2( term( *str ), char_class( str + 1 ) )
                  :  fails();
}

parser string( char *str ){
    return  *str  ?  sequence2( term(*str), string( str + 1 ) )
                  :  succeeds();
}

parser sequencen( int n, parser *pp ){
    return  n  ?  sequence2( *pp, sequencen( n - 1, pp + 1 ) )
               :  succeeds();
}

parser alternaten( int n, parser *pp){
    return  n  ?  alternate2( *pp, alternaten( n - 1, pp + 1 ) )
               :  fails();
}


int test( parser p, char *str ){
    printf( "%s:", str );
    fflush(0);
    return printf( "%d\n", parse( p, str ) );
}

int main( void ){
  parser p = sequencen( 7, (parser[]){
      char_class( "Hhj" ), string( "ello " ),
        char_class( "Wwm" ), string( "o" ), char_class( "ru" ), string( "ld" ),
        char_class("!.") });
    
    test( p, "hello World." );
    test( p, "jello mould!" );
    test( p, "YaMaMa" );

    parser q = many( term( 'x' ) );
    test( q, "y" );
    test( q, "xy" );
    test( q, "xxy" );
    
    parser r = some( term( 'x' ) );
    test( r, "y" );
    test( r, "xy" );
    test( r, "xxy" );

    parser s = n_or_more( 3, term( 'a' ) );
    test( s, "aa" );
    test( s, "aaa" );
    test( s, "aaaa" );
    test( s, "aaaaa" );

    parser number = some( char_class("0123456789") );
    test( number, "0 f" );
    test( number, "f 0" );
    test( number, "123f" );
    test( number, "9999aaa" );

    number = sequence2( many( term( ' ' ) ), number );
    test( number, " 0 f" );
    test( number, "  f 0" );
    test( number, "   123f" );
    test( number, "    9999aaa" );
    return 0;
}

Norah@laptop ~
$ make pc2 CFLAGS+='-std=c99 -g'
cc -std=c99 -g    pc2.c   -o pc2

Norah@laptop ~
$ ./pc2
hello World.:Hh? hh? ee? ll? ll? oo?   ? WW? oo? rr? ll? dd? !.? ..? 12
jello mould!:Hj? hj? jj? ee? ll? ll? oo?   ? Wm? wm? mm? oo? ru? uu? ll? dd? !!? 12
YaMaMa:HY? hY? jY? -1
y:xy? 0
xy:xx? xy? 1
xxy:xx? xx? xy? 2
y:xy? -1
xy:xx? xy? 1
xxy:xx? xx? xy? 2
aa:aa? aa? a? -1
aaa:aa? aa? aa? a? 3
aaaa:aa? aa? aa? aa? a? 4
aaaaa:aa? aa? aa? aa? aa? a? 5
0 f:00? 0 ? 1 ? 2 ? 3 ? 4 ? 5 ? 6 ? 7 ? 8 ? 9 ? 1
f 0:0f? 1f? 2f? 3f? 4f? 5f? 6f? 7f? 8f? 9f? -1
123f:01? 11? 02? 12? 22? 03? 13? 23? 33? 0f? 1f? 2f? 3f? 4f? 5f? 6f? 7f? 8f? 9f? 3
9999aaa:09? 19? 29? 39? 49? 59? 69? 79? 89? 99? 09? 19? 29? 39? 49? 59? 69? 79? 89? 99? 09? 19? 29? 39? 49? 59? 69? 79? 89? 99? 09? 19? 29? 39? 49? 59? 69? 79? 89? 99? 0a? 1a? 2a? 3a? 4a? 5a? 6a? 7a? 8a? 9a? 4
 0 f:  ?  0? 00? 0 ? 1 ? 2 ? 3 ? 4 ? 5 ? 6 ? 7 ? 8 ? 9 ? 2
  f 0:  ?   ?  f? 0f? 1f? 2f? 3f? 4f? 5f? 6f? 7f? 8f? 9f? -1
   123f:  ?   ?   ?  1? 01? 11? 02? 12? 22? 03? 13? 23? 33? 0f? 1f? 2f? 3f? 4f? 5f? 6f? 7f? 8f? 9f? 6
    9999aaa:  ?   ?   ?   ?  9? 09? 19? 29? 39? 49? 59? 69? 79? 89? 99? 09? 19? 29? 39? 49? 59? 69? 79? 89? 99? 09? 19? 29? 39? 49? 59? 69? 79? 89? 99? 09? 19? 29? 39? 49? 59? 69? 79? 89? 99? 0a? 1a? 2a? 3a? 4a? 5a? 6a? 7a? 8a? 9a? 8

Norah@laptop ~
$ 

[toc] | [prev] | [next] | [standalone]

#111966

luser droog <luser.droog@gmail.com> writes:
<snip>
> This should be my last post so I can focus on other stuff, but I 
> fixed the quantifiers. Didn't want to leave the thread dangling
> with broken code.
>
> The idea for the Kleene star quantifier combinator is that it's
> a sequence
>
>   [ x ]
>
> where x is the input parser. But it could be zero, so wrap the 
> sequence in an alternation with succeeds.
>
>   << [ x ]  true >>
>
> Then stitch it up into a loop by putting the alternate inside
> the sequence.
>
>   y = << [ x y ]  true >>
>
> This will match 0 or more of x and return the length matched.

What about:

  parser p = sequence2(some(term('x')), string("xy"));
  test(p, "xxxxy");

?

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#111989

On Sunday, June 11, 2017 at 6:11:19 AM UTC-5, Ben Bacarisse wrote:
> luser droog <luser.droog@gmail.com> writes:
> <snip>
> > This should be my last post so I can focus on other stuff, but I 
> > fixed the quantifiers. Didn't want to leave the thread dangling
> > with broken code.
> >
> > The idea for the Kleene star quantifier combinator is that it's
> > a sequence
> >
> >   [ x ]
> >
> > where x is the input parser. But it could be zero, so wrap the 
> > sequence in an alternation with succeeds.
> >
> >   << [ x ]  true >>
> >
> > Then stitch it up into a loop by putting the alternate inside
> > the sequence.
> >
> >   y = << [ x y ]  true >>
> >
> > This will match 0 or more of x and return the length matched.
> 
> What about:
> 
>   parser p = sequence2(some(term('x')), string("xy"));
>   test(p, "xxxxy");
> 
> ?
> 

Touché. That doesn't work. The quantifiers I've supplied are strictly
greedy. I'm not sure how much work it would be to add backtracking
or some other strategy that would allow that parser to match. But OTOH
I don't immediately see the utility of it. I think I'll explicitly not
support that sort of usage for the time being. 

The paper I'm following uses fp magic to return all possible matches
from a parser.    http://eprints.nottingham.ac.uk/221/1/parsing.pdf

[toc] | [prev] | [next] | [standalone]

#112003

luser droog <luser.droog@gmail.com> writes:

> On Sunday, June 11, 2017 at 6:11:19 AM UTC-5, Ben Bacarisse wrote:
>> luser droog <luser.droog@gmail.com> writes:
>> <snip>
>> > This should be my last post so I can focus on other stuff, but I 
>> > fixed the quantifiers. Didn't want to leave the thread dangling
>> > with broken code.
>> >
>> > The idea for the Kleene star quantifier combinator is that it's
>> > a sequence
>> >
>> >   [ x ]
>> >
>> > where x is the input parser. But it could be zero, so wrap the 
>> > sequence in an alternation with succeeds.
>> >
>> >   << [ x ]  true >>
>> >
>> > Then stitch it up into a loop by putting the alternate inside
>> > the sequence.
>> >
>> >   y = << [ x y ]  true >>
>> >
>> > This will match 0 or more of x and return the length matched.
>> 
>> What about:
>> 
>>   parser p = sequence2(some(term('x')), string("xy"));
>>   test(p, "xxxxy");
>> 
>> ?
>
> Touché. That doesn't work. The quantifiers I've supplied are strictly
> greedy.

Just a small point to avoid confusion: "strictly greedy" seems to be
your own term, at least I've not hear it before.  The normal Kleene star
operator is greedy in the usual meaning of the term -- that it matches
the longest possible string /that still allows the whole pattern to
match/.

<snip>
-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#112084

On Monday, June 12, 2017 at 6:25:10 AM UTC-5, Ben Bacarisse wrote:
> luser droog <luser.droog@gmail.com> writes:
> 
> > On Sunday, June 11, 2017 at 6:11:19 AM UTC-5, Ben Bacarisse wrote:
> >> luser droog <luser.droog@gmail.com> writes:
> >> <snip>
> >> > This should be my last post so I can focus on other stuff, but I 
> >> > fixed the quantifiers. Didn't want to leave the thread dangling
> >> > with broken code.
> >> >
> >> > The idea for the Kleene star quantifier combinator is that it's
> >> > a sequence
> >> >
> >> >   [ x ]
> >> >
> >> > where x is the input parser. But it could be zero, so wrap the 
> >> > sequence in an alternation with succeeds.
> >> >
> >> >   << [ x ]  true >>
> >> >
> >> > Then stitch it up into a loop by putting the alternate inside
> >> > the sequence.
> >> >
> >> >   y = << [ x y ]  true >>
> >> >
> >> > This will match 0 or more of x and return the length matched.
> >> 
> >> What about:
> >> 
> >>   parser p = sequence2(some(term('x')), string("xy"));
> >>   test(p, "xxxxy");
> >> 
> >> ?
> >
> > Touché. That doesn't work. The quantifiers I've supplied are strictly
> > greedy.
> 
> Just a small point to avoid confusion: "strictly greedy" seems to be
> your own term, at least I've not hear it before.  The normal Kleene star
> operator is greedy in the usual meaning of the term -- that it matches
> the longest possible string /that still allows the whole pattern to
> match/.
> 

Thanks. A brief search suggests at least one person calls
this a "possessive" Kleene star.

https://cs.stackexchange.com/questions/40712/possessive-kleene-star-operator

[toc] | [prev] | [next] | [standalone]

#112104

On Monday, June 12, 2017 at 3:53:42 PM UTC-5, luser droog wrote:
> On Monday, June 12, 2017 at 6:25:10 AM UTC-5, Ben Bacarisse wrote:
> > luser droog <luser.droog@gmail.com> writes:
> > 
> > > On Sunday, June 11, 2017 at 6:11:19 AM UTC-5, Ben Bacarisse wrote:
> > >> luser droog <luser.droog@gmail.com> writes:
> > >> <snip>
> > >> > This should be my last post so I can focus on other stuff, but I 
> > >> > fixed the quantifiers. Didn't want to leave the thread dangling
> > >> > with broken code.
> > >> >
> > >> > The idea for the Kleene star quantifier combinator is that it's
> > >> > a sequence
> > >> >
> > >> >   [ x ]
> > >> >
> > >> > where x is the input parser. But it could be zero, so wrap the 
> > >> > sequence in an alternation with succeeds.
> > >> >
> > >> >   << [ x ]  true >>
> > >> >
> > >> > Then stitch it up into a loop by putting the alternate inside
> > >> > the sequence.
> > >> >
> > >> >   y = << [ x y ]  true >>
> > >> >
> > >> > This will match 0 or more of x and return the length matched.
> > >> 
> > >> What about:
> > >> 
> > >>   parser p = sequence2(some(term('x')), string("xy"));
> > >>   test(p, "xxxxy");
> > >> 
> > >> ?
> > >
> > > Touché. That doesn't work. The quantifiers I've supplied are strictly
> > > greedy.
> > 
> > Just a small point to avoid confusion: "strictly greedy" seems to be
> > your own term, at least I've not hear it before.  The normal Kleene star
> > operator is greedy in the usual meaning of the term -- that it matches
> > the longest possible string /that still allows the whole pattern to
> > match/.
> > 
> 
> Thanks. A brief search suggests at least one person calls
> this a "possessive" Kleene star.
> 
> https://cs.stackexchange.com/questions/40712/possessive-kleene-star-operator

Had some success on the postscript side. The missing ingredient is
having each parser return a list of results (lengths). So I'll probably
want to rewrite the whole thing with list management in mind.

But not right now.

[toc] | [prev] | [next] | [standalone]

#112330

On Tuesday, June 13, 2017 at 6:44:07 AM UTC-5, luser droog wrote:
> On Monday, June 12, 2017 at 3:53:42 PM UTC-5, luser droog wrote:
> > On Monday, June 12, 2017 at 6:25:10 AM UTC-5, Ben Bacarisse wrote:
> > > luser droog <luser.droog@gmail.com> writes:

> > > >> > This will match 0 or more of x and return the length matched.
> > > >> 
> > > >> What about:
> > > >> 
> > > >>   parser p = sequence2(some(term('x')), string("xy"));
> > > >>   test(p, "xxxxy");
> > > >> 
> > > >> ?
> > > >
> > > > Touché. That doesn't work. The quantifiers I've supplied are strictly
> > > > greedy.
> > > 
> > > Just a small point to avoid confusion: "strictly greedy" seems to be
> > > your own term, at least I've not hear it before.  The normal Kleene star
> > > operator is greedy in the usual meaning of the term -- that it matches
> > > the longest possible string /that still allows the whole pattern to
> > > match/.
> > > 
> > 
> > Thanks. A brief search suggests at least one person calls
> > this a "possessive" Kleene star.
> > 
> > https://cs.stackexchange.com/questions/40712/possessive-kleene-star-operator
> 
> Had some success on the postscript side. The missing ingredient is
> having each parser return a list of results (lengths). So I'll probably
> want to rewrite the whole thing with list management in mind.
> 
> But not right now.

Greedy, but not possessive.

Lists aren't so terrible, dealt with functionally.

Norah@laptop ~
$ cat pc3.c
#include <stdio.h>
#include <stdlib.h>

typedef struct parser *parser;
typedef struct result *result;
typedef result (*handler)( parser p, char *input );

struct parser {
  handler test;
  parser a, b;
  int c;
};

struct result {
  result next;
  int length_matched;
};

#define new_function_for_(type) \
  type new_##type ( struct type input ){ \
    type local = calloc( sizeof *local, 1 ); \
    return  local  ?  ( *local = input ), local  :  local; \
  }
new_function_for_(parser)
new_function_for_(result)


result parse( parser p, char *input ){  return  p->test( p, input );  }
result parse_fail( parser p, char *input ){  return  NULL;  }
result parse_succeed( parser p, char *input ){
  return  new_result( (struct result){ .next = NULL, .length_matched = 0 } );
}
result parse_term( parser p, char *input ){
  return  *input == p->c  ?
    new_result( (struct result){ .next = NULL, .length_matched = 1 } ) :
    NULL;
}

result parse_alternate( parser p, char *input ){
  result res = parse( p->a, input );
  if(  res  ){
    result r = res;
    while(  r->next  ) r = r->next;
    r->next = parse( p->b, input );
    return  res;
  } else  return  parse( p->b, input );
}

void amend_lengths( result r, int length ){
  if(  r  )  r->length_matched += length;
  if(  r->next  )  amend_lengths( r->next, length );
}

result parse_sequence_next( result r, parser p, char *input ){
  if(  ! r  )  return  NULL;
  result res = parse( p->b, input + r->length_matched );
  if(  res  ){
    amend_lengths( res, r->length_matched );
    result tail = res;
    while(  tail->next  )  tail = tail->next;
    tail->next = parse_sequence_next( r->next, p, input );
    return  res;
  } else  return  parse_sequence_next( r->next, p, input );
}

result parse_sequence( parser p, char *input ){
  result res = parse( p->a, input );
  return  parse_sequence_next( res, p, input );
}


parser fails(){  return  new_parser( (struct parser){ .test = parse_fail } ); }
parser succeeds(){  return  new_parser( (struct parser){ .test = parse_succeed } ); }

parser term( int c ){
  return  new_parser( (struct parser){ .test = parse_term, .c = c } );
}
parser alternate( parser a, parser b){
  return  new_parser( (struct parser){ .test = parse_alternate, .a = a, .b = b } );
}
parser sequence( parser a, parser b){
  return  new_parser( (struct parser){ .test = parse_sequence, .a = a, .b = b } );
}
parser many( parser a ){
  parser q = new_parser( (struct parser){ .test = parse_sequence, .a = a } );
  parser r = new_parser( (struct parser){ .test = parse_alternate, .a = q, .b = succeeds() } );
  q->b = r;
  return r;
}
parser some( parser a ){
  parser q = new_parser( (struct parser){ .test = parse_sequence, .a = a } );
  parser r = new_parser( (struct parser){ .test = parse_alternate, .a = q, .b = succeeds() } );
  q->b = r;
  return q;
}

parser char_class( char *str ){
  return  *str  ?  alternate( term( *str ), char_class( str + 1 ) )  :  fails();
}
parser string( char *str ){
  return  *str  ?  sequence( term( *str ), string( str + 1 ) )  :  succeeds();
}


void print_results( result res ){
  if(  res  )  printf( "%d ", res->length_matched ),
                 print_results( res->next );
}

void test( parser p, char *str ){
  printf( "%s:", str );
  fflush(0);
  result r = parse( p, str );
  print_results( r );
  printf( "\n" );
}

int main(){
  parser p = string("hello");
  test( p, "hello" );
  test( p, "hell" );
  test( p, "hello w" );
  test( p, "xxxxx" );

  parser q = many( term( 'x' ) );
  test( q, "xy" );
  test( q, "xx" );
  test( q, "xxxy" );
  test( q, "xxxxy" );
  test( q, "xxxxx" );
  
  parser r = sequence( many( term( 'x' ) ), string( "xy" ) );
  test( r, "xy" );
  test( r, "xx" );
  test( r, "xxxy" );
  test( r, "xxxxy" );
  test( r, "xxxxx" );
  return 0;
}

Norah@laptop ~
$ make pc3 CFLAGS+='-std=c99 -g'
cc -std=c99 -g    pc3.c   -o pc3

Norah@laptop ~
$ ./pc3
hello:5 
hell:
hello w:5 
xxxxx:
xy:1 0 
xx:2 1 0 
xxxy:3 2 1 0 
xxxxy:4 3 2 1 0 
xxxxx:5 4 3 2 1 0 
xy:2 
xx:
xxxy:4 
xxxxy:5 
xxxxx:

Norah@laptop ~
$ 

[toc] | [prev] | [next] | [standalone]

Page 1 of 2  [1] 2  Next page →

Back to top | Article view | comp.lang.c

csiph-web