The smallest grammar problem is to find a single-string CFG. So given a finite list of language samples, known to all lie in some CFG, can we, using the smallest grammars (approximated) of each respective sample, compute an approximate smallest CFG for the language?
I want to make a parser generator that automatically detects a grammar given some samples of programming languages.
This is extremely optimistic.
The first problem you face is that an approximate smallest grammar will at best help you find strings which occur frequently. It won't distinguish keywords from names, and it won't isolate words. (Note for reference that Lempel-Ziv has a good approximation ratio. Charikar, Lehman, Liu, Panigrahy, Prabhakaran, Sahai, & Shelat (2005) The smallest grammar problem, Information Theory, IEEE Transactions on, 51(7), 2554-2576).
The second, related, problem you face is tokenisation. Programming language grammars deal in tokens, not in characters. Just the issue of tabs vs spaces in the samples is likely to mess things up. This might be finessed by making assumptions about tokenisation and then finding approximate smallest grammars over the language of tokens, but be prepared for nasty surprises. E.g. string literals in C# are definitely non-trivial, and you might not have many instances of @-strings from which to infer.
The third problem is that some languages (particularly those designed for code-golf) have unusual tokenisation and so little grammar that the tokenisation is where the real difficulty lies. E.g. identifying the tokenisation of CJam operators is going to be hard. You might do slightly better if instead of working from a grammar per sample you concatenate the samples, separated by a token which doesn't occur in any sample, and then find an approximate shortest grammar for that super-sample. At least that way you might have sufficiently many occurrences of the more common multi-character tokens to pick them out as symbols.
