Создаём DSL на C#: Пишем парсер

Давно не было статьей, я просто хотел выпускать 1 статью в раз неделю, но не успевал, поэтому забросил и начал поиск работы. Не давно решил продолжить, и какого было мое удивление что работы оставалось на 3 дня. Чтож надеюсь следующую серию я выпишу быстрее.

1. Создаём синтаксис

2. Пишем парсер

3. Собираем blender

4. Добавляем семантику

5. Диагностика

6. Интегрируем Language Server Protocol и делаем поддержку в Visual Studio

7. Генерируем код

Работа с SourceText

Мы, конечно, могли бы создать свой аналог SourceText, но в этом откровенно мало смысла. В Roslyn уже есть готовая абстракция исходного текста, и почти всё, что нам нужно для парсера, у неё уже есть: доступ к символам по индексу, длина текста, работа со строками, получение подстрок, вычисление checksum и создание текста из строки, потока или массива байтов.

Чем же он так полезен? Во-первых, можно меньше думать о низкоуровневой работе с кодировками. SourceText умеет хранить информацию о кодировке исходного файла, а в самом парсере мы можем работать не с байтами, а с привычными для дотнета строками и char. Это сильно упрощает код лексера и парсера.

Во-вторых, SourceText не обязательно должен быть просто одной строкой. Внутри Roslyn есть разные реализации для разных сценариев: обычный текст, большой текст, текст после изменений и композиция из сегментов. То есть нам не нужно заранее решать, как именно хранить исходный файл в памяти. Мы можем опираться на уже готовую инфраструктуру Roslyn.

Поэтому, поизучав этот вопрос, я решил не создавать копию SourceText, а использовать существующую реализацию. Возможно в будущем мне это аукнется кстати, но надеюсь что нет.

TextWindow

Но как я упоминал ранее SourceText может состоять из сегментов текста, и доступ к конкретному символу может работать медленнее из-за дополнительных операция и проверок, поэтому что мы делаем это банально сразу запрашиваем небольшой кусок текста

using Microsoft.CodeAnalysis.Text;namespace Akbura.Language;internal struct SlidingTextWindow{    public const char InvalidCharacter = char.MaxValue;    public const int DefaultWindowLength = 1024;    private static readonly ObjectPool<char[]> s_windowPool =        new(() => new char[DefaultWindowLength]);    public SourceText Text { get; }    private readonly int _textEnd;    private int _positionInText;    private ArraySegment<char> _characterWindow;    private int _characterWindowStartPositionInText;    public SlidingTextWindow(SourceText text)    {        Text = text;        _textEnd = text.Length;        _characterWindow = new ArraySegment<char>(s_windowPool.Allocate());        ReadChunkAt(0);    }    private void ReadChunkAt(int position)    {        position = Math.Min(position, _textEnd);        var amountToRead = Math.Min(_textEnd - position, DefaultWindowLength);        Text.CopyTo(            position,            _characterWindow.Array!,            0,            amountToRead);        _characterWindowStartPositionInText = position;        _characterWindow = new(_characterWindow.Array!, 0, amountToRead);    }    public readonly int Position => _positionInText;    public readonly ReadOnlySpan<char> CurrentWindowSpan    {        get        {            var start = _positionInText - _characterWindowStartPositionInText;            return start < 0 || start >= _characterWindow.Count                ? default                : _characterWindow.AsSpan(start);        }    }    private readonly int CharacterWindowEndPositionInText =>        _characterWindowStartPositionInText + _characterWindow.Count;    private readonly bool PositionIsWithinWindow(int position)    {        return position >= _characterWindowStartPositionInText &&               position < CharacterWindowEndPositionInText;    }    public void Reset(int position)    {        _positionInText = Math.Min(position, _textEnd);        if (PositionIsWithinWindow(_positionInText))        {            return;        }        ReadChunkAt(_positionInText);    }    public readonly bool IsReallyAtEnd()    {        return Position >= _textEnd;    }    public void AdvanceChar(int count)    {        _positionInText += count;    }    public char PeekChar()    {        if (IsReallyAtEnd())        {            return InvalidCharacter;        }        var position = _positionInText;        if (!PositionIsWithinWindow(position))        {            ReadChunkAt(position);        }        return _characterWindow.Array![position - _characterWindowStartPositionInText];    }}

Справедливости ради не только этим занимается TextWindow, но эта структура была создана по сути только ради этого, остальные API это очень приятные и удобные плюшки.

Интернирование строк

В C# одинаковые строковые литералы обычно не создаются как разные объекты. Например:

var a = "Hello";var b = "Hello";Console.WriteLine($"Is same object? {object.ReferenceEquals(a, b)}");

В большинстве обычных случаев этот код выведет true, потому что строковые литералы попадают в intern pool. CLR хранит таблицу интернированных строк и может возвращать одну и ту же ссылку для одинаковых строковых значений.

Но код, который мы парсим, приходит уже во время выполнения программы. Например, если в исходном файле несколько раз встречается один и тот же идентификатор, то при обычном создании строк мы можем получить несколько разных объектов string с одинаковым текстом.

button {    color: red;}button {    background: red;}

Здесь button и red встречаются повторно. Если каждый раз создавать новую строку, мы будем тратить лишнюю память. Поэтому в SlidingTextWindow(та самая приятная плюшка) используется своя таблица строк. Она работает как локальный кэш: если такая строка уже встречалась, мы можем вернуть уже существующий объект, а не создавать новый.

internal struct SlidingTextWindow{    private readonly StringTable _strings;    public SlidingTextWindow(SourceText text)    {        this.Text = text;        _textEnd = text.Length;        _strings = StringTable.GetInstance();        _characterWindow = new ArraySegment<char>(s_windowPool.Allocate());        // Read the first chunk of the file into the character window.        this.ReadChunkAt(0);    }    public readonly string Intern(StringBuilder text)    {        return _strings.Add(text);    }    public readonly string Intern(char[] array, int start, int length)        => Intern(array.AsSpan(start, length));    public readonly string Intern(ReadOnlySpan<char> chars)        => _strings.Add(chars);}

Важно, что здесь используется не глобальный string.Intern, а собственный StringTable. Это полезно для парсера: таблица живёт только столько, сколько нужен SlidingTextWindow, и не загрязняет глобальный intern pool приложения.

Важный момент мы не будет интернировать все, а только часто повторяющие элементы, идентификаторы, литералы или даже пробелы. Так ключевые слова уже закешированы, и пунктуация кстати тоже.

Давайте подробнее разберем как работает StringTable

StringTable это не полноценная замена string.Intern, а локальный lossy cache строк. Он не хранит строки вечно и не гарантирует дедупликацию всех строк. Его задача гораздо проще: быстро переиспользовать часто встречающиеся значения во время парсинга.

Внутри StringTable есть два уровня кэша: локальный L1-кэш и общий shared L2-кэш.

Сначала строка ищется в локальной таблице. Это самый быстрый путь: индекс вычисляется напрямую из хеша, после чего проверяется одна запись.

private static int LocalIdxFromHash(int hash){    return hash & LocalSizeMask;}

Упрощённо это выглядит так:

посчитать hash => взять один индекс => проверить одну запись

Если запись совпала по хешу и тексту, StringTable сразу возвращает уже существующий объект string.

Если в L1-кэше промах, проверяется общий shared L2-кэш:

private static readonly SegmentedArray<Entry> s_sharedTable = new(SharedSize);

L2-кэш общий для разных экземпляров StringTable, поэтому он помогает переиспользовать строки между разными парсерами. Например, если один парсер уже встретил строку button, другой экземпляр парсера может получить тот же объект строки через shared-кэш.

Поиск в L2 устроен сложнее. Там проверяется небольшой bucket, а обход выполняется через quadratic probing.

Что такое quadratic probing?

Quadratic probing — это способ обхода bucket в hash table при коллизиях. Если первая ячейка занята, проверяются позиции по квадратичной последовательности: 0, 1, 3, 6, 10 и так далее. Такой обход распределяет проверки и замены по bucket.

for (var i = 1; i < SharedBucketSize + 1; i++){    e = arr[idx].Text;    var hash = arr[idx].HashCode;    if (e != null)    {        if (hash == hashCode && TextEquals(e, chars))        {            break;        }        e = null;    }    else    {        break;    }    idx = (idx + i) & SharedSizeMask;}

Из-за этого L2-кэш работает тяжелее, чем L1:

1. он общий для разных экземпляров StringTable;

2. он больше по размеру;

3. при поиске проверяется bucket;

4. при записи используется Volatile.Write;

5. для общего счётчика используется Interlocked.Increment.

Если строка нашлась в shared-кэше, она возвращается и одновременно записывается обратно в локальный L1-кэш. Следующий доступ к этой же строке уже сможет пройти по быстрому пути.

Если строка не найдена ни в L1, ни в L2, она создаётся через ToString() или Substring(), после чего добавляется в оба кэша.

Замена элементов в shared-кэше

Shared-кэш ограничен по размеру. При добавлении новой строки код сначала пытается найти свободное место в bucket:

for (var i = 1; i < SharedBucketSize + 1; i++){    if (arr[curIdx].Text == null)    {        idx = curIdx;        goto foundIdx;    }    curIdx = (curIdx + i) & SharedSizeMask;}

Если свободного места нет, выбирается одна позиция внутри bucket и заменяется новой строкой.

Для выбора позиции используется дешёвый псевдослучайный механизм. Счётчик стартует со значения на основе Guid.NewGuid().GetHashCode():

private int _localRandom = Guid.NewGuid().GetHashCode();private static int s_sharedRandom = Guid.NewGuid().GetHashCode();

Дальше это значение просто увеличивается. Такой механизм не похож на полноценный Random.Next(), но для выбора позиции в bucket этого достаточно.

var i1 = LocalNextRandom() & SharedBucketSizeMask;idx = (idx + ((i1 * i1 + i1) / 2)) & SharedSizeMask;

LocalNextRandom() даёт меняющееся число, а & SharedBucketSizeMask ограничивает его размером bucket. После этого используется та же формула, что и в quadratic probing:

(n² + n) / 2

Так замены распределяются по разным позициям bucket, а кэш не вытесняет постоянно одну и ту же ячейку.

Короткий итог

L1-кэш используется для самого быстрого доступа внутри текущего экземпляра StringTable.

L2-кэш помогает переиспользовать строки между разными экземплярами StringTable.

Оба уровня являются lossy cache. Строка может быть вытеснена, и это нормально. В исходном коде обычно есть высокая локальность данных: одни и те же идентификаторы, ключевые слова и литералы встречаются много раз. Поэтому даже ограниченный кэш помогает уменьшить количество повторных аллокаций.

Делаем Lexer

Во многих статьях про компиляторы цепочка выглядит примерно так:

Tokenizer => Parser

Иногда ещё пишут:

Tokenizer => Lexer => Parser

Но в Roslyn-подобной архитектуре такая схема не очень хорошо описывает происходящее. Тут важно уточнить: слова tokenizer и lexer часто используют почти как синонимы. Поэтому проблема не в названии класса. Проблема в идее отдельного простого слоя, который просто режет текст на куски, а потом кто-то другой превращает эти куски в нормальные синтаксические токены.

В нашем случае такой промежуточный слой только добавил бы лишнюю работу. Минимальная самостоятельная единица green tree — это не просто «тип токена и текст», а GreenSyntaxToken. Он уже может содержать leading trivia, trailing trivia, диагностические данные и, в случае литералов, ещё и распарсенное значение.

То есть если сделать отдельный простой tokenizer, то он, скорее всего, будет производить что-то вроде:

TokenKind + text + position

А потом всё равно пришлось бы превращать это в:

GreenSyntaxToken    leading trivia    kind    value    trailing trivia    diagnostics

Получается лишний этап:

SourceText    ↓Tokenizer    ↓Intermediate token    ↓GreenSyntaxToken    ↓Parser

А практической пользы от этого почти нет. Поэтому, как и в Roslyn, lexer сразу производит синтаксические токены, пригодные для построения дерева.

Почему lexer не просто режет текст

Один и тот же символ может иметь разный смысл в зависимости от места, где он встретился. Самый простой пример:

+ // это PlusToken"asdas + sadas d"// это один StringLiteralToken;// знак + внутри строки не является отдельным токеном

Символ < тоже хороший пример:

<      // LessThanToken<=     // LessEqualsToken</div> // LessSlashToken, IdentifierToken, GreaterThanToken

В Akbura ситуация ещё интереснее, потому что внутри языка могут встречаться участки C#-кода. Поэтому lexer должен уметь менять режим работы.

LexerMode

В моём lexer есть LexerMode:

internal enum LexerMode{    TopLevel = 0,    InInlineExpression = 1 << 0,    InExpressionUntilSemicolon = 1 << 1,    InExpressionUntilComma = 1 << 2,    InArgumentExpression = 1 << 3,    InMarkup = 1 << 4,    InTypeName = 1 << 5,    InAkcss = 1 << 6,    InCSharpParameterList = 1 << 7,    InCSharpArgumentList = 1 << 8,}

Идея такая: parser может попросить lexer прочитать следующий участок текста не в обычном режиме, а в специальном контексте. Например:

TopLevel    обычный режим языка AkburaInAkcss    режим внутри akcss-блокаInInlineExpression    C#-выражение до }InExpressionUntilSemicolon    C#-выражение до ;InExpressionUntilComma    C#-выражение до ,InArgumentExpression    C#-аргумент до , или )InTypeName    C#-типInCSharpParameterList    C#-список параметровInCSharpArgumentList    C#-список аргументов

Это уже не похоже на простой tokenizer. Lexer не просто идёт по тексту и отдаёт очередной кусок. Он знает, в каком режиме находится, и выбирает другой способ чтения.

Главный метод выглядит так:

public GreenSyntaxToken Lex(LexerMode mode){    _mode = mode;    if (mode != LexerMode.TopLevel && mode != LexerMode.InAkcss)    {        var tokenInfo = mode switch        {            LexerMode.InInlineExpression => ParseInlineExpression(),            LexerMode.InExpressionUntilSemicolon => ParseExpressionUntilSemicolon(),            LexerMode.InExpressionUntilComma => ParseExpressionUntilComma(),            LexerMode.InArgumentExpression => ParseArgumentExpression(),            LexerMode.InTypeName => ParseTypeName(),            LexerMode.InCSharpParameterList => ParseCSharpParameterList(),            LexerMode.InCSharpArgumentList => ParseCSharpArgumentList(),            _ => default        };        return CreateToken(in tokenInfo, null, null, null);    }    if (TryQuickScanToken(mode, out var quickToken))    {        return quickToken;    }    return ParseNextToken();}

Здесь хорошо видно общую схему:

если режим C#-вставки    читаем кусок как C# и возвращаем CSharpRawTokenиначе    пробуем quick scannerесли quick scanner не справился    запускаем обычный полный lexer

Обычный путь: ParseNextToken

Когда lexer находится в TopLevel или InAkcss, он читает обычный токен Akbura. Делается это через ParseNextToken:

private GreenSyntaxToken ParseNextToken(){    var tokenInfo = ParseNextTokenInfo(        out var leading,        out var trailing,        out var errors);    return CreateToken(in tokenInfo, leading, trailing, errors);}

А внутри ParseNextTokenInfo токен собирается из трёх частей:

private TokenInfo ParseNextTokenInfo(    out GreenSyntaxListBuilder leading,    out GreenSyntaxListBuilder trailing,    out ImmutableArray<AkburaDiagnostic> errors){    _leadingTriviaCache.Clear();    LexSyntaxTrivia(isTrailing: false, triviaList: ref _leadingTriviaCache);    leading = _leadingTriviaCache;    TokenInfo tokenInfo = default;    Start();    ParseSyntaxToken(ref tokenInfo);    errors = GetErrors();    _trailingTriviaCache.Clear();    LexSyntaxTrivia(isTrailing: true, triviaList: ref _trailingTriviaCache);    trailing = _trailingTriviaCache;    return tokenInfo;}

Сначала lexer читает leading trivia, потом сам токен, потом trailing trivia.

Например:

/* comment */ button

Комментарий перед button не исчезает. Он становится частью leading trivia токена button. Это важно для Roslyn-подобной архитектуры, потому что дерево должно сохранять исходный текст достаточно точно: пробелы, переносы строк и комментарии нельзя просто выбросить.

Trivia

Trivia — это то, что не является основным синтаксисом, но всё равно принадлежит исходному тексту:

пробелыпереносы строкоднострочные комментариимногострочные комментарии

В lexer это обрабатывается отдельно:

private void LexSyntaxTrivia(bool isTrailing, ref GreenSyntaxListBuilder triviaList){    while (true)    {        Start();        var character = TextWindow.PeekChar();        if (character == SlidingTextWindow.InvalidCharacter)        {            return;        }        if (character > 127)        {            if (SyntaxFacts.IsWhitespace(character))            {                character = ' ';            }            else if (SyntaxFacts.IsNewLine(character))            {                character = '\n';            }        }        switch (character)        {            case ' ':            case '\t':            case '\v':            case '\f':            case '\u001A':                AddTrivia(ScanWhitespace(), ref triviaList);                break;            case '\r':            case '\n':                var eol = ScanEndOfLine();                AddTrivia(eol, ref triviaList);                if (isTrailing)                {                    return;                }                break;            case '/':            {                var next = TextWindow.PeekChar(1);                if (next == '/')                {                    LexSingleLineComment(ref triviaList);                    break;                }                if (next == '*')                {                    LexMultiLineComment(ref triviaList);                    break;                }                return;            }            default:                return;        }    }}

Тут есть важное правило: trailing trivia останавливается на переносе строки. То есть комментарий или пробел после токена может быть trailing trivia, но если встретился перенос строки, следующий токен уже начнёт новую строку.

Пробелы тоже оптимизированы. Один обычный пробел вообще не создаёт новый объект, а возвращается как готовая trivia:

if (this.CurrentLexemeWidth == 1 && onlySpaces){    return GreenSyntaxFactory.Space;}

А короткие последовательности пробелов могут проходить через кэш:

if (width < MaxCachedTokenSize){    return _cache.LookupWhitespaceTrivia(        TextWindow,        this.LexemeStartPosition,        hashCode);}

Это мелочь, но такие мелочи очень важны. В реальном коде пробелов и переносов строк много, поэтому даже trivia нужно обрабатывать аккуратно.

ParseSyntaxToken

После leading trivia lexer вызывает ParseSyntaxToken. Это основной метод для чтения обычных токенов Akbura. Он смотрит на текущий символ и выбирает, что делать дальше.

Упрощённо это выглядит так:

private void ParseSyntaxToken(ref TokenInfo info){    var character = TextWindow.PeekChar();    switch (character)    {        case '+':            TextWindow.AdvanceChar();            info.Kind = SyntaxKind.PlusToken;            return;        case '<':            TextWindow.AdvanceChar();            if (TextWindow.TryAdvance('/'))            {                info.Kind = SyntaxKind.LessSlashToken;                return;            }            if (TextWindow.TryAdvance('='))            {                info.Kind = SyntaxKind.LessEqualsToken;                return;            }            info.Kind = SyntaxKind.LessThanToken;            return;        case >= '0' and <= '9':            ScanNumericLiteral(ref info);            return;        case '_':        case >= 'a' and <= 'z':        case >= 'A' and <= 'Z':            ScanIdentifierOrKeyword(ref info);            return;    }}

Этот метод показывает, почему lexer не может быть совсем «тупым». Например, символ < может означать сразу несколько вещей:

<  => LessThanToken<= => LessEqualsToken</ => LessSlashToken

То же самое с =:

=  => EqualsToken== => EqualsEqualsToken=> => ArrowToken

И с точкой:

.  => DotToken.. => DoubleDotToken

Lexer обязан смотреть вперёд, иначе он не сможет правильно определить границу токена.

Идентификаторы и ключевые слова

Идентификатор кажется простой вещью, но на практике его лучше читать в два этапа: быстрый путь для частого случая и медленный путь для сложных случаев.

private bool TryParseIdentifier(ref TokenInfo token){    if (TryParseIdentifier_Fast(ref token))    {        return true;    }    return TryParseIdentifier_Slow(ref token);}

Быстрый путь работает только для обычных ASCII-идентификаторов:

[_a-zA-Z][_a-zA-Z0-9]*

Он читает текст прямо из CurrentWindowSpan, быстро проверяет символы и завершает идентификатор на известных разделителях. Если всё хорошо, текст интернируется:

var text = TextWindow.Intern(span[..length]);token.Text = text;token.Kind = SyntaxKind.IdentifierToken;

Но если встречается что-то сложное, например Unicode-символ, escape sequence или surrogate pair, быстрый путь возвращает false, и lexer переходит к медленному пути.

Медленный путь уже умеет больше:

Unicode lettersUnicode escape sequences: \uXXXX, \UXXXXXXXXsurrogate pairsformatting charactersescaped identifier sequences

И вот тут снова видна та же философия:

частый случай — быстросложный случай — медленнее, но корректно

После чтения идентификатора lexer проверяет, не является ли он ключевым словом:

if (_cache.TryGetKeywordKind(info.Text, out var keywordKind)){    if (SyntaxFacts.IsContextualKeyword(keywordKind))    {        info.Kind = SyntaxKind.IdentifierToken;        info.ContextualKind = keywordKind;    }    else    {        info.Kind = keywordKind;        info.ContextualKind = keywordKind;    }}

Тут есть важное отличие hard keyword от contextual keyword.

Hard keyword сразу становится отдельным токеном. А contextual keyword лексически остаётся IdentifierToken, но внутри несёт дополнительный ContextualKind. Это нужно, потому что значение такого слова зависит от места в синтаксисе. Parser потом сможет решить, использовать его как ключевое слово или как обычный идентификатор.

Числовые литералы

Числа — это отдельная большая часть lexer. На первый взгляд число — это просто несколько цифр подряд. Но на практике нужно поддерживать намного больше вариантов:

1231_000_0000xFF0b1010123u123L123UL1.51e101.5f1.5d1.5m

Метод ScanNumericLiteral сначала определяет, какой это литерал:

decimalhexadecimalbinaryreal numberinteger with suffixfloating-point with suffix

Например, если число начинается с 0x или 0X, оно читается как hex:

if (character == '0'){    character = TextWindow.PeekChar(1);    if (character == 'x' || character == 'X')    {        TextWindow.AdvanceChar(2);        isHex = true;    }    else if (character == 'b' || character == 'B')    {        TextWindow.AdvanceChar(2);        isBinary = true;    }}

Для обычных десятичных чисел lexer отдельно проверяет дробную часть:

if ((character = TextWindow.PeekChar()) == '.'){    var ch2 = TextWindow.PeekChar(1);    if (ch2 >= '0' && ch2 <= '9')    {        hasDecimal = true;        _builder.Append(character);        TextWindow.AdvanceChar();        ScanNumericLiteralSingleInteger(            ref underscoreInWrongPlace,            ref usedUnderscore,            ref firstCharWasUnderscore,            isHex: false,            isBinary: false);    }}

То есть 123.332 становится одним NumericLiteralToken, потому что точка находится между цифрами и является частью числового литерала.

Также lexer обрабатывает exponent:

1e101E-101.5e+3

И суффиксы:

f / F => floatD / d => doublem / M => decimalu / U => uint или ulongL / l => long или ulong

После этого lexer не просто сохраняет текст числа, а сразу определяет его тип и значение:

info.Kind = SyntaxKind.NumericLiteralToken;info.Text = this.GetInternedLexemeText();var valueText = TextWindow.Intern(_builder);

Для целых чисел используется UInt64.TryParse или отдельный разбор binary-чисел, а потом выбирается самый подходящий тип:

intuintlongulong

Например, если число без суффикса помещается в int, оно станет System_Int32. Если не помещается, lexer попробует uint, потом long, потом ulong.

Для float и double используется отдельный класс RealParser (эхх вспомнил школьные года как писал на Pascal Abc.Net):

private float GetValueSingle(string text){    if (!RealParser.TryParseFloat(text, out var result))    {        this.AddError(ErrorCodes.ERR_FloatOverflow, ["float"]);    }    return result;}private double GetValueDouble(string text){    if (!RealParser.TryParseDouble(text, out var result))    {        this.AddError(ErrorCodes.ERR_FloatOverflow, ["double"]);    }    return result;}

RealParser нужен не просто для вызова float.Parse или double.Parse. Он конвертирует десятичный floating-point literal в ближайшее представимое IEEE-значение и использует округление round-to-nearest, ties-to-even. Также он не поддерживает ведущий знак, потому что в C# и похожих языках -1.0 — это не один отрицательный числовой токен, а оператор unary minus плюс положительный литерал 1.0.

И это важный момент: lexer читает именно литерал. Знак - остаётся отдельным токеном, а отрицательное число появляется уже на уровне синтаксиса или семантики.

Для decimal используется decimal.TryParse, потому что decimal в .NET — это отдельный тип с другими правилами представления:

private decimal GetValueDecimal(string text, int start, int end){    if (!decimal.TryParse(        text,        NumberStyles.AllowDecimalPoint | NumberStyles.AllowExponent,        CultureInfo.InvariantCulture,        out var result))    {        this.AddError(start, end - start, ErrorCodes.ERR_FloatOverflow, ["decimal"]);    }    return result;}

В итоге NumericLiteralToken хранит не только исходный текст, но и уже готовое значение нужного типа. Это ещё одна причина, почему простой tokenizer был бы слишком слабым слоем для такой архитектуры.

C#-фрагменты внутри Akbura

Одна из особенностей Akbura — возможность использовать C#-выражения или типы внутри своего синтаксиса. В таких местах lexer не пытается вручную разбирать весь C# заново. Вместо этого он собирает нужный фрагмент текста и передаёт его Roslyn.

Например, inline expression читается до }:

private TokenInfo ParseInlineExpression(){    return ParseExpressionUntil('}');}

Но просто читать до первой } нельзя. Внутри выражения могут быть скобки:

SomeMethod(new { Value = 10 })

Поэтому lexer следит за глубиной вложенности:

var paren = 0;var brace = 0;var bracket = 0;

И останавливается только тогда, когда встретил terminator на нулевой глубине:

if (character == terminator && paren == 0 && brace == 0 && bracket == 0){    break;}

После этого собранный текст передаётся в Roslyn:

var parsed = CSharpSyntaxFactory.ParseExpression(    expressionText,    0,    options: null,    consumeFullText: true); tokenInfo.CSharpNode = parsed; tokenInfo.CSharpSyntaxKind = parsed.Kind();

Для типов используется ParseTypeName:

var parsed = CSharpSyntaxFactory.ParseTypeName(    sourceText,    startParse,    options: null,    consumeFullText: false);

Для списков параметров:

var parsed = CSharpSyntaxFactory.ParseParameterList(    sourceText,    startParse,    options: null,    consumeFullText: false);

Для списков аргументов:

var parsed = CSharpSyntaxFactory.ParseArgumentList(    sourceText,    startParse,    options: null,    consumeFullText: false);

Наружу всё это возвращается как специальный токен:

Kind = SyntaxKind.CSharpRawToken

А в CreateToken для такого токена есть отдельная ветка:

if (tokenInfo.Kind == SyntaxKind.CSharpRawToken){    AkburaDebug.AssertNotNull(tokenInfo.CSharpNode);    return GreenSyntaxToken.CreateCSharpRawToken(tokenInfo.CSharpNode);}

То есть для Akbura это один raw-токен, но внутри него уже лежит полноценный Roslyn C# syntax node. Это позволяет не изобретать свой C# parser и не пытаться руками повторять весь синтаксис C#.

Создание GreenSyntaxToken

После того как lexer собрал TokenInfo, leading trivia, trailing trivia и diagnostics, он вызывает CreateToken.

private static GreenSyntaxToken CreateToken(    in TokenInfo tokenInfo,    GreenSyntaxListBuilder? leading,    GreenSyntaxListBuilder? trailing,    ImmutableArray<AkburaDiagnostic>? diagnostics){    var leadingNode = leading?.ToListNode();    var trailingNode = trailing?.ToListNode();    GreenSyntaxToken? token = null;    if (tokenInfo.Kind == SyntaxKind.IdentifierToken)    {        token = GreenSyntaxToken.Identifier(            leadingNode,            tokenInfo.Text!,            trailingNode);    }    else if (tokenInfo.Kind == SyntaxKind.NumericLiteralToken)    {        // Create typed numeric literal token.    }    else    {        token = GreenSyntaxFactory.Token(            leadingNode,            tokenInfo.Kind,            trailingNode);    }    if (diagnostics?.IsDefaultOrEmpty == false)    {        token = Unsafe.As<GreenSyntaxToken>(token.WithDiagnostics(diagnostics));    }    return token;}

Для обычной пунктуации достаточно SyntaxKind. Для идентификаторов нужен текст. Для числовых литералов нужен не только текст, но и значение. Поэтому NumericLiteralToken создаётся по-разному в зависимости от ValueKind:

System_Int32    => int literalSystem_UInt32   => uint literalSystem_Int64    => long literalSystem_UInt64   => ulong literalSystem_Single   => float literalSystem_Double   => double literalSystem_Decimal  => decimal literal

Если во время чтения токена появились ошибки, они прикрепляются прямо к green token:

if (diagnostics?.IsDefaultOrEmpty == false){    token = Unsafe.As<GreenSyntaxToken>(token.WithDiagnostics(diagnostics));}

Таким образом, lexer не просто возвращает тип токена. Он возвращает полноценный объект синтаксического дерева.

Ошибки и восстановление

Lexer не должен падать на первом неизвестном символе. Если он встречает неожиданную последовательность, он создаёт диагностическое сообщение и всё равно продвигается дальше.

private void ConsumeUnexpected(    ref TokenInfo info,    int startingPosition,    bool isEscaped){    var ch = TextWindow.PeekChar();    if (ch != SlidingTextWindow.InvalidCharacter)    {        TextWindow.AdvanceChar();        if (char.IsHighSurrogate(ch) && char.IsLowSurrogate(TextWindow.PeekChar()))        {            TextWindow.AdvanceChar();        }    }    info.Text = GetInternedLexemeText();    info.Kind = SyntaxKind.IdentifierToken;    AddError(ErrorCodes.ERR_UnexpectedCharacter, [messageText]);}

Тут есть несколько важных деталей.

Во-первых, lexer всё равно потребляет символ, иначе можно попасть в бесконечный цикл.

Во-вторых, если символ является началом surrogate pair, он потребляет оба char, чтобы не разорвать Unicode-символ пополам.

В-третьих, ошибка сохраняется как diagnostic и потом прикрепляется к токену.

Это нужно для нормальной работы редактора и language server. Даже если пользователь написал ошибочный код, parser всё равно должен построить хотя бы частичное дерево, чтобы IDE могла показать подсветку, диагностики и продолжить работу.

Итог

В итоге lexer в Akbura выполняет сразу несколько задач:

читает leading и trailing triviaраспознаёт punctuation tokensчитает идентификаторы и ключевые словаподдерживает contextual keywordsчитает числовые литералы и сразу определяет их значенияобрабатывает Unicode identifiers и escape sequencesумеет переключаться между LexerModeделегирует C#-фрагменты Roslyn parserсоздаёт GreenSyntaxTokenприкрепляет diagnosticsиспользует quick scanner для быстрого пути

Поэтому называть этот слой простым tokenizer было бы не совсем корректно. Tokenizer обычно ассоциируется с механическим разбиением текста на токены. Здесь же lexer является полноценной частью Roslyn-подобной архитектуры: он сохраняет trivia, учитывает режим разбора, создаёт typed literals, умеет работать с C#-вставками и сразу возвращает готовые green tokens для parser.

Фактически задача lexer превратить SourceText не просто в поток кусочков текста, а в поток полноценных синтаксических токенов, из которых parser уже сможет построить green tree.

QuickScanner

Отлично, в оригинальном рослине есть еще fast path для лексера, ровно как и для идентификаторов.

Обычный путь делает довольно много работы:

прочитать leading triviaпрочитать сам токенпрочитать trailing triviaсоздать GreenSyntaxTokenприкрепить diagnostics, если они есть

Это корректный и полный путь, но он не всегда дешёвый. В исходном коде очень много простых случаев: короткие идентификаторы, пробелы, переносы строк и простая пунктуация.

Например:

button {    color: red;}

Здесь почти всё состоит из простых токенов. Для таких случаев можно попробовать быстрый путь — QuickScanner.

Важно: QuickScanner не заменяет обычный lexer. Обычный lexer всё ещё остаётся источником истины. Quick scanner имеет право обрабатывать только простые и очевидные случаи. Если он встречает что-то сложное или сомнительное, он просто возвращает false, а дальше работает обычный lexer.

Поэтому главное правило quick scanner-а такое:

если получилось быстро и безопасно — возвращаем токенесли есть сомнение — ничего не трогаем и отдаём работу обычному lexer

В коде это правило видно здесь:

private bool TryQuickScanToken(LexerMode mode, out GreenSyntaxToken token){    var position = TextWindow.Position;    if (TryQuickScanTokenCore(mode, out token))    {        return true;    }    Debug.Assert(        TextWindow.Position == position,        "Quick scanner fallback must not consume text.");    token = null!;    return false;}

Если быстрый путь не сработал, позиция в тексте должна остаться той же самой. Это очень важно. Quick scanner может отказаться от работы, но не должен портить состояние lexer-а.

Старый QuickScanner

Сначала разберём старый вариант quick scanner-а. Его идея была простая: попробовать вручную быстро прочитать leading trivia, сам токен и trailing trivia, а потом создать готовый GreenSyntaxToken.

Упрощённая схема выглядела так:

CurrentWindowSpan    ↓прочитать leading trivia    ↓прочитать простой токен    ↓прочитать trailing trivia    ↓посчитать hash всего токена    ↓найти токен в кэше или создать новый    ↓сдвинуть TextWindow

То есть старый quick scanner пытался сделать почти всё сам.

Что он умел быстро читать

Старый вариант был рассчитан только на простые случаи:

whitespacenewlineidentifierпростое int32-числопростая punctuation

Если встречался сложный случай, scanner сразу делал fallback.

Например, комментарии не обрабатывались как простой whitespace, потому что / может означать много разных вещей:

/       обычный slash token//      однострочный комментарий/*      многострочный комментарий/>      slash-greater token

В такой ситуации безопаснее отдать работу обычному lexer.

Leading и trailing trivia

Сначала старый quick scanner пытался прочитать trivia перед токеном.

Простые пробелы и переносы строк он мог обработать быстро:

' '      whitespace'\t'     whitespace'\r'     newline или часть CRLF'\n'     newline

Но если встречался /, scanner не пытался сам разбирать комментарий и уходил в fallback.

После самого токена он делал то же самое для trailing trivia. При этом trailing trivia должна остановиться на переносе строки, потому что перенос строки обычно уже относится к границе между токенами.

Сам токен

После leading trivia scanner смотрел на первый символ токена и выбирал быстрый путь.

Примерно так:

state = ch switch{    '_' or (>= 'a' and <= 'z') or (>= 'A' and <= 'Z') => QuickScanState.Identifier,    >= '0' and <= '9' => QuickScanState.Number,    '+' or '-' or '*' or '%' or '^' or '|' or '&' or '?' or ':' or ';' or ',' => QuickScanState.Punctuation,    '.' or '=' or '!' or '<' or '>' or '{' or '}' or '[' or ']' or '(' or ')' or '/' => QuickScanState.Punctuation,    _ => QuickScanState.Bad};

Дальше для каждого типа токена был отдельный метод:

TryQuickScanIdentifierTryQuickScanDecimalInt32TryQuickScanPunctuation

То есть если это идентификатор — scanner отдельно читал identifier. Если число — отдельно пытался прочитать простое число. Если punctuation — отдельно проверял punctuation.

Identifier

Для identifier старый quick scanner читал только простой ASCII-вариант:

[_a-zA-Z][_a-zA-Z0-9]*

Если встречался Unicode, escape sequence или другой сложный символ, scanner не пытался быть умнее и возвращал false.

Это правильное поведение. Quick scanner должен покрывать частый случай, а не весь язык.

Number

С числами история похожая. Старый quick scanner мог быстро обработать только простое decimal int32:

123421000

Но такие варианты уже слишком сложные для быстрого пути:

123.451e100xFF0b10101_000123u123L

Они уходили в обычный lexer, где уже есть полноценный ScanNumericLiteral и отдельный RealParser для floating-point литералов.

Punctuation

Для punctuation был отдельный switch. Например, символ < мог превратиться в разные токены:

case '<':    if (next == '/')    {        kind = SyntaxKind.LessSlashToken;        width = 2;        return true;    }    if (next == '=')    {        kind = SyntaxKind.LessEqualsToken;        width = 2;        return true;    }    kind = SyntaxKind.LessThanToken;    width = 1;    return true;

Это работало, но такой код начинал дублировать обычный lexer. Если добавить новый punctuation token в основной lexer, нужно не забыть обновить quick scanner.

Создание токена

Главное отличие старого варианта в том, что он сам создавал токен.

После успешного чтения он собирал данные:

kindleading triviatrailing triviatextint value, если это число

А потом создавал GreenSyntaxToken напрямую:

private static GreenSyntaxToken CreateQuickToken(QuickTokenData data){    return data.Kind switch    {        SyntaxKind.IdentifierToken =>            GreenSyntaxFactory.Identifier(data.Leading, data.Text!, data.Trailing),        SyntaxKind.NumericLiteralToken =>            GreenSyntaxFactory.Literal(data.Leading, data.Text!, data.IntValue, data.Trailing),        _ =>            GreenSyntaxFactory.Token(data.Leading, data.Kind, data.Trailing)    };}

И вот здесь появляется главный минус старого подхода. Quick scanner начинает быть не просто быстрым фильтром, а маленькой второй реализацией lexer-а.

Он сам:

читает triviaчитает identifierчитает numberчитает punctuationсоздаёт GreenSyntaxToken

Это даёт ускорение, но увеличивает количество логики, которую нужно поддерживать параллельно с обычным lexer.

Почему старый вариант всё равно был полезен

Несмотря на минусы, старый quick scanner был полезен. Он убирал часть работы для самых частых коротких токенов и уменьшал количество аллокаций за счёт кэша.

Но архитектурно у него была проблема: он слишком много знал о создании токена. Из-за этого он начинал конкурировать с обычным lexer, хотя quick scanner должен быть только быстрым путём перед ним.

Коротко:

старый QuickScanner = маленький быстрый lexer для простых случаев

Он работал, но хотелось сделать hot path ещё проще.

Новый QuickScanner

Теперь перейдём к новой версии quick scanner-а.

Главная идея новой версии в том, что quick scanner занимается только быстрым определением границ простого токена. Он проходит по участку текста, вычисляет full width, считает hash и пробует найти готовый токен в кэше. Если токена в кэше нет, создание настоящего GreenSyntaxToken выполняет обычный lexer.

Схема работы выглядит так:

quick scanner находит full width + hash    ↓ищем токен в кэше    ↓если cache miss, обычный lexer создаёт GreenSyntaxToken

Так quick scanner остаётся небольшим быстрым слоем перед основным lexer-ом и не дублирует всю его логику.

Две таблицы

Новая версия использует две таблицы.

Первая таблица классифицирует символы. Вместо проверки каждого символа через большой switch, scanner сначала переводит символ в одну из категорий:

private enum CharFlags : byte{    White,    CR,    LF,    Letter,    Digit,    Punct,    Dot,    Slash,    Asterisk,    Bang,    Colon,    Less,    Equals,    Greater,    Complex,    EndOfFile}

Например:

'a' => Letter'7' => Digit' ' => White'.' => Dot'/' => Slash'<' => Less'=' => EqualsUnicode или неизвестное => Complex

В коде это выглядит так:

var flags = (uint)uc < (uint)charPropertiesLength    ? (CharFlags)charProperties[uc]    : CharFlags.Complex;

Сейчас быстрый lookup ограничен ASCII-диапазоном:

var charPropertiesLength = Math.Min(128, charProperties.Length);

Поэтому символы выше 127 считаются Complex и обрабатываются обычным lexer-ом. Unicode identifiers и другие сложные случаи остаются на полном пути разбора.

Вторая таблица отвечает за переходы состояний:

private static ReadOnlySpan<byte> StateTransitions => [...]

Именно здесь quick scanner работает как конечный автомат.

Состояния

Состояние хранит, что scanner уже успел распознать:

private enum QuickScanState : byte{    Initial,    FollowingWhite,    FollowingCR,    Ident,    Number,    Punctuation,    Dot,    Slash,    Bang,    Colon,    Less,    Equals,    Greater,    DoneAfterNext,    Done,    Bad = Done + 1}

Смысл основных состояний такой:

Initial          ещё не начали токенIdent            читаем identifierNumber           читаем простое числоPunctuation      читаем простую punctuationDot              увидели .Slash            увидели /Bang             увидели !Colon            увидели :Less             увидели <Equals           увидели =Greater          увидели >FollowingWhite   читаем trailing whitespaceFollowingCR      увидели \r и проверяем возможный \nDone             токен успешно распознанBad              быстрый путь не подходит, нужен fallback

Отдельные состояния для Dot, Slash, Bang, Colon, Less, Equals, Greater нужны потому, что эти символы могут образовывать двухсимвольные токены:

.  или ../  или />!  или !=:  или ::<  или <= или </=  или == или =>>  или >=

Например, если scanner увидел <, он ещё не может сразу завершить токен. Следующий символ решит, будет это <, <= или </.

Таблица переходов

В коде StateTransitions выглядит как плоский массив, но логически это таблица:

строка   = текущее состояниеколонка  = категория текущего символазначение = следующее состояние

На рисунке ниже показана эта таблица в более читаемом виде.

Scanner сначала получает CharFlags, а затем одним обращением к массиву берёт следующее состояние:

state = (QuickScanState)stateTransitions[    ((int)state << CharFlagsShift) + (int)flags];

CharFlagsShift равен 4, потому что в таблице 16 колонок. Сдвиг state << 4 фактически означает state * 16, то есть переход к нужной строке таблицы. Возможно, компилятор сам бы заменил это выражение на сдвиг, но я был в этом не уверен, так как ILSPY показал что нет.

Например:

Initial + Letter => IdentIdent + Letter   => IdentIdent + Digit    => IdentIdent + White    => FollowingWhite

Буквы и цифры продолжают идентификатор. Пробел после идентификатора переводит scanner в состояние trailing whitespace.

Пример работы DFA

Посмотрим на два конкретных примера.

В первом примере scanner читает:

button {

Символ b переводит автомат из Initial в Ident. Дальше u, t, t, o, n тоже классифицируются как Letter, поэтому состояние остаётся Ident.

Пробел после button переводит scanner в FollowingWhite. Сам пробел можно включить в cached token как trailing trivia. Следующий символ { уже не входит в текущий token span, но он помогает понять, что текущий cached token закончился:

FollowingWhite + Punct => Done

В итоге quick scanner может закэшировать участок:

button␠

А { останется для следующего токена.

Во втором примере scanner читает:

>= value

> переводит автомат в Greater, = переводит его в Punctuation, пробел переводит его в FollowingWhite, а следующая буква v завершает текущий cached token:

Initial + Greater       => GreaterGreater + Equals        => PunctuationPunctuation + White     => FollowingWhiteFollowingWhite + Letter => Done

В итоге cached token span будет:

>=␠

А value начнётся уже как следующий токен.

Как таблица заменяет if/switch

Если писать переходы вручную, код быстро превращается во вложенные switch:

private static QuickScanState MoveSlow(QuickScanState state, CharFlags flags){    switch (state)    {        case QuickScanState.Initial:            switch (flags)            {                case CharFlags.Letter:                    return QuickScanState.Ident;                case CharFlags.Digit:                    return QuickScanState.Number;                case CharFlags.Dot:                    return QuickScanState.Dot;                case CharFlags.Slash:                    return QuickScanState.Slash;                case CharFlags.Complex:                    return QuickScanState.Bad;            }            break;        case QuickScanState.Ident:            switch (flags)            {                case CharFlags.Letter:                case CharFlags.Digit:                    return QuickScanState.Ident;                case CharFlags.White:                    return QuickScanState.FollowingWhite;                case CharFlags.Slash:                case CharFlags.Complex:                    return QuickScanState.Bad;                default:                    return QuickScanState.Done;            }    }    return QuickScanState.Bad;}

Таблица переходов заменяет эту логику одной формулой:

state = (QuickScanState)stateTransitions[    ((int)state << CharFlagsShift) + (int)flags];

Индекс считается так:

номер строки * 16 + номер колонки

То есть:

текущее состояние + категория символа = следующее состояние

Вместо большого количества условий получается одно обращение к массиву.

Основной цикл

Главный цикл quick scanner-а теперь выглядит довольно компактно:

var state = QuickScanState.Initial;var hashCode = HashCode.FnvOffsetBias;var currentIndex = 0;for (; currentIndex < textWindowCharSpan.Length; currentIndex++){    var c = textWindowCharSpan[currentIndex];    var uc = unchecked((int)c);    var flags = (uint)uc < (uint)charPropertiesLength        ? (CharFlags)charProperties[uc]        : CharFlags.Complex;    state = (QuickScanState)stateTransitions[        ((int)state << CharFlagsShift) + (int)flags];    if (state >= QuickScanState.Done)    {        goto exitLoop;    }    hashCode = HashCode.CombineFNVHash(hashCode, c);}

На каждый символ scanner делает только несколько операций:

берёт charполучает CharFlagsделает переход по таблицепроверяет Done/Badобновляет FNV hash

Он не создаёт trivia, не создаёт identifier string, не парсит int и не вызывает GreenSyntaxFactory. Поэтому hot path становится заметно проще.

Что происходит при Done и Bad

В QuickScanState есть маленькая деталь:

Done,Bad = Done + 1

Bad специально идёт сразу после Done, чтобы можно было выйти из цикла одной проверкой:

if (state >= QuickScanState.Done){    goto exitLoop;}

Если итоговое состояние равно Done, quick scanner уверен в границе токена. Он проверяет длину, сдвигает TextWindow и ищет токен в кэше:

token = _cache.LookupToken(    textWindowCharSpan[..tokenLength],    hashCode,    static lexer => CreateQuickTokenFromRegularLexer(lexer),    this);

Если такой токен уже был, он возвращается сразу. Если нет, вызывается обычный lexer:

private static GreenSyntaxToken CreateQuickTokenFromRegularLexer(Lexer lexer){    var fullTokenStart = lexer.LexemeStartPosition;    lexer.TextWindow.Reset(fullTokenStart);    var token = lexer.ParseNextToken();    return token;}

Это главное отличие от старого варианта: новый quick scanner не создаёт GreenSyntaxToken сам, а только помогает быстро найти границы и hash.

Если итоговое состояние равно Bad, быстрый путь не подходит. Это не ошибка пользователя. В таком случае scanner возвращает false, а обычный lexer продолжает работу с той же позиции.

В Bad уходят, например, такие случаи:

Unicode identifierчисло с точкой: 123.45hex/binary number: 0xFF, 0b1010комментарий: // ... или /* ... */слишком длинный токенграница SlidingTextWindowнеизвестный символ

Главное правило остаётся таким: quick scanner быстро обрабатывает простой и частый случай, а всё сомнительное отправляет в fallback.

Сравнение подходов

Теперь можно сравнить старый и новый варианты.

Старый quick scanner:

+ понятный+ сам создаёт токен+ умеет простые trivia, identifier, int32, punctuation- много if/switch- частично дублирует обычный lexer- сам создаёт GreenSyntaxToken- сложнее поддерживать одинаковое поведение с обычным lexer

Новый quick scanner:

+ один компактный цикл по символам+ переходы через таблицу+ быстро считает full width и FNV hash+ не создаёт токен сам+ cache miss делегирует обычному lexer+ меньше риск расхождения с обычным lexer- таблицу переходов сложнее читать- нужно аккуратно поддерживать StateTransitions- сложные случаи сразу уходят в fallback

Главное различие можно сформулировать так:

старый QuickScanner = маленький второй lexer для простых случаевновый QuickScanner = быстрый фильтр перед обычным lexer

Бенчмарки

Теперь посмотрим на цифры. Здесь сравниваются два подхода отдельно: старый quick scanner без табличного автомата и новый quick scanner с табличными переходами.

Старый quick scanner

Старый вариант действительно ускорял lexer, но прирост был относительно небольшой: примерно от 4% до 8%.

Новый quick scanner

Новый вариант даёт более заметный относительный прирост: примерно от 16% до 24%.

Аллокации

По памяти оба подхода дают похожий эффект.

В обоих случаях снижение аллокаций примерно около 8%. Это ожидаемо: основную экономию даёт не сама таблица переходов, а кэширование коротких токенов и trivia.

Важная оговорка

Эти бенчмарки не стоит воспринимать как идеально стерильное сравнение двух реализаций. Quick scanner в обычной сборке всегда включён, поэтому для тестов мне пришлось добавить отдельные флаги, чтобы его можно было принудительно отключать. Кроме того, для unit-тестов понадобился сбор статистики quick scanner-а, который не должен попадать в обычную итоговую сборку.

Из-за особенностей Visual Studio старые benchmark/unit-test проекты некорректно работали с условными символами: через dotnet test и dotnet run всё компилировалось нормально, но сама Visual Studio показывала псевдоошибки. Чтобы нормально продолжать работу в IDE, я добавил отдельные конфигурации DebugStats и ReleaseStats.

Побочный эффект в том, что вместе с quick scanner статистику начали собирать и другие части инфраструктуры: обычный lexer, SyntaxFactory, GreenNodeCache и т.д. Поэтому baseline в этих замерах изменился, и напрямую сравнивать raw time старой и новой версии не совсем корректно.

Главный вывод здесь другой: внутри своей конфигурации новый quick scanner стабильно даёт заметный прирост производительности — около 16–24%. Даже без дополнительной статистики порядок прироста на Job.LongRun должен оставаться примерно таким же. Но для абсолютно честного сравнения raw time нужно сделать отдельный чистый benchmark без статистики и с одинаковыми условиями сборки.

Если честно, я вообще не хотел делать DFA, потому что считал выигрыш от него незначительным. Из-за того, что совмещаются два языка и часть работы парсера отдаётся C#, это мне очень не нравилось. Но так как я обещал в прошлой части использовать его, пришлось выполнять обещание. И, если честно, результатом я очень доволен. Прирост в 20% — это не так уж и плохо.

Переходим к Parser

С lexer-ом мы наконец-то получили поток токенов. Казалось бы, теперь всё просто: берём токены один за другим и строим дерево. Но на практике parser — это не просто while по токенам. Его задача чуть неприятнее: он должен понять структуру языка, не потерять исходный текст, уметь восстанавливаться после ошибок и при этом не пытаться заниматься семантикой.

Самый важный момент: parser не должен решать, имеет ли код смысл. Он должен ответить на другой вопрос: какую синтаксическую форму пытался написать пользователь?

Например, если пользователь написал:

state count = ;

это плохой код, но это всё ещё похоже на state-объявление. Parser не должен просто упасть или сказать: «я ничего не понял». Он должен построить StateDeclarationSyntax, положить туда отсутствующий initializer как missing token / missing node и добавить diagnostic. Тогда IDE сможет подсветить ошибку, но дерево всё равно останется пригодным для анализа, форматирования и дальнейшей работы.

В этом смысле parser работает немного как очень терпеливый читатель. Он видит мусор, но пытается сохранить максимум структуры.

Поток токенов

Внутри parser-а обычно есть несколько базовых операций:

private GreenSyntaxToken CurrentToken => PeekToken(0);private GreenSyntaxToken PeekToken(int offset){    // посмотреть токен вперёд, не съедая его}private GreenSyntaxToken EatToken(){    // взять текущий токен и перейти к следующему}private GreenSyntaxToken EatToken(SyntaxKind expected){    // взять ожидаемый токен или создать missing token}

CurrentToken нужен почти везде. PeekToken позволяет отличать похожие конструкции. Например, для inline Akcss блока нам важно увидеть не просто @, а пару токенов:

SyntaxKind.AtToken when PeekToken(1).Kind == SyntaxKind.AkcssKeyword

Потому что @akcss { ... } — это inline-блок стилей, а @akcss = 1; — это уже обычный C# verbatim identifier, и парсер не должен их путать.

EatToken — это место, где parser реально двигается вперёд. Если текущий токен подходит, он просто возвращается. Если нет, parser создаёт missing token нужного вида, добавляет diagnostic и продолжает работу. Это один из базовых механизмов восстановления.

Упрощённо это выглядит так:

private GreenSyntaxToken EatToken(SyntaxKind expected){    if (CurrentToken.Kind == expected)    {        return EatToken();    }    AddError(CurrentToken, $"Expected {expected}");    return GreenSyntaxFactory.MissingToken(expected);}

В реальном коде, конечно, больше деталей: trivia, позиция, сообщения диагностики, специальные случаи восстановления. Но идея именно такая.

Почему parser хранит токены с trivia

Можно было бы подумать, что parser-у нужны только meaningful-токены: state, count, =, 0, ;. Пробелы и переносы строк вроде бы не важны. Но если мы хотим нормальный tooling, это не так.

Нам нужно уметь сделать:

syntax.ToFullString()

и получить обратно ровно тот текст, который написал пользователь. С теми же пробелами, переносами строк, комментариями и даже ошибочными кусками. Это очень важное свойство для компилятора, который хочет жить внутри IDE.

Поэтому trivia не выбрасывается. Lexer приклеивает leading и trailing trivia к токенам, а parser просто переносит эти токены в дерево. Благодаря этому синтаксическое дерево становится lossless: оно хранит не только смысловую структуру, но и исходное представление текста.

Например:

state   count   =   0;

и

state count = 0;

семантически могут означать одно и то же, но синтаксически это разные тексты. Parser обязан сохранить оба варианта без нормализации.

Верхний уровень документа

Для Akbura верхний уровень устроен как список AkTopLevelMember:

using System;namespace Demo.App;state count = 0;<Button>    {count}</Button>

На этом уровне могут встречаться using, namespace, inject, param, state, useEffect, command, обычные C# statements, inline @akcss и markup root. Parser смотрит на текущий токен и выбирает подходящий метод разбора:

internal GreenAkTopLevelMemberSyntax ParseCompilationUnitMember(){    return CurrentToken.Kind switch    {        SyntaxKind.AtToken when PeekToken(1).Kind == SyntaxKind.AkcssKeyword            => ParseInlineAkcssBlockSyntax(),        SyntaxKind.UsingKeyword            => ParseUsingDirectiveSyntax(),        SyntaxKind.GlobalKeyword when PeekToken(1).Kind == SyntaxKind.UsingKeyword            => ParseUsingDirectiveSyntax(),        SyntaxKind.NamespaceKeyword            => ParseNamespaceDeclarationSyntax(),        _ => ParseTopLevelMember()    };}

Здесь уже видно, почему lexer mode и lookahead так важны. Один и тот же символ < может быть началом markup-элемента, а может быть частью C# выражения. Один и тот же @ может быть началом inline Akcss, Akcss-директивой или verbatim identifier. Parser должен аккуратно выбирать контекст, а не просто реагировать на один символ.

Дальше мы разберём, как именно parser строит такие top-level members, как он переключает режимы lexer-а и как делает recovery, когда пользователь написал почти правильный, но всё-таки сломанный код.

ParseTopLevelMember

После специальных file-level конструкций parser попадает в обычный разбор top-level member. Здесь логика ещё проще: смотрим на текущий токен и выбираем конкретный метод.

internal GreenAkTopLevelMemberSyntax ParseTopLevelMember(){    return CurrentToken.Kind switch    {        SyntaxKind.StateKeyword => ParseStateDeclaration(),        SyntaxKind.ParamKeyword => ParseParamDeclarationSyntax(),        SyntaxKind.InjectKeyword => ParseInjectDeclarationSyntax(),        SyntaxKind.CommandKeyword => ParseCommandDeclarationSyntax(),        SyntaxKind.UseEffectKeyword => ParseUseEffectDeclarationSyntax(),        SyntaxKind.LessThanToken => ParseMarkupRootSyntax(),        _ => ParseCSharpStatementSyntax()    };}

Это один из тех моментов, где хорошо видно, что Akbura — это не полностью отдельный язык, а надстройка над C#. Всё, что parser не распознал как собственную конструкцию Akbura, он отдаёт в ParseCSharpStatementSyntax.

Например:

state count = 0;if(count > 10){    Console.WriteLine(count);}<Button>{count}</Button>

Первую строку parser распознает как StateDeclarationSyntax, последнюю как MarkupRootSyntax, а if уйдёт в C# statement. Это важно, потому что я не хочу заново реализовывать весь C# parser. Это было бы безумием в плохом смысле слова.

То есть стратегия такая:

Akbura-конструкция?  => парсим самиmarkup?              => парсим самиобычный C#?          => отдаём C# parser-у

Переключение режимов lexer-а

До этого момента lexer работал в обычном TopLevel режиме. Но внутри Akbura есть участки, где один и тот же текст нужно читать по-другому.

Например, inline Akcss:

@akcss {    .card {        Padding: 12;    }}

В обычном режиме точка . и @ могут иметь один смысл, а внутри Akcss — другой. Поэтому перед разбором inline Akcss parser временно переключает lexer mode:

internal GreenInlineAkcssBlockSyntax ParseInlineAkcssBlockSyntax(){    var mode = _mode;    _mode = Lexer.LexerMode.InAkcss;    try    {        var atToken = EatToken(SyntaxKind.AtToken);        var akcssKeyword = EatToken(SyntaxKind.AkcssKeyword);        var openBrace = EatToken(SyntaxKind.OpenBraceToken);        var members = ParseAkcssTopLevelMemberList();        var closeBrace = EatToken(SyntaxKind.CloseBraceToken);        return GreenSyntaxFactory.InlineAkcssBlockSyntax(            atToken,            akcssKeyword,            openBrace,            members,            closeBrace);    }    finally    {        _mode = mode;    }}

try/finally здесь не декоративный. Parser может встретить сломанный код, missing token, неожиданную конструкцию, но режим lexer-а всё равно нужно вернуть обратно. Иначе одна ошибка внутри @akcss может испортить весь остаток файла.

Такая же идея используется и для C# выражений. Например, в state:

state count = 10 + GetDefaultCount();

Правая часть — это C# expression. Akbura parser не разбирает его по операторам. Он переключает lexer в специальный режим, забирает один CSharpRawToken, а внутри него уже лежит Roslyn-овская C# нода.

private GreenCSharpExpressionSyntax ParseCSharpExpressionInMode(    Lexer.LexerMode expressionMode){    var mode = _mode;    _mode = expressionMode;    var token = EatToken();    _mode = mode;    return GreenSyntaxFactory.CSharpExpressionSyntax(token);}

Я специально оставляю C# как отдельный raw-фрагмент, потому что Akbura parser-у не нужно знать, как устроен a + b * c, lambda expression или generic method call. Для этого уже есть Roslyn.

C# block как смешанный блок

Самый интересный случай — блоки C# control flow. Например:

if(isOpen){    Console.WriteLine("Opened");    <TextBlock Text="Opened!"/>}

Это не Razor-style @if внутри markup. Это обычный C# if на top-level, но его тело может содержать и C# statements, и markup. Поэтому CSharpBlockSyntax внутри Akbura хранит не просто список C# токенов, а список AkTopLevelMember.

private GreenCSharpBlockSyntax ParseCSharpBlock(){    var openBraceToken = EatToken(SyntaxKind.OpenBraceToken);    var members = _pool.Allocate<GreenAkTopLevelMemberSyntax>();    try    {        while (CurrentToken.Kind is not               (SyntaxKind.EndOfFileToken or SyntaxKind.CloseBraceToken))        {            var member = ParseTopLevelMember();            members.Add(member);        }        var closeBraceToken = EatToken(SyntaxKind.CloseBraceToken);        return GreenSyntaxFactory.CSharpBlockSyntax(            openBraceToken,            members.ToList(),            closeBraceToken);    }    finally    {        _pool.Free(members);    }}

Здесь намеренно вызывается ParseTopLevelMember, а не ParseCompilationUnitMember. Это маленькое, но важное ограничение: внутри C# блока можно писать state, markup или обычные C# statements, но file-level using, namespace и @akcss туда не должны попадать как нормальные конструкции.

То есть такой код допустим:

if(isOpen){    Console.WriteLine("Hello");    <TextBlock Text="Opened" />}

А такой подход с markup-internal control flow я специально не добавлял:

<Button>    @if(isOpen)    {        <TextBlock />    }</Button>

Это уже другой язык и другая модель рендера. Сейчас условный rendering делается через обычный C# control flow на top-level или через классический способ скрытия элементов, например IsVisible={isOpen}.

Почему это удобно

Получается довольно простое разделение ответственности:

Lexer       => режет текст на токены и raw C# фрагментыParser      => строит lossless syntax treeRoslyn      => разбирает C# expressions/statements/typesSemantics   => позже проверит смыслCodegen     => позже превратит дерево в C# код

Parser не должен знать, существует ли DashboardViewModel, правильный ли тип у UserId, можно ли применить utility .gap-(double value) к конкретному контролу, и что значит SelectedTask. Всё это появится на следующих этапах.

На этапе parser-а важно другое:

не потерять текстпостроить максимально похожую структуруне упасть на ошибкеоставить достаточно информации для semantic layer

С такой базой уже можно переходить к конкретным синтаксическим конструкциям: state, param, inject, useEffect, command, markup и inline Akcss.

Разбор конкретных конструкций

Теперь можно коротко пройтись по основным конструкциям, которые parser уже умеет собирать. Почти все они устроены по одному шаблону: parser съедает несколько ожидаемых токенов, вызывает вложенные методы для сложных частей и в конце собирает green node через GreenSyntaxFactory.

State, param и inject

Самые простые объявления выглядят примерно так:

inject ILogger<DashboardPage> log;param int UserId = 1;param bind string Search = "";state bool isOpen = false;state ReactList tasks = bind viewModel.Tasks;

У inject есть keyword, тип, имя и ;.

У param появляется binding keyword, optional type и optional default value.

У state появляется initializer. Он может быть обычным выражением или bindable initializer:

state count = 0;state tasks = bind viewModel.Tasks;

Parser здесь не проверяет, существует ли viewModel.Tasks, подходит ли тип и можно ли такое значение привязать к state. Он только строит форму:

StateKeywordType?NameEqualsInitializerSemicolon

Вся проверка типов и символов останется для semantic layer.

useEffect

useEffect чуть интереснее, потому что у него есть основной block и дополнительные cancel / finally blocks:

useEffect(UserId, Search) {    log.LogInformation("Loading user");}cancel {    log.LogInformation("Cancelled");}finally {    log.LogInformation("Done");}

Parser читает dependency list как список имён, затем основной C# block. После него он смотрит, идут ли cancel и finally.

Синтаксически это одна top-level конструкция. Поэтому в AkburaDocumentSyntax.Members весь пример выше занимает один элемент: UseEffectDeclarationSyntax.

Это удобно для дальнейшей семантики. Semantic layer сможет рассматривать основной block, cancel block и finally block как части одного эффекта.

command

command описывает контракт действия:

command Task Refresh(int userId);

Здесь parser читает return type, имя, parameter list и semicolon. Тело у command отсутствует. Смысл команды появится позже, когда codegen превратит её в объект с состоянием выполнения и вызовом.

На уровне parser-а это обычная декларация:

CommandKeywordReturnTypeNameParameterListSemicolon

Markup

Markup — самая заметная часть языка:

<StackPanel class="card" gap-4 p-4 {isBusy}:opacity-50>    <TextBlock Text="Dashboard" />    <Button OnClick={count++}>Open</Button></StackPanel>

Parser начинает с <, читает имя элемента, затем список attributes и закрывающий token > или />.

Attributes делятся на несколько видов:

Title="Dashboard"bind:Value={Search}out:Selected={SelectedTask}w-30gap-4{isBusy}:opacity-50

Обычные attributes становятся MarkupPlainAttributeSyntax.

bind: и out: становятся MarkupPrefixedAttributeSyntax.

Tailwind-like attributes становятся TailwindAttributeSyntax. У них может быть simple prefix, expression prefix, numeric segment или expression segment:

md:w-40{isMobile}:h-15p-{size}gap-{state * 2}

Внутри body parser читает текст, inline expressions и вложенные элементы:

<Button>    Hello {name}    <Icon Name="save" /></Button>

Inline expression хранится как { expr }, где expr снова уходит в C# expression mode.

Inline Akcss

Inline Akcss позволяет писать стили прямо в .akbura файле:

@akcss {    .card {        Padding: 12;        @if(IsHovered) {            Background: "AliceBlue";        }    }    @utilities {        .gap-(double value) {            RowGap: value * Spacing;        }    }}

При входе в такой block parser переключает lexer в InAkcss. Внутри работают Akcss selectors, style rules, utilities, assignments и @if.

После закрывающей } режим возвращается обратно. Это важный инвариант: локальный block не должен менять способ чтения всего оставшегося файла.

Recovery и тесты

Для parser-а мало пройти happy path. Пользователь большую часть времени пишет код в промежуточном состоянии: где-то нет ;, где-то не закрыта }, где-то attribute начат и не закончен.

Поэтому тесты проверяют две вещи.

Первая: правильные примеры строят ожидаемые node types.

Assert.IsType<GreenStateDeclarationSyntax>(syntax.Members[0]);Assert.IsType<GreenMarkupRootSyntax>(syntax.Members[1]);

Вторая: исходный текст сохраняется полностью.

Assert.Equal(code, syntax.ToFullString());

Это простая проверка, которая ловит очень много проблем. Если parser потерял пробел, перенос строки, сломанный attribute или неожиданный token, тест сразу покажет расхождение.

Отдельно проверяются сломанные конструкции:

state count = ;<Button @if(isOpen)>@akcss

Такие случаи должны давать diagnostics и всё равно возвращать дерево. IDE сможет показать ошибку пользователю и продолжить подсветку следующих строк.

Итог

В этой части получился полноценный lexer и первый рабочий parser для Akbura.

Мы взяли SourceText, сделали SlidingTextWindow, добавили локальное интернирование строк, научили lexer читать токены, trivia и C# raw fragments. Затем добавили quick scanner, сначала простой, потом табличный DFA. После этого parser начал собирать lossless syntax tree: top-level declarations, C# blocks, markup, Tailwind-like attributes и inline Akcss.

Главный результат этой части: .akbura файл уже можно разобрать в дерево, сохранить исходный текст через ToFullString() и получить достаточно структуры для следующих этапов.

Дальше путь становится интереснее. Ииии сложнее. Следующая часть — это blender. Ладно бы синтаксические конструкции Akbura, с ними работать легко, но как быть с C#? Один токен заменить несложно, для этого нужно будет просто использовать SyntaxTokenParser. Но как быть с целыми синтаксическими конструкциями? Возможно, придётся стучаться в сам Roslyn и написать им pull request, чтобы они добавили метод вроде SyntaxFactory.Reparse<T>(T, TextChangeEventArgs) where T : SyntaxNode. Но не хотелось бы этого делать, да и вряд ли они согласятся такое добавить даже с пометкой RSEXPERIMENTAL.

И тем не менее для меня лично следующая часть будет интересной, так как до этого я просто копировал, вставлял и адаптировал Roslyn под себя, а сейчас придётся подумать головой.