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

    image В «Ростелеком-Солар» мы разрабатываем статический анализатор кода на уязвимости и НДВ, который работает в том числе на деревьях разбора. Для их построения мы пользуемся оптимизированной версией 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
    Ростелеком-Солар
    Безопасность по имени Солнце

    Комментарии 5

      +1

      Если есть сложности с ANTLR, возможно вам проще сделать парсер вручную с простым рекурсивным спуском, без разделения на лексер и парсер? У меня про это есть статья, это не так уж сложно, пример про Heredoc как раз есть в статье. Можно сделать либо универсальный парсер, который будет парсить любую грамматику, но медленно, либо генератор парсера для конкретной грамматики, это работает довольно быстро.

        0

        Мой коллега для этого использует javacc, там файл грамматики как бы смешан с джава-кодом, в чем есть как минусы (не такое красивое разделение, как в ANTLR), так и плюсы (гибкость, и, если все сделать правильно, производительность)

          0
          не такое красивое разделение, как в ANTLR

          Оно и в ANTLR не особо красиво — к сожалению, универсальные вставки кода в нем невозможны. Ну и у автора в статье файл грамматики тоже смешан с джава-кодом.

        0
        Для их построения мы пользуемся оптимизированной версией ANTLR4

        По факту оптимизированный рантайм оказался тыквой.


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


        Работа еще не закончена, но вот что уже получается для леворекурсивных и нелеворекурсивных правил (LeftRecursionGrammar.g4) на стандартном и оптимизированном рантаймах (писал уже об этом в компиляторном Telegram чате):


        |               Method | Mode |   Runtime |       Mean |    Error |   StdDev | Ratio |
        |--------------------- |----- |---------- |-----------:|---------:|---------:|------:|
        |    LeftRecursionTest |   LL | Optimized | 1,433.2 us | 22.36 us | 20.91 us |  1.00 |
        | NotLeftRecursionTest |   LL | Optimized |   375.2 us |  3.70 us |  3.28 us |  0.26 |
        |                      |      |           |            |          |          |       |
        |    LeftRecursionTest |   LL |  Standard |   552.9 us |  4.60 us |  4.07 us |  1.00 |
        | NotLeftRecursionTest |   LL |  Standard |   382.2 us |  4.25 us |  3.98 us |  0.69 |
        |                      |      |           |            |          |          |       |
        |    LeftRecursionTest |  SLL | Optimized | 1,427.7 us | 15.61 us | 14.60 us |  1.00 |
        | NotLeftRecursionTest |  SLL | Optimized |   373.3 us |  3.20 us |  3.00 us |  0.26 |
        |                      |      |           |            |          |          |       |
        |    LeftRecursionTest |  SLL |  Standard |   550.6 us |  4.02 us |  3.76 us |  1.00 |
        | NotLeftRecursionTest |  SLL |  Standard |   382.4 us |  4.00 us |  3.74 us |  0.69 |

        Т.е. нелеворекрусивная версия в 4 раза быстрее леворекурсивной на Optimized рантайме. Для Standard разница поменьше, но все равно есть.


        Поэтому советую не использовать левую рекурсию, если производительность важна.


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

        Такое решение выглядит не очень чисто, т.к. дерево разбора становится мутабельным. Не рассматривали возможность преобразование дерева ANTLR в свое собственное представление с использованием Listener? Во-первых, таковое будет занимать меньше памяти, во-вторых, обработка лишних WS и NL упростится. Правда строить такое дерево сложнее — снизу вверх, сворачивая токены и узлы, приходящие снизу.


        Ну и последнее: планируете ли вы выложить грамматику в Open Source? По ней получилось бы легче и детальней оценить грамматику.

          0
          Не рассматривали возможность преобразование дерева ANTLR в свое собственное представление с использованием Listener?

          С помощью листенеров дерево ANTLR перегоняется в XML, но это происходит без всяких оптимизаций, дерево трансформируется один в один — это не то, что нам нужно. Таких возможностей не рассматривали.
          планируете ли вы выложить грамматику в Open Source?

          пока не планируем, но следите за обновлениями)

        Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

        Самое читаемое