11

Are the C++, C# or Java languages context-free or context-sensitive?

Bill the Lizard
  • 398,270
  • 210
  • 566
  • 880
Adam Lee
  • 24,710
  • 51
  • 156
  • 236

1 Answers1

7

C++ is neither context-free nor context-sensitive, since the template system is Turing-complete and determining whether a piece of C++ code is legal C++ is undecidably hard. For example, I could define a template class that simulates a TM on a string and then creates a constant with value 1 if the machine accepts and 0 if it does not. If I did that, then the following code would be legal iff the TM halted on the given input:

int myArray[TMTemplate</* ... args ... */>::value];

Since if the TM rejects, this creates an array of size 0, which is not allowed.

Neither C# nor Java is context-free, because checking of whether a variable is used correctly and consistently throughout a particular scope is known not to be context-free (the proof is complex and relies on Ogden's lemma). However, I'm not sure whether or not they are context-sensitive.

Hope this gives a partial answer to your questions!

templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065
  • 7
    I'm not sure if the turing-completeness of templates affects the *grammar* of C++. Sure, the results of template metaprogramming can decide wether a program passes certain semantic checks, but that goes far beyond the scope of grammars. And templates change nothing about syntax: If the program has a syntax error, templates aren't instanciated, and if they are instanciated, they never result in syntax errors. Do you also consider all statically-typed languages context-sensitive because you need to know all types involved to decide wether e.g. an assignment statement is valid? –  Mar 11 '12 at 08:55
  • @delnan- I was interpreting the question such that any statically-typed language is not context-free, since the correctness of the program depends on how the types relate. I'm approaching this from the perspective of "if you gathered up all strings representing legal X programs, what sort of language do you get back?" That set isn't context-free, even if as a precondition for being valid the string has to be in the grammar. Does that make sense? And is this an unreasonable interpretation of the question? – templatetypedef Mar 11 '12 at 09:03
  • 3
    Under that interpretation, your answer makes sense. It's not how I would have interpreted the question, but that's because I assume "context-free language" (as used by OP) is just a shorthand for "language with a context-free grammar". But I think it makes sense (and if that was indeed the question, your answer is correct). You should add that explanation to the answer, to prevent further misunderstandings. –  Mar 11 '12 at 09:12
  • 3
    Variable type testing and "correctness" evaluation has nothing to do with whether a language is context-free or not. You're talking about static analysis and that is not part of the parser. A language can only be said to be context-sensitive if and only if the state of the parser can change what a rule matches. Also, if a language is not context-free it is context-sensitive - a language can't be neither. – B T Jan 05 '13 at 21:53
  • 2
    @BT- It is absolutely not the case that a language is either context-free or context-sensitive. The context-sensitive languages are a strict superset of the context-free languages, but they do not cover all languages. There are infinitely more languages that are not context-sensitive than there are context-sensitive languages. Specifically: a language is context-sensitive iff there is a linear bounded automaton for it, and the number of LBAs is infinitely smaller than the number of languages. – templatetypedef Jan 05 '13 at 22:02
  • 2
    @BT- Additionally, while traditionally a compiler works by first doing parsing and then doing semantic analysis, from a formal language perspective the set of all strings that are valid programs is not context-free. There are many strings that can legally be *parsed* but are not legal programs. My answer referred to the fact that the set of all legal computer programs in a language isn't context-free, rather than there not being a grammar that a compiler could use for it. – templatetypedef Jan 05 '13 at 22:03
  • Alright, seems you're right on both counts. My apologies. My confusion was based on the fact that any language that isn't context-free is certainly sensitive to context, despite the term "context-sensitive" having a more technical (and non-intuitive) definition. – B T Jan 05 '13 at 23:03
  • I realize this answer is a bit older, but since I don't know enough C++ to know what to google: does this invalidity of the template-using version of the code snippet stem purely from the possibility that the template might return something non-positive? As referenced [here](http://stackoverflow.com/questions/3783282/declaring-an-array-of-negative-length), this might actually compile, but like I said, I'm not all that good with C++. Also, the argument regarding the template encoding a halting problem black box seems fishy to me; we know there can't be such a template for general strings. – G. Bach Jun 19 '15 at 18:04
  • @G.Bach Yes, that's right. Also, I'm not sure I understand what you mean by "there cannot be a template for general strings." Can you elaborate? – templatetypedef Jun 19 '15 at 18:06
  • I took your summary of the proof idea to mean "we build a template that decides the halting problem" - I now realize that you probably actually meant "we have to wait for the template to try to decide the halting problem to figure out how big our array should be"; but then I don't see how that's different from, say, using a function to do that, and the actual problem isn't the template system, but not knowing whether we ever figure out the length of the array we want to create. – G. Bach Jun 19 '15 at 18:11
  • @G.Bach Oh, I see. It's not so much that the template decides the halting problem as much as the template simulates the execution of the TM and evaluates to 1 if the TM accepts and 0 if it rejects. Deciding whether the program is well-formed then essentially reduces to deciding whether a TM accepts, which is impossible in general. – templatetypedef Jun 19 '15 at 18:20
  • That would mean it doesn't make a difference whether we put the TM simulation into a template or a function, right? (I thought this might apply to Java as well, but was surprised to find out that creating an array of non-positive length is valid Java, you just get a `NegativeArraySizeException` for negative lengths - pretty weird.) – G. Bach Jun 19 '15 at 18:26
  • @G.Bach C++ arrays must be sized at compile-time, so we couldn't put that code into a normal function (I believe). – templatetypedef Jun 19 '15 at 18:36