Ir al contenido principal

Ralsina.Me — El sitio web de Roberto Alsina

The middle path

In my pre­vi­ous post, I men­tioned how PySPF does some­thing us­ing a reg­u­lar ex­pres­sion which I could­n't eas­i­ly re­pro­duce in C.

So, I start­ed look­ing at pars­er gen­er­a­tors to use the orig­i­nal SPF RFC's gram­mar.

But that had its own prob­lem­s.... and then came ragel.

Ragel is a fi­nite state ma­chine com­pil­er, and you can use it to gen­er­ate sim­ple parsers and val­ida­tors.

The syn­tax is very sim­ple, the re­sults are pow­er­ful, and here's the main chunk of code that lets you parse a SPF do­main-spec (it work­s, too!):

machine domain_spec;
name = ( alpha ( alpha | digit | '-' | '_' | '.' )* );
macro_letter = 's' | 'l' | 'o' | 'd' | 'i' | 'p' | 'h' | 'c' | 'r' | 't';
transformers = digit* 'r'?;
delimiter = '.' | '-' | '+' | ',' | '|' | '_' | '=';
macro_expand = ( '%{' macro_letter transformers delimiter* '}' ) |
               '%%' | '%_' | '%-';
toplabel = ( alnum* alpha alnum* ) |
           ( alnum{1,} '-' ( alnum | '-' )* alnum );
domain_end = ( '.' toplabel '.'? ) | macro_expand;
macro_literal = 0x21 .. 0x24 | 0x26 .. 0x7E;
macro_string = ( macro_expand | macro_literal )*;
domain_spec := macro_string domain_end 0 @{ res = 1; };

And in fac­t, it's sim­pler than the AB­NF gram­mar used in the RFC:

name             = ALPHA *( ALPHA / DIGIT / "-" / "_" / "." )
macro-letter     = "s" / "l" / "o" / "d" / "i" / "p" / "h" /
                   "c" / "r" / "t"
transformers     = *DIGIT [ "r" ]
delimiter        = "." / "-" / "+" / "," / "/" / "_" / "="
macro-expand     = ( "%{" macro-letter transformers *delimiter "}" )
                   / "%%" / "%_" / "%-"
toplabel         = ( *alphanum ALPHA *alphanum ) /
                   ( 1*alphanum "-" *( alphanum / "-" ) alphanum )
domain-end       = ( "." toplabel [ "." ] ) / macro-expand
macro-literal    = %x21-24 / %x26-7E
macro-string     = *( macro-expand / macro-literal )
domain-spec      = macro-string domain-end

So, thumbs up for ragel!

Up­date:

  • The code looks very bad on python or agre­­ga­­tors.

  • This piece of code alone fixed 20 test cas­es from the SPF suit­­e, and now on­­ly 8 fail. Neat!


Contents © 2000-2024 Roberto Alsina