Search code examples
compiler-constructioncontext-free-grammarcontext-sensitive-grammar

Which languages are context-sensitive?

I'm learning "Compiler Theory", it says most of languages used "deterministic context-free grammar". I wonder is there any language use "context-sensitive grammar"?

Update:

I asked someone, he said that c++ and ruby has some context-sensitive grammars.

For example, in c++, this code:

abc();

If there is a method called abc, then abc() means "the invocation of this method". If there is a class class abc{ }, then it means "create an instance of class abc".

And in ruby, since it has meta-programming, it has more context-sensitive grammars.

Is he right?

Solution

  • Context-sensitive grammar has symbols that change their meaning in relation with various nonterminals they are used in their context. In computer world, they are pretty rare, because it quite complicates writing of the parser - decision if a string belongs to a certain context-sensitive grammar is PSPACE-complete.