Search code examples
compiler-theorycontext-free-grammar

What programming languages are context-free?


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 :-)


Solution

  • 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.