Proof that ASN.1 is a context-sensitive grammar

[maradydd]

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.

Comments

[alexey-rom.livejournal.com]

I expect you've seen this already: http://www.haskell.org/haskellwiki/The_Monad.Reader/Issue4/Why_Attribute_Grammars_Matter

[maradydd.livejournal.com]

I had not, though that's awesome and I may very well end up citing it in my thesis. Thanks!

[http://users.livejournal.com/_rck_/]

What is the thesis about? (And yes, I would like to see the code.)