On 03/23/2010 10:44 PM, Tim Starling wrote:
Just because a language is context-sensitive doesn't mean it will be hard to write a parser for it. That's just a myth propagated by computer scientists who, strangely enough given their profession, have a disdain for the algorithm as a descriptive framework.
Context free grammars have a strong advantage because they come with documentation built in. Given a BNF-esque description of a language, it is possible to understand, at a high level, how the language works. This means it's easy to write a parser (though much easier to get the parser written automatically), it's also more pleasant to verify properties of the language (no state to keep track of), and to reason about the consequences of modifications. Of course it is possible to give decent documentation for a context-sensitive language; from what I've seen, this just doesn't happen.
Take for example Python and perl, or Markdown and MediaWiki. In both cases the former has a syntax that can be mainly modeled by a context free grammar and there are many implementations that all work. The latter of the pair has a context sensitive grammar defined only by the reference implementation, there are no other parsers with feature completeness. This is certainly not a technical limitation, rather a reflection on the ability of your average human programmer.
Conrad