Clever Geek Handbook

ANTLRの難しさ：Ruby文法の作成

画像Rostelecom-Solarでは、脆弱性とNDV用の静的コードアナライザーを開発しています。これは、解析ツリーでも機能します。それらを構築するために、コンパイラ、インタプリタ、およびトランスレータを開発するためのツールである ANTLR4の最適化バージョンを使用します。リポジトリには、多くのプログラミング言語の文法が含まれています。ただし、Rubyの文法が欠けているため、誰も実装していないようです。似たような自家製の言語の文法しかありません



、最も単純なケースのみを解析します。言語には重要な構文があるため、Rubyの文法を実装するのは難しいため、これは驚くべきことではありません。しかし、たとえば、自分の言語を書いて、その方法を考えたい人にとっては非常に便利です。または、私たちの記事で説明されている技術的な問題を解決する必要がある人のために。さて、ここで行う新しい文法を作成する必要があります。



ANTLRは、言語分析をレクサーとパーサーに分割することを提案しています。



Lexerは、言語のアルファベットから指定された文字シーケンスに基づいてトークンを生成します。文字のシーケンスが複数のトークンの定義と一致する場合、最も長いものが選択され、その中で最初に優先されます（書き込みの順序で指定されます）。



パーサーは、レクサーから取得したトークン（端末文字とも呼ばれます）を使用して、言語の文（完全なコマンド）を形成します。



一般的に、文法の綴りは他の言語と同じです。著者の本、ドキュメント、またはこのような多数のチュートリアルから学ぶことができます。



この記事では、基本的な実装は省略され、書き込みの技術的な難しさのみが考慮されます。



レクサーの問題



一般に、レクサーで考えられる唯一の問題は、一連の文字とそれに付随する障害物に対して有効なトークンを発行することです。



補間



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。合計すると、mod内にトークンがあります。 



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には、文字列、文字列と記号の配列（通常の意味では、Rubyの記号ではありません）、正規表現、およびシェルコマンドを書き込むためのPerlに着想を得た追加の構文があります。これらのコマンドの構文の後には、オプションのタイプ識別子と区切り文字が続きます。次に例を示します。%w|a b c|-3つの文字列の配列。ただし、セパレータのペアブラケットとしても使用できます{} [] () <>。可能なすべての識別子を指定するだけでは機能しません-次に、たとえば、シーケンス 



q = 3
5%q


正しく認識されません。レクサーは、トークンを作成することにより、最も長い文字列を単純に食べます%q。



スペース文字、数字、文字など、明らかに無効な区切り文字がないかどうかのチェックを作成し、それを述語（トークンの作成を続行するために特定の場所で満たす必要がある条件）としてトークンに追加することにより、 



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


ほとんどの場合 機能する保護が得られます（これについては後で詳しく説明します）。また、代替案に応じて、対応するセパレーターの期待値を追加します。 



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

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


ここで、startStringModeはモード切り替えとネストサポートのユーティリティ関数です。 



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、便宜上、生成されるトークンのタイプを変更します。



分割またはregexの開始



通常の式の構文は次のとおりです/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トークンの最終作成の-functionを 



@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で、はすべての演算子のハッシュマップです。



パーサーの問題



空白文字



非常に不快な驚きは、スペースが解析に与える影響でした。通常、これらは文法にまったく影響を与えず、ヘルプ-> skipまたは別のチャネルへの変換によってストリームから削除されるだけです。ただし、多くの言語では、助けを借りていくつかの構成要素を区別しています。



したがって、たとえば、a+3およびa + 3括弧なしで関数呼び出しも、ことはできませんが +3、多分。したがって、すべてのパーサールールは次のようになります（NL-newline、WS-whitespace）。 



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


この問題を軽減するために、このようなゴミから解析ツリーをクリーンアップするリスナーを作成しましょう。 



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


またはそれでも（興味深いことに、マークダウンは構文を正しく認識しません）。 



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


問題は、行の終わりを理解する必要があることです。また、どのコンテンツがどの行に属しているかを知ることも便利です。これを行うには、最初に解析保留中のheredocsのリストを作成します（パーサーは、コンテキストとモードに応じて、任意の数のトークンを前方にロードできます） 



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




さらに、保留中のheredocsで行の終わりを確認したので、処理関数を呼び出します。 



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


処理関数自体を以下に示します。ここでは、最後のheredocsのみを処理します（レクサーは先に進んでいた可能性がありますが、この場合、パーサーはまだトークンを吸収していないため、情報を保存します） 



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レクサーとの類推による）、および処理の必要性を示すステートメントのスタック。 



    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が終了するとき。



heredocsを必要なステートメントに割り当てるには、スタックが必要です。補間内に新しいものがある可能性があります。



heredocが通常の式であり、文字列が行のトークンと見なされる場合や、行の終わりが現在の式の後ろにある複雑な場合を正しく認識するために、次のパーサーコードを記述します。 



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で、はローカル変数のリストであり（を介してそれらを参照する必要があります$）、空白トークンはカウントされません。リスナーによってツリー構築中に削除されます。



それでは、関数自体を書いてみましょう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();
}


最後のstatementWithoutHeredocTail仕上げは、heredocsを処理するための不要な中間ルールを削除することです。同じリスナーを使用して、ノードの子をその祖先に再度ハングさせます。 



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


あいまいさ



未解決の問題は、関数呼び出しと、たとえば、実行時にシンボルテーブルを使用してのみ解決できる通常の加算（および同時にユニアリー操作とバイナリ操作のシンボル）との違いでした。



結論としてa +a +a +a...、各ステップの入り口では、通常の加算と引数なしの関数呼び出しの両方が可能です（ただし、この場合、Rubyは最初の引数の符号の後にスペースを必要としません）。これにより、グラフに沿ったウォークが指数関数的に増加するようです。予測。



ただし、コンテキスト内の単一演算子の後にANTLRスペースを許可しないだけでは機能しません。左側の再帰式を手動で書き直す必要があります。これは、引数がない場合に自動的に解決されます。「誰も」が理由なしに30を超える用語を書くという事実に依存して、この問題は消えます。



結論



実験的に、この文法は99％のファイルを解析できます。



したがって、3024ルビーファイルを含むaws-sdk-rubyは、7でのみクラッシュし、fastlaneは1028を含み、2-xで、Ruby on Railsは2081で、19でクラッシュします。



ただし、式に含まれるheredocsのような根本的な問題点はまだあります 



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の開発者、Fedor Usov


More articles:


All Articles