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]

That's cool. One more thing to learn...

[maradydd.livejournal.com]

The nice folks in #haskell also pointed me at uuagc (http://hackage.haskell.org/package/uuagc), which I'll try after I get the Happy version implemented and working. Its syntax is rather less yacc-like, so baby steps for now, but it'll be interesting to compare their performance. (The parser combinators look like they'll be especially useful for stuff like dynamically generating a parser from an .asn1 declaration.)

[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.)

[alexey-rom.livejournal.com]

Glad to help!

[vatine]

I guess you've looked at packrat parsers? Don't know if they'd be suitable, though. They're very much designed for lazy evaluation.

Hackage?

[dons.pip.verisignlabs.com (from livejournal.com)]

Will you release your parser as a package on Hackage? It could be very useful to other groups.

Re: Hackage?

[maradydd.livejournal.com]

Absolutely! I'm still working on the actual code part -- what I have right now is just a raw AG -- but I'm aiming to have parsers for both BER and DER at minimum, CER and PER if anyone cares. I also plan to write C bindings for it.

weighing those hammers

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

I dont know enough about the specific grammar you are implementing, but I wanted to point out that often the grammars can be simplified if the semantics of the parser can be beefed up.

Consider the problem of enforcing variable declarations a la Java. At the level of the grammar, enforcing declaration before use requires a context sensitive grammar (the proof is in Ullmann et al, I will hunt it down if you need it for the thesis), but almost everyone I know of, including the Java Spec, writes context free grammars for Java and lets the compiler bitch about the mismatch.

This really came to the fore for me after some work related research on the question of which natural languages are context-sensitive; it turns out that you can almost always pull apart the opponent's examples by designing your grammar a little bit different--esp in English.

PS: Admittedly, reading the other posts, it looks like attribute grammars allow you to get that very split in your management of the context sensitivity that I was talking about.