SynKit Syntax Toolkit

SynKit is a collection of syntax-related modules within the Yoakke ecosystem designed for grammar analysis, lexer/parser generation, and syntax tooling development. It consists of four primary components:

• Lexing: Declarative lexer definition using regular expression annotations over token types. These are compiled into Deterministic Finite Automata (DFAs) for high performance.
• Parsing: Recursive descent parsing using BNF-like notation via method annotations. It supports automatic transformation of direct left-recursion and precedence tables.
• Syntax trees: Tools for managing Abstract Syntax Trees (ASTs), including automated generation of equality, hash implementations, and visitor patterns for AST nodes.
• Error reporting: A fluent API for generating formatted, colorized, and aligned error messages for console output, including support for custom syntax-highlighters for source lines.

When parsing sequences with separators (like comma-separated lists), the raw tuple types generated by the parser can be complex and difficult to work with.

The library provides the Punctuated<TValue, TPunct> type to simplify this. It is implicitly convertible from the complex tuples generated by common patterns like:

• (expr (',' expr)*)? (0 or more, no trailing separator)
• expr (',' expr)* (1 or more, no trailing separator)
• (initializer (',' initializer)* ','?)? (0 or more, optional trailing separator)
• (initializer (',' initializer)* ','?) (1 or more, optional trailing separator)

Note: For 1-or-more patterns, the result is a non-nullable tuple. If the pattern is at the top level of a rule, the library unwraps it into the parameter list, which prevents conversion to Punctuated. To avoid this, wrap the construct in parentheses (...) within your rule string.

[Rule("name_list : Lparen (Identifier (',' Identifier)*)? Rparen")]
private static List<string> NameList(
    IToken<TokenType> _lp,
    Punctuated<IToken<TokenType>, IToken<TokenType>> elements,
    IToken<TokenType> _rp) => elements.Values.Select(t => t.Text).ToList();

Instead of encoding precedence into the grammar structure, use precedence attributes on your binary operator rules. Precedence is determined by the order of attribute declaration (lower precedence to higher precedence).

Associativity Types

• [Left(...)]: Left associative (e.g., a + b + c is (a + b) + c).
• [Right(...)]: Right associative (e.g., a ^ b ^ c is a ^ (b ^ c)).
• [Precedence(...)]: Non-associative.

Example Implementation

[Left("||")]                    // Lowest precedence
[Left("&&")]  
[Left("==", "!=")]
[Left("<", ">", "<=", ">=")]
[Left("+", "-")]
[Left("*", "/", "% ")]
[Right("^")]                    // Highest precedence
[Rule("expression")]
public static int BinaryOp(int left, IToken op, int right)
{
    return op.Text switch
    {
        "+" => left + right,
        "-" => left - right,
        "*" => left * right,
        "/" => left / right,
        "^" => (int)Math.Pow(left, right),
        _ => throw new NotSupportedException($"Operator {op.Text}")
    };
}

[Left("+", "-")]          // Lower precedence, left associative
[Left("*", "/")]          // Higher precedence, left associative  
[Right("^")]              // Right associative exponentiation
[Rule("expression")]      // Inferred rule for binary operators
public static int BinaryOp(int left, IToken op, int right)
{
    return op.Text switch
    {
        "+" => left + right,
        "-" => left - right,
        "*" => left * right,
        "/" => left / right,
        "^" => (int)Math.Pow(left, right),
        _ => throw new NotSupportedException($"Operator {op.Text}")
    };
}

The parser supports standard EBNF-style syntax within the [Rule] attribute to handle optional elements and repetitions.

Repetition

Use * for zero or more occurrences. When using repetition, the method signature should accept an IReadOnlyList<T> of the repeated items.

[Rule("modifier_list: modifier*")]
public static List<Modifier> ModifierList(IReadOnlyList<Modifier> modifiers) 
    => modifiers.ToList();

Optional and Complex Sequences

You can combine elements to define complex sequences, such as a comma-separated list where the first element is required and subsequent elements are optional.

[Rule("parameter_list: parameter (',' parameter)*")]
public static List<Parameter> ParameterList(Parameter first, IReadOnlyList<(IToken, Parameter)> rest)
{
    var result = new List<Parameter> { first };
    result.AddRange(rest.Select(x => x.Item2));
    return result;
}

SynKit is built around three primary architectural pillars designed for high performance and developer ergonomics:

1. Source Generation Over Reflection: Instead of using runtime reflection, SynKit uses C# source generators to create lexers and parsers at compile time. This ensures zero runtime reflection overhead, compile-time validation of grammar rules, and the ability to step through generated code during debugging.
2. Attribute-Driven Configuration: You define your grammar and tokens directly on your code using attributes:
   • [Token]: Defines literal tokens.
   • [Regex]: Defines pattern-based tokens.
   • [Rule]: Defines parser production rules.
   • [Left], [Right]: Specifies operator precedence and associativity.
3. Immutable Error Handling: Errors are treated as immutable objects. You can combine and enrich ParseError objects using the | operator. Errors include position information, expected elements, and semantic context.