3 ms·

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

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

fi-le 10mo ago
Thank you, corrected!
xg15 10mo ago
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 10mo ago
  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 10mo ago
    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 10mo ago
      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-languages-are-context-free?utm_source=perplexity 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 10mo ago
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 10mo ago

Thank you, corrected!

xg15 10mo ago

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 10mo ago
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 10mo ago
  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 10mo ago
    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-languages-are-context-free?utm_source=perplexity 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 10mo ago

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.