Сложности работы с ANTLR: пишем грамматику Ruby04.08.2020 12:03

Проблема заключается в том, что нужно понимать, где заканчивается строка, а также было бы удобно знать, какой контент относится к какой строке. Для этого сначала создадим лист ожидающих парсинга 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 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 CONTEXTS = new ArrayList<>();
    private final List heredocRulesCount = new ArrayList<>();
    private final Stack 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 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

© Habrahabr.ru