What programming languages are context-free?

Question

Or, to be a little more precise: which programming languages are defined by a context-free grammar?

From what I gather C++ is not context-free due to things like macros and templates. My gut tells me that functional languages might be context free, but I don't have any hard data to back that up with.

Extra rep for concise examples :-)

Answer 1

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. For example, if the set of all compiling C programs were context free, then by intersecting with a regular language (also known as a regex), the set of all compiling C programs that match

^int main\(void\) { int a+; a+ = a+; return 0; }$

would be context-free, but this is clearly isomorphic to the language a^kba^kba^k, which is well-known not to be context-free.

Answer 2

Depending on how you understand the question, the answer changes. But IMNSHO, the proper answer is that all modern programming languages are in fact context sensitive. For example there is no context free grammar that accepts only syntactically correct C programs. People who point to yacc/bison context free grammars for C are missing the point.

Answer 3

Most of the modern programming languages are not context-free languages. As a proof, if I delve into the root of CFL its corresponding machine PDA can't process string matchings like {ww | w is a string}. So most programming languages require that.

Example:

int fa; // w
fa=1; // ww as parser treat it like this

Answer 4

I think Haskell and ML are supporting context free. See this link for Haskell.

Answer 5

VHDL is somewhat context sensitive.

(Google: parsing-vhdl-is-very-hard)

Answer 6

To go for the most dramatic example of a non-context-free grammar, Perl's grammar is, as I understand it, turing-complete.