Menu
Are the C++, C# or Java languages context-free or context-sensitive?
246
A Boolean grammar was constructed to specify syntax and static semantics (including scoping rules) of a programming language.
Context-sensitive grammars are more general than context-free grammars, in the sense that there are languages that can be described by CSG but not by context-free grammars. Context-sensitive grammars are less general (in the same sense) than unrestricted grammars.
In context sensitive grammar, there is either left context or right context (αAβ i.e. α is left context and β is right) with variables. But in context free grammar (CFG) there will be no context. For example in production rule. S →0 B S 2 , B 0 → 0 B.
All regular languages are context-free languages, but not all context-free languages are regular. Most arithmetic expressions are generated by context-free grammars, and are therefore, context-free languages.
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!
98
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
