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