Is C# considered a context free language?

Question

I have been looking for this, but there is a lot of different answers to this question on the MSDN forums.

Some people say that "All computer language grammars are context free" and others say that any language that has white-space sensitive syntax is likely context-sensitive and therefore not context-free (F# and Python).

Whould be nice a definitive answer and maybe some proof.

Answer 1

I would describe C# as having a context-free grammar, but the language has context-sensitive rules that are not expressed in the grammar.

From Wikipedia (Formal grammar):

A context-free grammar is a grammar in which the left-hand side of each production rule consists of only a single nonterminal symbol.

From the C# 4.0 specification, section 2.2.1 (Grammar notation):

The lexical and syntactic grammars are presented using grammar productions. Each grammar production defines a non-terminal symbol and the possible expansions of that non-terminal symbol into sequences of non-terminal or terminal symbols.

As I read it, that means that the production rules defining the C# language are context-free. The left-hand side of each production rule is a single non-terminal symbol. By contrast, a context-sensitive grammar may have multiple terminal and non-terminal symbols on the left-hand side of a production rule.

There are, however, many rules in the specification that are context-sensitive. For example, "A local variable must be definitely assigned (§5.3) at each location where its value is obtained." Also, "The signature of a method must be unique in the class in which the method is declared." These are both cases where the validity of any particular fragment depends on the context in which it appears.

Of course, many programming languages have similar requirements, including C. I doubt most would consider C a context-sensitive language. I think this answer summarized it well:

The set of programs that are syntactically correct is context-free for almost all languages. The set of programs that compile is not context-free for almost all languages.

As for Python and F#, as I said in my comment, those languages are usually described as having semantic (or sometimes syntactic) whitespace not context-sensitive.