Executando verificação de segurança...
18
kht
10 min de leitura ·

ANTLR - Uma ferramenta para fazer parsing de expressões (ou: não use regex quando há soluções melhores)

O ANTLR (ANother Tool for Language Recognition) é uma excelente ferramenta a ser usada quando você precisa fazer o parsing de expressões complexas.

Para ficar mais claro, vou usar como exemplo um projeto que trabalhei. Basicamente, ele tinha várias fórmulas cadastradas. Um exemplo simples (com os nomes, valores e contexto completamente modificados):

@IDADE == 18 ? 0 : @SALARIO > 1000 ? 1 : @BENEFICIOS < 100 ? 2 : 3 + @BONUS

A sintaxe é similar a várias linguagens, usando o operador ternário: se idade é igual a 18, retorna zero, senão verifica se o salário é maior que 1000. Caso seja, retorna 1, senão verifica se o benefício é menor que 100 (retornando 2 caso seja, ou 3 mais o valor do bônus se não for).

O detalhe é que os valores que começam com @ correspondem a queries no banco de dados. Ou seja, IDADE tinha um query cadastrada, que retornava um valor, que por sua vez seria usado na fórmula. O mesmo para SALARIO e os demais.

Primeira alternativa: regex + replace

A primeira versão usava uma regex para capturar todos os nomes no formato @NOME. Em seguida executava as queries, e fazia um replace dos resultados. No caso acima, seriam executadas 4 queries e 4 replaces.

Porém, muitas vezes demorava bastante por serem queries custosas e complexas. Daí veio a ideia de otimizar.

Por exemplo, se a idade é igual a 18, a expressão retorna zero e neste caso não seria necessário executar as outras queries. Se a idade não fosse 18, mas o salário fosse maior que 1000, não precisaria executar as queries @BENEFICIOS E @BONUS. E assim por diante.

Só que fazer isso com regex já fica mais complicado. A princípio daria para fazer um split usando ? ou : como separador, mas como há várias operações aninhadas, começa a ficar complexo demais.

Vale lembrar que o sistema permitia outras expressões, como AND e OR, que por sinal caem no mesmo problema. Por exemplo, @IDADE < 18 OR @IDADE > 65: se a idade for menor que 18, eu nem preciso avaliar a segunda condição, pois já sei que ela é verdadeira. Agora imagine uma expressão bem complexa, misturando condições AND e OR juntamente com ternários aninhados, além de parênteses (sem limite de aninhamento), etc. Fazer isso com regex se torna bem complicado e custoso.

A alternativa com ANTLR

Com ANTLR, basta que você defina uma gramática, que é um arquivo que contém a definição de todas as expressões válidas.

Claro que aqui tem uma curva de aprendizado que confesso que não é simples, mas que pode valer a pena. Para tal, vamos criar um projeto simples. Eu fiz em Java, mas o ANTLR atualmente suporta 10 linguagens (C++, C#, Dart, Java, JavaScript, PHP, Python, Swift, TypeScript e Go). Então a ideia básica aqui serve para todas.

Primeiro criei um projeto chamado formula-parser com a seguinte estrutura:

src/main/java/parser
 |_ FormulaValue.java
 |_ Main.java
 |_ FormulaEvaluator.java
src/main/antlr4/parser
 |_ Formula.g4
pom.xml

No pom.xml eu adiciono a dependência do ANTLR e demais configurações (obs: para este exemplo, usei o JDK 20):

<project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/maven-v4_0_0.xsd">
    <modelVersion>4.0.0</modelVersion>
    <groupId>br.jus.csjt.sigep.folhaweb</groupId>
    <artifactId>formula-parser</artifactId>
    <packaging>jar</packaging>
    <name>formula-parser</name>
    <version>1.0.0</version>
    <properties>
        <project.build.sourceEncoding>UTF-8</project.build.sourceEncoding>
        <antlr4.version>4.13.2</antlr4.version>
        <maven.compiler.source>20</maven.compiler.source>
        <maven.compiler.target>20</maven.compiler.target>
        <exec.mainClass>parser.Main</exec.mainClass>
    </properties>
    <dependencies>
        <dependency>
            <groupId>org.antlr</groupId>
            <artifactId>antlr4-runtime</artifactId>
            <version>${antlr4.version}</version>
        </dependency>
        <dependency>
            <groupId>org.antlr</groupId>
            <artifactId>antlr4-maven-plugin</artifactId>
            <version>${antlr4.version}</version>
            <scope>compile</scope>
        </dependency>
    </dependencies>
    <build>
        <plugins>
            <plugin>
                <groupId>org.antlr</groupId>
                <artifactId>antlr4-maven-plugin</artifactId>
                <version>${antlr4.version}</version>
                <configuration>
                    <arguments>
                        <argument>-visitor</argument>
                    </arguments>
                </configuration>
                <executions>
                    <execution>
                        <goals>
                            <goal>antlr4</goal>
                        </goals>
                    </execution>
                </executions>
            </plugin>
        </plugins>
    </build>
</project>

E no arquivo Formula.g4 eu coloco a gramática que define o formato de uma expressão:

grammar Formula;

formula: expr EOF;

expr
 : expr op=(MULT | DIV) expr               #multiplicationExpr
 | expr op=(PLUS | MINUS) expr             #additiveExpr
 | expr op=(GTEQ | LTEQ | GT | LT) expr    #relationalExpr
 | expr op=(EQ | NEQ) expr                 #equalityExpr
 | expr '&&' expr                          #andExpr
 | expr '||' expr                          #orExpr
 | <assoc=right>expr '?' expr ':' expr     #ternaryExpr
 | atom                                    #atomExpr
 ;

PLUS: '+';
MINUS: '-';
MULT: '*';
DIV: '/';
EQ: '==';
NEQ: '!=';
GT: '>';
LT: '<';
GTEQ: '>=';
LTEQ: '<=';

atom
 : '(' expr ')'   #parenthesisAtom
 | (INT | FLOAT)  #numberAtom
 | '@' NOME       #idAtom
 ;

INT: [0-9]+;
FLOAT
 : [0-9]+ '.' [0-9]* 
 | '.' [0-9]+
 ;
NOME: [a-zA-Z_] [a-zA-Z_0-9]*;
SPACE: [ \t\r\n] -> skip;

O formato usado é uma extensão do BNF (Backus-Naur Form), e para mais detalhes, sugiro ler a documentação. A sintaxe é bem complexa e cheia de detalhes que não caberiam aqui, mas resumindo: eu defini que uma expressão pode ser um cálculo (com as operações de soma, subtração, multiplicação e divisão), ou de comparações (igual, diferente, maior que, menor que, etc), além do operador ternário e expressões AND e OR. Também há a definição de números (que usa uma sintaxe bem similar à de regex, como o [0-9]+ para designar "um ou mais dígitos de 0 a 9") e das variáveis no formato @NOME.

Depois, basta rodar mvn install para que o ANTLR gere os arquivos necessários. Isso vai variar de uma linguagem para outra (e para mais detalhes, veja a documentação). Em Java, ele gera as classes em target/generated-sources (e veja como configurar sua IDE para que estas façam parte do classpath).

Depois, criei a classe FormulaValue, que representa um valor da fórmula. No caso, o valor pode ser tanto um número quanto um boolean. Por exemplo, na expressão que citei no início, @IDADE == 18 é uma expressão booleana, enquanto que 3 + @BONUS é uma expressão numérica. Enfim, a classe é bem simples, possuindo um boolean e um BigDecimal, sendo que se o número for null, então ela é booleana:

package parser;

import java.math.BigDecimal;

public class FormulaValue {
    // valor pode ser um booleano ou um número: se número é null, então é booleano
    private final boolean bool;
    private final BigDecimal number;
    public FormulaValue(boolean bool) {
        this(bool, null);
    }
    public FormulaValue(double d) {
        this(false, new BigDecimal(d));
    }
    public FormulaValue(BigDecimal number) {
        this(false, number);
    }
    public FormulaValue(boolean bool, BigDecimal number) {
        this.bool = bool;
        this.number = number;
    }
    public Boolean booleanValue() {
        return this.bool;
    }
    public BigDecimal numberValue() {
        return this.number;
    }
    public boolean isNumber() {
        return this.number != null;
    }
    @Override
    public int hashCode() {
        return this.isNumber() ? this.number.hashCode() : Boolean.hashCode(this.bool);
    }
    @Override
    public boolean equals(Object obj) {
        if (this == obj) {
            return true;
        }
        if (obj == null || getClass() != obj.getClass()) {
            return false;
        }
        final FormulaValue other = (FormulaValue) obj;
        boolean thisIsNumber = this.isNumber();
        if (thisIsNumber != other.isNumber()) {
            return false;
        }
        return thisIsNumber ? this.number.equals(other.number) : this.bool == other.bool;
    }

    @Override
    public String toString() {
        return this.isNumber() ? String.valueOf(this.number) : String.valueOf(this.bool);
    }
}

E por fim, a classe FormulaEvaluator, que é onde de fato será feita a avaliação da expressão:

package parser;

import java.math.BigDecimal;
import java.util.HashMap;
import java.util.Map;

public class FormulaEvaluator extends FormulaBaseVisitor<FormulaValue> {
    // Map que simula os valores já lidos do banco de dados
    private Map<String, FormulaValue> bd = new HashMap<>();
    public FormulaEvaluator(Map<String, FormulaValue> bd) {
        this.bd = bd;
    }

    @Override
    public FormulaValue visitFormula(FormulaParser.FormulaContext ctx) {
        return this.visit(ctx.expr());
    }

    @Override
    public FormulaValue visitTernaryExpr(FormulaParser.TernaryExprContext ctx) {
        FormulaValue condition = this.visit(ctx.expr(0));
        return condition.booleanValue() ? this.visit(ctx.expr(1)) : this.visit(ctx.expr(2));
    }

    @Override
    public FormulaValue visitIdAtom(FormulaParser.IdAtomContext ctx) {
        String id = ctx.NOME().getText();
        System.out.printf("Procurando variável %s\n", id);
        if (bd.containsKey(id)) { // a busca no Map simula a query sendo executada no banco
            return bd.get(id);
        }
        throw new IllegalArgumentException("Valor " + id + " não encontrado");
    }

    @Override
    public FormulaValue visitNumberAtom(FormulaParser.NumberAtomContext ctx) {
        BigDecimal number = new BigDecimal(ctx.getText());
        boolean isNotZero = number.compareTo(BigDecimal.ZERO) != 0;
        return new FormulaValue(isNotZero, number);
    }

    @Override
    public FormulaValue visitParenthesisAtom(FormulaParser.ParenthesisAtomContext ctx) {
        return this.visit(ctx.expr()); // expressão entre parênteses, retorna o valor de toda a expressão
    }

    @Override
    public FormulaValue visitMultiplicationExpr(FormulaParser.MultiplicationExprContext ctx) {
        FormulaValue left = this.visit(ctx.expr(0));
        FormulaValue right = this.visit(ctx.expr(1));
        switch (ctx.op.getType()) {
            case FormulaParser.MULT: // multiplicação
                return new FormulaValue(left.numberValue().multiply(right.numberValue()));
            case FormulaParser.DIV: // divisão
                return new FormulaValue(left.numberValue().divide(right.numberValue()));
            default:
                throw new RuntimeException("unknown operator: " + FormulaParser.tokenNames[ctx.op.getType()]);
        }
    }

    @Override
    public FormulaValue visitAdditiveExpr(FormulaParser.AdditiveExprContext ctx) {
        FormulaValue left = this.visit(ctx.expr(0));
        FormulaValue right = this.visit(ctx.expr(1));
        switch (ctx.op.getType()) {
            case FormulaParser.PLUS: // adição
                return new FormulaValue(left.numberValue().add(right.numberValue()));
            case FormulaParser.MINUS: // subtração
                return new FormulaValue(left.numberValue().subtract(right.numberValue()));
            default:
                throw new RuntimeException("unknown operator: " + FormulaParser.tokenNames[ctx.op.getType()]);
        }
    }

    @Override
    public FormulaValue visitRelationalExpr(FormulaParser.RelationalExprContext ctx) {
        FormulaValue left = this.visit(ctx.expr(0));
        FormulaValue right = this.visit(ctx.expr(1));
        switch (ctx.op.getType()) {
            case FormulaParser.LT: // menor
                return new FormulaValue(left.numberValue().compareTo(right.numberValue()) < 0);
            case FormulaParser.LTEQ: // menor ou igual
                return new FormulaValue(left.numberValue().compareTo(right.numberValue()) <= 0);
            case FormulaParser.GT: // maior
                return new FormulaValue(left.numberValue().compareTo(right.numberValue()) > 0);
            case FormulaParser.GTEQ: // maior ou igual
                return new FormulaValue(left.numberValue().compareTo(right.numberValue()) >= 0);
            default:
                throw new RuntimeException("unknown operator: " + FormulaParser.tokenNames[ctx.op.getType()]);
        }
    }

    @Override
    public FormulaValue visitEqualityExpr(FormulaParser.EqualityExprContext ctx) {
        FormulaValue left = this.visit(ctx.expr(0));
        FormulaValue right = this.visit(ctx.expr(1));
        switch (ctx.op.getType()) {
            case FormulaParser.EQ: // igual
                return new FormulaValue(left.numberValue().compareTo(right.numberValue()) == 0);
            case FormulaParser.NEQ: // diferente
                return new FormulaValue(left.numberValue().compareTo(right.numberValue()) != 0);
            default:
                throw new RuntimeException("unknown operator: " + FormulaParser.tokenNames[ctx.op.getType()]);
        }
    }

    @Override
    public FormulaValue visitAndExpr(FormulaParser.AndExprContext ctx) {
        FormulaValue left = this.visit(ctx.expr(0));
        if (left.booleanValue()) { // se o primeiro é verdadeiro, avalia o segundo
            return new FormulaValue(this.visit(ctx.expr(1)).booleanValue());
        }
        return new FormulaValue(false); // se o primeiro é falso, o resultado com certeza é falso
    }

    @Override
    public FormulaValue visitOrExpr(FormulaParser.OrExprContext ctx) {
        FormulaValue left = this.visit(ctx.expr(0));
        if (left.booleanValue()) { // se o primeiro é verdadeiro, não precisa avaliar o segundo
            return new FormulaValue(true);
        }
        return new FormulaValue(this.visit(ctx.expr(1)).booleanValue()); // o primeiro é falso, avalia o segundo
    }
}

Basicamente, para cada tipo de expressão definida em Formula.g4, ele cria um método correspondente, usando os mesmos nomes que estão lá (por exemplo, para ternaryExpr foi criado o método visitTernaryExpr, cujo parâmetro contém os seus operandos). Então basta avaliarmos cada um de acordo com o seu operador.

Dois detalhes importantes:

  • Usei um Map para simular os valores que estão no banco. Mas no sistema real, em vez de pegar o valor do Map, ele executaria a respectiva query.
  • No método visitIdAtom eu coloquei alguns prints para sabermos quando uma variável é consultada ou não.

Repare também que esta classe herda de FormulaBaseVisitor, que é uma das classes geradas pelo ANTLR.

Agora na classe Main, faço um teste simples:

package parser;

import java.util.HashMap;
import java.util.Map;
import org.antlr.v4.runtime.CharStreams;
import org.antlr.v4.runtime.CommonTokenStream;
import org.antlr.v4.runtime.tree.ParseTree;

public class Main {
    public static void main(String[] args) throws Exception {
        testeParser("@IDADE == 18 ? 0 : @SALARIO > 1000 ? 1 : @BENEFICIOS < 100 ? 2 : 3 + @BONUS",
            new HashMap<>() {{ // dois colchetes mesmo, não é erro: https://stackoverflow.com/a/6802512
                put("IDADE", new FormulaValue(18));
            }});
    }

    public static void testeParser(String expressao, Map<String, FormulaValue> map) throws Exception {
        FormulaLexer lexer = new FormulaLexer(CharStreams.fromString(expressao));
        FormulaParser parser = new FormulaParser(new CommonTokenStream(lexer));
        ParseTree tree = parser.formula();
        FormulaEvaluator visitor = new FormulaEvaluator(map);
        System.out.println("Expressão: " + expressao);
        if (map != null) {
            System.out.println("Variáveis: " + map);
        }
        System.out.println("Resultado=" + visitor.visit(tree).toString());
    }
}

OBS: new HashMap<>() seguido de {{ não é erro: https://stackoverflow.com/a/6802512

Eu criei o Map contendo IDADE igual a 18, então ele nem vai precisar verificar as demais variáveis. A saída é:

Expressão: @IDADE == 18 ? 0 : @SALARIO > 1000 ? 1 : @BENEFICIOS < 100 ? 2 : 3 + @BONUS
Variáveis: {IDADE=18}
Procurando variável IDADE
Resultado=0

Repare como ele nem sequer chega a procurar por SALARIO, e nem as outras - ou seja, no sistema real, as respectivas queries não seriam executadas. Ele executa somente o que precisa.

Mudando o teste para que a idade não seja 18, mas o salário seja maior que 1000:

testeParser("@IDADE == 18 ? 0 : @SALARIO > 1000 ? 1 : @BENEFICIOS < 100 ? 2 : 3 + @BONUS",
    new HashMap<>() {{
        put("IDADE", new FormulaValue(20));
        put("SALARIO", new FormulaValue(2000));
    }});

Agora ele só procura por IDADE e SALARIO:

Expressão: @IDADE == 18 ? 0 : @SALARIO > 1000 ? 1 : @BENEFICIOS < 100 ? 2 : 3 + @BONUS
Variáveis: {IDADE=20, SALARIO=2000}
Procurando variável IDADE
Procurando variável SALARIO
Resultado=1

Considerações finais

Claro que daria para fazer com regex, e até mesmo argumentar que a curva de aprendizado do ANTLR seria mais complicada e demorada do que uma expressão regular (por mais complexa que seja). Quanto ao desempenho, também teria que medir em casos reais (no meu projeto, o ANTLR teve desempenho melhor).

De qualquer forma, eu ainda acho que vale a pena porque estamos usando a ferramenta correta para o problema em questão. Regex é uma ferramenta para busca de padrões em um texto. ANTLR é um gerador de parsers para expressões em um formato específico. Com a regex, vc obtém partes do texto, mas sem o contexto (eu não sei se aquela parte é um operador ou operando, tenho que fazer testes adicionais para tal). Com o ANTLR, vc já tem todas as informações disponíveis, podendo inclusive usar os nomes definidos no arquivo .g4.

Embora seja possível usar regex para este caso, e até seja relativamente mais fácil para casos mais simples, o ANTLR é mais versátil e escala melhor conforme as expressões vão ficando mais complexas.

A gramática do ANTLR é naturalmente recursiva e por isso reflete melhor a natureza das expressões. Afinal, eu posso ter uma expresão dentro de outra, dentro de outra, dentro de outra, etc, indefinidamente. Com regex, fica bem mais complicado separar cada parte corretamente, ainda mais quando há operadores aninhados e expressões entre parênteses (regex para este caso é particularmente complicada e costuma usar recursos que nem todas as linguagens possuem).

Lembrando também que o ANTLR não é só para expressões numéricas, e sim para qualquer tipo de texto (e até arquivos binários) em um formato específico. Por exemplo, vc pode usar como parte de um compilador.

Enfim, embora pareça complicado no início, acho que é uma alternativa que vale a pena ter à disposição na sua caixa de ferramentas. Regex é legal e eu particularmente gosto bastante, mas nem sempre é a melhor solução.

Carregando publicação patrocinada...
2
lpalomo

Gosto muito do Antlr, como fico tentando fazer compiladores sempre esbarro nesse tema.

Tem um gerador que também é bem interessante chamado Pest (ele é para Rust)

Vale ressaltar que o Antlr possui uma comunidade bem ativa, tendo refeito a sintaxe de diversas línguagens

2
1
Silvair

Para o pessoal que trabalha com .Net, existe a biblioteca [Flee].(https://github.com/mparlak/Flee)

Ela é sensacional, permite resolver expressões em tempo de execução além de permitir ser estendida, criando suas próprias funções personalizadas.

  • Resolvendo expressões:
using Flee.PublicTypes;

public class DynamicExpressions
{
    private readonly ExpressionContext expressionContext = new();

    public DynamicExpressions()
    {
        // Exemplo de inclusão de funções customizadas
        expressionContext.Imports.AddType(typeof(CustomFunctions));

        // Inclusão da System.Math, para permitir utilizar todos os seus métodos
        expressionContext.Imports.AddType(typeof(Math), "Math");

        //Configurações de regionalidade
        expressionContext.ParserOptions.DecimalSeparator = '.';
        expressionContext.ParserOptions.FunctionArgumentSeparator = ',';
        expressionContext.ParserOptions.RecreateParser();
    }

    /// <summary>
    /// Recebe uma expressão booleana em formato string e retorna o resultado
    /// </summary>
    /// <param name="expression"></param>
    /// <returns></returns>
    public bool EvaluateBoolExpression(string expression)
    {
        bool result;

        try
        {
            IGenericExpression<bool> e = expressionContext.CompileGeneric<bool>(expression);
            result = e.Evaluate();
        }
        catch (Exception ex)
        {
            throw new Exception("Erro ao validar a expressão booleana: (" + expression + ") - '" + ex.Message + "'");
        }
        return result;
    }


    /// <summary>
    /// Recebe uma expressão matemática em formato string e retorna o resultado
    /// </summary>
    /// <param name="expression"></param>
    /// <returns></returns>
    public double EvaluateDoubleExpression(string expression)
    {
        double result;

        try
        {            
            // Exemplo de utilização de método da System.Math
            // double valorArredondado = expressionContext.CompileGeneric<double>("Math.Round(1.55540040, 2)").Evaluate();

            // Exemplos de utilização de método personalizado
            
            //Arredonda(
            //    3.0 * MaiorValor(10.90 - 5.0, 0.0) + (10.0 + 15.0 + 20.0)
            //, 2)
            
            //double somaArray = expressionContext.CompileGeneric<double>("Soma(1.5, 2, 3, 4, 5, 6)").Evaluate();
            
            //double valorArredondadoAbnt5891 = expressionContext.CompileGeneric<double>("ArredondaAbnt5891(1.55540040, 2)").Evaluate();

            IGenericExpression<double> e = expressionContext.CompileGeneric<double>(expression);
            result = e.Evaluate();
        }
        catch (Exception ex)
        {
            throw new Exception("Erro ao validar a expressão matemática: (" + expression + ") - '" + ex.Message + "'");
        }
        return result;
    }
}
  • Estendendo:
    /// <summary>
    /// Funções personalizadas 
    /// Todos os métodos incluídos nesta classe, estarão disponíveis para uso nas expressoes
    /// </summary>
    public static class CustomFunctions
    {    
        /// <summary>
        /// Método de arredondamento "round-half-even"
        /// Ou "arredondamento do banqueiro"
        /// </summary>
        /// <param name="value"></param>
        /// <param name="digits"></param>
        /// <returns></returns>
        public static double ArredondaAbnt5891(double value, int digits)
        {
            return Math.Round(value, digits, MidpointRounding.ToEven);
        }
    
        /// <summary>
        /// Método de arredondamento "AwayFromZero"
        /// </summary>
        /// <param name="value"></param>
        /// <param name="digits"></param>
        /// <returns></returns>
        public static double Arredonda(double value, int digits)
        {
            return Math.Round(value, digits, MidpointRounding.AwayFromZero);
        }

        /// <summary>
        /// Executa a soma de todos os itens do array de doubles
        /// </summary>
        /// <param name="valores"></param>
        /// <returns></returns>
        public static double Soma(params double[] valores)
        {
            double resultado = 0;

            for (int i = 0; i < valores.Length; i++)
            {
                resultado += valores[i];
            }

            return resultado;
        }
    }
-5
hbm

ANTLR é pela sua exposição bem útil mesmo, mas confesso ter até calafrios ao rever a velha sintaxe do Java em um exemplo. Ainda bem que outras linguagens também operam com ANTLR, vou tentar algo no python e esse post vai ser bem útil mesmo.