Kesulitan ANTLR: Menulis Tata Bahasa Ruby

Di Rostelecom-Solar kami sedang mengembangkan penganalisis kode statis untuk kerentanan dan NDV, yang juga berfungsi pada pohon parse. Untuk membuatnya, kami menggunakan versi ANTLR4 yang dioptimalkan , alat untuk mengembangkan kompiler, juru bahasa, dan penerjemah.



The repositori berisi tata bahasa dari banyak bahasa pemrograman. Namun, ia tidak memiliki tata bahasa Ruby, yang tampaknya belum diimplementasikan oleh siapa pun. Hanya ada tata bahasa dari bahasa buatan yang serupa, hanya mengurai kasus yang paling sederhana. Ini tidak mengherankan, karena tata bahasa Ruby sulit untuk diterapkan, karena bahasanya memiliki sintaks non-trivial. Tetapi akan sangat berguna bagi mereka yang, misalnya, ingin menulis bahasa mereka sendiri dan memikirkan cara melakukannya. Atau bagi mereka yang perlu menyelesaikan kesulitan teknis yang dibahas dalam artikel kami. Nah, kita harus menulis tata bahasa baru, yang akan kita lakukan di sini.



ANTLR mengusulkan untuk membagi analisis bahasa menjadi lexer dan parser.



Lexer terlibat dalam menghasilkan token berdasarkan urutan karakter tertentu dari alfabet bahasa. Jika urutan karakter cocok dengan definisi beberapa token, yang terpanjang dipilih, dan di antaranya - yang pertama dalam prioritas (yang ditentukan oleh urutan penulisan).



Parser membentuk kalimat (perintah lengkap) dari bahasa menggunakan token (juga disebut karakter terminal) yang diperoleh dari lexer.



Secara umum pengejaan grammar tidak berbeda dengan bahasa lain. Anda bisa belajar dari buku penulis , dokumentasi, atau melalui berbagai tutorial seperti ini .



Dalam artikel ini, implementasi dasar akan dihilangkan dan hanya kesulitan teknis penulisan yang akan dipertimbangkan.

Masalah lexer

Secara umum, satu-satunya masalah yang mungkin terjadi dalam lexer adalah penerbitan token yang valid dengan urutan karakter dan hambatan terkait.

Interpolasi

Beberapa string Ruby memungkinkan interpolasi - penyisipan kode arbitrer di dalam menggunakan sintaks #{code}. Misalnya:

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

Kami akan menangani bantuan mode - "lexers kecil" khusus yang dirancang untuk tugas tertentu, seperti parsing string kami:

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

Di setiap tingkat bersarang, jumlah kurung kurawal harus dipertahankan karena situasi formulir (Anda harus keluar dari interpolasi pada penjepit keriting penutup ke-2):

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

Untuk melakukan ini, mari buat tumpukan openedCurlyBracesInsideString. Secara total, kami memiliki token di dalam mod:

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

Sekarang Anda harus keluar dari mode normal (DEFAULT_MODE) tepat waktu, untuk ini kami menambahkan kode ke token:

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

% -notasi

Ruby memiliki sintaks tambahan yang diilhami Perl untuk menulis string, array string dan simbol (yang bukan simbol di Ruby dalam arti biasa), ekspresi reguler, dan perintah shell. Sintaks untuk perintah ini% diikuti dengan pengenal tipe opsional dan karakter pemisah. Misalnya: %w|a b c|- larik tiga string. Namun, ini juga dapat digunakan sebagai tanda kurung berpasangan pemisah {} [] () <>. Ini tidak akan berfungsi hanya untuk menentukan semua pengenal yang mungkin - lalu, misalnya, urutannya

q = 3
5%q

tidak akan dikenali dengan benar. Lexer hanya akan memakan string karakter terpanjang dengan membuat token %q.



Dengan membuat pemeriksaan untuk tidak adanya pemisah yang jelas-jelas tidak valid, seperti karakter spasi, digit, dan huruf, dan menambahkannya ke token sebagai predikat (kondisi yang harus dipenuhi di tempat tertentu untuk melanjutkan pembuatan token),

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

kami mendapatkan perlindungan yang hampir selalu berhasil (lebih lanjut tentang itu nanti). Kami juga menambahkan ekspektasi pemisah yang sesuai tergantung pada alternatifnya.

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

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

di mana startStringModeadalah fungsi utilitas untuk peralihan mode dan dukungan bersarang.

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

Counterexample: 5%q|1 - diurai dengan benar hanya dalam konteks parser, ketika diketahui bahwa setelah 5 tugas tidak boleh ada string.



Anda mungkin berpikir bahwa menemukan pembatas yang cocok dengan melihat ke depan saja sudah cukup, tetapi ada contoh untuk itu juga - 5%q|1|1. Dari mana menjadi jelas bahwa ketika membagi menjadi lexer dan parser, kasus seperti itu tidak dapat diurai.



Namun, ini sangat jarang terjadi, jadi ¯ \ _ (ツ) _ / ¯ akan melakukannya. Di dalam mode, kita tinggal menunggu separator.

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

di mana typemengubah jenis token yang dihasilkan untuk kenyamanan.

Divisi atau awal regex

Sintaks ekspresi reguler adalah sebagai berikut /regexp/(serta notasi persentase yang disebutkan di atas). Masalah yang sama dari konteks parser muncul seperti pada paragraf sebelumnya, untuk menguranginya, kami membuat cek

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

dan tambahkan ke token

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

Untuk menghitung ulang variabel isOp, isPrevNL, isPrevWSdan menimpa emit-fungsi dari penciptaan akhir dari 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);
}

di mana OPERATORShashmap semua operator.

Masalah parser

Karakter spasi

Kejutan yang cukup tidak menyenangkan adalah efek spasi pada penguraian. Biasanya mereka tidak mempengaruhi tata bahasa dengan cara apapun dan hanya dihapus dari aliran dengan bantuan -> skipatau terjemahan ke saluran lain. Namun, sejumlah bahasa masih membedakan beberapa konstruksi dengan bantuannya.



Jadi, misalnya, a+3dan a + 3tidak bisa menjadi panggilan fungsi tanpa tanda kurung, tapi +3mungkin. Oleh karena itu, semua aturan parser terlihat seperti ini (NL - baris baru, WS - spasi):

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

Untuk mengurangi masalah, mari kita tulis pendengar yang akan membersihkan pohon parse kita dari sampah tersebut.

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 dan parser

Sintaks khusus untuk menentukan string multi-baris. Mungkin begitu

<<STR
content line 1
content line 2
STR

atau bahkan itu (yang menarik, penurunan harga tidak mengenali sintaks dengan benar).

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

Masalahnya adalah Anda perlu memahami di mana garis itu berakhir, dan akan lebih mudah untuk mengetahui konten mana yang termasuk dalam garis mana. Untuk melakukan ini, pertama-tama buat daftar heredoc yang tertunda penguraian (parser, bergantung pada konteks dan mode, dapat memuat sejumlah token yang berubah-ubah)

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

dan kami akan menambahkannya saat tersedia

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

Selanjutnya, setelah melihat akhir baris dengan heredocs yang tertunda, kami memanggil fungsi pemrosesan.

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

Fungsi pemrosesan itu sendiri ditunjukkan di bawah ini: di sini kami hanya memproses heredocs terakhir (lexer bisa saja melanjutkan, tetapi parser dalam kasus ini belum menyerap token, jadi kami menyimpan informasinya)

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

Ini perlu ditimpa nextTokenuntuk keluar dari mode dan menghitung jumlah token untuk setiap 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;
}

Sekarang mari kita mulai dengan parser.



Dengan bantuan, @parser::memberstambahkan ke parser: link ke lexer, node string tempat kami akan mentransfer kontennya, jumlah node interpolasi (dengan analogi dengan heredocTokensCountlexer), serta setumpuk pernyataan yang menunjukkan perlunya pemrosesan.

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

Mari memodifikasi unit kode secara langsung:

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- kode yang dijalankan saat parser memasukkan aturan @after- saat keluar.



Tumpukan diperlukan untuk menetapkan heredocs ke pernyataan yang diperlukan, karena mungkin ada yang baru di dalam interpolasi.



Untuk mengenali dengan benar kasus di mana heredoc bisa menjadi ekspresi biasa dan di mana string dapat dianggap sebagai token dalam satu baris, serta kasus kompleks saat akhir string berada di belakang ekspresi saat ini, kami menulis kode parser berikut:

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

Untuk penghitungan node interpolasi yang sama, kami memodifikasi kode aturan dengan konten string (di + 2sini diperlukan untuk menghitung token yang membuka dan menutup interpolasi)

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

di mana localsdaftar variabel lokal (Anda perlu merujuknya melalui $), dan token spasi tidak dihitung, karena dihapus selama pembangunan pohon oleh pendengar kami.



Sekarang mari kita tulis fungsinya sendiri processHeredocs. Mari kita hitung berapa banyak node yang akan diambil

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

Dimulai dengan anak yang mana, kita akan mulai membuang isi baris pada tempatnya

int currentChild = ctx.getChildCount() - heredocNodesCount;

Mengaitkan konten ke node yang sesuai

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

Kami menghapus node itu sendiri, konteks heredoc dan daftar jumlah node interpolasi

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

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

Sebagai sentuhan terakhir, Anda dapat menghapus aturan perantara yang tidak perlu untuk memproses statementWithoutHeredocTailheredocs - dengan menggantung ulang anak simpul ke leluhurnya menggunakan pendengar yang sama

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

Kemenduaan

Masalah yang belum terpecahkan adalah perbedaan antara pemanggilan fungsi dan, misalnya, penambahan biasa (serta simbol operasi uner dan biner secara bersamaan), yang hanya dapat diselesaikan menggunakan tabel simbol pada waktu proses.



Intinya adalah bahwa di pintu masuk a +a +a +a...pada setiap langkah dapat ada penambahan biasa dan pemanggilan fungsi tanpa argumen (meskipun dalam kasus ini Ruby membutuhkan tidak adanya spasi setelah tanda argumen pertama), yang tampaknya mengarah pada pertumbuhan eksponensial berjalan di sepanjang grafik prediksi.



Namun, hanya melarang spasi ANTLR setelah operator unary dalam konteks tidak akan berfungsi - Anda harus menulis ulang ekspresi rekursif kiri secara manual, yang secara otomatis diselesaikan untuk kasus tanpa argumen. Mengandalkan fakta bahwa "tidak ada" yang menulis lebih dari tiga puluh istilah tanpa alasan, masalah ini menghilang.

Kesimpulan

Secara eksperimental, tata bahasa ini dapat mengurai 99% file.



Jadi, aws-sdk-ruby , yang berisi 3024 file ruby, hanya mogok di tujuh, fastlane , berisi 1028, pada 2-x, dan Ruby on Rails pada 2081, pada 19.



Namun, masih ada poin-poin penting seperti heredoc yang dimasukkan dalam ekspresi

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

atau digunakan sebagai ekspresi, semua tipe blok

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)

Saya harap teknik yang dijelaskan dalam artikel ini akan membantu Anda mengatasi kesulitan tata bahasa Anda. Jika Anda berpikir bahwa salah satu masalah dapat diselesaikan dengan lebih baik - selamat datang di komentar.



Penulis: Fedor Usov, pengembang Solar appScreener