Syntax Highlighting / Lexical analysis Algorithms

Question

What is the general algorithm used by a syntax highlighter? I have implemented a simple approach using alternation in regex:

STRING_PATTERN|COMMENT_PATTERN|KEYWORD_PATTERNS

Since detecting whether something is a string or a pattern depends on which comes first:

// This is a "comment"

"This is a // string"

But it gets a bit more complicated with keywords. This approach is working in my current implementation, but I'm not convinced it's optimal.

Another problem is the order you highlight in. If you highlight numbers before identifiers/keywords then you might accidentally highlight a number within a keyword...

EDIT:

My plugin is now here: http://wordpress.org/extend/plugins/crayon-syntax-highlighter/

Answer 1

You might struggle to do this with regex because it doesn't help your syntax highlighting understand the context, i.e. a regex will match something that appears anywhere, irrespective of whether it's part of a larger possible match.

You need to investigate parser generators such as Antlr which - given a valid, unambiguous grammar - are capable of giving you tokens that take these details into account. E.g. if a comment is defined as "//" up to an EOL, it will return a comment token, which will supersede any string characters or whatever inside.

The standard approach for parsers like this is to read in the stream of characters (or tokens, more specifically) one at a time, so the highlighting depends not on the order of the rules you define but the order of their appearance in the stream.

For example, a string could be two double-quote marks and everything in between (except for another double quote). A comment is two slashes and everything up to the end-of-line.

When parsing, if you find a double-quote then your program goes into a "I think it's a string" mode and once it finds the matching end-quote it confirms a string token, and returns it for highlighting. Similarly, if it finds two slashes then it searches until it finds an end-of-line (or end-of-file, in reality), then returns that as a token for highlighting.

It gets more complicated when there are multiple possible matching rules, e.g. for single and multi line comments. If you grab a single slash character, your program needs to read another character before it can reject some of those options, i.e. until it gets either a second slash or * then it won't know what sort of token it's in.

Fundamentally it all comes down to state machines. You could try building your own, or you could get something like Antlr, feed it a grammar, and let it do all your work for you.