Path: csiph.com!eternal-september.org!feeder.eternal-september.org!reader01.eternal-september.org!.POSTED!not-for-mail
From: M Joshua Ryan <luser.droog@gmail.com>
Newsgroups: comp.lang.c
Subject: [PC] regex parser using monoidal parser combinators
Date: Mon, 08 Apr 2019 00:36:59 -0500
Organization: A noiseless patient Spider
Lines: 82
Message-ID: <vriuftqtt5vo.fsf@gmail.com>
Mime-Version: 1.0
Content-Type: text/plain
Injection-Info: reader02.eternal-september.org; posting-host="7aa74308be0ddfd1e51026a340a56610"; logging-data="11659"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX19qA3TeeIMV+rcVI3U3H1mvhH4RqijnIPM="
User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/25.3 (cygwin)
Cancel-Lock: sha1:ziqGK5yrOhMCQKE0PgLm2KSYaD8= sha1:WUP6qb9FDsc/L3Xtd8qv5bsMYTI=
Xref: csiph.com comp.lang.c:142894

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