FluentIL – Parte 8 – Compilando expressões

Posted on junho 1, 2011 by elemarjr

Olá pessoal, como estamos?

Outro dia falei sobre como reconhecer tokens em cadeias de caracteres. Depois, falei como fazer o parsing destes tokens conforme uma gramática LL(1). São conhecimentos fundamentais para quem pretende entender como funciona (ou se escreve) um compilador.

No post de hoje utilizo os conceitos já apresentados para adicionar suporte a “compilação” de expressões em nossa DSL para emitting.

Como de costume, você pode fazer o download de todo o código fonte de https://github.com/elemarjr/FluentIL. Os posts anteriores também estão disponíveis.

Ouvindo: Lord of Rings – Soundtrack

Gramática que desejamos suportar

A gramática que desejo suportar é um pouco mais “sofisticada” do que a apresentada outro dia. Observe (pseudo-gramática ANTLR).

expression
        :       logicalExpression EOF!
        ;

logicalExpression
        :       booleanAndExpression (OR^ booleanAndExpression )*
        ;

OR      :       '||' 

booleanAndExpression
        :       equalityExpression (AND^ equalityExpression)*
        ;

AND     :       '&&' 

equalityExpression
        :       relationalExpression ((EQUALS|NOTEQUALS)^ relationalExpression)*
        ;

EQUALS
        :       '==';
NOTEQUALS
        :       '!=' | '<>';

relationalExpression
        :       additiveExpression ( (LT|LTEQ|GT|GTEQ)^ additiveExpression )*
        ;

LT      :       '<';
LTEQ    :       '<=';
GT      :       '>';
GTEQ    :       '>=';

additiveExpression
        :       multiplicativeExpression ( (PLUS|MINUS)^ multiplicativeExpression )*
        ;

PLUS    :       '+';
MINUS   :       '-';

multiplicativeExpression
        :       powerExpression ( (MULT|DIV|MOD)^ powerExpression )*
        ;

MULT    :       '*';
DIV     :       '/';
MOD     :       '%';

powerExpression
        :       unaryExpression ( POW^ unaryExpression )*
        ;

POW     :       '^';

unaryExpression
        :       primaryExpression
        |       NOT^ primaryExpression
        |       MINUS primaryExpression -> ^(NEGATE primaryExpression)
        ;

NOT     :       '!' | 'not';

primaryExpression
        :       '('! logicalExpression ')'!
        |       value
        ;

value
        :       INTEGER
        |       FLOAT
        |       identifier
        ;

As principais diferenças percebidas são:

possibilidade informar números negativos (no exemplo que havia apresentado antes isso não era possível);
negação (not)
suporte a comparações;
suporte a expreções lógicas mais compexas com And e Or.

Observe como essa gramática garante as precedências.

Implementando o Scanner

A código do Scanner (ou seja, o código que converte uma sequência de caracteres em tokens) é uma evolução da apresentada outro dia. Em outras palavras, continuo usando Table-driven scanning.

Fiz umas melhorias na fluência para “geração” da tabela. Além disso, criei uma especialização da classe Scanner para nosso código em IL. Observe:

class ExpressionScanner : Scanner
{
    public ExpressionScanner() :
        base(BuildTable())
    {}

    private static StateTable BuildTable()
    {
        string whitespaces = " \t\n";
        string digits = "0123456789";
        string letters = "qwertyuiopasdfghjklzxcvbnm";

        return new StateTable("s1")
            .WithState("s1", new State()
                .WithGoTo(whitespaces, "s17")
                .WithGoTo(digits, "s14")
                .WithGoTo(letters, "s16")
                .WithGoTo('/', "s2")
                .WithGoTo('.', "s13")
                )

            .WithState("s2", new State("divide")
                .WithGoTo('/', "s3")
                .WithGoTo('*', "s4")
                )
            .WithState("s3", new State()
                .WithGoTo(" \t", "s3")
                .WithGoTo('\n', "s18")
                .WithGoTo("/*()+-:.", "s3")
                .WithGoTo(digits, "s3")
                .WithGoTo(letters, "s3")
                )
            .WithState("s4", new State()
                .WithGoTo(" \t\n/()+-:.", "s4")
                .WithGoTo('*', "s5")
                .WithGoTo(digits, "s4")
                .WithGoTo(letters, "s4")
                )
            .WithState("s5", new State()
                .WithGoTo(whitespaces, "s4")
                .WithGoTo('/', "s18")
                .WithGoTo('*', "s5")
                .WithGoTo("()+-:.", "s4")
                .WithGoTo(digits, "s4")
                .WithGoTo(letters, "s4")
                )
            .WithState("s12", new State("assign"))
            .WithState("s13", new State()
                .WithGoTo(digits, "s15")
                )
            .WithState("s14", new State("integer")
                .WithGoTo(digits, "s14")
                .WithGoTo('.', "s15")
                )
            .WithState("s15", new State("float")
                .WithGoTo(digits, "s15")
                )
            .WithState("s16", new State("identifier")
                .WithGoTo(digits, "s16")
                .WithGoTo(letters, "s16")
                )
            .WithState("s17", new State("white_space")
                .WithGoTo(whitespaces, "s17")
                )
            .WithState("s18", new State("comment"))

            .WithToken('(', "lparen")
            .WithToken(')', "rparen")
            .WithToken('+', "plus")
            .WithToken('-', "minus")
            .WithToken('*', "times")
            .WithToken('>', "gt")
            .WithToken(">=", "geq")
            .WithToken('<', "lt")
            .WithToken("<=", "leq")
            .WithToken("==", "eq")
            .WithToken("!", "not")
            .WithToken("!=", "neq")
            .WithToken("<>", "neq")
            .WithToken(":=", "assign")
            .WithToken("||", "or")
            .WithToken("&&", "and")
            .WithToken("^", "pow")
            .WithToken("%", "mod")
            ;
    }
}

Perfeito! Repare que há tokens reconhecidos por esse scanner que não são suportados pela gramática que apresentei. Optei por deixar o scanner mais “completo” agora. No futuro, aprimoro o scanner.

Implementando o Parser

Como estou proponto uma gramática toda nova, implemento um Parser todo novo. Para escrever o parser, utilzei a mesma técnica de outro dia: implementei um Recursive descendent parser.

O código é um pouco extenso, mas vale a pena. Vamos por partes:

internal class Parser : IDisposable
{
    public IEnumerable Source { get; private set; }
    public DynamicMethodBody MethodBody { get; private set; }

    internal Parser(IEnumerable source,
        DynamicMethodBody body = null)
    {
        this.Source = source;
        this.MethodBody = body;
    }

    IEnumerator SourceEnumerator;
    Token input_token;
    Token GetNextToken()
    {
        while (this.SourceEnumerator.MoveNext())
        {
            var result = this.SourceEnumerator.Current;
            if (result.Id != "white_space" &&
                result.Id != "comment" )
                return result;
        }

        return new Token("EOP", "EOP");
    }

    public void Dispose()
    {
        this.SourceEnumerator.Dispose();
    }

    public static void Parse(string expression,
        DynamicMethodBody methodBody = null)
    {
        new Parser(
            new ExpressionScanner().Scan(expression),
            methodBody
            ).Parse();
    }
 //..
}

Gostaria de chamar a atenção para o método estático Parse. Ele gera um novo parser contando com o Scanner que desenvolvemos acima e um DynamicMethodBody que será utilizado para a ocorrência dos emittings. Repare também como o método GetNextToken descarta espaços em branco e comentários (não reconhedios pela gramática).

Daqui para diante, a lógica é sempre a mesma. Implemento um método para cada não-terminal da grmática. Comecemos por LogicalExpression:

public void Parse()
{
    if (this.SourceEnumerator != null)
        this.SourceEnumerator.Dispose();

    this.SourceEnumerator = this.Source.GetEnumerator();
    input_token = GetNextToken();
    Begin("Expression");
    LogicalExpression();
    Match("EOP");
    End();
}

void LogicalExpression()
{
    Begin("Logical");
    switch (input_token.Id)
    {
        case "integer":
        case "float":
        case "lparen":
        case "not":
        case "minus":
        case "identifier":
            BooleanExpression();
            BooleanExpressionTail();
            break;
        default:
            throw new UnexpectedTokenException(input_token);
    }
    End();
}

Como pode perceber, sempre que um não-terminal possui recursão, implemento dois métodos de controle: um para a primeira parte, outro para a recursão (sufixo Tail);

void BooleanExpression()
{
    Begin("Boolean");
    switch (input_token.Id)
    {
        case "integer":
        case "float":
        case "lparen":
        case "not":
        case "minus":
        case "identifier":
            BooleanAndExpression();
            BooleanAndExpressionTail();
            break;
        default:
            throw new UnexpectedTokenException(input_token);
    }
    End();
}

void BooleanExpressionTail()
{
    Begin("BooleanTail");
    switch (input_token.Id)
    {
        case "or":
            OrOp();
            var btrue = Guid.NewGuid().ToString();
            var bend = Guid.NewGuid().ToString();
            if (this.MethodBody != null)
                this.MethodBody
                    .Brtrue(btrue);
            BooleanExpression();
            BooleanExpressionTail();
            if (this.MethodBody != null)
                this.MethodBody
                    .Br_S(bend)
                    .MarkLabel(btrue)
                    .Ldc(1)
                    .MarkLabel(bend);
            break;
        case "rparen":
        case "EOP":
            Skip();
            break;
        default:
            throw new UnexpectedTokenException(input_token);
    }
    End();
}

private void OrOp()
{
    switch (input_token.Id)
    {
        case "or":
            Match(input_token.Id);
            break;
        default:
            throw new UnexpectedTokenException(input_token);
    }
}

Perceba como mesclo emitting e parsing. Perceba que só é necessário gerar IL se houver ocorrência do operador OR. A mesma lógica é percebida na implementação do And. Observe:

private void BooleanAndExpression()
{
    Begin("BooleanAnd");
    switch (input_token.Id)
    {
        case "integer":
        case "float":
        case "not":
        case "lparen":
        case "minus":
        case "identifier":
            EqualityExpression();
            EqualityExpressionTail();
            break;
        default:
            throw new UnexpectedTokenException(input_token);
    }
    End();
}

void BooleanAndExpressionTail()
{
    Begin("BooleanAndTail");
    switch (input_token.Id)
    {
        case "and":
            AndOp();
            var bfalse = Guid.NewGuid().ToString();
            var bend = Guid.NewGuid().ToString();
            if (this.MethodBody != null)
                this.MethodBody
                    .Brfalse(bfalse);
            BooleanAndExpression();
            BooleanAndExpressionTail();
            if (this.MethodBody != null)
                this.MethodBody
                    .Br_S(bend)
                    .MarkLabel(bfalse)
                    .Ldc(0)
                    .MarkLabel(bend);
            break;
        case "rparen":
        case "or":
        case "EOP":
            Skip();
            break;
        default:
            throw new UnexpectedTokenException(input_token);
    }
    End();
}

private void AndOp()
{
    switch (input_token.Id)
    {
        case "and":
            Match(input_token.Id);
            break;
        default:
            throw new UnexpectedTokenException(input_token);
    }
}

Repare como incorporo “Epsilon predicting” ignorando tokens que sejam compatíveis com tratamentos de nível mais alto.

Implementados OR e AND, adiciono suporte para comparações de igualdade. Observe:

private void EqualityExpression()
{
    Begin("Equality");
    switch (input_token.Id)
    {
        case "integer":
        case "float":
        case "not":
        case "lparen":
        case "minus":
        case "identifier":
            RelationalExpression();
            RelationalExpressionTail();
            break;
        default:
            throw new UnexpectedTokenException(input_token);
    }
    End();
}

void EqualityExpressionTail()
{
    Begin("EqualityTail");
    switch (input_token.Id)
    {
        case "eq":
        case "neq":
            var op = input_token.Id;
            EqualOp();
            EqualityExpression();
            EqualityExpressionTail();
            EmitOp(op);
            break;
        case "rparen":
        case "or":
        case "and":
        case "EOP":
            Skip();
            break;
        default:
            throw new UnexpectedTokenException(input_token);
    }
    End();
}

private void EqualOp()
{
    switch (input_token.Id)
    {
        case "eq":
        case "neq":
            Match(input_token.Id);
            break;
        default:
            throw new UnexpectedTokenException(input_token);
    }
}

O método auxiliar EmitOp seleciona o emitting adequado para o operador que foi utilizado. A sutileza aqui é “visitar” o lado esquerdo e direito da comparação antes de emitir o IL correspondente ao operador.

Para fins de clareza, segue o código do método EmitOp:

private void EmitOp(string operation)
{
    if (this.MethodBody == null)
        return;

    switch (operation)
    {
        case "plus":
            this.MethodBody.Add();
            break;
        case "minus":
            this.MethodBody.Sub();
            break;
        case "times":
            this.MethodBody.Mul();
            break;
        case "divide":
            this.MethodBody.Div();
            break;
        case "mod":
            this.MethodBody.Rem();
            break;
        case "lt":
            this.MethodBody.Clt();
            break;
        case "leq":
            this.MethodBody.Cle();
            break;
        case "gt":
            this.MethodBody.Cgt();
            break;
        case "geq":
            this.MethodBody.Cge();
            break;
        case "eq":
            this.MethodBody.Ceq();
            break;
        case "neq":
            this.MethodBody
                .Ceq()
                .Ldc(0)
                .Ceq();
            break;
        default:
            throw new NotSupportedException();
    }
}

A implementação dos demais não-terminais segue a mesma lógica apontada até aqui. Consulte o código-fonte para ter acesso a implementação completa.

Utilizando o parser no Emitting

Para adicionar suporte ao parser no Emitting, fiz três alterações no código.

Comecemos pela óbvia, adicionar um método Helper a DSL para execução do parsing:

public DynamicMethodBody Parse(string expression)
{
    Parser.Parse(expression, this);
    return this;
}

Esse simples helper permite escrever códigos assim:

[Test]
public void Parsing07()
{
    var il = IL.NewMethod()
        .WithParameter(typeof(int), "a")
        .WithParameter(typeof(int), "b")
        .Returns(typeof(bool))
        .Parse("a>=b")
        .Ret();

    var result = il.Invoke(3, 3);

    result.Should().Be(true);
}

[Test]
public void Parsing08()
{
    var il = IL.NewMethod()
        .WithParameter(typeof(int), "a")
        .WithParameter(typeof(int), "b")
        .Returns(typeof(bool))
        .Parse("a<=b")
        .Ret();

    var result = il.Invoke(3, 3);

    result.Should().Be(true);
}

[Test]
public void Parsing09()
{
    var il = IL.NewMethod()
        .WithParameter(typeof(int), "a")
        .WithParameter(typeof(int), "b")
        .Returns(typeof(bool))
        .Parse("a==b")
        .Ret();

    var result = il.Invoke(3, 3);

    result.Should().Be(true);
}

[Test]
public void Parsing10()
{
    var il = IL.NewMethod()
        .WithParameter(typeof(int), "a")
        .WithParameter(typeof(int), "b")
        .Returns(typeof(bool))
        .Parse("a!=b")
        .Ret();

    var result = il.Invoke(3, 3);

    result.Should().Be(false);
}

[Test]
public void Parsing11()
{
    var il = IL.NewMethod()
        .WithParameter(typeof(int), "a")
        .WithParameter(typeof(int), "b")
        .Returns(typeof(bool))
        .Parse("!(a<=b)")
        .Ret();

    var result = il.Invoke(3, 3);

    result.Should().Be(false);
}

[Test]
public void Parsing12()
{
    var il = IL.NewMethod()
        .Returns(typeof(int))
        .Parse("-(2+8)")
        .Ret();

    var result = il.Invoke();

    result.Should().Be(-10);
}

[Test]
public void Parsing13()
{
    var il = IL.NewMethod()
        .WithParameter(typeof(int), "a")
        .Returns(typeof(bool))
        .Parse("(a>5)&&(a<10)")
        .Ret();

    il.Invoke(6).Should().Be(true) ;
    il.Invoke(11).Should().Be(false);
}

[Test]
public void Parsing14()
{
    var il = IL.NewMethod()
        .WithParameter(typeof(int), "a")
        .Returns(typeof(bool))
        .Parse("(a%2)==0")
        .Ret();

    il.Invoke(6).Should().Be(true);
    il.Invoke(5).Should().Be(false);
}

[Test]
public void Parsing15()
{
    var il = IL.NewMethod()
        .WithParameter(typeof(int), "a")
        .Returns(typeof(bool))
        .Parse("(a>5)&&(a<10)&&(a%2==0)")
        .Ret();

    il.Invoke(5).Should().Be(false);
    il.Invoke(6).Should().Be(true);
    il.Invoke(7).Should().Be(false);
    il.Invoke(8).Should().Be(true);
    il.Invoke(9).Should().Be(false);
    il.Invoke(10).Should().Be(false);
}

Chamo atenção especialmente para o código do método Parsing15. Repare que faço três testes bacanas com parâmetros que não ficariam nada óbvios em IL. Considere o pseudo-IL resultante:


.param (0) [System.Int32] a
returns System.Boolean
        ldarg.0
        ldc.i4.5
        cgt
        brfalse IL_0
        ldarg.0
        ldc.i4 10
        clt
        brfalse IL_1
        ldarg.0
        ldc.i4.2
        rem
        ldc.i4.0
        ceq
        br.s IL_2
IL_1:
        ldc.i4.0
IL_2:
        br.s IL_3
IL_0:
        ldc.i4.0
IL_3:
        ret

Lindo, não!

Também criei uma versão do método auxiliar If (dê uma olhada no post 2 dessa série para pegar a idéia completa). Observe:

public DynamicMethodBody If(string expression)
{
    var emitter = new IfEmitter(this);
    _IfEmitters.Push(emitter);
    Parser.Parse(expression, this);
    emitter.EmitBranch(false);
    return this;
}

Isso permite que escrevamos códigos assim:

[Test]
public void Parsing17()
{
    var il = IL.NewMethod()
        .WithParameter(typeof(int), "a")
        .Returns(typeof(int))
        .If("a<5")
            .Ldc(5)
        .Else()
            .Ldarg("a")
        .EndIf()
        .Ret();

    il.Invoke(3).Should().Be(5);
    il.Invoke(4).Should().Be(5);
    il.Invoke(5).Should().Be(5);
    il.Invoke(6).Should().Be(6);
    il.Invoke(7).Should().Be(7);
}

Emitting nunca esteve em tão alto nível. Smiley de boca aberta

Por fim, também criei uma especialização da classe Number (parte 6) para permitir que expressões sejam passadas por parâmetro para métodos que esperam números. Observe:

public class ParseExpressionNumber : Number
{
    public string Expression { get; private set; }
    public ParseExpressionNumber(string expression)
    {
        this.Expression = expression;
    }

    public override void Emit(DynamicMethodBody generator)
    {
        Parser.Parse(this.Expression, generator);
    }
}

Nice!

Nos próximos posts devo revisitar exemplos práticos de uso de emitting que já demonstrei alterando o código para aproveitar as facilidades que adicionamos hoje.

Por hoje, era isso.

Smiley piscando

Posted in: C#, compiladores, DSL, FluentIL, Intermediate Language

Be the first to like this post.

Be the first to start a conversation

FluentIL – Parte 8 – Compilando expressões

Gramática que desejamos suportar

Implementando o Scanner

Implementando o Parser

Utilizando o parser no Emitting

Deixar uma Resposta Cancelar resposta

Pesquisa

Siga-me no Twitter

Meus links

Blogroll

Arquivo

RSS

Posts recentes

Posts mais acessados nas últimas horas

FluentIL – Parte 8 – Compilando expressões

Gramática que desejamos suportar

Implementando o Scanner

Implementando o Parser

Utilizando o parser no Emitting

Deixar uma Resposta Cancelar resposta

Pesquisa

Siga-me no Twitter

Meus links

Categorias

Blogroll

Arquivo

RSS

Posts recentes

Posts mais acessados nas últimas horas