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

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

[PC] regex parser using monoidal parser combinators

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

Contents

  [PC] regex parser using monoidal parser combinators M Joshua Ryan <luser.droog@gmail.com> - 2019-04-08 00:36 -0500
    Re: [PC] regex parser using monoidal parser combinators luser droog <luser.droog@gmail.com> - 2019-04-07 23:16 -0700

#142894 — [PC] regex parser using monoidal parser combinators

Elaborating the code further, it did become necessary to add
environments. This was needed for the 'into' combinator which sequences
two parsers p and q, but also makes the result from p available to q.
This required having an extensible list of (name, value) pairs in the v
parameter for all parsers and operators. 

It also became confusing to me to use the type 'object' all over the
place. So I made a handful of typedefs: parser, list, operator,
predicate. And this made it easier to write the functions since the
types are more meaningful. A parser constructor now returns a 'parser'.
A parser combinator accepts one or more 'parser' arguments and returns a
'parser'. A parsing function now receives a 'list' and returns a
'list'. To the compiler, these are all just aliases for 'object'. But to
the human reader, this should supply more informative context.

Cutting to the chase, here's the regular expression parser code.


object do_meta( parser a, object b ){
  switch( b->Int.i ){
  case '*':  a = many( a ); break;
  case '+':  a = some( a ); break;
  case '?':  a = maybe( a ); break;
  }
  return  a;
}

list on_dot( void *v, list o ){ return  item(); }
list on_chr( void *v, list o ){ return  lit( o ); }
list on_meta( void *v, list o ){
  object atom = assoc( Symbol(ATOM), v );
  return  o  ? do_meta( atom, o ) : atom;
}
list on_term( void *v, list o ){ return  collapse( seq, o ); }
list on_expr( void *v, list o ){ return  collapse( plus, o ); }
parser regex( char *re ){
  static parser p;
  if(  !p  ){
    parser  dot    = Char( '.' );
    parser  meta   = anyof( "*+?" );
    parser  chr    = noneof( "*+?.|()" );
    parser  expr_  = forward();
    parser  atom   = plus( using( dot, on_dot ),
                     plus( thenx( xthen( Char('('), expr_ ), Char(')') ),
                           using( chr, on_chr ) ) );
    parser  factor = into( atom, Symbol(ATOM), using( maybe( meta ), on_meta ) );
    parser  term   = using( seq( factor, many( factor ) ), on_term );
    parser  expr   = using( seq( term, many( xthen( Char('|'), term ) ) ), on_expr );
    *expr_ = *expr;
    //p = expr;
    p = trim( expr );
  }
  return  parse( p, string_input( re ) );
}

void test_regex(){
  object y = regex( ".?(b)+|a" );
  print( y ), puts("");
  parser p = trim( x( x( y ) ) );
  print( parse( p, string_input( "b" ) ) ), puts("");
  print( parse( p, string_input( "xbb" ) ) ), puts("");
  print( parse( p, string_input( "a" ) ) ), puts("");
}


And the output shows that it's working, at least for basic uses.


$ make pc7 cflags=-g && ./pc7
cc -std=c99 -g    pc7.c   -o pc7
((PARSER () ) () ) 
(((() (98 () ) ) () ) () ) 
(((120 (98 (98 () ) ) ) () ) () ) 
((97 () ) () ) 


Current commit:
https://github.com/luser-dr00g/pcomb/tree/a4434fd7466a5da20bec5ab6d96e19b287898b45
https://github.com/luser-dr00g/pcomb/archive/a4434fd7466a5da20bec5ab6d96e19b287898b45.zip

Just the single file:
https://github.com/luser-dr00g/pcomb/raw/a4434fd7466a5da20bec5ab6d96e19b287898b45/pc7.c

[toc] | [next] | [standalone]

#142895

On Monday, April 8, 2019 at 12:37:36 AM UTC-5, luser droog wrote:
> 
> It also became confusing to me to use the type 'object' all over the
> place. So I made a handful of typedefs: parser, list, operator,
> predicate. And this made it easier to write the functions since the
> types are more meaningful. A parser constructor now returns a 'parser'.
> A parser combinator accepts one or more 'parser' arguments and returns a
> 'parser'. A parsing function now receives a 'list' and returns a
> 'list'. To the compiler, these are all just aliases for 'object'. But to
> the human reader, this should supply more informative context.
> 
> Cutting to the chase, here's the regular expression parser code.
> 
> 
> object do_meta( parser a, object b ){
>   switch( b->Int.i ){
>   case '*':  a = many( a ); break;
>   case '+':  a = some( a ); break;
>   case '?':  a = maybe( a ); break;
>   }
>   return  a;
> }
> 
> list on_dot( void *v, list o ){ return  item(); }
> list on_chr( void *v, list o ){ return  lit( o ); }
> list on_meta( void *v, list o ){
>   object atom = assoc( Symbol(ATOM), v );
>   return  o  ? do_meta( atom, o ) : atom;
> }
> list on_term( void *v, list o ){ return  collapse( seq, o ); }
> list on_expr( void *v, list o ){ return  collapse( plus, o ); }

Sigh. These functions are all using the wrong types.
s/list/parser/g
s/object do_meta/parser do_meta/
s/object atom/parser atom/

[toc] | [prev] | [standalone]

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

csiph-web