Simple method for reliably detecting code in text?

Question

GMail has this feature where it will warn you if you try to send an email that it thinks might have an attachment.

Because GMail detected the string see the attached in the email, but no actual attachment, it warns me with an OK / Cancel dialog when I click the Send button.

We have a related problem on Stack Overflow. That is, when a user enters a post like this one:

my problem is I need to change the database but I don't won't to create 
a new connection. example:

DataSet dsMasterInfo = new DataSet();
Database db = DatabaseFactory.CreateDatabase("ConnectionString");
DbCommand dbCommand = db.GetStoredProcCommand("uspGetMasterName");

This user did not format their code as code!

That is, they didn't indent by 4 spaces per Markdown, or use the code button (or the keyboard shortcut ctrl+k) which does that for them.

Thus, our system is accepting a lot of edits where people have to go in and manually format code for people that are somehow unable to figure this out. This leads to a lot of bellyaching. We've improved the editor help several times, but short of driving over to the user's house and pressing the correct buttons on their keyboard for them, we're at a loss to see what to do next.

That's why we are considering a Google GMail style warning:

Did you mean to post code?

You wrote stuff that we think looks like code, but you didn't format it as code by indenting 4 spaces, using the toolbar code button or the ctrl+k code formatting command.

However, presenting this warning requires us to detect the presence of what we think is unformatted code in a question. What is a simple, semi-reliable way of doing this?

• Per Markdown, code is always indented by 4 spaces or within backticks, so anything correctly formatted can be discarded from the check immediately.
• This is only a warning and it will only apply to low-reputation users asking their first questions (or providing their first answers), so some false positives are OK, so long as they are about 5% or less.
• Questions on Stack Overflow can be in any language, though we can realistically limit our check to, say, the "big ten" languages. Per the tags page that would be C#, Java, PHP, JavaScript, Objective-C, C, C++, Python, Ruby.
• Use the Stack Overflow creative commons data dump to audit your potential solution (or just pick a few questions in the top 10 tags on Stack Overflow) and see how it does.
• Pseudocode is fine, but we use c# if you want to be extra friendly.
• The simpler the better (so long as it works). KISS! If your solution requires us to attempt to compile posts in 10 different compilers, or an army of people to manually train a bayesian inference engine, that's ... not exactly what we had in mind.

Answer 1

A proper solution would probably be some learned/statistical model, but here are some fun ideas:

1. Semi-colons at the end of a line. This alone would catch a whole bunch of languages.
2. Parentheses directly following text with no space to separate it: myFunc()
3. A dot or arrow between two words: foo.bar = ptr->val
4. Presence of curly braces, brackets: while (true) { bar[i]; }
5. Presence of "comment" syntax (/*, //, etc): /* multi-line comment */
6. Uncommon characters/operators: +, *, &, &&, |, ||, <, >, ==, !=, >=, <=, >>, <<, ::, __
7. Run your syntax highlighter on the text. If it ends up highlighting some high percentage of it, it's probably code.
8. camelCase text in the post.
9. nested parentheses, braces, and/or brackets.

One could keep track of the number of times each of these appears, and these could be used as features in a machine-learning algorithm like perceptron, the way SpamAssassin does.

Answer 2

I would be curious to see what are the average metrics of written English on one side, and code on the other side.

• length of paragraphs
• length of lines
• size of words
• chars used
• ratio between alphabetic, numeric and other symbol characters
• number of symbols per word
• etc.

Maybe that alone could discriminate already between code and the rest. At least I believe code, regardless of language, would show some noticeably different metrics in many cases.

The good news is: you already have plenty of data to build your statistics upon.

---

Ok I'm back with some data to back my assumptions up. :-)

I did a quick and dirty test on your own post and on the first post I found on StackOverflow, with a pretty advanced tool: wc.

Here is what I had after running wc on the text part and on the code part of those two examples:

First lets look at the English part:

• The English part of your post (2635 chars, 468 words, 32 lines)
  • 5 chars/word, 82 chars/line, 14 words/line
• The English part of the other post (1499 chars, 237 words, 12 lines)
  • 6 chars/word, 124 chars/line, 19 words/line

Pretty similar don't you think?

Now lets take a look at the code part!

• The code part of your post (174 chars, 13 words, 3 lines)
  • 13 chars/word, 58 chars/line, 4 words/line
• The code part of the other post (4181 chars, 287 words, 151 lines)
  • 14 chars/word, 27 chars/line, 2 words/line

See how not so different those metrics are, but more importantly, how different they are from the English metrics? And this is just using a limited tool. I am now sure you can get something really accurate by measuring more metrics (I'm thinking in particular of chars statistics).

I can haz cookie?

Answer 3

Typically, Markov chains are used to generate text, but they can also be used to predict the similarity of text (per C.E. Shannon 1950) to a trained model. I recommend multiple Markov chains.

For each prevalent language, train a Markov chain on a large, representative sample of code in the language. Then, for a Stack Overflow post for which you want to detect code, do the following for each of the chains:

• Loop through the lines in the post.
  • Declare two variables: ACTUAL=1.0 and HIGHEST=1.0
  • Loop through each character in the line.
    • For each character, find the probability in the Markov chain that the current character is the one following the previous N characters. Set ACTUAL = ACTUAL * PROB₁. If the current character is not present in the chain, then use a tiny value for PROB₁, like 0.000001.
    • Now, find the character most likely (i.e. the highest probability) to follow the previous N characters. Set HIGHEST = HIGHEST * PROB₂.
    • Obviously, PROB₂ >= PROB₁

For each line, you should have an ACTUAL and a HIGHEST value. Divide ACTUAL by HIGHEST. That will give you the fitness score as to whether a particular line is source code. That would associate a number with each of the lines in the example you gave:

my problem is I need to change the database but I don't won't to create // 0.0032
a new connection. example: // 0.0023

DataSet dsMasterInfo = new DataSet(); // 0.04
Database db = DatabaseFactory.CreateDatabase("ConnectionString");   // 0.05
DbCommand dbCommand = db.GetStoredProcCommand("uspGetMasterName");  // 0.04

Finally, you'll need to select a threshold to determine when there is code in the post. This could simply be a number selected by observation that yields high performance. It could also take into account the number of lines with a high score.

Training

To train, procure a large, representative sample of code in the language. Write a program to loop over the code text and associate each N-gram in the file (the range for N should be parameterized) with the statistical frequency of the subsequent character. This will yield multiple possible states of characters that follow the bigram, each associated with a probability. For example, the bigram "()" could have some following character probabilities of:

"()" 0.5-> ";"
"()" 0.2-> "."
"()" 0.3-> "{"

The first should be read, for example as "The probability that a semicolon follows an empty parenthetical is 0.5."

For training, I recommend N-grams of size two through five. Back when I did some research on this, we found that N-grams size two through five worked well for English. Since much of source code is English like, I'd suggest starting with that range and then adjusting to find the optimal parameter values as you find what works.

A caveat: The model is going to be affected by identifiers, method names, whitespace, and etc. However, you can tune the training to omit certain features of the training sample. For example, you could collapse all unnecessary whitespace. The presence of whitespace in the input (the Stack Overflow post) can be ignored as well. You could also ignore alphabetical case, which would be more resilient in the face of varying identifier naming conventions.

During my research, we found that our methods worked well for Spanish as well as English. I don't see why this wouldn't also work well for source code. Source code is even more structured and predictable than human language.

Answer 4

May I suggest a radically different approach? On SO the only human-language allowed is English, so anything that is non-English has 99.9% of chances to be a code snippet.

So my solution would be: use one of the many English language-checkers out there (just make sure they also signal - beside misspellings - syntax mistakes like double dots, or non-language symbols like # or ~). Then any line/paragraph that throws a large amount of errors and warnings should trigger the "is this code?" question.

This approach can also be adapted for those StackExchange sites using other languages than English, of course.

Just my 2¢...

Answer 5

Pseudo code would pose a real challenge because all programming language depend on special characters like '[]', ';', '()', etc. Simply count the occurrence of these special characters. Just like you would detect a binary file (more than 5% of a sample contains byte value 0).

Answer 6

I'm probably going to get a few down votes for this but I think you are approaching this from the wrong angle.

This line got me:

people have to go in and manually format code for people that are somehow unable to figure this out

IMO that standpoint is kind of arrogant. I find this a lot in software design where programmers and designers get annoyed with users who can't figure out how to use the software properly, when the problem isn't the user but the software itself - or the UI at least.

The root cause of this problem isn't the user but the fact that it isn't obvious to them that they can do this.

How about a change in UI to make this more obvious? Surely this will be:

1. more obvious to new users exactly what they need to do
2. easier for you to build rather than writing complex algorithms to detect code logic of a multitude of languages

Example:

Answer 7

I think you may need to target this against only specific languages, in general this problem is likely intractable as you can get languages which are pretty similar to English (e.g. inform7). but luckily the most used ones could be covered fairly easily.

My first cut would be to look for the sequence ";\n" which would get you a good match for C,C++,Java, C# and any other language that uses similar syntax and is really simple. It is also less likely to be used in English than a ; without a newline

Answer 8

Someone mentioned looking at the tags and then looking for syntax for that but that was shot down because this is aimed at new users.

A possible better solution would be to look for language names in the body of the question, then apply the same strategy. If I mention "Javascript", "Java" or "C#" then chances are that is what the question is about, and code in the question is likely to be in that language.

Answer 9

First, run it through spell check, it will find very few proper English words, however there should be lot of words that spellchecker will suggest to split.

Then there are punctuation/special characters not typical for plain English, typical for code:

• something(); just cannot be plain English;
• $something where something is not all numeric;
• -> between words w/o spaces;
• . between words w/o space;

Of course to have it working well, you might want to have Bayesian classifier built on top of these characteristics.

Answer 10

there are several sets of languages which share similar syntax. the most languages got influenced by a few languages, so the languages [AMPL, AWK, csh, C++, C-- , C#, Objective-C, BitC, D, Go, Java, JavaScript, Limbo, LPC, Perl, PHP, Pike, Processing[ were all influenced by C, so if you detect C you will probably detect all these languages. so you have only to write a simple pattern for detecting this language-sets.

i would also split the text into blocks because the most code will be split by two newlines or similar from the other text blocks in the post.

this can be easy done with javascript (a supersimple incomplete sample for the c family) :

var txt = "my problem is I need to change the database but I don't won't to create a new connection. example:\n\nDataSet dsMasterInfo = new DataSet();Database db = DatabaseFactory.CreateDatabase("ConnectionString");DbCommand dbCommand = db.GetStoredProcCommand("uspGetMasterName");";
var blocks = txt.split(/\n\n/gi); console.dir(blocks);
var i = blocks.length;
var cReg = /if\s*\(.+?\)|.*(?:int|char|string|short|long).*?=.+|while\s*\(.+?\)/gi;

while ( i-- ){
   var current = blocks[i];
   if ( cReg.test( current ) ){
      console.log("found code in block[" +  i + "]");
   }
}

Answer 11

Simply count words / punctuation character for each line. English will tend to have 4 or more, code less than 2.

The paragraph above has 18 words, and 4 punctuation characters, for example. This paragraph has 19 words and 4 punctuation, so within expectations.

Of course, this would need to be tested against newbie poor-english speakers questions, and it may be that in those cases, the statistics are skewed.

I expect that [non-whitespace].[whitespace or newline] is very rare in code, but common in English, so this could be counted as words, not punctuation.

I think the biggest problem will be inline code, where someone asks a question like:

If I say for (i=0; i>100; i++) {} what does that mean?

That's code and English, and should be marked up as with back-ticks:

If I say for (i=0; i>100; i++) {} what does that mean?

Answer 12

I think you should first make a distinction between (sufficiently) formatted code that only needs to be actually designated as such, and (too) poorly formatted code, which needs manual formatting anyway.

Formatted code has breaklines and indentation. That is: if a line is preceded by a single breakline, you have a good candidate. If it has leading whitespaces on top of that, you have a very good candidate.

Normal text uses two breaklines or two spaces and a breakline for formatting, so there's a clear criterion for distinction.

In LISP code you will not find semicolons, in Ruby code you may not find parenthesis, in pseudo code you might not find much at all. But in any (non-esoteric) language you will find decent code to be formatted with breaklines and indentation. There's nothing as universal as that. Because in the end code is, written to be read by humans.

So first, search for potential lines of code. Also, lines of code usually come in groups. If you have one, there's a good chance that the one above or below is a line of code as well.

Once you have singled out potential lines of code, you can check them against quantifiable criteria and pick some threshold:

• frequence of non-word characters
• frequence of identifiers: very short words or very long words with CamelCase or under_score style
• repetition of uncommon words

Also, now that there is programmers and cs, stackoverflow's scope is clearly narrowed down. One might consider denoting all language tags as languages. And when posting, you'd be asked to either pick at least one language tag, pick the language-agnostic tag or to explicitly omit it.

In the first case you know which languages to look for, in the second case, you might want to look for pseudo-code and in the last case, there probably won't be any code, because it's a question related to some technology or framework or such.

Answer 13

You could create a parser for each language you want to detect (language definitions for ANTLR are usually easy to find), then run each line of the question through each parser. If any line parses correctly, you probably have code.

The problem with this is that some english (natural language) sentences may parse as code, so you may want to include some of the other ideas as well, or you could limit positive results only if more than one or two consecutive lines parse correctly with the same language parser.

The other potential issue is that this will probably not pick up pseudocode, but that may be OK.

Answer 14

What may be the most future-proof and require the least manual adjustment in the long run ,as other languages (which look somewhat different than the programming languages used most now) become more popular and the currently used languages become less popular, is to do something like what Google Translate does (see the paragraph titled "How does it work?"), instead of looking for certain things like a.b and a(), etc.

In other words, instead of manually thinking of patterns found in code to look for, the computer can figure it out by itself. This can be done by having

1. lots of code in many different programming languages

   • Suggestion: automatically take code samples from web-based source code repositories like Google Code or Github, or even from things on Stackoverflow already marked as code

   • Note: it may be a good idea to parse out code comments

2. lots of english text taken from articles on the web

   • although not from articles about programming (otherwise they may have code in them and mix the system up :-) )

and having some kind of algorithm automatically find patterns in the code that are not in the english, and vice versa, and using those patterns to detect what is code and what is not code by running the algorithm on posts.

(However, I am not sure how such an algorithm would work. Other answers to the current question may have useful information for that.)

Then the system can re-scan the code every once in a while to account for changes in the way code looks at that point in time.