Proof that ASN.1 is a context-sensitive grammar
I just wrote an attribute grammar for the general object-encoding rules. (Not all of BER; that's next. Just section 8.1 of X.690.) Unless sections 8.2 through 8.22 throw me a curveball, which it doesn't look like they will, QED. It's fully left-recursive and uses only synthesized attributes, for all your efficient parsing needs. Boo yah.
If anyone playing along at home wants to have a look, drop me a comment.
FWIW, attribute grammars are absurdly simple in Haskell; Happy supports them natively. (Attribute grammars are somewhat intractable in strictly-evaluated languages because if you have to use strict evaluation, the data dependency graph gets impractically large very quickly. Haskell, which uses lazy evaluation, doesn't have this problem. Every day I come to love this little language more and more. Oh, and I can do a multiple-entry-point approach to support CER and DER. Seriously, how cool is that?)
Don Knuth, Haskell Curry, Simon Peyton-Jones, Simon Marlow and Andy Gill are totally my heroes forever and ever.
If anyone playing along at home wants to have a look, drop me a comment.
FWIW, attribute grammars are absurdly simple in Haskell; Happy supports them natively. (Attribute grammars are somewhat intractable in strictly-evaluated languages because if you have to use strict evaluation, the data dependency graph gets impractically large very quickly. Haskell, which uses lazy evaluation, doesn't have this problem. Every day I come to love this little language more and more. Oh, and I can do a multiple-entry-point approach to support CER and DER. Seriously, how cool is that?)
Don Knuth, Haskell Curry, Simon Peyton-Jones, Simon Marlow and Andy Gill are totally my heroes forever and ever.