Base de conhecimentoCentro de Exames
PT · PTPortuguês (Portugal)
Escolher idioma13

CKTIS / C#

Arquitetura de programas: parser, AST e interpretador de uma DSL

Separe a sintaxe de uma pequena linguagem específica de um domínio da sua execução. Um parser constrói uma árvore de sintaxe abstrata e um interpretador de AST calcula o resultado a partir dos seus nós. Esta separação permite testar, de forma independente, o processamento do texto, a representação do programa e as regras de execução.

Versão: .NET 10; repository net10.0 and LangVersion=preview; feature versions require per-entry verification

Sintaxe

DSL text → parser → abstract syntax tree (AST) → AST interpreter → result

A arquitetura de um programa define as responsabilidades dos seus componentes e o fluxo de dados entre eles. Para uma pequena linguagem específica de um domínio (DSL), que descreve um conjunto limitado de operações, use uma cadeia de processamento: texto → parser → abstract syntax tree (AST, árvore de sintaxe abstrata) → AST interpreter → resultado. Trata-se de um padrão de conceção, não de uma funcionalidade especial de C#.

O parser verifica a sintaxe e constrói nós AST, em vez de executar o comando durante a leitura. Um analisador léxico separado pode extrair primeiro os tokens; neste caso, basta dividir pelos espaços. Uma AST preserva a estrutura das operações, mas não necessariamente todo o texto de origem. Não a confunda com a árvore Roslyn completa, que também preserva comentários e espaços em branco.

O exemplo reconhece comandos da forma add <int> <int>. Parse divide o texto pelos caracteres de espaço, descarta os tokens vazios e espera que restem exatamente três tokens. O primeiro tem de ser add em minúsculas, e os outros dois têm de poder ser convertidos em valores Int32 por Int32.TryParse com NumberStyles.AllowLeadingSign e CultureInfo.InvariantCulture. O sinal inicial é opcional, e Int32.TryParse ignora caracteres NUL (U+0000) no fim dos tokens numéricos, pelo que também é aceite um algarismo seguido de um carácter NUL. Parse cria um Add com dois nós Number. Evaluate, o interpretador de AST, calcula recursivamente os valores dos nós; não gera código de máquina nem IL. A entrada add 2 3 produz 5.

A separação destas etapas permite testar o parser e o interpretador de forma independente. Parse lança FormatException se não houver exatamente três tokens, se o primeiro não for add ou se não for possível converter um dos dois tokens numéricos. Uma adição fora do intervalo de Int32 provoca OverflowException devido a checked. Esta é deliberadamente uma linguagem mínima, sem expressões aninhadas. Ao expandi-la, acrescente diagnósticos com posições no texto e limites para o comprimento da entrada e a profundidade da árvore; a separação das etapas, por si só, não torna segura a execução de programas não fidedignos.

Exemplos

using System;
using System.Globalization;

Expr ast = Parse("add 2 3");
Console.WriteLine(Evaluate(ast).ToString(CultureInfo.InvariantCulture));

static Expr Parse(string text)
{
    string[] tokens = text.Split(' ', StringSplitOptions.RemoveEmptyEntries);
    if (tokens.Length != 3 || tokens[0] != "add" ||
        !int.TryParse(tokens[1], NumberStyles.AllowLeadingSign,
            CultureInfo.InvariantCulture, out int left) ||
        !int.TryParse(tokens[2], NumberStyles.AllowLeadingSign,
            CultureInfo.InvariantCulture, out int right))
        throw new FormatException("Expected: add <int> <int>");

    return new Add(new Number(left), new Number(right));
}

static int Evaluate(Expr expr) => expr switch
{
    Number n => n.Value,
    Add a => checked(Evaluate(a.Left) + Evaluate(a.Right)),
    _ => throw new InvalidOperationException("Unknown AST node.")
};

abstract record Expr;
sealed record Number(int Value) : Expr;
sealed record Add(Expr Left, Expr Right) : Expr;

Resultado

5

O código apresentado e o resultado declarado foram verificados num ambiente isolado pelo método registado na prova de verificação desta versão exata.

Fontes