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

Groups > comp.lang.c > #111776

Re: Parser Combinators

Show all headers | View raw

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...

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