Mengapa menerapkan lexer sebagai array 2d dan switch raksasa?

Saya perlahan-lahan bekerja untuk menyelesaikan gelar saya, dan semester ini adalah Compiler 101. Kami menggunakan Buku Naga . Singkat ke kursus dan kita berbicara tentang analisis leksikal dan bagaimana itu dapat diimplementasikan melalui automata terbatas deterministik (selanjutnya, DFA). Siapkan berbagai status lexer Anda, tentukan transisi di antaranya, dll.

Tetapi baik profesor dan buku mengusulkan menerapkannya melalui tabel transisi yang berjumlah array 2d raksasa (berbagai negara non-terminal sebagai satu dimensi, dan simbol input yang mungkin sebagai yang lain) dan pernyataan saklar untuk menangani semua terminal serta pengiriman ke tabel transisi jika dalam kondisi non-terminal.

Teorinya baik dan bagus, tetapi sebagai seseorang yang sebenarnya menulis kode selama beberapa dekade, implementasinya keji. Itu tidak dapat diuji, tidak dapat dipertahankan, tidak dapat dibaca, dan itu adalah rasa sakit dan setengah untuk debug melalui. Lebih buruk lagi, saya tidak bisa melihat bagaimana praktisnya jika bahasa itu mampu UTF. Memiliki sejuta atau lebih entri tabel transisi per kondisi non-terminal menjadi tidak terburu-buru.

Jadi, apa masalahnya? Mengapa buku definitif tentang subjek mengatakan untuk melakukannya dengan cara ini?

Apakah overhead panggilan fungsi benar-benar sebanyak itu? Apakah ini sesuatu yang berfungsi dengan baik atau diperlukan ketika tata bahasa tidak diketahui sebelumnya (ekspresi reguler?)? Atau mungkin sesuatu yang menangani semua kasus, bahkan jika solusi yang lebih spesifik akan bekerja lebih baik untuk tata bahasa yang lebih spesifik?

( catatan: kemungkinan duplikat " Mengapa menggunakan pendekatan OO alih-alih pernyataan switch raksasa? " sudah dekat, tapi saya tidak peduli dengan OO. Pendekatan fungsional atau bahkan pendekatan imperatif yang lebih waras dengan fungsi mandiri akan baik-baik saja.)

Dan sebagai contoh, pertimbangkan bahasa yang hanya memiliki pengidentifikasi, dan pengidentifikasi itu [a-zA-Z]+. Dalam implementasi DFA, Anda akan mendapatkan sesuatu seperti:

private enum State
{
    Error = -1,
    Start = 0,
    IdentifierInProgress = 1,
    IdentifierDone = 2
}

private static State[][] transition = new State[][]{
    ///* Start */                  new State[]{ State.Error, State.Error (repeat until 'A'), State.IdentifierInProgress, ...
    ///* IdentifierInProgress */   new State[]{ State.IdentifierDone, State.IdentifierDone (repeat until 'A'), State.IdentifierInProgress, ...
    ///* etc. */
};

public static string NextToken(string input, int startIndex)
{
    State currentState = State.Start;
    int currentIndex = startIndex;
    while (currentIndex < input.Length)
    {
        switch (currentState)
        {
            case State.Error:
                // Whatever, example
                throw new NotImplementedException();
            case State.IdentifierDone:
                return input.Substring(startIndex, currentIndex - startIndex);
            default:
                currentState = transition[(int)currentState][input[currentIndex]];
                currentIndex++;
                break;
        }
    }

    return String.Empty;
}

(meskipun sesuatu yang akan menangani akhir file dengan benar)

Dibandingkan dengan apa yang saya harapkan:

public static string NextToken(string input, int startIndex)
{
    int currentIndex = startIndex;
    while (currentIndex < startIndex && IsLetter(input[currentIndex]))
    {
        currentIndex++;
    }

    return input.Substring(startIndex, currentIndex - startIndex);
}

public static bool IsLetter(char c)
{
    return ((c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z'));
}

Dengan kode yang di- NextTokenrefactored menjadi fungsinya sendiri setelah Anda memiliki beberapa tujuan dari awal DFA.

Dalam praktiknya, tabel ini dihasilkan dari ekspresi reguler yang menentukan token bahasa:

number := [digit][digit|underscore]+
reserved_word := 'if' | 'then' | 'else' | 'for' | 'while' | ...
identifier := [letter][letter|digit|underscore]*
assignment_operator := '=' | '+=' | '-=' | '*=' | '/=' 
addition_operator := '+' | '-' 
multiplication_operator := '*' | '/' | '%'
...

Kami memiliki utilitas untuk menghasilkan penganalisa leksikal sejak 1975 ketika lex ditulis.

Anda pada dasarnya menyarankan untuk mengganti ekspresi reguler dengan kode prosedural. Ini memperluas beberapa karakter dalam ekspresi reguler menjadi beberapa baris kode. Kode prosedural tulisan tangan untuk analisis leksikal dari bahasa apa pun yang cukup menarik cenderung tidak efisien dan sulit dipertahankan.

Motivasi untuk algoritma tertentu sebagian besar adalah latihan pembelajaran, jadi ia berusaha untuk tetap dekat dengan ide DFA, dan menjaga status dan transisi sangat eksplisit dalam kode. Sebagai aturan, tidak ada yang benar-benar akan secara manual menulis kode ini - Anda akan menggunakan alat untuk menghasilkan kode dari tata bahasa. Dan alat itu tidak akan peduli tentang keterbacaan kode karena itu bukan kode sumber, ini merupakan output berdasarkan definisi tata bahasa.

Kode Anda lebih bersih untuk seseorang yang mempertahankan DFA yang ditulis tangan, tetapi sedikit lebih jauh dihapus dari konsep yang diajarkan.

Lingkaran dalam:

                currentState = transition[(int)currentState][input[currentIndex]];
                currentIndex++;
                break;

memiliki banyak keunggulan kinerja. Tidak ada cabang di itu sama sekali, karena Anda melakukan hal yang persis sama untuk setiap karakter input. Kinerja kompiler dapat terjaga keamanannya oleh lexer (yang harus beroperasi pada skala setiap karakter input). Ini bahkan lebih benar ketika Buku Naga ditulis.

Dalam praktiknya, selain siswa CS yang mempelajari lexer, tidak ada yang harus mengimplementasikan (atau men-debug) loop dalam itu karena itu adalah bagian dari pelat boiler yang dilengkapi dengan alat yang membangun transitiontabel.

Dari memori, - sudah lama sejak saya membaca buku, dan saya cukup yakin saya tidak membaca edisi terbaru, saya pasti tidak ingat sesuatu yang tampak seperti Jawa - bagian itu ditulis dengan kode yang dimaksudkan sebagai templat, tabel diisi dengan lex like lexer generator. Masih dari memori, ada bagian pada kompresi tabel (sekali lagi dari memori, itu ditulis sedemikian rupa sehingga juga berlaku untuk parser yang digerakkan oleh tabel, sehingga mungkin lebih jauh dalam buku daripada apa yang Anda lihat). Demikian pula, buku yang saya ingat diasumsikan set karakter 8-bit, saya berharap bagian tentang penanganan set karakter yang lebih besar di edisi kemudian, mungkin sebagai bagian dari kompresi tabel. Saya telah memberikan cara alternatif untuk mengatasinya sebagai jawaban atas pertanyaan SO.

Ada keuntungan kinerja yang pasti dalam memiliki data loop ketat yang didorong dalam arsitektur modern: ini cukup cache friendly (jika Anda telah mengompresi tabel), dan prediksi lompat sesempurna mungkin (satu kehilangan di akhir lexem, mungkin satu ketinggalan untuk saklar pengiriman ke kode yang bergantung pada simbol; itu dengan asumsi bahwa dekompresi tabel Anda dapat dilakukan dengan lompatan yang dapat diprediksi). Memindahkan mesin status itu ke kode murni akan mengurangi kinerja prediksi lompatan dan mungkin meningkatkan tekanan cache.

Setelah bekerja melalui Buku Naga sebelumnya, alasan utama untuk memiliki tuas dan parser yang digerakkan oleh tabel adalah agar Anda dapat menggunakan ekspresi reguler untuk menghasilkan lexer dan BNF untuk menghasilkan parser. Buku ini juga membahas bagaimana alat seperti lex dan yacc bekerja, dan agar Anda tahu cara alat ini bekerja. Selain itu, penting bagi Anda untuk bekerja melalui beberapa contoh praktis.

Meskipun banyak komentar, itu tidak ada hubungannya dengan gaya kode yang ditulis pada 40-an, 50-an, 60-an ..., itu ada hubungannya dengan mendapatkan pemahaman praktis tentang apa yang dilakukan alat untuk Anda dan apa yang Anda miliki lakukan untuk membuatnya bekerja. Ini semua berkaitan dengan pemahaman mendasar bagaimana kompiler bekerja baik dari sudut pandang teoritis maupun praktis.

Mudah-mudahan, instruktur Anda juga akan membiarkan Anda menggunakan lex dan yacc (kecuali itu adalah kelas tingkat pascasarjana dan Anda bisa menulis lex dan yacc).

Terlambat ke pesta :-) Token dicocokkan dengan ekspresi reguler. Karena ada banyak dari mereka, Anda memiliki mesin multi regex, yang pada gilirannya adalah DFA raksasa.

"Lebih buruk lagi, aku tidak bisa melihat bagaimana praktisnya jika bahasa itu mampu UTF."

Itu tidak relevan (atau transparan). Selain UTF memiliki properti bagus, entitasnya tidak tumpang tindih bahkan sebagian. Misalnya byte yang mewakili karakter "A" (dari tabel ASCII-7) tidak digunakan lagi untuk karakter UTF lainnya.

Jadi, Anda memiliki DFA tunggal (yang merupakan multi-regex) untuk seluruh lexer. Bagaimana lebih baik untuk menuliskannya daripada array 2d?