Halo Saya sajikan kepada Anda terjemahan amatir dari panduan untuk menerapkan bahasa pemrograman JavaScript Anda - PL Tutorial .

Dari penerjemah

Kami akan membuat bahasa pemrograman kami sendiri - bahasa λ (dalam bahasa asli - λ bahasa ). Dalam proses pembuatan, kami akan menggunakan banyak teknik menarik, seperti keturunan rekursif, kontrol gaya transfer, dan teknik optimasi dasar. Dua versi penerjemah akan dibuat - penerjemah reguler dan CPS, trans-kompiler dalam JavaScript.

Penulis aslinya adalah Mihai Bazon , penulis perpustakaan UglifyJS yang terkenal (alat untuk meminimalkan dan memformat kode JS).

Entri

Jika Anda pernah menulis kompiler atau juru bahasa Anda, maka tidak akan ada yang baru untuk Anda. Tetapi jika Anda menggunakan ekspresi reguler untuk mem - parsing sesuatu yang terlihat seperti bahasa pemrograman, maka baca bagian tentang parsing . Mari kita menulis kode dengan bug lebih sedikit!

Artikel ini dibagi menjadi beberapa bagian dalam urutan "dari yang sederhana hingga yang kompleks". Saya tidak menyarankan Anda melewati bagian-bagian artikel, kecuali Anda memahami topiknya dengan baik. Anda selalu dapat kembali jika Anda tidak mengerti sesuatu.

Apa yang akan kita pelajari:

• Apa itu pengurai, dan bagaimana cara menulisnya.
• Cara menulis juru bahasa.
• Sekuel transfer, dan mengapa itu penting.
• Menulis kompiler (trans).
• Gaya transfer lanjutan.
• Beberapa teknik optimasi kode dasar.
• Contoh apa yang baru dalam bahasa λ kami dibandingkan dengan JavaScript.

Seiring dengan ini, saya akan menunjukkan mengapa Lisp adalah bahasa pemrograman yang hebat. Namun, bahasa yang kami kerjakan bukanlah bahasa Lisp. Ini memiliki sintaksis yang lebih kaya (notasi infiks klasik yang diketahui semua orang), sesuatu seperti Skema (kecuali makro). Baik atau tidak, tetapi makro adalah fitur utama dari Lisp - sesuatu yang bahasa lain (kecuali untuk dialek Lisp) tidak dapat melakukan sebaik itu. (Ya, aku tahu tentang SweetJS ... tutup, tapi bukan itu.)

Tapi pertama-tama, mari kenalkan bahasa pemrograman kami.

λ bahasa

Sebelum melakukan sesuatu, kita harus memiliki gambaran yang jelas tentang apa yang ingin kita lakukan. Akan lebih baik untuk menulis deskripsi tata bahasa, tapi saya akan membuatnya lebih mudah - tulis contoh program sederhana, jadi berikut adalah beberapa contoh bahasa λ:

#   println("Hello World!"); println(2 + 3 * 4); #       `lambda`  `λ` fib = lambda (n) if n < 2 then n else fib(n - 1) + fib(n - 2); println(fib(15)); print-range = λ(a, b) # `λ`     ,   `lambda` if a <= b then { # `then`  ,      print(a); if a + 1 <= b { print(", "); print-range(a + 1, b); } else println(""); #   }; print-range(1, 5); 

Kesimpulan:

 Hello World! 14 610 1, 2, 3, 4, 5 

Bahasa terlihat mirip dengan JavaScript, tetapi secara keseluruhan tidak. Pertama, tidak ada pernyataan, hanya ekspresi. Ekspresi harus mengembalikan nilai dan dapat digunakan di mana pun dalam ekspresi lain. Titik koma diperlukan untuk memisahkan ekspresi dalam "urutan" ekspresi. Kurung kurawal { dan } membuat urutan yang merupakan ekspresi itu sendiri, dan nilainya adalah nilai terakhir dari urutan. Program berikut ini benar:

 a = { fib(10); #    ,      fib(15) #        }; print(a); #  610 

Fungsi dibuat menggunakan kata kunci lambda atau λ . Setelah itu, dalam tanda kurung adalah daftar (mungkin kosong) nama argumen, dipisahkan dengan koma. Isi fungsi adalah satu ekspresi, tetapi dapat ditutup dalam urutan {...} . Perlu juga dicatat bahwa tidak ada kata kunci return . Fungsi mengembalikan nilai ekspresi terakhir.

Juga, tidak ada var . Untuk menambahkan variabel, Anda dapat menggunakan apa yang oleh pemrogram JavaScript disebut IIFE . Gunakan lambda , deklarasikan variabel sebagai argumen. Untuk variabel, ruang lingkup adalah fungsi, dan fungsi adalah penutupan, seperti dalam JavaScript [kira-kira. terjemahan: hingga ES6.].

Bahkan if adalah ekspresi. JavaScript menggunakan operator ternary untuk melakukan ini:

 a = foo() ? bar() : baz(); // JavaScript a = if foo() then bar() else baz(); # λ 

Kata kunci then adalah opsional jika cabang adalah urutan ( {...} ), seperti yang Anda lihat di atas. Dalam kasus lain, itu perlu. else digunakan jika cabang alternatif hadir. Dan lagi, then dan else mengambil ekspresi sebagai tubuh, tetapi Anda dapat menggabungkan beberapa ekspresi menjadi satu menggunakan {...} . Jika else tidak ada dan kondisinya false , maka hasil dari semuanya adalah false . Perlu dicatat bahwa false adalah kata kunci yang mewakili nilai yang merupakan satu-satunya nilai salah dalam bahasa λ:

 if foo() then print("OK"); 

akan menampilkan OK jika dan hanya jika hasil foo() tidak false . Juga, ada kata kunci true , tetapi sama sekali semua yang tidak false (dalam JavaScript, operator === ) akan dianggap true di cabang (termasuk angka 0 dan string kosong "" ).

Perhatikan bahwa tidak perlu tanda kurung di sekitar ekspresi if . Jika Anda menambahkannya, itu tidak akan menjadi kesalahan, karena ( ekspresi dimulai, tetapi mereka hanya berlebihan.

Seluruh program dapat diuraikan bahkan jika dikelilingi oleh tanda kurung, jadi Anda harus menambahkan ; setelah setiap ekspresi. Ekspresi terakhir adalah pengecualian.

Hebat, ini bahasa λ kecil kami. Dia tidak sempurna. Sintaksnya terlihat indah, tetapi memiliki kekurangan. Ada banyak fitur yang hilang, seperti objek dan array. Kami tidak memperhatikan mereka, karena mereka tidak dasar untuk bahasa pemrograman kami.

Selanjutnya, kita akan menulis parser untuk bahasa kita.

Konversi kode ke AST

Membuat parser adalah tugas yang sulit. Intinya, ia harus mengambil sepotong kode dan mengubahnya menjadi AST (pohon sintaksis abstrak). AST adalah representasi terstruktur dari suatu program dalam memori, abstrak karena tidak mengandung informasi lengkap tentang kode, hanya semantik. Deskripsi AST berada di bagian yang terpisah.

Misalnya, kami memiliki kode berikut:

 sum = lambda(a, b) { a + b; }; print(sum(1, 2)); 

Pengurai kami akan menghasilkan pohon sebagai objek JavaScript:

 { type: "prog", prog: [ //  : { type: "assign", operator: "=", left: { type: "var", value: "sum" }, right: { type: "lambda", vars: [ "a", "b" ], body: { //     "prog",  ,  //     ,  //     . type: "binary", operator: "+", left: { type: "var", value: "a" }, right: { type: "var", value: "b" } } } }, //  : { type: "call", func: { type: "var", value: "print" }, args: [{ type: "call", func: { type: "var", value: "sum" }, args: [ { type: "num", value: 1 }, { type: "num", value: 2 } ] }] } ] } 

Kesulitan utama dalam membuat parser adalah kesulitan dalam mengatur kode dengan benar. Parser harus bekerja pada level yang lebih tinggi daripada membaca karakter dari string. Beberapa pedoman untuk mengurangi kompleksitas kode:

• Tulis banyak fitur kecil. Di setiap fungsi, lakukan satu hal dan lakukan dengan baik.
• Jangan mencoba menggunakan ekspresi reguler untuk parsing. Mereka tidak bekerja. Mereka mungkin berguna dalam penganalisa leksikal , tetapi, untuk kesederhanaan, kami tidak akan menggunakannya.
• Jangan mencoba menebak. Saat Anda tidak yakin cara mem-parsing sesuatu, lempar pengecualian yang berisi lokasi kesalahan (baris dan kolom).

Agar kode lebih sederhana, kami akan membaginya menjadi tiga bagian, yang pada gilirannya dibagi menjadi beberapa fungsi kecil:

• Aliran karakter
• Aliran token (token)
• Parser

Aliran karakter

Ini adalah bagian yang paling mudah. Kami akan membuat objek streaming yang akan mewakili operasi karakter membaca berurutan dari string. Ini berisi empat fungsi:

• peek() - mengembalikan karakter berikutnya tanpa mengekstraksi dari aliran.
• next() - mengembalikan karakter berikutnya, mengekstraknya dari aliran.
• eof() - mengembalikan true jika tidak ada lagi karakter dalam aliran.
• croak(msg) - melempar pengecualian yang berisi pesan ( msg ) dan posisi saat ini di aliran.

Fungsi terakhir diperlukan agar Anda bisa melempar pengecualian yang berisi lokasi kesalahan.

Berikut ini seluruh kode untuk objek ini (sebut saja InputStream ). Itu cukup kecil sehingga Anda seharusnya tidak memiliki masalah dengan itu:

 function InputStream(input) { var pos = 0, line = 1, col = 0; return { next : next, peek : peek, eof : eof, croak : croak, }; function next() { var ch = input.charAt(pos++); if (ch == "\n") line++, col = 0; else col++; return ch; } function peek() { return input.charAt(pos); } function eof() { return peek() == ""; } function croak(msg) { throw new Error(msg + " (" + line + ":" + col + ")"); } } 

Harap dicatat bahwa ini bukan objek biasa (yang dibuat melalui yang new ). Untuk mendapatkan objek ini, Anda perlu: var stream = InputStream(string) .

Selanjutnya, kita akan menulis level abstraksi berikut: Token flow (token) .

Aliran token (token)

Tokenizer (lexer) menggunakan aliran karakter dan mengembalikan objek dengan antarmuka yang sama, tetapi nilai pengembalian fungsi peek() / next() akan menjadi token. Token adalah tipe dengan dua properti: type , value . Berikut beberapa contoh token:

 { type: "punc", value: "(" } // . : , ,     . . { type: "num", value: 5 } //  { type: "str", value: "Hello World!" } //  { type: "kw", value: "lambda" } //   { type: "var", value: "a" } //  { type: "op", value: "!=" } //  

Spasi putih (spasi, tab, jeda baris) dan komentar dilewati begitu saja.

Untuk menulis tokenizer, kita perlu melihat lebih dekat bahasa kita. Idenya adalah untuk memperhatikan bahwa tergantung pada karakter saat ini ( input.peek() ) kita dapat memutuskan token mana yang harus dibaca:

• Pertama, lewati spasi putih.
• Jika input.eof() , maka kembalikan null .
• Jika itu adalah karakter # , maka lewati semua karakter hingga akhir baris (dan kembalikan token berikutnya).
• Jika ini adalah tanda kutip, maka bacalah string.
• Jika ini adalah angka, maka baca nomornya.
• Jika itu surat, maka kami membaca kata, dan mengembalikan pengenal atau kata kunci.
• Jika ini adalah salah satu karakter khusus, maka kembalikan token yang sesuai.
• Jika ini adalah salah satu simbol dari operator, maka kami mengembalikan token yang sesuai.
• Jika tidak ada yang di atas berlaku, maka lemparkan pengecualian menggunakan input.croak() .

Kami akan memiliki fungsi read_next , fungsi utama tokenizer:

 function read_next() { read_while(is_whitespace); if (input.eof()) return null; var ch = input.peek(); if (ch == "#") { skip_comment(); return read_next(); } if (ch == '"') return read_string(); if (is_digit(ch)) return read_number(); if (is_id_start(ch)) return read_ident(); if (is_punc(ch)) return { type : "punc", value : input.next() }; if (is_op_char(ch)) return { type : "op", value : read_while(is_op_char) }; input.croak("Can't handle character: " + ch); } 

Di sini Anda dapat melihat banyak fungsi tambahan yang mengembalikan berbagai jenis token, seperti read_string() , read_number() , dll. ... Mereka ditempatkan dalam fungsi yang terpisah, sehingga kode terlihat lebih sederhana dan lebih indah.

Juga, menarik bahwa kami tidak mengambil semua simbol sekaligus: setiap kali parser meminta token berikutnya, kami akan membaca satu token. Jika terjadi kesalahan, kami bahkan tidak akan membaca semua karakter.

read_ident() akan membaca semua karakter dalam satu baris yang dapat menjadi bagian dari pengidentifikasi ( is_id() ). Identifier harus dimulai dengan huruf, λ , atau _ , dan dapat berisi karakter, angka, atau yang sama dari: ?!-<>= . Oleh karena itu foo-bar tidak akan dibaca sebagai tiga token, tetapi sebagai satu (digunakan). Apakah ini perlu untuk dapat mendefinisikan fungsi dengan nama seperti is-pair? atau string>= (maaf, ini Lisper dalam diriku).

Juga, read_ident() akan memeriksa apakah pengenal ada dalam daftar kata kunci yang dikenal, dan jika ada, kw -token akan dikembalikan, bukan var -token.

Saya pikir kode berbicara sendiri, jadi di sini adalah tokenizer yang sudah jadi untuk bahasa kita:

 function TokenStream(input) { var current = null; var keywords = " if then else lambda λ true false "; return { next : next, peek : peek, eof : eof, croak : input.croak }; function is_keyword(x) { return keywords.indexOf(" " + x + " ") >= 0; } function is_digit(ch) { return /[0-9]/i.test(ch); } function is_id_start(ch) { return /[a-zλ_]/i.test(ch); } function is_id(ch) { return is_id_start(ch) || "?!-<>=0123456789".indexOf(ch) >= 0; } function is_op_char(ch) { return "+-*/%=&|<>!".indexOf(ch) >= 0; } function is_punc(ch) { return ",;(){}[]".indexOf(ch) >= 0; } function is_whitespace(ch) { return " \t\n".indexOf(ch) >= 0; } function read_while(predicate) { var str = ""; while (!input.eof() && predicate(input.peek())) str += input.next(); return str; } function read_number() { var has_dot = false; var number = read_while(function(ch){ if (ch == ".") { if (has_dot) return false; has_dot = true; return true; } return is_digit(ch); }); return { type: "num", value: parseFloat(number) }; } function read_ident() { var id = read_while(is_id); return { type : is_keyword(id) ? "kw" : "var", value : id }; } function read_escaped(end) { var escaped = false, str = ""; input.next(); while (!input.eof()) { var ch = input.next(); if (escaped) { str += ch; escaped = false; } else if (ch == "\\") { escaped = true; } else if (ch == end) { break; } else { str += ch; } } return str; } function read_string() { return { type: "str", value: read_escaped('"') }; } function skip_comment() { read_while(function(ch){ return ch != "\n" }); input.next(); } function read_next() { read_while(is_whitespace); if (input.eof()) return null; var ch = input.peek(); if (ch == "#") { skip_comment(); return read_next(); } if (ch == '"') return read_string(); if (is_digit(ch)) return read_number(); if (is_id_start(ch)) return read_ident(); if (is_punc(ch)) return { type : "punc", value : input.next() }; if (is_op_char(ch)) return { type : "op", value : read_while(is_op_char) }; input.croak("Can't handle character: " + ch); } function peek() { return current || (current = read_next()); } function next() { var tok = current; current = null; return tok || read_next(); } function eof() { return peek() == null; } } 

• Fungsi next() tidak selalu memanggil read_next() , karena mungkin ada token yang telah dibaca sebelumnya (menggunakan fungsi peek() ). Untuk ini, kami memiliki variabel current yang berisi token saat ini.
• Hanya angka desimal yang didukung dalam notasi reguler (1E5, 0x, dll. Tidak didukung). Tetapi jika kami ingin menambahkan dukungan mereka, kami hanya akan mengubah read_number() .
• Tidak seperti JavaScript, satu-satunya karakter yang tidak dapat dihapus dalam sebuah string adalah tanda kutip dan garis miring terbalik. Baris dapat berisi jeda baris, tab, dan apa pun. Kami tidak menafsirkan kombinasi standar seperti \n , \t , dll ... Sangat mudah untuk mengulang ( read_string() ).

Sekarang kita memiliki alat yang ampuh untuk dengan mudah menulis parser , tetapi pertama-tama saya akan merekomendasikan melihat deskripsi AST .

Deskripsi AST

Seperti ditunjukkan di atas, parser akan membangun struktur yang menunjukkan semantik program. AST terdiri dari node. Setiap node adalah objek JavaScript biasa yang memiliki properti type yang menentukan tipe node, serta informasi tambahan yang tergantung pada jenisnya.

 123.5 

 { type: "num", value: 123.5 } 

 "Hello World" 

 { type: "str", value: "Hello World!" } 

 true false 

 { type: "bool", value: true } { type: "bool", value: false } 

 foo 

 { type: "var", value: "foo" } 

 lambda (x) 10 #  λ (x) 10 

 { type: "lambda", vars: [ "x" ], body: { type: "num", value: 10 } } 

 foo(a, 1) 

 { "type": "call", "func": { "type": "var", "value": "foo" }, "args": [ { "type": "var", "value": "a" }, { "type": "num", "value": 1 } ] } 

 if foo then bar else baz 

 { "type": "if", "cond": { "type": "var", "value": "foo" }, "then": { "type": "var", "value": "bar" }, "else": { "type": "var", "value": "baz" } } 

 if foo then bar 

 { "type": "if", "cond": { "type": "var", "value": "foo" }, "then": { "type": "var", "value": "bar" } } 

 a = 10 

 { "type": "assign", "operator": "=", "left": { "type": "var", "value": "a" }, "right": { "type": "num", "value": 10 } } 

 x + y * z 

 { "type": "binary", "operator": "+", "left": { "type": "var", "value": "x" }, "right": { "type": "binary", "operator": "*", "left": { "type": "var", "value": "y" }, "right": { "type": "var", "value": "z" } } } 

 { a = 5; b = a * 2; a + b; } 

 { "type": "prog", "prog": [ { "type": "assign", "operator": "=", "left": { "type": "var", "value": "a" }, "right": { "type": "num", "value": 5 } }, { "type": "assign", "operator": "=", "left": { "type": "var", "value": "b" }, "right": { "type": "binary", "operator": "*", "left": { "type": "var", "value": "a" }, "right": { "type": "num", "value": 2 } } }, { "type": "binary", "operator": "+", "left": { "type": "var", "value": "a" }, "right": { "type": "var", "value": "b" } } ] } 

 let (a = 10, b = a * 10) { a + b; } 

 { "type": "let", "vars": [ { "name": "a", "def": { "type": "num", "value": 10 } }, { "name": "b", "def": { "type": "binary", "operator": "*", "left": { "type": "var", "value": "a" }, "right": { "type": "num", "value": 10 } } } ], "body": { "type": "binary", "operator": "+", "left": { "type": "var", "value": "a" }, "right": { "type": "var", "value": "b" } } } 

Parser

Parser akan membangun pohon yang dijelaskan di atas.

Berkat pekerjaan yang kami lakukan di tokenizer, parser bekerja dengan aliran token, bukan aliran karakter. Masih ada banyak fitur tambahan di sini untuk menyederhanakan struktur. Kami akan berbicara tentang yang utama. Mari kita mulai dengan fungsi parser tingkat tinggi:

 function parse_lambda() { return { type: "lambda", vars: delimited("(", ")", ",", parse_varname), body: parse_expression() }; } 

Fungsi ini akan dipanggil ketika kata kunci lambda telah diambil dari aliran token, jadi kita hanya perlu mengambil nama argumen. Tetapi karena mereka berada dalam tanda kurung dan dipisahkan oleh koma, kita akan melakukan ini menggunakan fungsi yang delimited , yang mengambil argumen berikut: start , stop , separator , fungsi parser , yang mem-parsing setiap elemen secara terpisah. Dalam hal ini, kami menggunakan fungsi parse_varname , yang melempar kesalahan jika memperhatikan sesuatu yang tidak terlihat seperti variabel. Tubuh fungsi adalah ekspresi, jadi kami mendapatkannya dengan parse_expression .

Fungsi yang delimited adalah level yang lebih rendah:

 function delimited(start, stop, separator, parser) { var a = [], first = true; skip_punc(start); while (!input.eof()) { if (is_punc(stop)) break; if (first) first = false; else skip_punc(separator); if (is_punc(stop)) break; //      a.push(parser()); } skip_punc(stop); return a; } 

Seperti yang Anda lihat, itu menggunakan lebih banyak fungsi: is_punc dan skip_punc . Yang pertama mengembalikan true jika token saat ini adalah tanda baca yang diberikan (tanpa mengekstraknya), sementara skip_punc akan memeriksa apakah token saat ini adalah karakter tanda baca yang diberikan dan mengekstraknya (atau melemparkan pengecualian jika tidak).

Fungsi yang mem-parsing seluruh program tampaknya paling sederhana:

 function parse_toplevel() { var prog = []; while (!input.eof()) { prog.push(parse_expression()); if (!input.eof()) skip_punc(";"); } return { type: "prog", prog: prog }; } 

Karena kita hanya memiliki ekspresi, kita cukup memanggil parse_expression() dan membaca ekspresi sampai kita membaca semuanya. Menggunakan skip_punc(";") , kami melakukannya ; wajib setelah setiap ekspresi.

Contoh sederhana lain adalah parse_if() :

 function parse_if() { skip_kw("if"); var cond = parse_expression(); if (!is_punc("{")) skip_kw("then"); var then = parse_expression(); var ret = { type: "if", cond: cond, then: then }; if (is_kw("else")) { input.next(); ret.else = parse_expression(); } return ret; } 

Dia melewatkan kata kunci if (melempar pengecualian jika token saat ini bukan kata kunci if ), membaca kondisinya menggunakan parse_expression() . Jika simbol { tidak melangkah lebih jauh, maka kata kunci yang diperlukan (sintaksis tidak terlihat sangat bagus tanpanya). Cabang hanya ekspresi, jadi kami hanya menggunakan parse_expression() lagi untuk mereka. Cabang else adalah opsional, jadi kami terlebih dahulu memeriksa keberadaan kata kunci sebelum menguraikannya.

Dengan banyak fungsi kecil, kita dapat membuat kodenya sederhana. Kami menulis parser hampir seperti jika kami menggunakan bahasa tingkat tinggi khusus untuk parsing sintaks. Semua fungsi ini adalah "saling recursive", yaitu, kami memiliki parse_atom() , yang, tergantung pada token saat ini, memanggil fungsi lainnya. Salah satunya adalah parse_if() (dipanggil ketika token saat ini adalah if ) dan pada gilirannya panggilan parse_expression() . Tapi parse_expression() memanggil parse_atom() . Tidak ada rekursi yang tak terbatas karena salah satu fungsi selalu mengekstrak setidaknya satu token.

Metode parsing semacam ini disebut Recursive Descent Method , dan pada kenyataannya, yang paling mudah untuk ditulis.

Level bawah: parse_atom() dan parse_expression()

Fungsi parse_atom() memanggil fungsi lain, tergantung pada token saat ini:

 function parse_atom() { return maybe_call(function(){ if (is_punc("(")) { input.next(); var exp = parse_expression(); skip_punc(")"); return exp; } if (is_punc("{")) return parse_prog(); if (is_kw("if")) return parse_if(); if (is_kw("true") || is_kw("false")) return parse_bool(); if (is_kw("lambda") || is_kw("λ")) { input.next(); return parse_lambda(); } var tok = input.next(); if (tok.type == "var" || tok.type == "num" || tok.type == "str") return tok; unexpected(); }); } 

Ketika dia melihat braket pembuka, maka ekspresi kurung harus pergi, oleh karena itu, melewatkan braket, fungsi memanggil parse_expression() dan berharap untuk melewati braket penutup setelah itu. Jika dia melihat semacam kata kunci, maka dia memanggil fungsi yang sesuai. Jika dia melihat konstanta atau pengidentifikasi, lalu mengembalikannya apa adanya. Dan jika tidak ada yang muncul, itu disebut unexpected() , yang melempar pengecualian.

Ketika dia melihat { , dia memanggil parse_prog untuk mem-parsing urutan ekspresi. Juga, parse_prog membuat optimisasi sederhana: jika tidak ada ekspresi antara { dan } , maka ia mengembalikan false , jika hanya satu ekspresi, maka ia mengembalikannya saja. Jika tidak, prog node dengan array ekspresi dikembalikan.

 //     FALSE   , //     . var FALSE = { type: "bool", value: false }; function parse_prog() { var prog = delimited("{", "}", ";", parse_expression); if (prog.length == 0) return FALSE; if (prog.length == 1) return prog[0]; return { type: "prog", prog: prog }; } 

Dan di sini adalah fungsi parse_expression() . Tidak seperti parse_atom() , ini akan mem-parsing sebanyak mungkin ekspresi menggunakan maybe_binary() :

 function parse_expression() { return maybe_call(function(){ return maybe_binary(parse_atom(), 0); }); } 

Fungsi maybe_*

Fungsi-fungsi ini memeriksa apa yang muncul setelah ekspresi dan memutuskan apakah akan membungkus ekspresi dalam simpulnya, atau mengembalikannya apa adanya.

Fungsi maybe_call() sangat sederhana: ia mendapat fungsi yang mem-parsing ekspresi saat ini, dan jika bertemu ( setelah ekspresi, ia membungkus dirinya dalam call . Perhatikan bagaimana delimited() cocok untuk mem-parsing daftar argumen:

 function maybe_call(expr) { expr = expr(); return is_punc("(") ? parse_call(expr) : expr; } function parse_call(func) { return { type: "call", func: func, args: delimited("(", ")", ",", parse_expression) }; } 

Prioritas Operator

Fungsi maybe_binary(left, my_prec) digunakan untuk menggabungkan ekspresi seperti 1 + 2 * 3 . , , , :

 var PRECEDENCE = { "=": 1, "||": 2, "&&": 3, "<": 7, ">": 7, "<=": 7, ">=": 7, "==": 7, "!=": 7, "+": 10, "-": 10, "*": 20, "/": 20, "%": 20, }; 

, * "", + , , 1 + 2 * 3 (1 + (2 * 3)) ((1 + 2) * 3) .

, ( read_atom ) maybe_binary() ( ), ( my_prec ). maybe_binary , . , , .

, , , binary , , , (*):

 function maybe_binary(left, my_prec) { var tok = is_op(); if (tok) { var his_prec = PRECEDENCE[tok.value]; if (his_prec > my_prec) { input.next(); var right = maybe_binary(parse_atom(), his_prec) // (*); var binary = { type : tok.value == "=" ? "assign" : "binary", operator : tok.value, left : left, right : right }; return maybe_binary(binary, my_prec); } } return left; } 

, , , maybe_binary , ( my_prec ), , , . - , (, ), .

, , my_prec 0, binary ( assign = ).

, .

 var FALSE = { type: "bool", value: false }; function parse(input) { var PRECEDENCE = { "=": 1, "||": 2, "&&": 3, "<": 7, ">": 7, "<=": 7, ">=": 7, "==": 7, "!=": 7, "+": 10, "-": 10, "*": 20, "/": 20, "%": 20, }; return parse_toplevel(); function is_punc(ch) { var tok = input.peek(); return tok && tok.type == "punc" && (!ch || tok.value == ch) && tok; } function is_kw(kw) { var tok = input.peek(); return tok && tok.type == "kw" && (!kw || tok.value == kw) && tok; } function is_op(op) { var tok = input.peek(); return tok && tok.type == "op" && (!op || tok.value == op) && tok; } function skip_punc(ch) { if (is_punc(ch)) input.next(); else input.croak("Expecting punctuation: \"" + ch + "\""); } function skip_kw(kw) { if (is_kw(kw)) input.next(); else input.croak("Expecting keyword: \"" + kw + "\""); } function skip_op(op) { if (is_op(op)) input.next(); else input.croak("Expecting operator: \"" + op + "\""); } function unexpected() { input.croak("Unexpected token: " + JSON.stringify(input.peek())); } function maybe_binary(left, my_prec) { var tok = is_op(); if (tok) { var his_prec = PRECEDENCE[tok.value]; if (his_prec > my_prec) { input.next(); return maybe_binary({ type : tok.value == "=" ? "assign" : "binary", operator : tok.value, left : left, right : maybe_binary(parse_atom(), his_prec) }, my_prec); } } return left; } function delimited(start, stop, separator, parser) { var a = [], first = true; skip_punc(start); while (!input.eof()) { if (is_punc(stop)) break; if (first) first = false; else skip_punc(separator); if (is_punc(stop)) break; a.push(parser()); } skip_punc(stop); return a; } function parse_call(func) { return { type: "call", func: func, args: delimited("(", ")", ",", parse_expression), }; } function parse_varname() { var name = input.next(); if (name.type != "var") input.croak("Expecting variable name"); return name.value; } function parse_if() { skip_kw("if"); var cond = parse_expression(); if (!is_punc("{")) skip_kw("then"); var then = parse_expression(); var ret = { type: "if", cond: cond, then: then, }; if (is_kw("else")) { input.next(); ret.else = parse_expression(); } return ret; } function parse_lambda() { return { type: "lambda", vars: delimited("(", ")", ",", parse_varname), body: parse_expression() }; } function parse_bool() { return { type : "bool", value : input.next().value == "true" }; } function maybe_call(expr) { expr = expr(); return is_punc("(") ? parse_call(expr) : expr; } function parse_atom() { return maybe_call(function(){ if (is_punc("(")) { input.next(); var exp = parse_expression(); skip_punc(")"); return exp; } if (is_punc("{")) return parse_prog(); if (is_kw("if")) return parse_if(); if (is_kw("true") || is_kw("false")) return parse_bool(); if (is_kw("lambda") || is_kw("λ")) { input.next(); return parse_lambda(); } var tok = input.next(); if (tok.type == "var" || tok.type == "num" || tok.type == "str") return tok; unexpected(); }); } function parse_toplevel() { var prog = []; while (!input.eof()) { prog.push(parse_expression()); if (!input.eof()) skip_punc(";"); } return { type: "prog", prog: prog }; } function parse_prog() { var prog = delimited("{", "}", ";", parse_expression); if (prog.length == 0) return FALSE; if (prog.length == 1) return prog[0]; return { type: "prog", prog: prog }; } function parse_expression() { return maybe_call(function(){ return maybe_binary(parse_atom(), 0); }); } } 

Marijn Haverbeke, parse-js (Common Lisp), , . , , JS, .

: JavaScript. Bagian 2: Penerjemah