Menulis kompiler dalam bahasanya sendiri

Secara intuitif, tampaknya kompiler untuk bahasa Footidak dapat ditulis dalam Foo. Lebih khusus lagi, kompiler pertama untuk bahasa Footidak dapat ditulis dalam Foo, tetapi kompiler selanjutnya dapat ditulis untukFoo .

Tetapi apakah ini benar? Saya memiliki ingatan yang sangat samar tentang sebuah bahasa yang kompiler pertamanya ditulis dalam "dirinya sendiri". Apakah ini mungkin dan jika iya, bagaimana?

Ini disebut "bootstrap". Anda pertama-tama harus membangun kompiler (atau penerjemah) untuk bahasa Anda dalam beberapa bahasa lain (biasanya Java atau C). Setelah selesai, Anda dapat menulis versi baru kompiler dalam bahasa Foo. Anda menggunakan kompiler bootstrap pertama untuk mengkompilasi kompiler, dan kemudian menggunakan kompiler kompilasi ini untuk mengkompilasi segala sesuatu yang lain (termasuk versi itu sendiri di masa depan).

Sebagian besar bahasa memang diciptakan dengan cara ini, sebagian karena perancang bahasa suka menggunakan bahasa yang mereka ciptakan, dan juga karena kompiler non-sepele sering berfungsi sebagai tolok ukur yang berguna untuk seberapa "lengkap" bahasa itu.

Contohnya adalah Scala. Kompiler pertamanya dibuat di Pizza, bahasa eksperimental oleh Martin Odersky. Pada versi 2.0, kompiler sepenuhnya ditulis ulang di Scala. Sejak saat itu, kompiler Pizza lama dapat sepenuhnya dibuang, karena fakta bahwa kompiler Scala baru dapat digunakan untuk mengkompilasi sendiri untuk iterasi di masa mendatang.

Saya ingat mendengarkan podcast Rekayasa Perangkat Lunak Radio di mana Dick Gabriel berbicara tentang bootstrap penerjemah LISP asli dengan menulis versi telanjang-tulang di LISP di atas kertas dan dengan tangan memasangnya ke dalam kode mesin. Sejak saat itu, fitur LISP lainnya ditulis dan ditafsirkan dengan LISP.

Menambahkan rasa ingin tahu ke jawaban sebelumnya.

Berikut adalah kutipan dari manual Linux From Scratch , pada langkah di mana seseorang mulai membangun kompiler GCC dari sumbernya. (Linux From Scratch adalah cara untuk menginstal Linux yang secara radikal berbeda dari menginstal distribusi, di mana Anda harus benar - benar mengkompilasi setiap biner dari sistem target.)

make bootstrap

Target 'bootstrap' tidak hanya mengkompilasi GCC, tetapi juga mengkompilasinya beberapa kali. Ia menggunakan program yang dikompilasi dalam putaran pertama untuk mengkompilasi dirinya sendiri untuk kedua kalinya, dan kemudian lagi untuk ketiga kalinya. Kemudian membandingkan kompilasi kedua dan ketiga ini untuk memastikannya dapat mereproduksi dirinya sendiri dengan sempurna. Ini juga menyiratkan bahwa itu dikompilasi dengan benar.

Penggunaan target 'bootstrap' dimotivasi oleh fakta bahwa kompiler yang digunakan untuk membangun toolchain sistem target mungkin tidak memiliki versi yang sama dari kompiler target. Melanjutkan dengan cara itu seseorang pasti akan mendapatkan, dalam sistem target, kompiler yang dapat mengkompilasi dirinya sendiri.

Saat Anda menulis kompiler pertama untuk C, Anda menulisnya dalam bahasa lain. Sekarang, Anda memiliki kompiler untuk C di, katakanlah, assembler. Akhirnya, Anda akan datang ke tempat di mana Anda harus mengurai string, khususnya urutan melarikan diri. Anda akan menulis kode untuk dikonversi \nke karakter dengan kode desimal 10 (dan \rke 13, dll).

Setelah kompiler siap, Anda akan mulai mengimplementasikannya kembali dalam C. Proses ini disebut " bootstrap ".

Kode penguraian string akan menjadi:

...
if (c == 92) { // backslash
    c = getc();
    if (c == 110) { // n
        return 10;
    } else if (c == 92) { // another backslash
        return 92;
    } else {
        ...
    }
}
...

Saat ini dikompilasi, Anda memiliki biner yang mengerti '\ n'. Ini berarti Anda dapat mengubah kode sumber:

...
if (c == '\\') {
    c = getc();
    if (c == 'n') {
        return '\n';
    } else if (c == '\\') {
        return '\\';
    } else {
        ...
    }
}
...

Jadi di mana informasi bahwa '\ n' adalah kode untuk 13? Ada dalam biner! Itu seperti DNA: Mengkompilasi kode sumber C dengan biner ini akan mewarisi informasi ini. Jika kompiler mengkompilasi sendiri, ia akan meneruskan pengetahuan ini kepada keturunannya. Dari titik ini, tidak ada cara untuk melihat dari sumbernya sendiri apa yang akan dilakukan oleh kompiler.

Jika Anda ingin menyembunyikan virus di sumber beberapa program, Anda dapat melakukannya seperti ini: Dapatkan sumber dari kompiler, temukan fungsi yang mengkompilasi fungsi dan ganti dengan yang ini:

void compileFunction(char * name, char * filename, char * code) {
    if (strcmp("compileFunction", name) == 0 && strcmp("compile.c", filename) == 0) {
        code = A;
    } else if (strcmp("xxx", name) == 0 && strcmp("yyy.c", filename) == 0) {
        code = B;
    }

    ... code to compile the function body from the string in "code" ...
}

Bagian yang menarik adalah A dan B. A adalah kode sumber untuk compileFunction memasukkan virus, mungkin dienkripsi dalam beberapa cara sehingga tidak jelas dari pencarian biner yang dihasilkan. Ini memastikan bahwa kompilasi ke kompiler dengan dirinya sendiri akan mempertahankan kode injeksi virus.

B adalah sama untuk fungsi yang ingin kita ganti dengan virus kita. Sebagai contoh, bisa jadi fungsi "login" di file sumber "login.c" yang mungkin dari kernel Linux. Kita bisa menggantinya dengan versi yang akan menerima kata sandi "joshua" untuk akun root selain kata sandi normal.

Jika Anda mengompilasinya dan menyebarkannya sebagai biner, tidak akan ada cara untuk menemukan virus dengan melihat sumbernya.

Sumber asli gagasan: https://web.archive.org/web/20070714062657/http://www.acm.org/classics/sep95/

Anda tidak dapat menulis kompiler karena Anda tidak memiliki apa pun untuk dikompilasi dengan kode sumber awal Anda. Ada dua pendekatan untuk menyelesaikan ini.

Yang paling tidak disukai adalah sebagai berikut. Anda menulis kompiler minimal di assembler (yuck) untuk sekumpulan bahasa minimal dan kemudian menggunakan kompiler itu untuk mengimplementasikan fitur tambahan bahasa. Membangun jalan Anda sampai Anda memiliki kompiler dengan semua fitur bahasa untuk dirinya sendiri. Proses menyakitkan yang biasanya hanya dilakukan ketika Anda tidak punya pilihan lain.

Pendekatan yang disukai adalah menggunakan kompiler silang. Anda mengubah bagian belakang kompiler yang ada pada mesin yang berbeda untuk membuat output yang berjalan pada mesin target. Kemudian Anda memiliki kompiler penuh yang bagus dan bekerja pada mesin target. Paling populer untuk ini adalah bahasa C, karena ada banyak kompiler yang ada yang memiliki ujung belakang yang dapat ditukar.

Fakta yang sedikit diketahui adalah bahwa kompiler GNU C ++ memiliki implementasi yang hanya menggunakan subset C. Alasannya adalah karena biasanya mudah untuk menemukan kompiler C untuk mesin target baru yang memungkinkan Anda untuk kemudian membangun kompilator GNU C ++ lengkap darinya. Anda sekarang telah boot dengan mengikat diri Anda untuk memiliki kompiler C ++ pada mesin target.

Secara umum, Anda perlu memotong dulu kompiler yang berfungsi (jika primitif) - maka Anda dapat mulai berpikir untuk membuatnya hosting sendiri. Ini sebenarnya dianggap sebagai tonggak penting dalam beberapa bahasa.

Dari apa yang saya ingat dari "mono", kemungkinan mereka perlu menambahkan beberapa hal untuk membuatnya berfungsi: tim mono terus menunjukkan bahwa beberapa hal tidak mungkin dilakukan Reflection.Emit; tentu saja, tim MS mungkin membuktikan mereka salah.

Ini memiliki beberapa keunggulan nyata : ini adalah tes unit yang cukup bagus, sebagai permulaan! Dan Anda hanya memiliki satu bahasa untuk dikhawatirkan (yaitu mungkin pakar C # mungkin tidak tahu banyak C ++; tetapi sekarang Anda dapat memperbaiki kompiler C #). Tapi saya ingin tahu apakah tidak ada kebanggaan profesional dalam bekerja di sini: mereka hanya ingin hosting sendiri.

Bukan kompiler, tetapi saya baru-baru ini bekerja pada sistem yang self hosting; generator kode digunakan untuk menghasilkan pembuat kode ... jadi jika skema berubah saya cukup menjalankannya sendiri: versi baru. Jika ada bug, saya kembali ke versi sebelumnya dan coba lagi. Sangat nyaman, dan sangat mudah dirawat.

Perbarui 1

Saya baru saja menonton video Anders di PDC ini, dan (sekitar satu jam) dia memang memberikan alasan yang jauh lebih valid - semua tentang kompiler sebagai layanan. Hanya sebagai catatan.

Inilah dump (sebenarnya topik yang sulit untuk dicari):

• Smalltalk

• C

Ini juga ide PyPy dan Rubinius :

(Saya pikir ini mungkin juga berlaku untuk Forth , tapi saya tidak tahu apa-apa tentang Forth.)

GNAT, kompiler GNU Ada, membutuhkan kompiler Ada untuk sepenuhnya dibangun. Ini bisa menyebalkan ketika porting ke platform di mana tidak ada biner GNAT yang tersedia.

Sebenarnya, kebanyakan kompiler ditulis dalam bahasa yang mereka kompilasi, untuk alasan yang disebutkan di atas.

Kompiler bootstrap pertama biasanya ditulis dalam C, C ++ atau Majelis.

Compiler proyek Mono C # telah "self-host" untuk waktu yang lama sekarang, yang artinya adalah bahwa ia telah ditulis dalam bahasa C # itu sendiri.

Yang saya tahu adalah bahwa kompiler dimulai sebagai kode C murni, tetapi begitu fitur "dasar" dari ECMA diimplementasikan, mereka mulai menulis ulang kompiler dalam C #.

Saya tidak mengetahui keuntungan dari menulis kompiler dalam bahasa yang sama, tapi saya yakin itu ada hubungannya setidaknya dengan fitur-fitur yang dapat ditawarkan oleh bahasa itu sendiri (C, misalnya, tidak mendukung pemrograman berorientasi objek) .

Anda dapat menemukan informasi lebih lanjut di sini .

Saya menulis SLIC (Sistem Bahasa untuk Menerapkan Kompiler) dengan sendirinya. Lalu tangan mengompilasinya menjadi perakitan. Ada banyak hal untuk SLIC karena itu adalah kompiler tunggal dari lima sub-bahasa:

• SYNTAX Parser Programming Language PPL
• GENERATOR LISP 2 berdasarkan bahasa pembuatan kode merangkak pohon PSEUDO
• ISO In Sequence, PSEUDO code, Bahasa optimisasi
• PSEUDO Macro menyukai bahasa penghasil kode Majelis.
• MACHOP Bahasa assembly instruksi mesin yang mendefinisikan bahasa.

SLIC terinspirasi oleh CWIC (Compiler for Writing and Implementing Compiler). Tidak seperti kebanyakan paket pengembangan kompiler, SLIC dan CWIC membahas pembuatan kode dengan spesialisasi, khusus domain, bahasa. SLIC memperluas pembuatan kode CWIC dengan menambahkan sub-bahasa ISO, PSEUDO dan MACHOP yang memisahkan spesifik mesin target dari bahasa generator yang merangkak pohon.

LISP 2 pohon dan daftar

Sistem manajemen memori dinamis berbasis bahasa LISP 2 adalah komponen utama. Daftar diekspresikan dalam bahasa yang dicantumkan dalam tanda kurung siku, komponennya dipisahkan dengan koma, yaitu daftar tiga elemen [a, b, c].

Pohon:

     ADD
    /   \
  MPY     3
 /   \
5     x

diwakili oleh daftar yang entri pertamanya adalah objek simpul:

[ADD,[MPY,5,x],3]

Pohon biasanya ditampilkan dengan simpul terpisah sebelum cabang:

ADD[MPY[5,x],3]

Mengakhiri fungsi generator berbasis LISP 2

Fungsi generator adalah himpunan bernama (unparse) => action> pair ...

<NAME>(<unparse>)=><action>;
      (<unparse>)=><action>;
            ...
      (<unparse>)=><action>;

Unparse expressions adalah tes yang cocok dengan pola pohon dan / atau tipe objek yang memecahnya dan menugaskan bagian-bagian tersebut ke variabel lokal untuk diproses oleh tindakan proseduralnya. Jenis seperti fungsi kelebihan beban mengambil berbagai jenis argumen. Kecuali tes () => ... dicoba dalam urutan kode. Berhasil pertama yang tidak sukses menjalankan tindakan terkait. Ekspresi yang tidak umum adalah tes pembongkaran. ADD [x, y] cocok dengan dua pohon ADD tree yang menugaskan cabang-cabangnya ke variabel lokal x dan y. Tindakannya mungkin berupa ekspresi sederhana atau .BEGIN ... .END blok kode terikat. Saya akan menggunakan c style {...} blok hari ini. Pencocokan hierarki, [], aturan tidak umum dapat memanggil generator yang meneruskan hasil yang dikembalikan ke tindakan:

expr_gen(ADD[expr_gen(x),expr_gen(y)])=> x+y;

Khususnya expr_gen di atas tidak cocok dengan pohon ADD dua cabang. Di dalam pola tes generator argumen tunggal ditempatkan di cabang pohon akan dipanggil dengan cabang itu. Daftar argumennya adalah variabel lokal yang ditugaskan objek yang dikembalikan. Di atas unparse menentukan dua cabang adalah ADD tree disassembly, rekursif menekan setiap cabang untuk expr_gen. Cabang kiri kembali ke variabel lokal x. Demikian juga cabang kanan diteruskan ke expr_gen dengan y objek kembali. Di atas bisa menjadi bagian dari pengevaluasi ekspresi numerik. Ada fitur pintasan yang disebut vektor berada di atas alih-alih simpul simpul, vektor simpul dapat digunakan dengan vektor tindakan yang sesuai:

expr_gen(#node[expr_gen(x),expr_gen(y)])=> #action;

  node:   ADD, SUB, MPY, DIV;
  action: x+y, x-y, x*y, x/y;

        (NUMBER(x))=> x;
        (SYMBOL(x))=> val:(x);

Pengevaluasi ekspresi yang lebih lengkap di atas memberikan pengembalian dari cabang kiri expr_gen ke x dan cabang kanan ke y. Vektor aksi yang sesuai dilakukan pada x dan y yang dikembalikan. Pasangan undarse => aksi terakhir cocok dengan objek numerik dan simbol.

Simbol dan atribut simbol

Simbol mungkin memiliki nama atribut. val: (x) mengakses atribut val dari objek simbol yang terkandung dalam x. Tumpukan tabel simbol umum adalah bagian dari SLIC. Tabel SYMBOL dapat didorong dan muncul memberikan simbol lokal untuk fungsi. Simbol yang baru dibuat di katalogkan di tabel simbol atas. Pencarian simbol mencari tumpukan tabel simbol dari tabel paling atas terlebih dahulu ke belakang tumpukan.

Menghasilkan kode independen mesin

Bahasa generator SLIC menghasilkan objek instruksi PSEUDO, menambahkannya ke daftar kode bagian. FLUSH menyebabkan daftar kode PSEUDO dijalankan menghapus setiap instruksi PSEUDO dari daftar dan memanggilnya. Setelah eksekusi, memori objek PSEUDO dilepaskan. Badan prosedural tindakan PSEUDO dan GENERATOR pada dasarnya bahasa yang sama kecuali untuk output mereka. PSEUDO dimaksudkan untuk bertindak sebagai makro perakitan yang menyediakan sequentialization kode bebas mesin. Mereka menyediakan pemisahan mesin target spesifik dari bahasa generator merangkak pohon. PSEUDO memanggil fungsi MACHOP untuk mengeluarkan kode mesin. MACHOP digunakan untuk mendefinisikan pseudo ops perakitan (seperti dc, define constant, dll) dan instruksi mesin atau keluarga instruksi formated seperti menggunakan entri vektor. Mereka hanya mengubah parameter mereka menjadi urutan bidang bit yang membentuk instruksi. Panggilan MACHOP dimaksudkan agar terlihat seperti perakitan dan menyediakan format cetak bidang ketika perakitan ditampilkan dalam daftar kompilasi. Dalam kode contoh saya menggunakan komentar gaya c yang dapat dengan mudah ditambahkan tetapi tidak dalam bahasa aslinya. MACHOP memproduksi kode menjadi memori yang dapat dialamatkan. Linker SLIC menangani output dari kompiler. MACHOP untuk instruksi mode pengguna DEC-10 menggunakan entri vektor: MACHOP memproduksi kode menjadi memori yang dapat dialamatkan. Linker SLIC menangani output dari kompiler. MACHOP untuk instruksi mode pengguna DEC-10 menggunakan entri vektor: MACHOP memproduksi kode menjadi memori yang dapat dialamatkan. Linker SLIC menangani output dari kompiler. MACHOP untuk instruksi mode pengguna DEC-10 menggunakan entri vektor:

.MACHOP #opnm register,@indirect offset (index): // Instruction's parameters.
.MORG 36, O(18): $/36; // Align to 36 bit boundary print format: 18 bit octal $/36
O(9):  #opcd;          // Op code 9 bit octal print out
 (4):  register;       // 4 bit register field appended print
 (1):  indirect;       // 1 bit appended print
 (4):  index;          // 4 bit index register appended print
O(18): if (#opcd&&3==1) offset // immediate mode use value else
       else offset/36;         // memory address divide by 36
                               // to get word address.
// Vectored entry opcode table:
#opnm := MOVE, MOVEI, MOVEM, MOVES, MOVS, MOVSI, MOVSM, MOVSS,
         MOVN, MOVNI, MOVNM, MOVNS, MOVM, MOVMI, MOVMM, MOVMS,
         IMUL, IMULI, IMULM, IMULB, MUL,  MULI,  MULM,  MULB,
                           ...
         TDO,  TSO,   TDOE,  TSOE,  TDOA, TSOA,  TDON,  TSON;
// corresponding opcode value:
#opcd := 0O200, 0O201, 0O202, 0O203, 0O204, 0O205, 0O206, 0O207,
         0O210, 0O211, 0O212, 0O213, 0O214, 0O215, 0O216, 0O217,
         0O220, 0O221, 0O222, 0O223, 0O224, 0O225, 0O226, 0O227,
                           ...
         0O670, 0O671, 0O672, 0O673, 0O674, 0O675, 0O676, 0O677;

The .MORG 36, O (18): $ / 36; menyelaraskan lokasi ke batas 36 bit mencetak lokasi $ / 36 kata alamat 18 bit di oktal. 9 bit opcd, register 4 bit, bit tidak langsung dan register indeks 4 bit digabungkan dan dicetak seolah-olah bidang 18 bit tunggal. Alamat 18 bit / 36 atau nilai langsung adalah output dan dicetak dalam oktal. Contoh MOVEI dicetak dengan r1 = 1 dan r2 = 2:

400020 201082 000005            MOVEI r1,5(r2)

Dengan opsi perakitan kompiler, Anda mendapatkan kode perakitan yang dihasilkan dalam daftar kompilasi.

Tautkan bersama

SLIC linker disediakan sebagai perpustakaan yang menangani resolusi tautan dan simbol. Format pemuatan file keluaran spesifik target harus ditulis untuk mesin target dan ditautkan dengan perpustakaan pustaka linker.

Bahasa generator mampu menulis pohon ke file dan membacanya memungkinkan kompiler multipass untuk diimplementasikan.

Musim panas singkat pembuatan dan asal-usul kode

Saya telah membahas pembuatan kode terlebih dahulu untuk memastikan bahwa dipahami bahwa SLIC adalah kompiler yang benar. SLIC terinspirasi oleh CWIC (Compiler for Writing and Implementing Compiler) yang dikembangkan di Systems Development Corporation pada akhir 1960-an. CWIC hanya memiliki bahasa SYNTAX dan GENERATOR yang menghasilkan kode byte numerik dari bahasa GENERATOR. Kode byte ditempatkan atau ditanam (istilah yang digunakan dalam dokumentasi CWICs) ke buffer memori yang terkait dengan bagian yang disebutkan dan ditulis oleh pernyataan .FLUSH. Makalah ACM tentang CWIC tersedia dari arsip ACM.

Berhasil menerapkan bahasa pemrograman utama

Pada akhir 1970-an SLIC digunakan untuk menulis kompiler silang COBOL. Selesai dalam waktu sekitar 3 bulan kebanyakan oleh seorang programmer tunggal. Saya bekerja sedikit dengan programmer sesuai kebutuhan. Programer lain menulis perpustakaan runtime dan MACHOP untuk target TI-990 mini-COMPUTER. Kompiler COBOL yang dikompilasi secara substansial lebih banyak baris per detik daripada kompiler COBOL asli DEC-10 yang ditulis dalam perakitan.

Lebih ke kompiler maka biasanya dibicarakan

Sebagian besar penulisan kompiler dari awal adalah run time library. Anda membutuhkan tabel simbol. Anda membutuhkan input dan output. Manajemen memori dinamis dll. Dengan mudah bisa lebih bekerja menulis perpustakaan runtime untuk kompiler kemudian menulis kompiler. Tetapi dengan SLIC bahwa runtime library adalah umum untuk semua kompiler yang dikembangkan di SLIC. Perhatikan ada dua pustaka runtime. Satu untuk mesin target bahasa (COBOL misalnya). Yang lain adalah kompiler runtime perpustakaan kompiler.

Saya pikir saya telah menetapkan bahwa ini bukan generator parser. Jadi sekarang dengan sedikit pemahaman tentang ujung belakang saya bisa menjelaskan bahasa pemrograman parser.

Bahasa pemrograman Parser

Parser ditulis menggunakan rumus yang ditulis dalam bentuk persamaan sederhana.

<name> <formula type operator> <expression> ;

Elemen bahasa di tingkat terendah adalah karakter. Token dibentuk dari himpunan bagian dari karakter bahasa. Kelas karakter digunakan untuk memberi nama dan mendefinisikan subset karakter tersebut. Operator pendefinisian kelas karakter adalah karakter titik dua (:). Karakter yang merupakan anggota kelas dikodekan pada sisi kanan definisi. Karakter yang dapat dicetak tertutup dalam string primes single '. Karakter yang tidak tercetak dan khusus dapat diwakili oleh urutan numeriknya. Anggota kelas dipisahkan oleh suatu alternatif | operator. Rumus kelas berakhir dengan titik koma. Kelas karakter dapat mencakup kelas yang sebelumnya didefinisikan:

/*  Character Class Formula                                    class_mask */
bin: '0'|'1';                                                // 0b00000010
oct: bin|'2'|'3'|'4'|'5'|'6'|'7';                            // 0b00000110
dgt: oct|'8'|'9';                                            // 0b00001110
hex: dgt|'A'|'B'|'C'|'D'|'E'|'F'|'a'|'b'|'c'|'d'|'e'|'f';    // 0b00011110
upr:  'A'|'B'|'C'|'D'|'E'|'F'|'G'|'H'|'I'|'J'|'K'|'L'|'M'|
      'N'|'O'|'P'|'Q'|'R'|'S'|'T'|'U'|'V'|'W'|'X'|'Y'|'Z';   // 0b00100000
lwr:  'a'|'b'|'c'|'d'|'e'|'f'|'g'|'h'|'i'|'j'|'k'|'l'|'m'|
      'n'|'o'|'p'|'q'|'r'|'s'|'t'|'u'|'v'|'w'|'x'|'y'|'z';   // 0b01000000
alpha:  upr|lwr;                                             // 0b01100000
alphanum: alpha|dgt;                                         // 0b01101110

Skip_class 0b00000001 sudah ditentukan sebelumnya tetapi mungkin overroad akan mendefinisikan skip_class.

Singkatnya: Kelas karakter adalah daftar alternatif yang hanya bisa berupa konstanta karakter, ordinal karakter, atau kelas karakter yang didefinisikan sebelumnya. Ketika saya menerapkan kelas karakter: Rumus kelas diberikan topeng bit kelas. (Ditampilkan dalam komentar di atas) Rumus kelas apa pun yang memiliki karakter literal atau ordinal menyebabkan bit kelas dialokasikan. Topeng dibuat dengan oring masker kelas yang disertakan bersama dengan bit yang dialokasikan (jika ada). Tabel kelas dibuat dari kelas karakter. Entri yang diindeks oleh ordinal karakter berisi bit yang menunjukkan keanggotaan kelas karakter. Pengujian kelas dilakukan inline. Contoh kode IA-86 dengan ordinal karakter dalam eax menggambarkan pengujian kelas:

test    byte ptr [eax+_classmap],dgt

Diikuti oleh:

jne      <success>

atau

je       <failure>

Contoh kode instruksi IA-86 digunakan karena saya pikir instruksi IA-86 lebih dikenal saat ini. Nama kelas yang mengevaluasi topeng kelasnya adalah AND-non-destruktif dengan tabel-kelas diindeks oleh karakter ordinal (dalam eax). Hasil yang tidak nol menunjukkan keanggotaan kelas. (EAX memusatkan perhatian kecuali untuk al (rendahnya 8 bit EAX) yang berisi karakter).

Token sedikit berbeda dalam kompiler lama ini. Kata-kata kunci tidak dijelaskan sebagai token. Mereka hanya cocok dengan konstanta string yang dikutip dalam bahasa parser. String yang dikutip biasanya tidak disimpan. Pengubah dapat digunakan. A + menjaga string tetap cocok. (yaitu + '-' cocok dengan - karakter yang menjaga karakter saat berhasil) Operasi, (yaitu, 'E') memasukkan string ke dalam token. Ruang putih ditangani oleh rumus token yang melewatkan karakter SKIP_CLASS terkemuka hingga kecocokan pertama dibuat. Perhatikan bahwa kecocokan karakter skip_class secara eksplisit akan menghentikan lompatan yang memungkinkan token untuk memulai dengan karakter skip_class. Rumus token string melewatkan karakter skip_class terkemuka yang cocok dengan karakter quitedd kutipan tunggal atau string yang dikutip ganda. Yang menarik adalah pencocokan "karakter di dalam" string yang dikutip:

string .. (''' .ANY ''' | '"' $(-"""" .ANY | """""","""") '"') MAKSTR[];

Alternatif pertama cocok dengan karakter kutipan mana pun yang dikutip. Alternatif yang tepat cocok dengan string kutipan ganda yang dapat menyertakan karakter kutipan ganda menggunakan dua karakter "bersama-sama untuk mewakili karakter" tunggal. Rumus ini mendefinisikan string yang digunakan dalam definisi sendiri. Alternatif kanan bagian dalam '' '$ (- "" "" .ANY | "" "" "" "" "")' "'cocok dengan string kutipan ganda. Kita dapat menggunakan karakter yang dikutip tunggal untuk mencocokkan karakter kutipan ganda. Namun dalam string yang dikutip ganda jika kita ingin menggunakan karakter "kita harus menggunakan dua" karakter untuk mendapatkan satu. Misalnya dalam alternatif kiri yang cocok dengan karakter apa pun kecuali kutipan:

-"""" .ANY

intip negatif di depan - "" "" digunakan bahwa ketika berhasil (tidak cocok dengan "karakter") maka cocok dengan karakter .ANY (yang tidak bisa menjadi "karakter karena -" "" "menghilangkan kemungkinan itu). Alternatif yang tepat adalah mengambil - "" "" mencocokkan karakter "dan gagal adalah alternatif yang tepat:

"""""",""""

mencoba untuk mencocokkan dua "karakter yang menggantinya dengan satu ganda" menggunakan, "" "" untuk memasukkan thw tunggal "karakter. Kedua alternatif dalam gagal karakter kutipan string penutup cocok dan MAKSTR [] dipanggil untuk membuat objek string. $ urutan, loop saat berhasil, operator digunakan dalam mencocokkan urutan. Rumus token melewati karakter kelas skip utama (sedikit spasi). Setelah kecocokan pertama dibuat, skrip skip_class dinonaktifkan. Kita dapat memanggil fungsi yang diprogram dalam bahasa lain menggunakan []. MAKSTR [], MAKBIN [], MAKOCT [], MAKHEX [], MAKFLOAT [], dan MAKINT [] disediakan fungsi pustaka yang mengonversi string token yang cocok ke objek yang diketik. Rumus angka di bawah ini menggambarkan pengenalan token yang cukup kompleks:

number .. "0B" bin $bin MAKBIN[]        // binary integer
         |"0O" oct $oct MAKOCT[]        // octal integer
         |("0H"|"0X") hex $hex MAKHEX[] // hexadecimal integer
// look for decimal number determining if integer or floating point.
         | ('+'|+'-'|--)                // only - matters
           dgt $dgt                     // integer part
           ( +'.' $dgt                  // fractional part?
              ((+'E'|'e','E')           // exponent  part
               ('+'|+'-'|--)            // Only negative matters
               dgt(dgt(dgt|--)|--)|--)  // 1 2 or 3 digit exponent
             MAKFLOAT[] )               // floating point
           MAKINT[];                    // decimal integer

Rumus token angka di atas mengenali angka integer dan floating point. - Alternatif selalu berhasil. Objek numerik dapat digunakan dalam perhitungan. Objek token didorong ke tumpukan parse pada keberhasilan formula. Prospek eksponen dalam (+ 'E' | 'e', ​​'E') menarik. Kami ingin selalu memiliki E huruf besar untuk MAKEFLOAT []. Tapi kami mengizinkan huruf kecil 'e' menggantikannya menggunakan, 'E'.

Anda mungkin telah memperhatikan konsistensi kelas karakter dan rumus token. Formula parsing berlanjut dengan menambahkan alternatif penelusuran mundur dan operator konstruksi pohon. Backtracking dan non-backtracking operator alternatif mungkin tidak tercampur dalam level ekspresi. Anda mungkin tidak memiliki (a | b \ c) mencampur non-mundur | dengan \ backtracking alternatif. (a \ b \ c), (a | b | c) dan ((a | b) \ c) valid. Alternatif \ backtracking menyimpan keadaan parse sebelum mencoba alternatif kirinya dan pada kegagalan mengembalikan keadaan parse sebelum mencoba alternatif yang tepat. Dalam urutan alternatif, alternatif pertama yang berhasil memuaskan kelompok. Alternatif lebih lanjut tidak dicoba. Anjak piutang dan pengelompokan menyediakan penguraian memajukan terus menerus. Alternatif mundur membuat keadaan parse yang disimpan sebelum mencoba alternatif kirinya. Diperlukan pengulangan saat parse membuat kecocokan sebagian dan kemudian gagal:

(a b | c d)\ e

Di atas jika kegagalan pengembalian cd alternatif dicoba. Jika kemudian c mengembalikan kegagalan, alternatif lacak mundur akan dicoba. Jika a berhasil dan b gagal maka parse akan di-backtrack dan dicoba. Demikian juga c gagal dan b gagal parse di-backtrack dan e alternatif diambil. Mundur tidak terbatas dalam formula. Jika ada rumus parsing yang membuat kecocokan parsial kapan saja dan kemudian gagal, parse di-reset ke backtrack atas dan alternatifnya diambil. Kegagalan kompilasi dapat terjadi jika kode telah keluar rasa backtrack telah dibuat. Pelacakan mundur diatur sebelum memulai kompilasi. Kembali gagal atau mundur ke sana adalah kegagalan kompilator. Backtracks ditumpuk. Kita dapat menggunakan negatif - dan positif? intip / lihat ke depan operator untuk menguji tanpa memajukan parse. sedang tes string adalah mengintip ke depan hanya membutuhkan negara input disimpan dan diatur ulang. Pandangan ke depan akan menjadi ekspresi parsing yang membuat kecocokan sebagian sebelum gagal. Pandangan ke depan diimplementasikan menggunakan backtracking.

Bahasa parser bukan parser LL atau LR. Tapi bahasa pemrograman untuk menulis parser yang layak rekursif di mana Anda memprogram konstruksi pohon:

:<node name> creates a node object and pushes it onto the node stack.
..           Token formula create token objects and push them onto 
             the parse stack.
!<number>    pops the top node object and top <number> of parstack 
             entries into a list representation of the tree. The 
             tree then pushed onto the parse stack.
+[ ... ]+    creates a list of the parse stack entries created 
             between them:
              '(' +[argument $(',' argument]+ ')'
             could parse an argument list. into a list.

Contoh parsing yang umum digunakan adalah ekspresi aritmatika:

Exp = Term $(('+':ADD|'-':SUB) Term!2); 
Term = Factor $(('*':MPY|'/':DIV) Factor!2);
Factor = ( number
         | id  ( '(' +[Exp $(',' Exp)]+ ')' :FUN!2
               | --)
         | '(' Exp ')" )
         (^' Factor:XPO!2 |--);

Exp dan Term menggunakan loop membuat pohon kidal. Faktor yang menggunakan rekursi benar menciptakan pohon tangan kanan:

d^(x+5)^3-a+b*c => ADD[SUB[EXP[EXP[d,ADD[x,5]],3],a],MPY[b,c]]

              ADD
             /   \
          SUB     MPY
         /   \   /   \
      EXP     a b     c
     /   \
    d     EXP     
         /   \
      ADD     3
     /   \
    x     5

Berikut adalah sedikit kompiler cc, versi terbaru SLIC dengan komentar gaya c. Jenis fungsi (tata bahasa, token, kelas karakter, generator, PSEUDO, atau MACHOP ditentukan oleh sintaks awal mereka mengikuti id mereka. Dengan pengurai top-down ini Anda mulai dengan rumus penentu program:

program = $((declaration            // A program is a sequence of
                                    // declarations terminated by
            |.EOF .STOP)            // End Of File finish & stop compile
           \                        // Backtrack: .EOF failed or
                                    // declaration long-failed.
             (ERRORX["?Error?"]     // report unknown error
                                    // flagging furthest parse point.
              $(-';' (.ANY          // find a ';'. skiping .ANY
                     | .STOP))      // character: .ANY fails on end of file
                                    // so .STOP ends the compile.
                                    // (-';') failing breaks loop.
              ';'));                // Match ';' and continue

declaration =  "#" directive                // Compiler directive.
             | comment                      // skips comment text
             | global        DECLAR[*1]     // Global linkage
             |(id                           // functions starting with an id:
                ( formula    PARSER[*1]     // Parsing formula
                | sequencer  GENERATOR[*1]  // Code generator
                | optimizer  ISO[*1]        // Optimizer
                | pseudo_op  PRODUCTION[*1] // Pseudo instruction
                | emitor_op  MACHOP[*1]     // Machine instruction
                )        // All the above start with an identifier
              \ (ERRORX["Syntax error."]
                 garbol);                    // skip over error.

// Perhatikan bagaimana id diperhitungkan dan nanti digabungkan saat membuat pohon.

formula =   ("==" syntax  :BCKTRAK   // backtrack grammar formula
            |'='  syntax  :SYNTAX    // grammar formula.
            |':'  chclass :CLASS     // character class define
            |".." token   :TOKEN     // token formula
              )';' !2                // Combine node name with id 
                                     // parsed in calling declaration 
                                     // formula and tree produced
                                     // by the called syntax, token
                                     // or character class formula.
                $(-(.NL |"/*") (.ANY|.STOP)); Comment ; to line separator?

chclass = +[ letter $('|' letter) ]+;// a simple list of character codes
                                     // except 
letter  = char | number | id;        // when including another class

syntax  = seq ('|' alt1|'\' alt2 |--);

alt1    = seq:ALT!2 ('|' alt1|--);  Non-backtrack alternative sequence.

alt2    = seq:BKTK!2 ('\' alt2|--); backtrack alternative sequence

seq     = +[oper $oper]+;

oper    = test | action | '(' syntax ')' | comment; 

test    = string | id ('[' (arg_list| ,NILL) ']':GENCALL!2|.EMPTY);

action  = ':' id:NODE!1
        | '!' number:MAKTREE!1
        | "+["  seq "]+" :MAKLST!1;

//     C style comments
comment  = "//" $(-.NL .ANY)
         | "/*" $(-"*/" .ANY) "*/";

Yang perlu diperhatikan adalah bagaimana bahasa parser menangani komentar dan pemulihan kesalahan.

Saya pikir saya telah menjawab pertanyaan itu. Setelah menulis sebagian besar penerus SLIC, bahasa cc itu sendiri di sini. Belum ada kompiler untuk itu. Tapi saya bisa mengompilasinya menjadi kode assembly, fungsi asm c atau c ++ telanjang.

Ya, Anda bisa menulis kompiler untuk bahasa dalam bahasa itu. Tidak, Anda tidak perlu kompiler pertama untuk bahasa itu untuk bootstrap.

Yang Anda butuhkan untuk bootstrap adalah implementasi dari bahasa tersebut. Itu bisa berupa kompiler atau juru bahasa.

Secara historis, bahasa biasanya dianggap sebagai bahasa yang ditafsirkan atau bahasa yang dikompilasi. Penerjemah hanya ditulis untuk yang pertama dan kompiler hanya ditulis untuk yang terakhir. Jadi biasanya jika kompiler akan ditulis untuk suatu bahasa, kompiler pertama akan ditulis dalam bahasa lain untuk bootstrap itu, maka, secara opsional, kompiler akan ditulis ulang untuk bahasa subjek. Namun, menulis juru bahasa dalam bahasa lain merupakan pilihan.

Ini bukan hanya teoretis. Saya kebetulan sedang melakukan ini sendiri. Saya sedang mengerjakan kompiler untuk bahasa, Salmon, yang saya kembangkan sendiri. Saya pertama kali membuat kompiler Salmon di C dan sekarang saya sedang menulis kompiler di Salmon, jadi saya bisa membuat kompiler Salmon bekerja tanpa pernah memiliki kompiler untuk Salmon yang ditulis dalam bahasa lain.

Mungkin Anda bisa menulis BNF yang menggambarkan BNF.