4 ms·
Whether a language is context free depends on how much checking you want to happen in the parsing stage. A variable usage is valid only if that variable is in s
by jules 9y ago
Whether a language is context free depends on how much checking you want to happen in the parsing stage. A variable usage is valid only if that variable is in scope, and this trivially makes almost all languages context sensitive. Almost all programming languages become context free if you delay the checking of such errors to a subsequent stage instead of requiring it to be handled in the grammar. For example the following is syntactically valid Javascript according to the Javascript grammar, because the grammar does not handle variable scope:
var foo = 0;
var bar = boo; // typo
Context free grammars are actually an overpowered formalism for programming languages except for variable scope. Most languages don't require more than LR(1).
Monadic parser combinators can easily handle context sensitive grammars. The simplest example is a length prefixed field in network protocols. Context free grammars cannot parse this, but a monadic parser can read the length and then parse that many repetitions.