[weinzierl]

"This covers practically all programming languages, because they conform to a syntax tree where each branch is an application of such a production rule."

Except that practically all practically used programming languages are not context-free.

[xg15]

Is that so?

Programming languages usually have a number of "higher-level semantic layers" on top of the syntax tree that impose further constrains - e.g. that identifiers must have consistency between usage and definition, that all expressions are valid according to the type system, etc.

But all that stuff happens after an AST is created and so doesn't really affect the basic grammar.

I think if you ignore those higher-level constraints, a number of languages have valid context-free grammars.

[weinzierl]

In C, the token sequence

  T * x;

can be interpreted either as a declaration or as an expression (multiplication). Resolving this ambiguity requires context, namely whether T is a typedef name or an object name, which cannot be determined from syntax alone.

One could argue that it is acceptable to produce an ambiguous parse and defer the decision, and in practice compilers do rely on semantic information to resolve such cases.

However, this is not what context-free means in the Chomsky sense: a context-free grammar must be able to determine the syntactic structure without reference to prior declarations or semantic state.

[xg15]

Exactly - I'd see this as an example of a language that is not context-free, because generating the AST requires information beyond the root node/production and the characters of the subtree.

In contrast, languages like Java, JavaScript or C# would be context-free: The string

  hello(foo + bar * 5);

is not a "valid" JavaScript program, because of the undefined identifiers, but it does have a non-ambiguous AST.

[weinzierl]

Thanks for the clarification. C has an easy to demonstrate example and languages like Java, JavaScript and C# are (deliberately in my opinion) closer to a true context-free grammar but they all have counter-examples and so are not context-free in the computer science sense.

https://stackoverflow.com/questions/898489/what-programming-...

(See also the answer by Dave with currently only the second most votes. If that is what you mean, I agree.)

[krackers]

There is at least one turing complete programming language that is trivially context-free, Brainfuck, so at least for the purposes of expressivity it seems OK to consider context-free ones.

[fi-le]

Thank you, corrected!