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

Groups > comp.lang.c > #111674

Re: Parser Combinators

Show all headers | View raw

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

Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

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

csiph-web