Сложности работы с ANTLR: пишем грамматику Ruby

В «Ростелеком-Солар» мы разрабатываем статический анализатор кода на уязвимости и НДВ, который работает в том числе на деревьях разбора. Для их построения мы пользуемся оптимизированной версией ANTLR4 – инструмента для разработки компиляторов, интерпретаторов и трансляторов.

В репозитории можно найти грамматики множества языков программирования. Однако в нем отсутствует грамматика Ruby, которую, по всей видимости, никто так и не реализовал. Есть только грамматика похожего самодельного языка, парсящая лишь простейшие случаи. Это неудивительно, ведь грамматику Ruby сложно реализовать, так как язык обладает нетривиальным синтаксисом. Но она очень пригодилась бы тем, кто, например, захочет написать свой язык и задумается, как это сделать. Или тем, кому нужно решить технические сложности, рассмотренные в нашей статье. Ну что же – придется писать новую грамматику, чем прямо здесь и займемся.

В ANTLR предлагается разбивать анализ языка на лексер и парсер.

Лексер занимается тем, что формирует токены на основе заданных последовательностей символов из алфавита языка. Если последовательность символов подходит под определение нескольких токенов, выбирается наидлиннейший, а среди таких – первый по приоритету (который задается порядком записи).

Парсер формирует предложения (законченные команды) языка с помощью токенов (также называемых терминальными символами), получаемых из лексера.

В целом написание грамматики не отличается от других языков. Научиться можно с помощью авторской книги, документации или по многочисленным туториалам вроде этого.

В данной статье будет опущена базовая реализация и будут рассмотрены лишь технические сложности написания.

Проблемы лексера

В общем и целом, единственная возможная проблема, возникающая в лексере, – это выдача валидного токена по последовательности символов и сопутствующие этому препятствия.

Интерполяция

Некоторые строки в Ruby допускают интерполяцию – вставку произвольного кода внутрь с помощью синтаксиса #{code}. Например:

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

Справляться будем с помощью режимов – специфичных «маленьких лексеров», предназначенных под определенную задачу, вроде нашего парсинга строки:

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

На каждом уровне вложенности нужно поддерживать число открытых скобок из-за ситуаций вида (выйти из интерполяции нужно на 2-й закрывающей фигурной скобке):

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

Для этого заведем стек openedCurlyBracesInsideString. Итого внутри мода имеем токен:

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

Теперь же нужно вовремя выйти из обычного режима (DEFAULT_MODE), для этого добавим код в токены:

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);
        }
    }
};

%-нотации

В Ruby существует вдохновленный Perl дополнительный синтаксис написания строк, массивов строк и символов (который в Ruby не является символом в обычном понимании), регулярных выражений и шелл-команд. Синтаксис таких команд таков: %, следующий за ним опциональный идентификатор типа и символ-разделитель. Например: %w|a b c| — массив из трех строк. Однако, также можно использовать в качестве разделителя парные скобки: {} [] () <>. Просто задать все возможные идентификаторы не выйдет – тогда, например, последовательность

q = 3
5%q

будет распознаваться некорректно. Лексер просто съест самую длинную цепочку символов, создав токен %q.

Создав проверку на отсутствие явно невалидного разделителя вроде пробельного символа, цифры и буквы и добавив её в токен в качестве предиката (условие, которое обязано выполняться в определенном месте для продолжения конструирования токена),

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

получаем защиту, работающую почти всегда (об этом далее). Так же добавим ожидание соответствующего разделителя в зависимости от альтернативы.

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

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

где startStringMode — utility-функция для переключения режима и поддержки вложенности.

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

Контрпример: 5%q|1 — парсящийся корректно лишь в контексте парсера, когда известно, что после 5-ти задания строки быть не может.

Можно было бы подумать, что достаточно найти парный разделитель с помощью заглядывания вперед, однако и на такой случай есть пример — 5%q|1|1. Откуда становится ясно, что при разделении на лексер и парсер подобный случай распарсить невозможно.

Однако такое случается очень редко, так что сойдет ¯\_(ツ)_/¯. Внутри режима же просто ждем разделитель.

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

где type изменяет тип создаваемых токенов для удобства.

Деление или начало регулярного выражения

Синтаксис регулярного выражения таков /regexp/ (а также вышеупомянутая нотация с процентом). Возникает такая же проблема контекста парсера, как и в предыдущем пункте, для её смягчения создаем проверку

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

и добавляем в токен

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

Для пересчета переменных isOp, isPrevNL, isPrevWS также переопределяем emit-функцию итогового создания токена

@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);
}

где OPERATORS – hashmap всех операторов.

Проблемы парсера

Пробельные символы

Довольно неприятным сюрпризом стало влияние пробелов на парсинг. Обычно они никак не сказываются на грамматике и просто-напросто удаляются из потока с помощью -> skip или перевода в другой канал. Однако ряд языков все же различает некоторые конструкции с их помощью.

Так, например, a+3 и a + 3 не могут быть вызовом функции без скобок, а а +3 может. Поэтому все правила парсера выглядят так (NL — newline, WS — whitespace):

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

Для смягчения проблемы, напишем listener , который будет чистить нам дерево разбора от подобного мусора.

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 — Лексер и парсер

Специальный синтаксис задания многострочных строк. Может быть таким

<<STR
content line 1
content line 2
STR

или даже таким (интересно, что markdown не распознает синтаксис корректно).

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

Проблема заключается в том, что нужно понимать, где заканчивается строка, а также было бы удобно знать, какой контент относится к какой строке. Для этого сначала создадим лист ожидающих парсинга heredoc-ов (парсер в зависимости от контекста и режима может подгружать произвольное число токенов вперед)

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;
    }
}

и будем добавлять их по мере поступления

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;
}

Далее, увидев конец строки при ожидающих обработки heredoc-ах, вызовем функцию обработки.

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

Сама функция обработки приведена ниже: здесь обрабатываем лишь последние heredoc-и (лексер мог уйти вперед, однако парсер в таком случае еще не поглотил токены, так что сохраняем информацию)

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();
}

Нужно перезаписать nextToken для выхода из режима и подсчета числа токенов каждого 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;
}

Теперь займемся парсером.

С помощью @parser::members добавим в парсер: ссылку на лексер, узлы строк, куда будем переносить их контент, число узлов интерполяции (по аналогии с heredocTokensCount лексера), а также стек statement-ов с указанием необходимости обработки.

    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;
        }
    }

Модифицируем непосредственно единицу кода:

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 — код, который исполняется при входе парсера в правило, @after — при выходе.

Стек необходим для отнесения heredoc-ов к нужному statement-у, т.к. внутри интерполяции могут быть новые.

Для того, чтобы правильно распознать случаи, где heredoc может быть обычным expression и где строку можно считать токенами подряд, а также сложные кейсы, когда конец строки будет лежать за текущим выражением, пишем такой вот код парсера:

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);
        }
    }
...

Для самого же подсчета узлов интерполяции модифицируем код правила с контентом строки (+ 2 здесь нужно для подсчета токенов, открывающих и закрывающих интерполяцию)

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);
        }
    }
    ;

где locals — список локальных переменных (ссылаться на них нужно через $), а пробельные токены не считаются, т.к. удаляются во время построения дерева нашим listener-ом.

Теперь напишем саму функцию processHeredocs. Посчитаем, сколько узлов предстоит забрать

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

Начиная с какого ребенка, начнем перекидывать контент строк по своим местам

int currentChild = ctx.getChildCount() - heredocNodesCount;

Подвесим контент к соответствующему узлу

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;
        }
    }
}

Очищаем сам узел, контексты heredoc-ов и список числа узлов интерполяции

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

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

Последним штрихом можно удалить ненужное промежуточное правило для обработки heredoc-ов — statementWithoutHeredocTail, переподвешивая детей узла к его предку, с помощью того же listener-а

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);
                        }
                    }
            );
        }
    }
}

Ambiguity

Нерешенной проблемой стало различение вызовов функций и, например, обычного сложения (а также символа любой одновременно унарной и бинарной операции), что может быть решено лишь с помощью символьных таблиц в рантайме.

Суть заключается в том, что при входе a +a +a +a... на каждом шаге может быть как обычное сложение, так и вызов функции без аргументов (хотя и в таком случае Ruby требует отсутствия пробела после знака у первого аргумента), отчего по всей видимости возникает экспоненциальный рост хождений по графу предсказаний.

Однако просто-напросто запретить ANTLR пробел после унарного оператора в контексте не выйдет — придется вручную переписывать леворекурсивный expression, разрешаемый автоматически для случая без аргументов. Полагаясь на то, что “никто” не пишет более тридцати слагаемых без причины, данная проблема отпадает.

Заключение

Экспериментально данная грамматика может распарсить 99% файлов.

Так, aws-sdk-ruby, содержащий 3024 ruby-файла, падает лишь на семи, fastlane, содержащий 1028, на 2-x, а Ruby on Rails c 2081, на 19-ти.

Однако все же есть принципиально бОльные моменты вроде heredoc-ов, входящих в expression

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

или используемых как выражения, любых типов блоков

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)

Надеюсь, приемы, описанные в статье, помогут вам справиться с трудностями вашей грамматики. Если считаете, что какую-то из проблем можно решить лучше – добро пожаловать в комментарии.

Автор: Федор Усов, разработчик Solar appScreener