Dificuldades do ANTLR: escrevendo uma gramática de Ruby

Na Rostelecom-Solar, estamos desenvolvendo um analisador de código estático para vulnerabilidades e NDV, que também funciona em árvores de análise. Para construí-los, usamos uma versão otimizada do ANTLR4 , uma ferramenta para o desenvolvimento de compiladores, intérpretes e tradutores.



O repositório contém gramáticas de muitas linguagens de programação. No entanto, ele carece da gramática Ruby, que aparentemente ninguém implementou. Existe apenas uma gramática de uma linguagem caseira semelhante, analisando apenas os casos mais simples. Isso não é surpreendente, uma vez que a gramática Ruby é difícil de implementar, já que a linguagem tem uma sintaxe não trivial. Mas seria muito útil para quem, por exemplo, quer escrever sua própria língua e pensar em como fazê-lo. Ou para aqueles que precisam resolver as dificuldades técnicas discutidas em nosso artigo. Bem, teremos que escrever uma nova gramática, o que faremos aqui mesmo.



ANTLR propõe dividir a análise da linguagem em lexer e parser.



A Lexer está empenhada em gerar tokens com base em sequências específicas de caracteres do alfabeto do idioma. Se uma sequência de caracteres corresponde à definição de vários tokens, o mais longo é selecionado, e entre eles - o primeiro em prioridade (que é especificado pela ordem de escrita).



O analisador forma sentenças (comandos completos) da linguagem usando tokens (também chamados de caracteres terminais) obtidos do lexer.



Em geral, a grafia da gramática não é diferente de outras línguas. Você pode aprender com o livro do autor , documentação ou vários tutoriais como este .



Neste artigo, a implementação básica será omitida e apenas as dificuldades técnicas de redação serão consideradas.

Problemas Lexer

Em geral, o único problema possível em um lexer é a emissão de um token válido sobre uma sequência de caracteres e os obstáculos associados.

Interpolação

Algumas strings Ruby permitem interpolação - a inserção de código arbitrário dentro de usando sintaxe #{code}. Por exemplo:

a = 3
"Hello #{if a%2==1 then "Habr!" else "World!" end}"

Vamos lidar com a ajuda de modos - "pequenos lexers" específicos projetados para uma tarefa específica, como nossa análise de uma string:

DoubleQuote: '"' {++nestedStringLevel;}    -> pushMode(InterpolationString);

Em cada nível de aninhamento, o número de chaves abertas deve ser mantido devido às situações da forma (você precisa sair da interpolação na 2ª chave de fechamento):

"Kappa #{
    buf = ''
    [1, 2, 3].each { |x| buf += x.to_s }
    buf
}"

Para fazer isso, vamos criar uma pilha openedCurlyBracesInsideString. No total, temos um token dentro do mod:

StartInterpolation: '#{' {openedCurlyBracesInsideString.push(0);}    -> pushMode(DEFAULT_MODE);

Agora você precisa sair do modo normal (DEFAULT_MODE) a tempo, para isso adicionamos o código aos tokens:

OpenCurlyBracket:             '{' {
    if (nestedStringLevel > 0 && !openedCurlyBracesInsideString.empty()) {
        final int buf = openedCurlyBracesInsideString.pop();
        openedCurlyBracesInsideString.push(buf + 1);
    }
};
CloseCurlyBracket:            '}' {
    if (nestedStringLevel > 0 && openedCurlyBracesInsideString.peek() <= 0) {
       popMode();
       openedCurlyBracesInsideString.pop();
    } else {
        if (!openedCurlyBracesInsideString.empty()) {
            final int buf = openedCurlyBracesInsideString.pop();
            openedCurlyBracesInsideString.push(buf - 1);
        }
    }
};

% -notations

Ruby tem sintaxe adicional inspirada em Perl para escrever strings, arrays de strings e símbolos (que não é um símbolo em Ruby no sentido usual), expressões regulares e comandos shell. A sintaxe para esses comandos é% seguida por um identificador de tipo opcional e um caractere separador. Por exemplo: %w|a b c|- uma matriz de três strings. No entanto, ele também pode ser usado como um par de colchetes separadores {} [] () <>. Não funcionará apenas para especificar todos os identificadores possíveis - então, por exemplo, a sequência

q = 3
5%q

não será reconhecido corretamente. O lexer simplesmente comerá a cadeia de caracteres mais longa criando um token %q.



Criando uma verificação para a ausência de um separador obviamente inválido, como um caractere de espaço, um dígito e uma letra e adicionando-o ao token como um predicado (uma condição que deve ser atendida em um determinado lugar para continuar construindo o token),

StringArrayConstructorwToken: '%w' {canBeDelimiter()}?;

obtemos proteção que quase sempre funciona (mais sobre isso depois). Também adicionamos uma expectativa do separador correspondente, dependendo da alternativa.

StartArrayConstructorNotInterpolated
    : StringArrayConstructorwToken ( Brackets {setPairDelimiter();} | ~[(<{[] {setCharDelimiter();} ) {startStringMode(ArrayConstructorw);}

fragment Brackets: '(' | '[' | '{' | '<';

onde startStringModeestá uma função utilitária para troca de modo e suporte de aninhamento.

public void startStringMode(final int mode) {
    pushMode(mode);
    ++nestedStringLevel;
}

Contra-exemplo: 5%q|1 - analisado corretamente apenas no contexto de um analisador, quando se sabe que após 5 atribuições não pode haver string.



Você pode pensar que é suficiente encontrar um separador correspondente olhando para frente, mas há um exemplo para tal caso - 5%q|1|1. De onde fica claro que ao dividir em um lexer e um analisador, tal caso não pode ser analisado.



No entanto, isso acontece muito raramente, então ¯ \ _ (ツ) _ / ¯ servirá. Dentro do modo, apenas aguardamos o separador.

ArraywWhitespace: WhitespaceAll                           -> skip;
ArraywText:       ({!isDelimiter()}? ArraywTextFragment)+ -> type(StringPart);
ArraywEnd:        . {nestedStringLevel--;}                -> type(HereDocEnd), popMode;

onde typemuda o tipo de tokens gerados por conveniência.

Divisão ou início de regex

A sintaxe da expressão regular é a seguinte /regexp/(bem como a notação de porcentagem mencionada anteriormente). O mesmo problema do contexto do analisador surge como no parágrafo anterior, para mitigá-lo, criamos uma verificação

public boolean canBeRegex() {
    return isPrevWS && " \t\r\u000B\f\b\n".indexOf((char) _input.LA(1)) == -1 || isPrevNL || isOp || prevNonWsType == StartInterpolation;
}

e adicionar ao token

Divide:                       '/' {
    if (canBeRegex()) {
        startHereDoc(RegExp);
    }
};

Para recalcular as variáveis isOp, isPrevNL, isPrevWSe override emit-função da criação final do token

@Override
public void emit(final Token token) {
    final String txt = token.getText();
    final int type = token.getType();
    isPrevNL = type == NL;
    isPrevWS = type == WS;
    if (!isPrevWS && !isPrevNL && type != SingleLineComment && type != MultiLineComment) {
        isOp = OPERATORS.contains(type);
        prevNonWsChar = txt.charAt(txt.length() - 1);
        prevNonWsType = type;
    }
    super.emit(token);
}

onde OPERATORSestá o hashmap de todos os operadores.

Problemas do analisador

Caracteres de espaço em branco

Uma surpresa bastante desagradável foi o efeito dos espaços na análise. Normalmente, eles não afetam a gramática de forma alguma e são simplesmente removidos do fluxo com a ajuda -> skipou tradução para outro canal. No entanto, várias linguagens ainda fazem distinção entre algumas construções com sua ajuda.



Então, por exemplo, a+3e a + 3não pode ser uma chamada de função sem parênteses, mas +3talvez. Portanto, todas as regras do analisador se parecem com isto (NL - nova linha, WS - espaço em branco):

    | expression WS* op=('+' | '-') (NL | WS)* expression

Para atenuar o problema, vamos escrever um ouvinte que limpará nossa árvore de análise desse lixo.

public class RemovingTokensListener implements ParseTreeListener {
        private List<Integer> unwantedTokens;

        ...

        @Override
        public void visitTerminal(final TerminalNode node) {
            if (this.unwantedTokens.contains(node.getSymbol().getType())) {
                ((ParserRuleContext) node.getParent().getRuleContext()).removeLastChild();
            }
        }
}

Heredoc - Lexer e parser

Sintaxe especial para especificar strings de várias linhas. Talvez sim

<<STR
content line 1
content line 2
STR

ou mesmo isso (curiosamente, o markdown não reconhece a sintaxe corretamente).

value = 123
print <<STR_WITH_INTERPOLATION, <<'STR_WITHOUT_INTERPOLATION'.strip
content 1 and #{value}
STR_WITH_INTERPOLATION
     content 2 and #{value}
STR_WITHOUT_INTERPOLATION

O problema é que você precisa entender onde termina a linha e também seria conveniente saber qual conteúdo pertence a qual linha. Para fazer isso, primeiro crie uma lista de heredocs com análise pendente (o analisador, dependendo do contexto e modo, pode carregar um número arbitrário de tokens para a frente)

public final HeredocsHolder HEREDOCS = new HeredocsHolder();

public static final class HereDocEntry {
    public final String name;
    public final HereDocType type;
    public final boolean isInterpolated;
    public int partsNumber;

    public HereDocEntry(final String name, final HereDocType type, final boolean isInterpolated) {
        this.name = name;
        this.type = type;
        this.isInterpolated = isInterpolated;
        this.partsNumber = 0;
    }
}

public static final class HeredocsHolder {
    public final List<HereDocEntry> entries;
    public int toProcess;

    HeredocsHolder() {
        this.entries = new ArrayList<>();
        this.toProcess = 0;
    }
}

e nós os adicionaremos assim que estiverem disponíveis

StartHereDoc
    : HereDocToken HereDocName {
        heredocIdentifier = getHeredocIdentifier('\'');
        setText(getText().trim());
        keepHereDoc(HereDoc, false);
    }
    ;

public void keepHereDoc(final int mode, final boolean isInterpolated) {
    HEREDOCS.entries.add(new HereDocEntry(heredocIdentifier, getHereDocType(), isInterpolated));
    ++HEREDOCS.toProcess;
    isFirstNL = true;
}

Além disso, tendo visto o fim da linha com heredocs pendentes, chamamos a função de processamento.

NL:                           '\n' {
    final int next = _input.LA(1);
    if (HEREDOCS.toProcess > 0 && isFirstNL) {
        startHereDocRoutine();
        isFirstNL = false;
        insideHeredoc = true;
    }
};

A função de processamento em si é mostrada abaixo: aqui processamos apenas os últimos heredocs (o lexer poderia ter ido em frente, mas o analisador neste caso ainda não absorveu os tokens, então salvamos as informações)

public void startHereDocRoutine() {
    final int stopIdx = HEREDOCS.entries.size() - HEREDOCS.toProcess;
    for (int i = HEREDOCS.entries.size() - 1; i >= stopIdx; --i) {
        if (HEREDOCS.entries.get(i).isInterpolated) {
            pushMode(HereDocInterpolated);
        } else {
            pushMode(HereDoc);
        }
    }
    nestedStringLevel += HEREDOCS.toProcess;
    currentHeredocIt = HEREDOCS.entries.listIterator(HEREDOCS.entries.size() - HEREDOCS.toProcess);
    currentHeredoc = currentHeredocIt.next();
}

Ele precisa ser substituído nextTokenpara sair do modo e contar o número de tokens para cada heredoc

@Override
public Token nextToken()
{
    final CommonToken token = (CommonToken)super.nextToken();
    final int ttype = token.getType();
    if (insideHeredoc && ttype == StartInterpolation) {
        ++heredocTokensCount;
    }
    if (_mode == HereDoc || _mode == HereDocInterpolated) {
        if (ttype == VarName) {
            ++heredocTokensCount;
        } else if (ttype == StringPart) {
            ++heredocTokensCount;
            final String txt = token.getText();
            if (CheckHeredocEnd(txt)) {
                token.setText(txt.trim());
                token.setType(HereDocEnd);
                nestedStringLevel--;
                popMode();
                currentHeredoc.partsNumber = heredocTokensCount;
                if (currentHeredocIt.hasNext()) {
                    currentHeredoc = currentHeredocIt.next();
                }
                heredocTokensCount = 0;
                --HEREDOCS.toProcess;
                if (_mode == DEFAULT_MODE) {
                    insideHeredoc = false;
                }
            }
        }
    }
    return token;
}

Agora vamos começar com o analisador.



Com a ajuda, @parser::membersadicione ao analisador: um link para um lexer, nós de string para onde transferiremos seu conteúdo, o número de nós de interpolação (por analogia com um heredocTokensCountlexer), bem como uma pilha de declarações indicando a necessidade de processamento.

    private final RubyLexer lexer = (RubyLexer)_input.getTokenSource();
    private final List<ParserRuleContext> CONTEXTS = new ArrayList<>();
    private final List<Integer> heredocRulesCount = new ArrayList<>();
    private final Stack<StatementEntry> statements = new Stack<>();

    private static final class StatementEntry {
        public boolean needProcess;
        public int currentHeredoc;

        StatementEntry() {
            this.needProcess = false;
            this.currentHeredoc = 0;
        }
    }

Vamos modificar a unidade de código diretamente:

statement
@init {
    statements.push(new StatementEntry());
}
@after {
    if (statements.peek().needProcess) {
        processHeredocs($ctx);
    }
    statements.pop();
}
    : statementWithoutHeredocTail ({statements.peek().needProcess}? interpolatedStringPart* HereDocEnd {++statements.peek().currentHeredoc;})*
    ;

@init- o código que é executado quando o analisador entra na regra @after- quando ele sai.



A pilha é necessária para atribuir heredocs à declaração necessária, uma vez que pode haver novos dentro da interpolação.



Para reconhecer corretamente os casos em que heredoc pode ser uma expressão comum e onde uma string pode ser considerada tokens em uma linha, bem como casos complexos em que o final de uma string ficará atrás da expressão atual, escrevemos o seguinte código de analisador:

string:
...
    | StartInterpolatedHereDoc (memberAccess* WS* NL interpolatedStringPart* HereDocEnd)? {
        if ($ctx.HereDocEnd() == null) {
            CONTEXTS.add($ctx);
            heredocRulesCount.add(0);
            statements.peek().needProcess = true;
        } else {
             lexer.HEREDOCS.entries.remove(0);
        }
    }
...

Para a mesma contagem de nós de interpolação, modificamos o código da regra com o conteúdo da string ( + 2aqui é necessário contar os tokens que abrem e fecham a interpolação)

interpolatedStringPart
locals[int nodesCount = 0]
    : StringPart
    | VarName
    | StartInterpolation (WS* statement {++$nodesCount;})* (WS* rawStatement {++$nodesCount;})? WS* '}' {
        final int cur = statements.peek().currentHeredoc;
        if (cur < heredocRulesCount.size()) {
            heredocRulesCount.set(cur, heredocRulesCount.get(cur) + $nodesCount + 2);
        }
    }
    ;

onde localsé uma lista de variáveis ​​locais (você precisa se referir a eles $), e os tokens de espaço em branco não são contados, uma vez que são removidos durante a construção da árvore por nosso ouvinte.



Agora vamos escrever a própria função processHeredocs. Vamos contar quantos nós pegar

int heredocNodesCount = 0;
for (int i = 0; i < CONTEXTS.size(); ++i) {
    heredocNodesCount += lexer.HEREDOCS.entries.get(i).partsNumber;
    heredocNodesCount += heredocRulesCount.get(i);
}

A partir de qual criança, começaremos a jogar o conteúdo das falas em seus lugares

int currentChild = ctx.getChildCount() - heredocNodesCount;

Conectando conteúdo ao nó correspondente

for (int i = 0; i < CONTEXTS.size(); ++i) {
    final RubyLexer.HereDocEntry entry = lexer.HEREDOCS.entries.remove(0);
    final ParserRuleContext currentContext = CONTEXTS.get(i);
    final int currentNodesCount = entry.partsNumber + heredocRulesCount.get(i);
    for (int j = 0; j < currentNodesCount; ++j, ++currentChild) {
        final ParseTree child = ctx.getChild(currentChild);
        if (child instanceof TerminalNode) {
            ((TerminalNodeImpl) child).setParent(currentContext);
            currentContext.addChild((TerminalNodeImpl) child);
        } else if (child instanceof ParserRuleContext) {
            ((ParserRuleContext) child).setParent(currentContext);
            currentContext.addChild((ParserRuleContext) child);
        } else {
            // parser failed
            clear();
            return;
        }
    }
}

Limpamos o nó em si, os contextos heredoc e a lista do número de nós de interpolação

for (int i = 0; i < heredocNodesCount; ++i) {
    ctx.removeLastChild();
}
clear();

private void clear() {
    CONTEXTS.clear();
    heredocRulesCount.clear();
}

O toque final é remover uma regra intermediária desnecessária para lidar com statementWithoutHeredocTailheredocs - reencaixando os filhos do nó em seu ancestral usando o mesmo ouvinte

public class RemovingRulesListener implements ParseTreeListener {
    private List<Integer> unwantedRules;

    ...

    @Override
    public void exitEveryRule(final ParserRuleContext ctx) {
        if (this.unwantedRules.contains(ctx.getRuleIndex())) {
            final ParserRuleContext parentCtx =
                    (ParserRuleContext) ctx.getParent().getRuleContext();
            parentCtx.children.remove(ctx);
            ctx.children.forEach(
                    child -> {
                        if (child instanceof RuleContext) {
                            ((RuleContext) child).setParent(parentCtx);
                            parentCtx.addChild((RuleContext) child);
                        } else if (child instanceof TerminalNode) {
                            ((TerminalNodeImpl) child).setParent(parentCtx);
                            parentCtx.addChild((TerminalNodeImpl) child);
                        }
                    }
            );
        }
    }
}

Ambiguidade

Um problema não resolvido era a distinção entre chamadas de função e, por exemplo, adição comum (bem como o símbolo de qualquer operação unária e binária simultaneamente), que só pode ser resolvido usando tabelas de símbolos em tempo de execução.



A conclusão é que, na entrada de a +a +a +a...cada etapa, pode haver adição comum e uma chamada de função sem argumentos (embora neste caso Ruby não exija espaço após o sinal do primeiro argumento), o que aparentemente leva a um crescimento exponencial de percursos ao longo do gráfico previsões.



No entanto, simplesmente desabilitar o espaço ANTLR após o operador unário no contexto não funcionará - você terá que reescrever manualmente a expressão recursiva à esquerda, que é resolvida automaticamente para o caso sem argumentos. Baseando-se no fato de que “ninguém” escreve mais de trinta termos sem motivo, esse problema desaparece.

Conclusão

Experimentalmente, essa gramática pode analisar 99% dos arquivos.



Assim, aws-sdk-ruby , contendo 3024 arquivos ruby, trava apenas em sete, fastlane , contendo 1028, em 2-x, e Ruby on Rails em 2081, em 19.



No entanto, ainda existem pontos doloridos, como heredoces, incluídos na expressão

option(:sts_regional_endpoints,
  default: 'legacy',
  doc_type: String,
  docstring: <<-DOCS) do |cfg|
Passing in 'regional' to enable regional endpoint for STS for all supported
regions (except 'aws-global'), defaults to 'legacy' mode, using global endpoint
for legacy regions.
  DOCS
  resolve_sts_regional_endpoints(cfg)
end

ou usado como expressões, qualquer tipo de bloco

def test_group_by_with_order_by_virtual_count_attribute
    expected = { "SpecialPost" => 1, "StiPost" => 2 }
    actual = Post.group(:type).order(:count).limit(2).maximum(:comments_count)
    assert_equal expected, actual
end if current_adapter?(:PostgreSQLAdapter)

Espero que as técnicas descritas neste artigo o ajudem a lidar com as dificuldades de sua gramática. Se você acha que algum dos problemas pode ser resolvido melhor - bem-vindo aos comentários.



Autor: Fedor Usov, desenvolvedor do Solar appScreener