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

Groups > comp.lang.c > #142894

[PC] regex parser using monoidal parser combinators

Show all headers | View raw

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

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

Thread

[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

csiph-web