views:

704

answers:

4

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

+1  A: 

Almost all modern languages are context free. C++ is one of the rare exceptions due to some things you can do with templates. No others come to mind that are not context free, although things like XML integration in VB.NET and also LINQ queries in both C# and VB might require context sensitivity. At least, Paul Vick, then head of the VB team, mentioned that XML in VB is quite hard to parse.

Konrad Rudolph
And have been since Algol-60.
S.Lott
What about the issues discussed here:http://eli.thegreenplace.net/2007/11/24/the-context-sensitivity-of-cs-grammar/
n3rd
+3  A: 

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.

Dave
+1 for the answer which is true. The accepted answer is misleading.
Derrick Turk
+1  A: 

VHDL is somewhat context sensitive.

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

Graham Gimbert
I'm a new user and am not allowed to post links.
Graham Gimbert
@Graham: no, you absolutely may. There's no restriction for new users on posting links.
Konrad Rudolph
A: 

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

Devin Jeanpierre