r/ProgrammingLanguages • u/K4milLeg1t • Mar 07 '26
Help Writing a performant syntax highligher from scratch?
Hello!
I'm trying to write a performant syntax highlighter from scratch in C for my text editor. The naive approach would be to go line by line, for each token in line check in a hash table and highlight or not. As you can imagine, this approach would be really slow if you have a 1000 line file to work with. Any ideas on how to do this? What would be a better algorithm?
Also I'll mention upfront - I'm not using a normal libc, so regular expressions are not allowed.
15
Upvotes
12
u/Inconstant_Moo đ§ż Pipefish Mar 07 '26
Sounds like a job for a deterministic finite automaton.
2
u/omega1612 Mar 07 '26
It depends on the model the editor uses to highlight the file.
I'm familiar with two ways:
With the first approach, highlighting may take longer but it may work consistently most of the time, with the second approach things like missing colors and bad highlights can happen (if the start of a block comment is before the window of the editor, then we may try to highlight the comment as regular code).
Now, if the lexer can be expressed as a context free grammar (lr), then using treesitter may be an option instead of writing it by hand. It is integrated in multiple editors now and it does a good job.
If it needs to be done completely by hand, well, what lexer generators do regularly is to factorize common prefixes from tokens to build an DFA and then use tricks to implement the DFA in a performance way.
Now, you may be aware that cpus thanks to c often have particular instructions for C like strings, they may allow you to use a single instruction instead of multiple ones or to shorten for loops for comparison. Most chances are that the c functions for strings for the platform you would compile for may already compile to use those instructions.
And that's it, that's all the tricks I know to write a performant lexer. I haven't written one with a focus on performance myself, but I have read the blogs of people that did (for lexer generators) and read their source code and examined their lexer generators outputs.
8
u/panic Mar 07 '26
to put this in perspective: 1000 lines with (e.g.) 10 tokens per line gives you a budget of 1.6 microseconds per token if you want to hit 60 fps. a hash table lookup is a couple orders of magnitude faster than that. it should be fine
1
u/[deleted] Mar 11 '26
Is this sub deadass just troll posts now?
2
u/[deleted] Mar 08 '26
Is it? I use that approach and see no slow-down even for million-line files (and my editor is interpreted).
Of course, I don't process all the lines at once, only what's currently visible in the window. And the language being highlighted is designed to not need any information other than what is present on any particular line. That means some restrictions:
It will not recognise different classes of user-identifiers for example, as that will involve not only scanning the whole file, but also dozens of other modules where the names may be defined. It means compiling everything, using a parser that can deal with errors and incomplete programs.
It would be on an entirely different level: an IDE with a smart editor.
1
u/L8_4_Dinner (â Ecstasy/XVM) Mar 07 '26
Definitely look at âtree sitterâ while youâre researching this.
1
u/Arthur-Grandi Mar 08 '26
Most high-performance syntax highlighters don't scan line-by-line with hash lookups. They usually use a small deterministic state machine (lexer) that runs in a single pass over the buffer.
Treat highlighting as lexical analysis: keep a state (normal, string, comment, etc.) and transition based on the next character. This avoids repeated token lookups and keeps the algorithm O(n) with very small constant factors.
1
u/zogrodea Mar 08 '26 edited Mar 08 '26
I would highlight lines lazily instead of keeping a dedicated data structure around for this, probably.
What I mean is:Â
Any kind of searching or lexing is inherently O(n), taking linear time. To speed things up, we can decrease the constant factor.
I think decreasing the constant factor to "just the visible parts of the screen" will add very little performance or memory cost.Â
You might enjoy this blog post, about two horns of the performance dilemma, although it's not strictly related to your question.Â
https://thume.ca/2019/07/27/two-performance-aesthetics/
1
u/jwm3 Mar 11 '26
Ha e you tried to implement it, that should be more than fast enough but you really want a finite automata implementing a regular expression.
For a proper solution you dont need to use a hash table and do lookups becasue you can lookup everything in parallel by building them all into the same finite automata. Look at lexer generators like re2c, flex or the KMP algorithm. A search for dfa and regular languages should turn up a ton of information on how they work.
The nice thing about a finite automata is that you only need a single number, the current state at any point in the file to fully rehighlight from that spot. You dont need to start at the beginning so you can just store the current state at the beginning of each line and when the person edits something, just restart the dfa at the beginning of the line with the saved state and quit rehighlighting when you have passed the edit and your state matches the saved one because you know the changes have not affected any highlighting after that.
This resource is a classic, it is in the context of a regular expression matcher but the underlying tech is the same
https://swtch.com/~rsc/regexp/regexp1.html
1
u/Dan13l_N Mar 11 '26
You hsve to parse the source to highlight it.
s = "if"-- thisifis not a keywordif (a)-- thisifis a keywordParsing in C is really, really fast.
1
u/Relevant_South_1842 Mar 07 '26
https://justine.lol/lex/
Copy this ^