Semantic Analysis and Code Generation: Type Checking, Symbol Tables and Compiling an AST to Expression Trees

Version note: The code in this post was built with .NET 10 (SDK 10.0.404), Entity Framework Core 10.0.15 (SQL Server provider) and Microsoft.CodeAnalysis.CSharp 5.12.0 and verified with xUnit v3 4.0.3 tests.

Guess First

In this post we connect the filter language we write for Bookstore, the online bookstore used as the shared example across this site's series, to EF Core. A user types price < 300 and author = "Jane Austen" and the filter goes to SQL Server. First question: how do 300 and Jane Austen appear in the generated SQL, as literals written into the query text or as parameters?

Second question: a user types title contains "50%_off". contains will become LIKE in SQL. Do the % and _ the user typed act as LIKE wildcards, or are they searched for as plain characters?

Parsing Is Not Understanding

The parser from post 03 accepts the filter price = "abc" without any objection. Syntactically it is flawless: a field, an operator, a literal. The problem is the meaning: price is a number, "abc" is a string, and the two cannot be compared. The stage that finds this is called semantic analysis. Roughly, it does two jobs. Binding connects every name to its declaration: price is the Book.Price property. Type checking computes the type of every expression and checks that it follows the rules.

The interpreter did this check while running, book by book, and the error only appeared when it reached the relevant row. Now we will do the same check once, before the filter is applied to any book. The output of this stage is a new tree: a bound tree in which every node knows its type and every name its symbol. Roslyn makes the same split internally: the parser produces a syntax tree, the binder builds a bound tree from it, and that is exposed to the outside as the SemanticModel API. Code generation works from the bound tree, not the syntax tree.

Symbol Tables and Scope

The first thing binding needs is a symbol table: which names exist, and what does each one point to? Our language has a single scope, the fields a filter can read:

namespace Bookstore.Filter.Binding;

public enum FilterType { Int, Decimal, String, Bool, Error }

public sealed record FieldSymbol(string Name, FilterType Type, PropertyInfo Property);

// The only scope of the language: the fields a filter may read. Anything else is an unknown name.
public sealed class SymbolTable
{
    private readonly FrozenDictionary<string, FieldSymbol> _fields;

    public SymbolTable(IEnumerable<FieldSymbol> fields) =>
        _fields = fields.ToFrozenDictionary(f => f.Name, StringComparer.OrdinalIgnoreCase);

    public static SymbolTable ForBooks { get; } = new(
    [
        Field("isbn", FilterType.String, nameof(Book.Isbn)),
        Field("title", FilterType.String, nameof(Book.Title)),
        Field("author", FilterType.String, nameof(Book.Author)),
        Field("price", FilterType.Decimal, nameof(Book.Price)),
        Field("year", FilterType.Int, nameof(Book.Year)),
        Field("stock", FilterType.Int, nameof(Book.Stock)),
    ]);

    public IEnumerable<string> Names => _fields.Keys;

    public FieldSymbol? Lookup(string name) => _fields.GetValueOrDefault(name);

    private static FieldSymbol Field(string name, FilterType type, string property) =>
        new(name, type, typeof(Book).GetProperty(property)!);
}

Filling the table automatically with typeof(Book).GetProperties() is tempting, but we wrote it by hand on purpose. The symbol table is also an allow list: if a property customers should not see, such as CostPrice or SupplierId, is added to Book later, the filter language must not expose it on its own. The type is written in the table as well; price is a decimal, year an int.

A single scope is not enough in a real programming language. In C#, a lambda parameter, a method's locals, the class's fields and the types brought in with using form nested scopes. Name lookup starts in the innermost scope and moves one level out if it finds nothing. Roslyn does this with binders chained to each other: the lambda's binder points to the method's, which points to the class's. Since our language has no let or subqueries, the chain has a single link; but the rule is the same, a name either binds to a symbol or is an error.

Type Checking and Implicit Conversion

The binder walks the AST and produces a bound node for every node. Literals first, because this is where the difference between 300 and 300.0 shows up:

private static BoundLiteral BindLiteral(Literal literal) => literal.Value switch
{
    // 300 is an int, 300.0 and 49.90 are decimals: decimal keeps the scale it was parsed with
    decimal d when d.Scale == 0 && d is >= int.MinValue and <= int.MaxValue => new BoundLiteral((int)d, FilterType.Int),
    decimal d => new BoundLiteral(d, FilterType.Decimal),
    string s => new BoundLiteral(s, FilterType.String),
    bool b => new BoundLiteral(b, FilterType.Bool),
    _ => throw new InvalidOperationException($"unexpected literal {literal.Value}"),
};

The real rules are in comparison. contains works only with strings, = and != with equal types or two numbers, and the ordering operators only with numbers. We do not allow comparing strings with <, because in memory the result would be decided by string.CompareOrdinal and in SQL Server by the column's collation; we do not want the two back ends to return different books for the same filter.

private BoundExpr BindComparison(ComparisonExpr c)
{
    BoundExpr left = BindExpr(c.Left);
    BoundExpr right = BindExpr(c.Right);
    if (left.Type == FilterType.Error || right.Type == FilterType.Error)
        return new BoundError(); // the cause is already reported; do not add a second error

    string symbol = Operators.Symbol(c.Operator);
    bool numeric = IsNumeric(left.Type) && IsNumeric(right.Type);
    bool valid = c.Operator switch
    {
        ComparisonOperator.Contains => left.Type == FilterType.String && right.Type == FilterType.String,
        ComparisonOperator.Equal or ComparisonOperator.NotEqual => numeric || left.Type == right.Type,
        // ordering strings would depend on collation, so only numbers can be ordered
        _ => numeric,
    };
    if (!valid)
    {
        Error(c.Position, $"operator '{symbol}' cannot be applied to {Name(left.Type)} and {Name(right.Type)}");
        return new BoundError();
    }

    // implicit conversion: int widens to decimal, as in C#
    if (numeric && left.Type != right.Type)
    {
        if (left.Type == FilterType.Int)
            left = ToDecimal(left);
        else
            right = ToDecimal(right);
    }
    return new BoundComparison(left, c.Operator, right);
}

// a literal is converted now (constant folding); a field gets a conversion node that runs per row
private static BoundExpr ToDecimal(BoundExpr operand) => operand is BoundLiteral { Value: int value }
    ? new BoundLiteral((decimal)value, FilterType.Decimal)
    : new BoundConversion(operand, FilterType.Decimal);

In price < 300 the left side is a decimal and the right side an int. C#'s rule applies here too: there is an implicit conversion from int to decimal, not the other way round. The binder adds the conversion to the tree explicitly. A conversion node appears in the tree even though the user never wrote one; that is exactly what an implicit conversion is inside a compiler. A literal being converted does not have to wait, though: 300 becomes 300m during binding. This is called constant folding. The ldc.i4 300 and newobj Decimal::.ctor(int32) pair we saw in the IL in post 01 was also how Roslyn produced the constant 300m; it was not converting an int variable at run time.

The role of BoundError matters. In prise < 300 we write one error for the unknown name; the comparison then receives the Error type and returns BoundError without writing a second error. Without that, a single typo would produce a separate "cannot be applied to error and int" message for every expression that uses it.

$ dotnet run --project src/Bookstore.Filter.Cli -- check 'price = "abc"'
price = "abc"
      ^ error at 1:7: operator '=' cannot be applied to decimal and string
$ dotnet run --project src/Bookstore.Filter.Cli -- check 'prise < 300 and stock > 0'
prise < 300 and stock > 0
^ error at 1:1: unknown field 'prise'; did you mean 'price'?
$ dotnet run --project src/Bookstore.Filter.Cli -- check 'price and stock'
price and stock
^ error at 1:1: 'and' needs true or false, but this operand is decimal
price and stock
          ^ error at 1:11: 'and' needs true or false, but this operand is int
$ dotnet run --project src/Bookstore.Filter.Cli -- check 'title < "M"'
title < "M"
      ^ error at 1:7: operator '<' cannot be applied to string and string

In post 03, price = "abc" returned Dune and then blew up on The Hobbit. Now the filter is rejected before it touches any book. The "did you mean" hint compares the unknown name with the names in the table by Levenshtein distance and suggests one if it is at most two letters away.

Code Generation: From the Bound Tree to an Expression Tree

Time to turn the verified tree into something that runs. We target Expression<Func<Book, bool>> because in .NET it is an IR that two different back ends understand: Compile() turns it into a delegate that runs in memory, and EF Core turns it into SQL. The Expression Tree API itself is covered in the C# Advanced series post "Expression Trees in C#: Holding a Lambda as Data, and the Bridge to EF Core"; here we use it as a compiler's back end:

public enum LiteralMode
{
    // values are read from a holder object; EF Core turns them into SQL parameters
    Parameterized,
    // values are embedded as constants; EF Core writes them into the SQL text
    Inline,
}

// Code generation: bound tree -> Expression<Func<Book, bool>>. The tree is only ever built from a type-checked
// bound tree, so Expression.* factory methods never see mismatched operand types.
public static class ExpressionCompiler
{
    private static readonly MethodInfo StringContains = typeof(string).GetMethod(nameof(string.Contains), [typeof(string)])!;

    public static Expression<Func<Book, bool>> Compile(BoundExpr root, LiteralMode mode = LiteralMode.Parameterized)
    {
        ParameterExpression book = Expression.Parameter(typeof(Book), "book");
        return Expression.Lambda<Func<Book, bool>>(Emit(root, book, mode), book);
    }

    private static Expression Emit(BoundExpr node, ParameterExpression book, LiteralMode mode) => node switch
    {
        BoundField field => Expression.Property(book, field.Field.Property),
        BoundLiteral literal => EmitLiteral(literal, mode),
        BoundConversion conversion => Expression.Convert(Emit(conversion.Operand, book, mode), typeof(decimal)),
        BoundNot not => Expression.Not(Emit(not.Operand, book, mode)),
        BoundLogical { Operator: LogicalOperator.And } and =>
            Expression.AndAlso(Emit(and.Left, book, mode), Emit(and.Right, book, mode)),
        BoundLogical or => Expression.OrElse(Emit(or.Left, book, mode), Emit(or.Right, book, mode)),
        BoundComparison comparison => EmitComparison(comparison, book, mode),
        _ => throw new InvalidOperationException("cannot generate code for a filter with errors"),
    };

    private static Expression EmitLiteral(BoundLiteral literal, LiteralMode mode)
    {
        Type type = literal.Type switch
        {
            FilterType.Int => typeof(int),
            FilterType.Decimal => typeof(decimal),
            FilterType.String => typeof(string),
            _ => typeof(bool),
        };
        if (mode == LiteralMode.Inline)
            return Expression.Constant(literal.Value, type);

        // same shape the C# compiler produces for a captured local: a field read on a closure object
        object holder = Activator.CreateInstance(typeof(Captured<>).MakeGenericType(type), literal.Value)!;
        return Expression.Field(Expression.Constant(holder), "value");
    }

    private sealed class Captured<T>(T value)
    {
        // the field name becomes the SQL parameter name (@value, @value1, ...)
        public readonly T value = value;
    }
}

The code generation step is short, because the binder did the hard work. Every bound node maps to an Expression factory call; and becomes AndAlso and short-circuits like && in C#, and BoundConversion becomes Expression.Convert. Had we tried the same thing on a tree that was never type checked, Expression.LessThan would have refused to compare a decimal with an int and thrown an InvalidOperationException. FilterCompiler.Compile puts the whole pipeline together: length check, parse, bind, code generation.

$ dotnet run --project src/Bookstore.Filter.Cli -- check 'price < 300 and author = "Jane Austen"'
book => ((book.Price < value(Bookstore.Filter.CodeGen.ExpressionCompiler+Captured`1[System.Decimal]).value) AndAlso (book.Author == value(Bookstore.Filter.CodeGen.ExpressionCompiler+Captured`1[System.String]).value))
Emma                   Jane Austen       199.00 TRY  stock 7
Persuasion             Jane Austen       185.00 TRY  stock 3
Sense and Sensibility  Jane Austen       210.00 TRY  stock 5

The first line is the expression tree's ToString(); the lines below it are the result of SampleBooks.All.Where(...) with the delegate produced by Compile(). We now have two implementations of the same language: the interpreter from post 03 and the compiled delegate. One of the tests checks that both return the same books for five different filters. This is one of the most effective ways to test a compiler: run two implementations on the same inputs and compare the results.

The Same Tree, as SQL: EF Core and ToQueryString

Handing the expression tree to EF Core brings the second back end in. ToQueryString() shows the SQL that would be sent without connecting to the database; BookstoreContext is set up with the SQL Server provider, but the commands in this post never open a connection:

static int Sql(string filter, LiteralMode mode)
{
    CompiledFilter compiled = FilterCompiler.Compile(filter, mode);
    if (!compiled.Success)
        return Report(filter, compiled.Diagnostics);

    using BookstoreContext db = BookstoreContext.ForSqlServer();
    Console.WriteLine(db.Books.Where(compiled.Expression!).ToQueryString());
    return 0;
}

$ dotnet run --project src/Bookstore.Filter.Cli -- sql 'price < 300 and author = "Jane Austen"'
DECLARE @value decimal(10,2) = 300.0;
DECLARE @value1 nvarchar(100) = N'Jane Austen';

SELECT [b].[Isbn], [b].[Author], [b].[Price], [b].[Stock], [b].[Title], [b].[Year]
FROM [Books] AS [b]
WHERE [b].[Price] < @value AND [b].[Author] = @value1
$ dotnet run --project src/Bookstore.Filter.Cli -- sql-inline 'price < 300 and author = "Jane Austen"'
SELECT [b].[Isbn], [b].[Author], [b].[Price], [b].[Stock], [b].[Title], [b].[Year]
FROM [Books] AS [b]
WHERE [b].[Price] < 300.0 AND [b].[Author] = N'Jane Austen'

The answer to the first guess depends on a choice made in code generation. EF Core writes values embedded with Expression.Constant into the SQL text as literals. If we read the value from a field of an object instead, imitating the shape the C# compiler produces for a local variable captured by a lambda, EF Core turns it into a parameter. The parameter's name comes from the field's name. Even its type comes from the column mapping: decimal(10,2) and nvarchar(100) come from the HasPrecision and HasMaxLength settings in BookstoreContext.

There are two reasons to prefer parameters. The first is SQL Server's plan cache: with literals, every different price means a different query text and a separate execution plan; with parameters, one plan is reused. The second is security. In literal mode EF Core escapes quotes correctly, but user input never entering the SQL text under any circumstances is a stronger guarantee.

$ dotnet run --project src/Bookstore.Filter.Cli -- sql "author = \"x' OR 1=1 --\""
DECLARE @value nvarchar(100) = N'x'' OR 1=1 --';

SELECT [b].[Isbn], [b].[Author], [b].[Price], [b].[Stock], [b].[Title], [b].[Year]
FROM [Books] AS [b]
WHERE [b].[Author] = @value
$ dotnet run --project src/Bookstore.Filter.Cli -- sql 'title contains "50%_off"'
DECLARE @value_contains nvarchar(200) = N'%50\%\_off%';

SELECT [b].[Isbn], [b].[Author], [b].[Price], [b].[Stock], [b].[Title], [b].[Year]
FROM [Books] AS [b]
WHERE [b].[Title] LIKE @value_contains ESCAPE N'\'
$ dotnet run --project src/Bookstore.Filter.Cli -- sql 'year >= 1900.5 or title contains "Dune"'
DECLARE @value decimal(18,2) = 1900.5;
DECLARE @value1_contains nvarchar(200) = N'%Dune%';

SELECT [b].[Isbn], [b].[Author], [b].[Price], [b].[Stock], [b].[Title], [b].[Year]
FROM [Books] AS [b]
WHERE CAST([b].[Year] AS decimal(18,2)) >= @value OR [b].[Title] LIKE @value1_contains ESCAPE N'\'

The answer to the second guess is here too. When EF Core translates string.Contains with a parameter, it escapes the user's % and _ characters with a backslash and adds ESCAPE to the query; 50%_off is searched for as plain text. We did not assume this; one of the tests checks the SQL text, so if a future EF Core version changes the behavior, the test will break.

The last output shows the trace of an implicit conversion in SQL. year is an int column and 1900.5 is a decimal; the binder put the conversion on the field side, and in SQL that became CAST([b].[Year] AS decimal(18,2)). A function applied to the column itself usually prevents SQL Server from using an index on that column for a seek. Which side the conversion goes on makes no difference in memory, but it changes the query plan in the database.

The Roslyn Equivalent: SyntaxTree and SemanticModel

We can see the C# compiler's counterparts of the stages we wrote with the Microsoft.CodeAnalysis.CSharp package. The sample parses two methods that look like a Bookstore query; one is correct, the other contains the mistake b.Price == "abc":

// 1. syntax only: the parser knows the shape, not the meaning
SyntaxTree tree = CSharpSyntaxTree.ParseText(code);
Console.WriteLine($"syntax errors: {tree.GetDiagnostics().Count()}");

// 2. a compilation adds references; the semantic model answers "what does this name mean?"
IEnumerable<MetadataReference> references = ((string)AppContext.GetData("TRUSTED_PLATFORM_ASSEMBLIES")!)
    .Split(Path.PathSeparator)
    .Select(path => MetadataReference.CreateFromFile(path));
CSharpCompilation compilation = CSharpCompilation.Create("Demo", [tree], references,
    new CSharpCompilationOptions(OutputKind.DynamicallyLinkedLibrary));
SemanticModel model = compilation.GetSemanticModel(tree);

foreach (BinaryExpressionSyntax binary in tree.GetRoot().DescendantNodes().OfType<BinaryExpressionSyntax>()
             .Where(b => !b.IsKind(SyntaxKind.LogicalAndExpression)))
{
    string op = model.GetSymbolInfo(binary).Symbol?.ToDisplayString() ?? "(no operator found)";
    TypeInfo right = model.GetTypeInfo(binary.Right);
    Conversion conversion = model.GetConversion(binary.Right);
    string kind = conversion.IsIdentity ? "identity" : conversion.IsNumeric ? "implicit numeric" : "none";
    Console.WriteLine($"{binary,-26} {op}");
    Console.WriteLine($"{"",-26} right operand: {right.Type} -> {right.ConvertedType} ({kind})");
}

MemberAccessExpressionSyntax price = tree.GetRoot().DescendantNodes().OfType<MemberAccessExpressionSyntax>()
    .First(m => m.Name.Identifier.Text == "Price");
Console.WriteLine($"b.Price binds to: {model.GetSymbolInfo(price).Symbol?.ToDisplayString()} ({model.GetSymbolInfo(price).Symbol?.Kind})");

// 3. the binder's errors only appear once there is a compilation; formatted in English on any machine
foreach (Diagnostic diagnostic in compilation.GetDiagnostics().Where(d => d.Severity == DiagnosticSeverity.Error))
    Console.WriteLine(CSharpDiagnosticFormatter.Instance.Format(diagnostic, CultureInfo.InvariantCulture));

$ dotnet run --project samples/RoslynSemantic
syntax errors: 0
b.Price < 300              decimal.operator <(decimal, decimal)
                           right operand: int -> decimal (implicit numeric)
b.Author == "Jane Austen"  string.operator ==(string, string)
                           right operand: string -> string (identity)
b.Price == "abc"           (no operator found)
                           right operand: string -> string (identity)
b.Price binds to: Book.Price (Property)
(11,26): error CS0019: Operator '==' cannot be applied to operands of type 'decimal' and 'string'

The output is exactly what our binder does. The syntax tree has no errors; b.Price == "abc" is syntactically valid. b.Price binds to a property symbol. For <, decimal's operator is chosen and an implicit numeric conversion is recorded for the 300 on the right; that is what our ToDecimal does as well. No suitable operator is found for "abc", and the CS0019 error comes only from the compilation, that is, from the binder. If you want to look at these by hand, SharpLab (sharplab.io) shows the syntax tree, the IL and the JIT output of a line of C# in the browser. In Visual Studio, with the .NET Compiler Platform SDK component installed, the View > Other Windows > Syntax Visualizer window also shows the tree of the file in the editor live.

This split also explains where the tools that extend C# plug into the pipeline. Analyzers look at the syntax tree and the semantic model and produce diagnostics; writing your own rules is the topic of the upcoming Static Analysis series. Source Generators read the compilation (with its syntax and semantic information) and add new source files, and the compiler includes them before emit. Writing one is covered in the C# Advanced series post "Source Generators in C#: Generating Code at Compile Time with IIncrementalGenerator".

In Production

A query language that takes user input is part of your attack surface. In our language SQL injection is closed by construction: field names can only come from the symbol table, values always become parameters, and EF Core, not us, produces the SQL. But injection is not the only risk; there is also resource consumption. We added a depth limit in post 03. It is not enough:

$ dotnet run --project src/Bookstore.Filter.Cli -- chain 5000
chain: 69995 chars, 0 parse error(s), AST depth 5001
bound: 0 error(s)
limited: error at 1:1: filter is 69995 characters long (limit 1000)
$ dotnet run --project src/Bookstore.Filter.Cli -- chain 200000
chain: 2799995 chars, 0 parse error(s), AST depth 200001
Stack overflow.
Repeated 22715 times:
--------------------------------
   at Bookstore.Filter.Binding.Binder.BindLogical(Bookstore.Filter.Syntax.BinaryExpr)
   at Bookstore.Filter.Binding.Binder.BindExpr(Bookstore.Filter.Syntax.Expr)
--------------------------------
   at Bookstore.Filter.Binding.Binder.Bind(Bookstore.Filter.Syntax.Expr, Bookstore.Filter.Binding.SymbolTable)

The chain command parses and binds a stock > 0 and stock > 0 and ... chain, bypassing the length limit. The Pratt parser collected 200,000 conditions on a single level without an error; but the AST is 200,001 levels deep, and the binder, which walks the tree recursively, took the process down. The parser's depth limit never kicked in. That is why FilterCompiler.Compile limits the input to 1,000 characters before anything else; that also caps the depth of the tree at a few hundred. For a filter typed into a search box, 1,000 characters is plenty.

Do not forget the cost on the database side. title contains "a" becomes LIKE '%a%' and scans the whole table. On a large catalog you need to require at least a few characters for contains, add a TOP or paging to the query and keep EF Core's command timeout low. These are the responsibility of the API that runs the language, not of the language itself; the ASP.NET Core Web API series post "Pagination, Filtering and Sorting" and the .NET 7 what's-new post, which covers rate limiting, deal with that side.

Compile() generates new IL and hands it to the JIT on every call. If the same filter text comes in often, cache the compiled delegate by filter text; EF Core also caches the compiled form of parameterized queries on its side, which is one more benefit of using parameters.

Common Pitfalls

Assuming the two back ends carry the same meaning. The in-memory delegate compares with string.Contains, ordinal and case-sensitive. In SQL Server the result depends on the column's collation, and the commonly used default collations are case-insensitive. title contains "dune" can find Dune in the database while returning nothing in memory. We did not run the queries against a database in this post; this difference is known behavior, and when designing the language you either accept it or apply the same rule explicitly on both sides.

Filling the symbol table automatically with reflection. Every new property added to the entity becomes filterable on its own. Filterable fields should be a deliberate allow list.

Leaving type checking to code generation. Expression.Equal(decimal, string) throws an exception, but it names no line and no column. Catch the error in the binder, where the user can understand it; code generation should only ever see a valid tree.

Putting an implicit conversion on an arbitrary side. Converting a literal is free; converting a column costs something on every row and can lose an index in the database. Wherever possible, convert the constant side.

A Small Experiment

★☆☆ Remove the HasMaxLength(100) setting for the Author column in BookstoreContext and run the sql command again. How did the parameter's type change? Think about what that does to the plan cache.

★★☆ Add a DateOnly field called published to the language, with date literals of the form published >= 2020-01-01. What did you change in the lexer, the binder and code generation? Write a test that checks the SQL produced by ToQueryString.

★★★ For comparisons between an int column and a fractional literal, such as year >= 1900.5, write a rule that applies the conversion to the literal instead of the column (equivalent to year >= 1901). For which operators do you round up, and for which down? Verify the rule with a test that compares the in-memory delegate with the interpreter.

The front end is complete: text became tokens, tokens a tree, the tree a verified bound tree, and that a delegate or SQL. In the next post we move to the other end of the back end, the .NET runtime: we will look at the stack-based structure of IL, tiered compilation, Dynamic PGO, inlining and the escape analysis of .NET 10 through DOTNET_JitDisasm output.