Creating a DSL in C#: Writing a Parser

There have not been articles for a long time. I just wanted to publish one article once a week, but I did not have enough time, so I dropped it and started looking for a job. Recently I decided to continue, and how surprised I was when it turned out that only about three days of work were left. Well, I hope I will write the next part faster.

1. Creating the syntax
2. Writing the parser
3. Building the blender
4. Adding semantics
5. Diagnostics
6. Integrating Language Server Protocol and adding Visual Studio support
7. Generating code

Working With SourceText

Of course, we could create our own analogue of SourceText, but honestly there is little sense in that. Roslyn already has a ready abstraction of source text, and almost everything we need for the parser is already there: access to characters by index, text length, working with lines, getting substrings, computing a checksum, and creating text from a string, a stream, or a byte array.

Why is it so useful? First, we can think less about low-level work with encodings. SourceText can store information about the encoding of the source file, and inside the parser we can work not with bytes, but with strings and char, which are familiar in .NET. This greatly simplifies the lexer and parser code.

Second, SourceText does not necessarily have to be just one string. Inside Roslyn there are different implementations for different scenarios: ordinary text, large text, text after changes, and a composition of segments. So we do not need to decide in advance exactly how to store the source file in memory. We can rely on the already existing Roslyn infrastructure.

So, after studying this question, I decided not to create a copy of SourceText, but to use the existing implementation. Maybe this will come back to me in the future, by the way, but I hope not.

TextWindow

But as I mentioned earlier, SourceText can consist of text segments, and access to a specific character can work more slowly because of additional operations and checks. So what we do is simply request a small piece of text right away.

using Microsoft.CodeAnalysis.Text;

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];
    }
}

To be fair, TextWindow does not do only this, but this structure was created essentially for this exact purpose. The rest of the API is very pleasant and convenient extras.

String Interning

In C#, identical string literals are usually not created as different objects. For example:

var a = "Hello";
var b = "Hello";

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

In most ordinary cases this code will print true, because string literals get into the intern pool. The CLR stores a table of interned strings and can return the same reference for equal string values.

But the code that we parse arrives already during program execution. For example, if the same identifier occurs several times in a source file, then with ordinary string creation we can get several different string objects with the same text.

button {
    color: red;
}

button {
    background: red;
}

Here button and red occur repeatedly. If we create a new string every time, we will spend extra memory. That is why SlidingTextWindow (that same pleasant extra) uses its own string table. It works as a local cache: if such a string has already occurred, we can return the existing object instead of creating a new one.

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);
}

It is important that this uses not the global string.Intern, but its own StringTable. This is useful for the parser: the table lives only as long as the SlidingTextWindow is needed, and it does not pollute the application's global intern pool.

An important point: we will not intern everything, only frequently repeated elements: identifiers, literals, or even spaces. Keywords are already cached, and punctuation, by the way, is cached too.

Let us take a closer look at how StringTable works.

StringTable is not a full replacement for string.Intern, but a local lossy cache of strings. It does not store strings forever and does not guarantee deduplication of all strings. Its task is much simpler: quickly reuse frequently occurring values during parsing.

Inside StringTable there are two cache levels: a local L1 cache and a shared L2 cache.

First the string is searched in the local table. This is the fastest path: the index is computed directly from the hash, and then one entry is checked.

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

In simplified form it looks like this:

compute hash => take one index => check one entry

If the entry matched by hash and text, StringTable immediately returns the already existing string object.

If there is a miss in the L1 cache, the shared L2 cache is checked:

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

The L2 cache is shared between different StringTable instances, so it helps reuse strings between different parsers. For example, if one parser has already encountered the string button, another parser instance can receive the same string object through the shared cache.

The search in L2 is arranged in a more complex way. There a small bucket is checked, and traversal is performed through quadratic probing.

Quadratic probing is a way of walking through a bucket in a hash table during collisions. If the first cell is occupied, positions are checked by a quadratic sequence: 0, 1, 3, 6, 10, and so on. Such traversal distributes checks and replacements across the 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;
}

Because of this the L2 cache works harder than L1:

1. it is shared between different StringTable instances;
2. it is larger in size;
3. during search a bucket is checked;
4. Volatile.Write is used during writing;
5. Interlocked.Increment is used for the shared counter.

If the string is found in the shared cache, it is returned and at the same time written back into the local L1 cache. The next access to this same string will already be able to go through the fast path.

If the string is not found in either L1 or L2, it is created through ToString() or Substring(), after which it is added to both caches.

Replacing Elements In The Shared Cache

The shared cache is limited in size. When adding a new string, the code first tries to find a free place in the bucket:

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

If there is no free place, one position inside the bucket is selected and replaced by the new string.

To choose the position, a cheap pseudo-random mechanism is used. The counter starts from a value based on Guid.NewGuid().GetHashCode():

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

Then this value is simply incremented. Such a mechanism does not look like a full Random.Next(), but for choosing a position in a bucket it is enough.

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

LocalNextRandom() gives a changing number, and & SharedBucketSizeMask limits it by the bucket size. After that the same formula as in quadratic probing is used:

(n² + n) / 2

This distributes replacements across different positions of the bucket, and the cache does not constantly evict the same cell.

Short Summary

The L1 cache is used for the fastest access inside the current StringTable instance.

The L2 cache helps reuse strings between different StringTable instances.

Both levels are lossy caches. A string can be evicted, and that is normal. In source code there is usually high locality of data: the same identifiers, keywords, and literals occur many times. So even a limited cache helps reduce the number of repeated allocations.

Making The Lexer

In many articles about compilers, the chain looks approximately like this:

Tokenizer => Parser

Sometimes they also write:

Tokenizer => Lexer => Parser

But in a Roslyn-like architecture such a scheme does not describe what is happening very well. Here it is important to clarify: the words tokenizer and lexer are often used almost as synonyms. So the problem is not in the class name. The problem is in the idea of a separate simple layer that simply cuts text into pieces, and then somebody else turns those pieces into normal syntax tokens.

In our case such an intermediate layer would only add extra work. The minimal independent unit of the green tree is not simply “token type and text”, but GreenSyntaxToken. It can already contain leading trivia, trailing trivia, diagnostic data, and, in the case of literals, also the parsed value.

That is, if we make a separate simple tokenizer, it will most likely produce something like:

TokenKind + text + position

And then we would still have to turn this into:

GreenSyntaxToken
    leading trivia
    kind
    value
    trailing trivia
    diagnostics

So we get an extra stage:

SourceText
    ↓
Tokenizer
    ↓
Intermediate token
    ↓
GreenSyntaxToken
    ↓
Parser

And there is almost no practical benefit from this. Therefore, as in Roslyn, the lexer immediately produces syntax tokens suitable for building the tree.

Why The Lexer Does Not Simply Cut Text

The same character can have different meaning depending on the place where it occurs. The simplest example:

+ // this is PlusToken

"asdas + sadas d"
// this is one StringLiteralToken;
// the + sign inside the string is not a separate token

The < character is also a good example:

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

In Akbura the situation is even more interesting, because pieces of C# code can occur inside the language. Therefore the lexer must be able to change its mode of operation.

LexerMode

In my lexer there is 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,
}

The idea is this: the parser can ask the lexer to read the next section of text not in the ordinary mode, but in a special context. For example:

TopLevel
    ordinary Akbura language mode

InAkcss
    mode inside an akcss block

InInlineExpression
    C# expression until }

InExpressionUntilSemicolon
    C# expression until ;

InExpressionUntilComma
    C# expression until ,

InArgumentExpression
    C# argument until , or )

InTypeName
    C# type

InCSharpParameterList
    C# parameter list

InCSharpArgumentList
    C# argument list

This no longer looks like a simple tokenizer. The lexer does not simply go through the text and return the next piece. It knows which mode it is in and chooses a different way of reading.

The main method looks like this:

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();
}

Here the general scheme is clearly visible:

if the mode is a C# insertion
    read the piece as C# and return CSharpRawToken

otherwise
    try quick scanner

if quick scanner did not handle it
    run the normal full lexer

The Normal Path: ParseNextToken

When the lexer is in TopLevel or InAkcss, it reads an ordinary Akbura token. This is done through ParseNextToken:

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

    return CreateToken(in tokenInfo, leading, trailing, errors);
}

And inside ParseNextTokenInfo the token is assembled from three parts:

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;
}

First the lexer reads leading trivia, then the token itself, then trailing trivia.

For example:

/* comment */ button

The comment before button does not disappear. It becomes part of the leading trivia of the button token. This is important for a Roslyn-like architecture, because the tree must preserve the source text accurately enough: spaces, line breaks, and comments cannot simply be thrown away.

Trivia

Trivia is what is not the main syntax, but still belongs to the source text:

spaces
line breaks
single-line comments
multi-line comments

In the lexer this is handled separately:

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;
        }
    }
}

There is an important rule here: trailing trivia stops on a line break. That is, a comment or space after a token can be trailing trivia, but if a line break is encountered, the next token will already start a new line.

Spaces are optimized too. One ordinary space does not create a new object at all, but is returned as a ready trivia:

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

And short sequences of spaces can go through the cache:

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

This is a small thing, but such small things are very important. In real code there are many spaces and line breaks, so even trivia has to be handled carefully.

ParseSyntaxToken

After leading trivia, the lexer calls ParseSyntaxToken. This is the main method for reading ordinary Akbura tokens. It looks at the current character and chooses what to do next.

In simplified form it looks like this:

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;
    }
}

This method shows why the lexer cannot be completely “dumb”. For example, the < character can mean several things at once:

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

The same with =:

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

And with a dot:

.  => DotToken
.. => DoubleDotToken

The lexer is required to look ahead, otherwise it will not be able to correctly determine the token boundary.

Identifiers And Keywords

An identifier seems like a simple thing, but in practice it is better to read it in two stages: a fast path for the common case and a slow path for complex cases.

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

    return TryParseIdentifier_Slow(ref token);
}

The fast path works only for ordinary ASCII identifiers:

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

It reads text directly from CurrentWindowSpan, quickly checks characters, and finishes the identifier on known separators. If everything is fine, the text is interned:

var text = TextWindow.Intern(span[..length]);

token.Text = text;
token.Kind = SyntaxKind.IdentifierToken;

But if something complex is encountered, for example a Unicode character, an escape sequence, or a surrogate pair, the fast path returns false, and the lexer moves to the slow path.

The slow path can already do more:

Unicode letters
Unicode escape sequences: \uXXXX, \UXXXXXXXX
surrogate pairs
formatting characters
escaped identifier sequences

And here we again see the same philosophy:

common case — fast
complex case — slower, but correct

After reading the identifier, the lexer checks whether it is a keyword:

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;
    }
}

There is an important difference here between a hard keyword and a contextual keyword.

A hard keyword immediately becomes a separate token. A contextual keyword lexically remains IdentifierToken, but inside it carries an additional ContextualKind. This is needed because the meaning of such a word depends on its place in the syntax. The parser can later decide whether to use it as a keyword or as an ordinary identifier.

Numeric Literals

Numbers are a separate large part of the lexer. At first glance a number is simply several digits in a row. In practice, many more variants must be supported:

123
1_000_000
0xFF
0b1010
123u
123L
123UL
1.5
1e10
1.5f
1.5d
1.5m

The ScanNumericLiteral method first determines what kind of literal this is:

decimal
hexadecimal
binary
real number
integer with suffix
floating-point with suffix

For example, if a number starts with 0x or 0X, it is read as 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;
    }
}

For ordinary decimal numbers the lexer separately checks the fractional part:

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);
    }
}

So 123.332 becomes one NumericLiteralToken, because the dot is between digits and is part of the numeric literal.

The lexer also handles exponent:

1e10
1E-10
1.5e+3

And suffixes:

f / F => float
D / d => double
m / M => decimal
u / U => uint or ulong
L / l => long or ulong

After this the lexer does not simply store the text of the number, but immediately determines its type and value:

info.Kind = SyntaxKind.NumericLiteralToken;
info.Text = this.GetInternedLexemeText();

var valueText = TextWindow.Intern(_builder);

For integers, UInt64.TryParse or separate parsing of binary numbers is used, and then the most suitable type is selected:

int
uint
long
ulong

For example, if a number without a suffix fits into int, it will become System_Int32. If it does not fit, the lexer will try uint, then long, then ulong.

For float and double a separate class RealParser is used (ehh, I remembered my school years when I wrote in 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 is needed not just to call float.Parse or double.Parse. It converts a decimal floating-point literal to the nearest representable IEEE value and uses round-to-nearest, ties-to-even rounding. It also does not support a leading sign, because in C# and similar languages -1.0 is not one negative numeric token, but a unary minus operator plus a positive literal 1.0.

And this is an important point: the lexer reads exactly the literal. The - sign remains a separate token, and the negative number appears already at the syntax or semantic level.

For decimal, decimal.TryParse is used, because decimal in .NET is a separate type with different representation rules:

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;
}

As a result, NumericLiteralToken stores not only the source text, but also the already prepared value of the needed type. This is another reason why a simple tokenizer would be too weak a layer for such an architecture.

C# Fragments Inside Akbura

One of the features of Akbura is the ability to use C# expressions or types inside its own syntax. In such places the lexer does not try to manually parse all of C# again. Instead it collects the needed text fragment and passes it to Roslyn.

For example, an inline expression is read until }:

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

But simply reading until the first } is not possible. There can be braces inside the expression:

SomeMethod(new { Value = 10 })

Therefore the lexer tracks nesting depth:

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

And it stops only when it has met the terminator at zero depth:

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

After that the collected text is passed to Roslyn:

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

tokenInfo.CSharpNode = parsed;
tokenInfo.CSharpSyntaxKind = parsed.Kind();

For types ParseTypeName is used:

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

For parameter lists:

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

For argument lists:

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

Outwardly all this is returned as a special token:

Kind = SyntaxKind.CSharpRawToken

And in CreateToken there is a separate branch for such a token:

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

That is, for Akbura this is one raw token, but inside it there is already a full Roslyn C# syntax node. This lets us avoid inventing our own C# parser and avoid trying to manually repeat all of C# syntax.

Creating GreenSyntaxToken

After the lexer has collected TokenInfo, leading trivia, trailing trivia, and diagnostics, it calls 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;
}

For ordinary punctuation, SyntaxKind is enough. Identifiers need text. Numeric literals need not only text, but also a value. Therefore NumericLiteralToken is created differently depending on ValueKind:

System_Int32    => int literal
System_UInt32   => uint literal
System_Int64    => long literal
System_UInt64   => ulong literal
System_Single   => float literal
System_Double   => double literal
System_Decimal  => decimal literal

If errors appeared while reading the token, they are attached directly to the green token:

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

Thus the lexer does not simply return a token type. It returns a full syntax tree object.

Errors And Recovery

The lexer should not crash on the first unknown character. If it meets an unexpected sequence, it creates a diagnostic message and still moves forward.

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]);
}

There are several important details here.

First, the lexer still consumes the character, otherwise it can get into an infinite loop.

Second, if the character is the beginning of a surrogate pair, it consumes both char values, so as not to split a Unicode character in half.

Third, the error is stored as a diagnostic and then attached to the token.

This is needed for normal editor and language server work. Even if the user wrote invalid code, the parser should still build at least a partial tree so that the IDE can show highlighting, diagnostics, and continue working.

Summary

As a result, the lexer in Akbura performs several tasks at once:

reads leading and trailing trivia
recognizes punctuation tokens
reads identifiers and keywords
supports contextual keywords
reads numeric literals and immediately determines their values
handles Unicode identifiers and escape sequences
can switch between LexerMode values
delegates C# fragments to the Roslyn parser
creates GreenSyntaxToken
attaches diagnostics
uses quick scanner for the fast path

So calling this layer a simple tokenizer would not be quite correct. A tokenizer is usually associated with mechanical splitting of text into tokens. Here the lexer is a full part of a Roslyn-like architecture: it preserves trivia, takes the parse mode into account, creates typed literals, can work with C# insertions, and immediately returns ready green tokens for the parser.

In fact, the task of the lexer is to turn SourceText not simply into a stream of pieces of text, but into a stream of full syntax tokens, from which the parser can already build a green tree.

QuickScanner

Great, in original Roslyn there is also a fast path for the lexer, just like there is one for identifiers.

The normal path does quite a lot of work:

read leading trivia
read the token itself
read trailing trivia
create GreenSyntaxToken
attach diagnostics, if there are any

This is the correct and full path, but it is not always cheap. In source code there are very many simple cases: short identifiers, spaces, line breaks, and simple punctuation.

For example:

button {
    color: red;
}

Here almost everything consists of simple tokens. For such cases we can try a fast path — QuickScanner.

Important: QuickScanner does not replace the normal lexer. The normal lexer still remains the source of truth. Quick scanner is allowed to handle only simple and obvious cases. If it meets something complex or doubtful, it simply returns false, and then the normal lexer works.

Therefore the main rule of the quick scanner is this:

if it was possible quickly and safely — return the token
if there is doubt — touch nothing and give the work to the normal lexer

In code this rule is visible here:

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;
}

If the fast path did not work, the position in the text must remain exactly the same. This is very important. Quick scanner can refuse to work, but it must not damage the lexer’s state.

Old QuickScanner

First let us look at the old version of the quick scanner. Its idea was simple: try to manually and quickly read leading trivia, the token itself, and trailing trivia, and then create a ready GreenSyntaxToken.

The simplified scheme looked like this:

CurrentWindowSpan
    ↓
read leading trivia
    ↓
read a simple token
    ↓
read trailing trivia
    ↓
compute hash of the whole token
    ↓
find the token in the cache or create a new one
    ↓
move TextWindow

That is, the old quick scanner tried to do almost everything itself.

What It Could Read Quickly

The old version was designed only for simple cases:

whitespace
newline
identifier
simple int32 number
simple punctuation

If a complex case was encountered, the scanner immediately did fallback.

For example, comments were not handled as simple whitespace, because / can mean many different things:

/       ordinary slash token
//      single-line comment
/*      multi-line comment
/>      slash-greater token

In such a situation it is safer to give the work to the normal lexer.

Leading And Trailing Trivia

First the old quick scanner tried to read trivia before the token.

It could handle simple spaces and line breaks quickly:

' '      whitespace
'\t'     whitespace
'\r'     newline or part of CRLF
'\n'     newline

But if / was encountered, the scanner did not try to parse the comment itself and went to fallback.

After the token itself it did the same for trailing trivia. At the same time trailing trivia must stop at a line break, because a line break usually already belongs to the boundary between tokens.

The Token Itself

After leading trivia, the scanner looked at the first character of the token and selected a fast path.

Approximately like this:

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
};

Then there was a separate method for each token type:

TryQuickScanIdentifier
TryQuickScanDecimalInt32
TryQuickScanPunctuation

That is, if it was an identifier, the scanner separately read the identifier. If it was a number, it separately tried to read a simple number. If it was punctuation, it separately checked punctuation.

Identifier

For an identifier, the old quick scanner read only the simple ASCII variant:

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

If Unicode, an escape sequence, or another complex character was encountered, the scanner did not try to be smarter and returned false.

This is the correct behavior. Quick scanner should cover the common case, not the whole language.

Number

With numbers the story is similar. The old quick scanner could quickly handle only a simple decimal int32:

123
42
1000

But such variants are already too complex for the fast path:

123.45
1e10
0xFF
0b1010
1_000
123u
123L

They went to the normal lexer, where there is already a full ScanNumericLiteral and a separate RealParser for floating-point literals.

Punctuation

For punctuation there was a separate switch. For example, the < character could turn into different tokens:

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;

This worked, but this code started to duplicate the normal lexer. If a new punctuation token is added to the main lexer, one must not forget to update the quick scanner.

Creating The Token

The main difference of the old version is that it created the token itself.

After successful reading it collected data:

kind
leading trivia
trailing trivia
text
int value, if this is a number

And then it created GreenSyntaxToken directly:

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)
    };
}

And here the main minus of the old approach appears. Quick scanner starts being not simply a fast filter, but a small second implementation of the lexer.

It itself:

reads trivia
reads identifier
reads number
reads punctuation
creates GreenSyntaxToken

This gives acceleration, but increases the amount of logic that has to be maintained in parallel with the normal lexer.

Why The Old Version Was Still Useful

Despite the minuses, the old quick scanner was useful. It removed part of the work for the most frequent short tokens and reduced the number of allocations thanks to the cache.

But architecturally it had a problem: it knew too much about token creation. Because of this it started competing with the normal lexer, although quick scanner should be only a fast path before it.

Briefly:

old QuickScanner = small fast lexer for simple cases

It worked, but I wanted to make the hot path even simpler.

New QuickScanner

Now let us move to the new version of quick scanner.

The main idea of the new version is that quick scanner deals only with fast determination of the boundaries of a simple token. It goes through a section of text, computes full width, computes hash, and tries to find a ready token in the cache. If the token is not in the cache, the normal lexer creates the real GreenSyntaxToken.

The work scheme looks like this:

quick scanner finds full width + hash
    ↓
look for the token in the cache
    ↓
if cache miss, the normal lexer creates GreenSyntaxToken

So quick scanner remains a small fast layer before the main lexer and does not duplicate all of its logic.

Two Tables

The new version uses two tables.

The first table classifies characters. Instead of checking every character through a large switch, the scanner first translates the character into one of the categories:

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

For example:

'a' => Letter
'7' => Digit
' ' => White
'.' => Dot
'/' => Slash
'<' => Less
'=' => Equals
Unicode or unknown => Complex

In code it looks like this:

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

Right now the fast lookup is limited to the ASCII range:

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

Therefore characters above 127 are considered Complex and are handled by the normal lexer. Unicode identifiers and other complex cases stay on the full parse path.

The second table is responsible for state transitions:

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

This is exactly where quick scanner works as a finite automaton.

States

The state stores what the scanner has already managed to recognize:

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

The meaning of the main states is this:

Initial          have not started the token yet
Ident            reading identifier
Number           reading a simple number
Punctuation      reading simple punctuation
Dot              saw .
Slash            saw /
Bang             saw !
Colon            saw :
Less             saw <
Equals           saw =
Greater          saw >
FollowingWhite   reading trailing whitespace
FollowingCR      saw \r and checking possible \n
Done             token successfully recognized
Bad              fast path does not fit, fallback is needed

Separate states for Dot, Slash, Bang, Colon, Less, Equals, Greater are needed because these characters can form two-character tokens:

.  or ..
/  or />
!  or !=
:  or ::
<  or <= or </
=  or == or =>
>  or >=

For example, if the scanner saw <, it still cannot immediately finish the token. The next character will decide whether this is <, <=, or </.

Transition Table

In code StateTransitions looks like a flat array, but logically it is a table:

row    = current state
column = category of the current character
value  = next state

The figure below shows this table in a more readable form.

The scanner first receives CharFlags, and then takes the next state with one array access:

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

CharFlagsShift is equal to 4, because the table has 16 columns. The shift state << 4 effectively means state * 16, that is, moving to the needed row of the table. Perhaps the compiler would replace this expression with a shift itself, but I was not sure about that, because ILSPY showed that it did not.

For example:

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

Letters and digits continue the identifier. A space after the identifier transfers the scanner into the trailing whitespace state.

Example Of DFA Work

Let us look at two concrete examples.

In the first example the scanner reads:

button {

The character b transfers the automaton from Initial to Ident. Then u, t, t, o, n are also classified as Letter, so the state remains Ident.

The space after button transfers the scanner to FollowingWhite. The space itself can be included into the cached token as trailing trivia. The next character { no longer belongs to the current token span, but it helps understand that the current cached token has ended:

FollowingWhite + Punct => Done

As a result, quick scanner can cache the section:

button␠

And { will remain for the next token.

In the second example the scanner reads:

>= value

> transfers the automaton to Greater, = transfers it to Punctuation, the space transfers it to FollowingWhite, and the next letter v finishes the current cached token:

Initial + Greater       => Greater
Greater + Equals        => Punctuation
Punctuation + White     => FollowingWhite
FollowingWhite + Letter => Done

As a result, the cached token span will be:

>=␠

And value will already start as the next token.

How The Table Replaces if/switch

If we write transitions manually, the code quickly turns into nested switch statements:

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;
}

The transition table replaces this logic with one formula:

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

The index is computed like this:

row number * 16 + column number

That is:

current state + character category = next state

Instead of a large number of conditions, we get one array access.

Main Loop

The main loop of quick scanner now looks quite compact:

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);
}

For each character the scanner does only a few operations:

takes char
gets CharFlags
makes transition through the table
checks Done/Bad
updates FNV hash

It does not create trivia, does not create an identifier string, does not parse int, and does not call GreenSyntaxFactory. Therefore the hot path becomes noticeably simpler.

What Happens On Done And Bad

There is a small detail in QuickScanState:

Done,
Bad = Done + 1

Bad intentionally comes immediately after Done, so that it is possible to exit the loop with one check:

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

If the final state is Done, quick scanner is confident in the token boundary. It checks the length, moves TextWindow, and looks for the token in the cache:

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

If such a token has already existed, it is returned immediately. If not, the normal lexer is called:

private static GreenSyntaxToken CreateQuickTokenFromRegularLexer(Lexer lexer)
{
    var fullTokenStart = lexer.LexemeStartPosition;

    lexer.TextWindow.Reset(fullTokenStart);
    var token = lexer.ParseNextToken();

    return token;
}

This is the main difference from the old version: the new quick scanner does not create GreenSyntaxToken itself, but only helps quickly find boundaries and hash.

If the final state is Bad, the fast path does not fit. This is not a user error. In this case the scanner returns false, and the normal lexer continues work from the same position.

For example, such cases go to Bad:

Unicode identifier
number with a dot: 123.45
hex/binary number: 0xFF, 0b1010
comment: // ... or /* ... */
too long token
SlidingTextWindow boundary
unknown character

The main rule remains this: quick scanner quickly handles the simple and frequent case, and everything doubtful is sent to fallback.

Comparing The Approaches

Now we can compare the old and new variants.

Old quick scanner:

+ understandable
+ creates the token itself
+ can handle simple trivia, identifier, int32, punctuation

- many if/switch statements
- partially duplicates the normal lexer
- creates GreenSyntaxToken itself
- harder to keep the same behavior as the normal lexerd

New quick scanner:

+ one compact loop over characters
+ transitions through a table
+ quickly computes full width and FNV hash
+ does not create the token itself
+ cache miss delegates to the normal lexer
+ lower risk of divergence from the normal lexer

- the transition table is harder to read
- StateTransitions must be maintained carefully
- complex cases immediately go to fallback

The main difference can be formulated like this:

old QuickScanner = small second lexer for simple cases

new QuickScanner = fast filter before the normal lexer

Benchmarks

Now let us look at the numbers. Here the two approaches are compared separately: the old quick scanner without a table automaton and the new quick scanner with table transitions.

Old quick scanner

The old version really sped up the lexer, but the gain was relatively small: approximately from 4% to 8%.

New quick scanner

The new version gives a more noticeable relative gain: approximately from 16% to 24%.

Allocations

In memory both approaches give a similar effect.

In both cases the allocation reduction is approximately around 8%. This is expected: the main saving is given not by the transition table itself, but by caching short tokens and trivia.

These benchmarks should not be perceived as a perfectly sterile comparison of two implementations. Quick scanner is always enabled in a normal build, so for tests I had to add separate flags in order to forcibly disable it. In addition, unit tests needed quick scanner statistics collection, which should not get into the normal final build.

Because of Visual Studio specifics, the old benchmark/unit-test projects incorrectly worked with conditional symbols: through dotnet test and dotnet run everything compiled normally, but Visual Studio itself showed pseudo-errors. To continue working normally in the IDE, I added separate DebugStats and ReleaseStats configurations.

The side effect is that together with quick scanner, other parts of the infrastructure also started collecting statistics: the normal lexer, SyntaxFactory, GreenNodeCache, and so on. Therefore the baseline in these measurements changed, and directly comparing raw time of the old and new version is not quite correct.

The main conclusion here is different: inside its own configuration, the new quick scanner consistently gives a noticeable performance gain — about 16–24%. Even without additional statistics, the order of gain on Job.LongRun should remain approximately the same. But for an absolutely honest comparison of raw time, a separate clean benchmark without statistics and with identical build conditions must be made.

To be honest, I did not want to make a DFA at all, because I considered the gain from it insignificant. Because two languages are combined and part of the parser’s work is given to C#, I really did not like this. But since I promised in the previous part to use it, I had to keep the promise. And, honestly, I am very pleased with the result. A 20% gain is not so bad.

Moving To The Parser

With the lexer, we finally got a stream of tokens. It would seem that now everything is simple: take tokens one by one and build the tree. But in practice the parser is not simply a while over tokens. Its task is a little more unpleasant: it must understand the structure of the language, not lose the source text, be able to recover after errors, and at the same time not try to do semantics.

The most important point: the parser should not decide whether the code makes sense. It should answer another question: what syntactic form was the user trying to write?

For example, if the user wrote:

state count = ;

this is bad code, but it still looks like a state declaration. The parser should not simply crash or say: "I understood nothing." It should build StateDeclarationSyntax, put the missing initializer there as a missing token / missing node, and add a diagnostic. Then the IDE will be able to highlight the error, but the tree will still remain suitable for analysis, formatting, and further work.

In this sense the parser works a bit like a very patient reader. It sees garbage, but tries to preserve as much structure as possible.

Token Stream

Inside the parser there are usually several basic operations:

private GreenSyntaxToken CurrentToken => PeekToken(0);

private GreenSyntaxToken PeekToken(int offset)
{
    // look at a token ahead without consuming it
}

private GreenSyntaxToken EatToken()
{
    // take the current token and move to the next one
}

private GreenSyntaxToken EatToken(SyntaxKind expected)
{
    // take the expected token or create a missing token
}

CurrentToken is needed almost everywhere. PeekToken allows distinguishing similar constructs. For example, for an inline Akcss block it is important for us to see not simply @, but a pair of tokens:

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

Because @akcss { ... } is an inline styles block, while @akcss = 1; is already an ordinary C# verbatim identifier, and the parser should not confuse them.

EatToken is the place where the parser really moves forward. If the current token fits, it is simply returned. If not, the parser creates a missing token of the needed kind, adds a diagnostic, and continues working. This is one of the basic recovery mechanisms.

In simplified form it looks like this:

private GreenSyntaxToken EatToken(SyntaxKind expected)
{
    if (CurrentToken.Kind == expected)
    {
        return EatToken();
    }

    AddError(CurrentToken, $"Expected {expected}");

    return GreenSyntaxFactory.MissingToken(expected);
}

In real code, of course, there are more details: trivia, position, diagnostic messages, special recovery cases. But the idea is exactly this.

Why The Parser Stores Tokens With Trivia

One could think that the parser needs only meaningful tokens: state, count, =, 0, ;. Spaces and line breaks seem unimportant. But if we want normal tooling, this is not so.

We need to be able to do:

syntax.ToFullString()

and get back exactly the text that the user wrote. With the same spaces, line breaks, comments, and even broken pieces. This is a very important property for a compiler that wants to live inside an IDE.

Therefore trivia is not thrown away. The lexer glues leading and trailing trivia to tokens, and the parser simply transfers these tokens into the tree. Thanks to this the syntax tree becomes lossless: it stores not only the meaningful structure, but also the original representation of the text.

For example:

state   count   =   0;

and

state count = 0;

semantically can mean the same thing, but syntactically they are different texts. The parser must preserve both variants without normalization.

Top Level Of The Document

For Akbura, the top level is arranged as a list of AkTopLevelMember:

using System;
namespace Demo.App;

state count = 0;

<Button>
    {count}
</Button>

At this level there can be using, namespace, inject, param, state, useEffect, command, ordinary C# statements, inline @akcss, and markup root. The parser looks at the current token and selects the appropriate parse method:

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()
    };
}

Here it is already visible why lexer mode and lookahead are so important. The same character < can be the beginning of a markup element, or it can be part of a C# expression. The same @ can be the beginning of inline Akcss, an Akcss directive, or a verbatim identifier. The parser must carefully choose the context, and not simply react to one character.

Next we will look at exactly how the parser builds such top-level members, how it switches lexer modes, and how it does recovery when the user wrote almost correct, but still broken code.

ParseTopLevelMember

After special file-level constructs, the parser gets into ordinary parsing of a top-level member. Here the logic is even simpler: look at the current token and choose a concrete method.

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()
    };
}

This is one of those moments where it is clearly visible that Akbura is not a completely separate language, but a layer over C#. Everything that the parser did not recognize as its own Akbura construct, it gives to ParseCSharpStatementSyntax.

For example:

state count = 0;

if(count > 10)
{
    Console.WriteLine(count);
}

<Button>{count}</Button>

The first line the parser recognizes as StateDeclarationSyntax, the last as MarkupRootSyntax, and if will go into a C# statement. This is important because I do not want to implement the whole C# parser again. That would be madness in the bad sense of the word.

That is, the strategy is this:

Akbura construct? => parse ourselves
markup?           => parse ourselves
ordinary C#?      => give to the C# parser

Switching Lexer Modes

Up to this point the lexer worked in the normal TopLevel mode. But inside Akbura there are sections where the same text must be read differently.

For example, inline Akcss:

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

In the normal mode the dot . and @ can have one meaning, and inside Akcss another. Therefore before parsing inline Akcss, the parser temporarily switches 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 here is not decorative. The parser can meet broken code, a missing token, an unexpected construct, but the lexer mode still has to be returned back. Otherwise one error inside @akcss can spoil the entire rest of the file.

The same idea is used for C# expressions. For example, in state:

state count = 10 + GetDefaultCount();

The right-hand side is a C# expression. The Akbura parser does not parse it by operators. It switches the lexer into a special mode, takes one CSharpRawToken, and inside it there already lies a Roslyn C# node.

private GreenCSharpExpressionSyntax ParseCSharpExpressionInMode(
    Lexer.LexerMode expressionMode)
{
    var mode = _mode;

    _mode = expressionMode;

    var token = EatToken();

    _mode = mode;

    return GreenSyntaxFactory.CSharpExpressionSyntax(token);
}

I intentionally leave C# as a separate raw fragment, because the Akbura parser does not need to know how a + b * c, a lambda expression, or a generic method call is arranged. Roslyn already exists for that.

C# Block As A Mixed Block

The most interesting case is C# control flow blocks. For example:

if(isOpen)
{
    Console.WriteLine("Opened");

    <TextBlock Text="Opened!"/>
}

This is not Razor-style @if inside markup. This is an ordinary C# if at top-level, but its body can contain both C# statements and markup. Therefore CSharpBlockSyntax inside Akbura stores not simply a list of C# tokens, but a list of 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);
    }
}

Here ParseTopLevelMember is intentionally called, not ParseCompilationUnitMember. This is a small but important limitation: inside a C# block one can write state, markup, or ordinary C# statements, but file-level using, namespace, and @akcss should not get there as normal constructs.

That is, such code is allowed:

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

And I intentionally did not add such an approach with markup-internal control flow:

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

This is already another language and another render model. For now conditional rendering is done through ordinary C# control flow at top-level or through the classic way of hiding elements, for example IsVisible={isOpen}.

Why This Is Convenient

The result is a fairly simple separation of responsibilities:

Lexer       => cuts text into tokens and raw C# fragments
Parser      => builds a lossless syntax tree
Roslyn      => parses C# expressions/statements/types
Semantics   => will later check meaning
Codegen     => will later turn the tree into C# code

The parser should not know whether DashboardViewModel exists, whether the type of UserId is correct, whether utility .gap-(double value) can be applied to a specific control, and what SelectedTask means. All of this will appear in the next stages.

At the parser stage something else is important:

not to lose text
build the most similar structure possible
not crash on an error
leave enough information for semantic layer

With such a base we can already move on to concrete syntactic constructs: state, param, inject, useEffect, command, markup, and inline Akcss.

Parsing Concrete Constructs

Now we can briefly go through the main constructs that the parser can already assemble. Almost all of them are arranged according to one pattern: the parser consumes several expected tokens, calls nested methods for complex parts, and at the end assembles a green node through GreenSyntaxFactory.

State, param And inject

The simplest declarations look approximately like this:

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

inject has a keyword, type, name, and ;.

param gets a binding keyword, optional type, and optional default value.

state gets an initializer. It can be an ordinary expression or a bindable initializer:

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

The parser here does not check whether viewModel.Tasks exists, whether the type fits, and whether such a value can be bound to state. It only builds the form:

StateKeyword
Type?
Name
Equals
Initializer
Semicolon

All checking of types and symbols will remain for the semantic layer.

useEffect

useEffect is a little more interesting, because it has a main block and additional cancel / finally blocks:

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

The parser reads the dependency list as a list of names, then the main C# block. After it, it looks whether cancel and finally follow.

Syntactically this is one top-level construct. Therefore in AkburaDocumentSyntax.Members, the whole example above takes one element: UseEffectDeclarationSyntax.

This is convenient for further semantics. The semantic layer will be able to consider the main block, cancel block, and finally block as parts of one effect.

command

command describes an action contract:

command Task Refresh(int userId);

Here the parser reads return type, name, parameter list, and semicolon. command has no body. The meaning of the command will appear later, when codegen turns it into an object with execution state and invocation.

At the parser level this is an ordinary declaration:

CommandKeyword
ReturnType
Name
ParameterList
Semicolon

Markup

Markup is the most visible part of the language:

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

The parser starts with <, reads the element name, then the attributes list and the closing token > or />.

Attributes are divided into several kinds:

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

Ordinary attributes become MarkupPlainAttributeSyntax.

bind: and out: become MarkupPrefixedAttributeSyntax.

Tailwind-like attributes become TailwindAttributeSyntax. They can have a simple prefix, expression prefix, numeric segment, or expression segment:

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

Inside the body the parser reads text, inline expressions, and nested elements:

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

The inline expression is stored as { expr }, where expr again goes into C# expression mode.

Inline Akcss

Inline Akcss allows writing styles directly in a .akbura file:

@akcss {
    .card {
        Padding: 12;

        @if(IsHovered) {
            Background: "AliceBlue";
        }
    }

    @utilities {
        .gap-(double value) {
            RowGap: value * Spacing;
        }
    }
}

When entering such a block, the parser switches the lexer to InAkcss. Inside, Akcss selectors, style rules, utilities, assignments, and @if work.

After the closing }, the mode returns back. This is an important invariant: a local block should not change the way the entire remaining file is read.

Recovery And Tests

For the parser it is not enough to pass the happy path. Most of the time the user writes code in an intermediate state: somewhere there is no ;, somewhere } is not closed, somewhere an attribute has started and not ended.

Therefore tests check two things.

First: correct examples build the expected node types.

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

Second: the source text is preserved completely.

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

This is a simple check that catches a lot of problems. If the parser lost a space, line break, broken attribute, or unexpected token, the test will immediately show a mismatch.

Broken constructs are checked separately:

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

Such cases should give diagnostics and still return a tree. The IDE will be able to show the error to the user and continue highlighting the next lines.

Summary

In this part we got a full lexer and the first working parser for Akbura.

We took SourceText, made SlidingTextWindow, added local string interning, taught the lexer to read tokens, trivia, and C# raw fragments. Then we added quick scanner, first simple, then table-based DFA. After that the parser started assembling a lossless syntax tree: top-level declarations, C# blocks, markup, Tailwind-like attributes, and inline Akcss.

The main result of this part: a .akbura file can already be parsed into a tree, the source text can be preserved through ToFullString(), and enough structure can be obtained for the next stages.

Further the path becomes more interesting. Aaand harder. The next part is the blender. Akbura syntactic constructs would be fine, they are easy to work with, but what about C#? Replacing one token is not hard; for that we will simply need to use SyntaxTokenParser. But what about whole syntactic constructs? Perhaps I will have to knock on Roslyn itself and write them a pull request so that they add a method like SyntaxFactory.Reparse<T>(T, TextChangeEventArgs) where T : SyntaxNode. But I would not want to do that, and they are unlikely to agree to add such a thing even with the RSEXPERIMENTAL mark.

And nevertheless, for me personally the next part will be interesting, because until now I was simply copying, pasting, and adapting Roslyn for myself, and now I will have to think with my head.