Three Algorithms for YSH Syntax Highlighting

Summary

Three Algorithms for YSH Syntax Highlighting On Zulip, I was asked how to write a syntax highlighter for YSH. Let's compare these ways of doing it: Coarse Parsing Editors like Vim and TextMate use the model of regexes + a context stack. With this model, we can recognize YSH "lexer modes", and produce an accurate highlighter. Coarse does not mean inaccurate! Context-Free Parsing Tree-sitter uses the model of resilient, incremental context-free parsing. YSH should eventually have a Tree-sitter grammar. But creating one is tricky because context-free grammars are too limited for "real languages". Recognizing most languages (Python, JavaScript, C) with Tree-sitter requires writing C code in an external scanner, and the same is true for YSH. Full Parsing We could use the YSH parser itself to create a 100% accurate syntax highlighter. ysh --tool syntax-tree myscript.ysh shows you the syntax tree. This likely wouldn't be useful in text editors. So, different tools have different computational models, and we have to express YSH syntax within those limits. After writing this Vim plugin for YSH, I wrote docs describing the "coarse parsing" algorithm, linked below. It's perhaps surprising that coarse parsing is not only easier than context-free parsing, but more accurate. For evidence of that, see the bugs fixed in tree-sitter-bash, particularly in the external scanner: Background on YSH Syntax YSH syntax is derived from Unix shell syntax, which means that it has lexer modes. The modes are roughly: Commands - echo hi Double-Quoted Strings - echo "sum = $[x + 42], today is $(date)" Expressions - var x = 42 + a[i] This makes YSH different than C or Java, but the same is true of Python and JavaScript. They grew more shell-like when they added string interpolation, in the 2010's: console.log(`sum = ${x + 42}`) // JavaScript print(f'sum = {x + 42}') # Python (See demo/nested.py and demo/nested.js.) Algorithm 1: Coarse Parsing - Vim, TextMate With coarse parsing, we break the proble...