Converting decision problems to grammars?
Yes, every decision problem can be converted into a grammar that generates exactly the "yes"-instances of the problem.

And no, even if the problem is decidable, there is not necessarily a context-sensitive (let alone a context-free) grammar. An example would be the equivalence problem for regular expressions with exponentiation. (reference)