Halo, Habr! Saya mempersembahkan untuk Anda terjemahan artikel "Learning Parser Combinators With Rust" .
Artikel ini mengajarkan dasar-dasar parser kombinatorial untuk orang-orang yang sudah akrab dengan Rust. Diasumsikan bahwa tidak ada pengetahuan lain yang diperlukan, dan segala sesuatu yang tidak terkait langsung dengan Rust, serta beberapa aspek penggunaannya yang tak terduga, akan dijelaskan. Artikel ini tidak akan membantu Anda mempelajari Karat jika Anda belum mengetahuinya, dan dalam hal ini, Anda kemungkinan besar tidak akan memahami parser kombinatorial dengan baik. Jika Anda ingin belajar Karat, saya merekomendasikan buku "Bahasa Pemrograman Karat" .
Dari sudut pandang pemula
Dalam kehidupan setiap programmer, ada saatnya ketika dia membutuhkan parser.
Seorang programmer pemula akan bertanya: "Apa itu parser?"
Programmer tingkat menengah akan berkata: "Sederhana, saya akan menulis ekspresi reguler."
Programmer master akan berkata: "Pergi, aku tahu lex dan yacc."
Seorang pemula berpikir yang terbaik dari semuanya.
Bukan berarti ekspresi reguler itu buruk. (Tapi tolong, jangan mencoba untuk menulis parser kompleks sebagai ekspresi reguler.) Bukan berarti tidak ada kesenangan dalam menggunakan alat yang kuat seperti parser dan generator lexer yang telah diasah untuk kesempurnaan selama ribuan tahun. Tetapi mempelajari dasar-dasar parser adalah suatu kesenangan . Ini juga yang akan Anda lewatkan jika Anda panik saat menggunakan ekspresi reguler atau generator parser, yang keduanya hanyalah abstraksi atas masalah sebenarnya. Dalam pikiran seorang pemula, seperti yang dikatakan seorang pria , ada banyak kemungkinan. Menurut ahli, hanya ada satu opsi yang benar.
Pada artikel ini, kita akan belajar bagaimana membuat parser dari awal
menggunakan metode umum dalam bahasa pemrograman fungsional yang dikenal sebagai parser kombinatorial . Mereka memiliki keuntungan menjadi sangat kuat segera setelah Anda memahami ide dasar mereka, sambil tetap sangat dekat dengan prinsip dasar. Karena satu-satunya abstraksi di sini adalah yang Anda buat sendiri. Combinator utama yang akan Anda gunakan di sini akan Anda buat sendiri.
Cara bekerja dengan artikel ini
Sangat disarankan agar Anda memulai dengan proyek Rust baru dan menulis cuplikan kode di src/lib.rs saat Anda membacanya (Anda dapat menempelnya langsung dari halaman, tetapi masukkan lebih baik, karena ini secara otomatis menjamin Anda akan membacanya sepenuhnya). Semua bagian kode yang Anda butuhkan disusun secara berurutan dalam artikel. Ingatlah bahwa kadang-kadang versi modifikasi dari fungsi yang Anda tulis sebelumnya diperkenalkan, dan dalam kasus ini Anda harus mengganti versi yang lama dengan yang baru.
Kode ini ditulis untuk versi rustc 1.34.0 menggunakan edisi bahasa 2018 . Anda dapat menggunakan versi kompiler apa pun, pastikan Anda menggunakan edisi yang mendukung edisi 2018 (pastikan Cargo.toml Anda berisi edition = "2018" ). Proyek ini tidak memerlukan dependensi eksternal.
Untuk melakukan tes yang disajikan dalam artikel, seperti yang diharapkan, cargo test .
Xcruciating Markup Language
Kami akan menulis parser untuk versi XML yang disederhanakan. Ini terlihat seperti ini:
<parent-element> <single-element attribute="value" /> </parent-element>
Elemen XML dibuka dengan < karakter dan pengidentifikasi yang terdiri dari huruf diikuti oleh sejumlah huruf, angka dan - . Ini diikuti oleh spasi dan daftar opsional dari pasangan atribut: pengidentifikasi lain seperti yang didefinisikan sebelumnya, diikuti oleh = dan string dalam tanda kutip ganda. Akhirnya, ada simbol penutup /> untuk menunjukkan satu elemen tanpa anak-anak, atau > untuk menunjukkan keberadaan urutan elemen anak berikutnya, dan tag penutup dimulai dengan </ , diikuti oleh pengidentifikasi yang harus cocok dengan tag pembuka, dan simbol penutup > .
Hanya itu yang akan kami dukung. Tidak akan ada ruang nama, tidak ada simpul teks, dan yang pasti tidak akan ada pemeriksaan skema. Kami bahkan tidak perlu khawatir lolos dari tanda kutip untuk string - mereka mulai dengan kutip ganda pertama, dan diakhiri dengan berikutnya, dan hanya itu.
Kita akan menguraikan elemen-elemen ini ke dalam struktur yang terlihat seperti ini:
#[derive(Clone, Debug, PartialEq, Eq)] struct Element { name: String, attributes: Vec<(String, String)>, children: Vec<Element>, }
Tidak ada tipe mewah, hanya string untuk nama (ini adalah pengidentifikasi di awal setiap tag), atribut dalam bentuk pasangan string (pengidentifikasi dan nilai) dan daftar anak-anak yang terlihat persis seperti orang tua.
(Jika Anda mencetak, pastikan untuk memasukkan bagian derive . Anda akan membutuhkannya nanti.)
Definisi Parser
Kalau begitu, saatnya untuk menulis parser.
Parsing adalah proses mendapatkan data terstruktur dari aliran informasi. Pengurai adalah yang memunculkan struktur ini.
Dalam disiplin yang akan kita teliti, parser, dalam bentuknya yang paling sederhana, adalah fungsi yang mengambil beberapa input dan mengembalikan output yang diurai bersama dengan sisa input, atau kesalahan yang mengatakan "Aku tidak bisa menguraikan ini."
Parser juga terlihat dalam bentuknya yang lebih kompleks. Anda dapat memperumit arti input, output, dan kesalahan, dan jika Anda membutuhkan pesan kesalahan yang baik yang Anda butuhkan, tetapi parser tetap sama: sesuatu yang mengkonsumsi input dan menghasilkan semacam output yang diuraikan bersama dengan apa tersisa dari input atau membuat Anda tahu bahwa itu tidak dapat menguraikan input ke output.
Mari kita menulisnya sebagai jenis fungsi.
Fn(Input) -> Result<(Input, Output), Error>
Lebih khusus: dalam kasus kami, kami ingin mengisi jenis dan mendapatkan fungsi yang mirip dengan yang ini. Yang akan kita lakukan adalah mengonversi string ke struktur Element . Saat ini, kami tidak ingin masuk ke detail pesan kesalahan, jadi kembalikan saja bagian dari baris yang tidak dapat kami uraikan. Akibatnya, fungsi kami akan terlihat seperti ini:
Fn(&str) -> Result<(&str, Element), &str>
Kami menggunakan irisan string karena ini adalah penunjuk yang efektif untuk sebuah fragmen string, dan kemudian kami dapat memisahkannya sesuka kami dengan "mengonsumsi" data input, memotong fragmen yang dianalisis, dan mengembalikan sisanya beserta hasilnya.
Mungkin lebih bersih untuk menggunakan &[u8] (sepotong byte yang cocok dengan karakter ASCII) sebagai tipe input, terutama karena irisan string berperilaku sedikit berbeda dari kebanyakan irisan - terutama karena Anda tidak dapat mengindeksnya dengan satu input[0] angka input[0] , Anda harus menggunakan input[0..1] fragmen input[0..1] . Di sisi lain, mereka memiliki banyak metode yang berguna untuk string parsing yang tidak memiliki irisan byte.
Bahkan, kita akan mengandalkan metode, bukan penggunaan indeks karakter, karena Unicode. Dalam UTF-8, dan semua string Rust adalah string UTF-8 yang valid, indeks ini tidak selalu sesuai dengan karakter individu, dan lebih baik bagi semua pihak yang tertarik untuk meminta perpustakaan standar untuk hanya bekerja dengannya untuk kami.
Pengurai pertama kami
Mari kita coba menulis parser yang hanya melihat karakter pertama dalam sebuah string
dan memutuskan apakah itu huruf a .
fn the_letter_a(input: &str) -> Result<(&str, ()), &str> { match input.chars().next() { Some('a') => Ok((&input['a'.len_utf8()..], ())), _ => Err(input), } }
Pertama, mari kita lihat jenis input dan output: kami mengambil string slice sebagai input dan kami mengembalikan Result dengan (&str, ()) , atau kesalahan dengan &str . Pasangan (&str, ()) adalah hal yang menarik: seperti yang kami katakan bahwa kami harus mengembalikan tuple dari konten berikut,
hasil parsing dan sisa input. &str adalah input berikutnya, dan hasilnya hanya tipe blok () , karena jika parser ini berhasil, hanya dapat memiliki satu hasil (kami menemukan huruf a ), dan kami tidak benar-benar perlu mengembalikan
huruf a dalam hal ini kami hanya perlu menunjukkan bahwa kami berhasil menemukannya.
Jadi, mari kita lihat kode parser itu sendiri. Kami tidak bercanda bahwa dengan mengandalkan pustaka standar, kami dapat menghindari sakit kepala dengan Unicode: kami mendapatkan iterator di atas karakter string menggunakan metode chars() dan mengambil karakter pertama darinya. Ini akan menjadi elemen tipe char dibungkus dalam Option , di mana None berarti bahwa kami mencoba menarik char dari string kosong.
Untuk membuat keadaan menjadi lebih buruk, char tidak selalu berarti apa yang Anda pikirkan sebagai karakter Unicode. Ini kemungkinan adalah apa yang Unicode sebut "cluster grapheme" , yang dapat terdiri dari beberapa char , yang sebenarnya "nilai skalar" , yang dua tingkat di bawah cluster grapheme. Namun, jalan ini mengarah ke kegilaan, dan untuk tujuan kita, kita jujur tidak mungkin melihat chars luar ASCII, jadi mari kita berhenti di situ.
Kami memetakan ke pola Some('a') , yang merupakan hasil spesifik yang kami cari, dan jika itu cocok, kami mengembalikan nilai keberhasilan kami:
Ok((&input['a'.len_utf8()..], ())) . Yaitu, kami menghapus bagian yang baru saja kami uraikan ( 'a' ) dari potongan garis dan mengembalikan sisanya bersama dengan nilai yang diurai kami, yang hanya kosong
() . Selalu mengingat monster Unicode, sebelum memotong, kami mengetahui panjangnya karakter UTF-8 dari 'a' melalui perpustakaan standar - itu adalah 1 (tapi jangan pernah melupakan monster Unicode).
Jika kami mendapatkan Some(char) , atau jika tidak None , maka kami akan mengembalikan kesalahan. Seperti yang Anda ingat, jenis kesalahan kami hanyalah irisan string, yang kami sampaikan sebagai input dan yang tidak dapat diuraikan. Itu tidak dimulai dengan a , jadi ini adalah kesalahan kami. Ini bukan kesalahan besar, tapi setidaknya ini sedikit lebih baik daripada hanya "ada sesuatu yang salah di suatu tempat."
Kami tidak benar-benar membutuhkan pengurai ini untuk mem-parsing XML, tetapi hal pertama yang harus kami lakukan adalah menemukan karakter pembuka < , jadi kami membutuhkan sesuatu yang sangat mirip. Kita juga perlu mem-parsing > , / dan = secara khusus, jadi mungkin kita dapat membuat fungsi yang membuat parser untuk karakter yang kita inginkan?
Membuat parser
Mari kita pikirkan hal ini: kita akan menulis sebuah fungsi yang membuat parser untuk string statis dengan panjang berapa pun , dan bukan hanya satu karakter. Ini bahkan lebih sederhana karena fragmen garis sudah merupakan irisan garis UTF-8 yang valid, dan kita tidak perlu memikirkan monster Unicode.
fn match_literal(expected: &'static str) -> impl Fn(&str) -> Result<(&str, ()), &str> { move |input| match input.get(0..expected.len()) { Some(next) if next == expected => { Ok((&input[expected.len()..], ())) } _ => Err(input), } }
Sekarang terlihat sedikit berbeda.
Pertama-tama, mari kita lihat tipenya. Sekarang fungsi kita mengambil string yang expected sebagai argumen dan mengembalikan sesuatu yang mirip dengan parser, alih-alih menjadi parser itu sendiri. Ini adalah fungsi yang mengembalikan fungsi urutan yang lebih tinggi . Pada dasarnya, kami menulis fungsi yang membuat fungsi mirip dengan fungsi the_letter_a kami sebelumnya.
Dengan demikian, alih-alih melakukan pekerjaan dalam tubuh fungsi, kami mengembalikan penutupan yang melakukan pekerjaan ini dan yang sesuai dengan tanda tangan dari jenis kami untuk penganalisa dari yang sebelumnya.
Pencocokan pola terlihat sama, kecuali bahwa kami tidak dapat mencocokkan string string kami secara langsung, karena kami tidak tahu persisnya, oleh karena itu kami menggunakan kondisi pencocokan if next == expected . Kalau tidak, itu persis sama dengan sebelumnya, tepat di dalam tubuh sirkuit.
Menguji parser kami
Mari kita menulis tes untuk ini untuk memastikan kita melakukannya dengan benar.
#[test] fn literal_parser() { let parse_joe = match_literal("Hello Joe!"); assert_eq!( Ok(("", ())), parse_joe("Hello Joe!") ); assert_eq!( Ok((" Hello Robert!", ())), parse_joe("Hello Joe! Hello Robert!") ); assert_eq!( Err("Hello Mike!"), parse_joe("Hello Mike!") ); }
Pertama kita membuat parser: match_literal("Hello Joe!") . Seharusnya menggunakan string "Hello Joe!" dan mengembalikan sisa string, atau gagal dan mengembalikan seluruh string.
Dalam kasus pertama, kami hanya memberikannya baris yang tepat yang kami harapkan, dan melihatnya mengembalikan string kosong dan nilai () , yang berarti "kami telah menganalisis string yang diharapkan, dan Anda tidak perlu mengembalikannya."
Yang kedua, kami memberi makan string "Hello Joe! Hello Robert!" dan kita melihat bahwa dia benar-benar menggunakan string "Hello Joe!" dan mengembalikan sisa input: " Hello Robert!" (ruang terkemuka dan yang lainnya).
Yang ketiga, kita memasukkan input yang salah: "Hello Mike!" dan perhatikan bahwa itu benar-benar menolak input dengan kesalahan. Bukan berarti Mike salah, biasanya tidak seperti apa yang dicari parser.
Parser untuk sesuatu yang kurang spesifik
Jadi ini memungkinkan kita untuk menganalisis < , > , = dan bahkan </ dan /> . Kita hampir selesai!
Selanjutnya setelah karakter pembuka < adalah nama elemen. Kami tidak dapat melakukan ini dengan perbandingan string sederhana. Tapi kita bisa melakukannya dengan regex ...
... tapi mari kita menahan diri. Ini akan menjadi ekspresi reguler yang akan sangat mudah untuk direplikasi dalam kode sederhana, dan untuk ini kita tidak perlu menggunakan paket regex . Mari kita lihat apakah kita dapat menulis parser kita sendiri untuk ini, hanya menggunakan pustaka Rust standar.
Ingat aturan untuk pengidentifikasi nama elemen, tampilannya seperti ini: satu karakter alfabet, diikuti oleh nol atau lebih dari simbol alfabet apa pun,
karakter, angka atau tanda hubung.
fn identifier(input: &str) -> Result<(&str, String), &str> { let mut matched = String::new(); let mut chars = input.chars(); match chars.next() { Some(next) if next.is_alphabetic() => matched.push(next), _ => return Err(input), } while let Some(next) = chars.next() { if next.is_alphanumeric() || next == '-' { matched.push(next); } else { break; } } let next_index = matched.len(); Ok((&input[next_index..], matched)) }
Seperti biasa, pertama-tama kita melihat jenisnya. Kali ini kami tidak menulis fungsi untuk membuat parser, kami hanya menulis parser itu sendiri, seperti untuk pertama kalinya. Perbedaan yang nyata di sini adalah bahwa alih-alih tipe hasil () kami mengembalikan sebuah String dalam tupel bersama dengan input yang tersisa. String ini akan berisi pengidentifikasi yang baru saja kita uraikan.
Dengan mengingat hal itu, pertama-tama kita membuat String kosong dan menyebutnya matched . Ini akan menjadi hasil kami. Kami juga mendapatkan iterator untuk karakter dalam input , yang akan mulai kita bagi.
Langkah pertama adalah melihat apakah ada simbol di awal. Kami menarik karakter pertama dari iterator dan memeriksa apakah itu huruf: next.is_alphabetic() . Pustaka Rust standar, tentu saja, akan membantu kami dengan Unicode - itu akan sesuai dengan huruf dalam alfabet apa pun, dan bukan hanya di ASCII. Jika itu adalah surat, kami memasukkannya ke dalam string kami di variabel yang matched , dan jika tidak, kami tidak melihat pengenal elemen dan segera kembali dengan kesalahan.
Pada langkah kedua, kami terus menarik karakter dari iterator, mengirimkannya ke baris yang kami buat sampai kami is_alphanumeric() karakter yang tidak memenuhi fungsi is_alphanumeric() (mirip dengan is_alphabetic() kecuali itu juga termasuk angka dalam alfabet apa pun) atau lari '-' .
Ketika kami pertama kali melihat sesuatu yang tidak memenuhi kriteria ini, kami menyelesaikan parsing, memutus loop dan mengembalikan sebuah String , mengingat untuk memotong fragmen yang kami gunakan dari input . Demikian pula, jika karakter berakhir dengan iterator, itu berarti bahwa kita telah mencapai akhir input.
Perlu dicatat bahwa kita tidak kembali dengan kesalahan ketika kita melihat sesuatu yang bukan alfanumerik atau tanda hubung. Kami sudah memiliki cukup untuk membuat pengidentifikasi yang valid setelah kami mencocokkan huruf pertama ini, dan itu cukup normal bahwa setelah mengurai pengidentifikasi kami akan ada lebih banyak elemen di baris input untuk analisis, jadi kami hanya menghentikan penguraian dan mengembalikan hasil kami. Hanya jika kami tidak dapat menemukan bahkan huruf pertama ini, kami benar-benar mengembalikan kesalahan, karena dalam kasus ini pasti tidak ada pengidentifikasi.
Ingat bahwa struktur Element adalah apa yang akan kita parsing dalam dokumen XML kita.
struct Element { name: String, attributes: Vec<(String, String)>, children: Vec<Element>, }
Bahkan, kami baru saja selesai menganalisis untuk bagian pertama, bidang name . String yang dikembalikan oleh parser langsung ke sana. Itu juga parser yang benar untuk bagian pertama dari setiap attribute .
Mari kita periksa.
#[test] fn identifier_parser() { assert_eq!( Ok(("", "i-am-an-identifier".to_string())), identifier("i-am-an-identifier") ); assert_eq!( Ok((" entirely an identifier", "not".to_string())), identifier("not entirely an identifier") ); assert_eq!( Err("!not at all an identifier"), identifier("!not at all an identifier") ); }
Kita melihat bahwa dalam kasus pertama, string "i-am-an-identifier" diurai sepenuhnya, hanya menyisakan string kosong. Dalam kasus kedua, parser mengembalikan "not" sebagai pengidentifikasi, dan sisa string dikembalikan sebagai input yang tersisa. Dalam kasus ketiga, pengurai gagal dengan segera, karena karakter pertama yang ditemukan bukan huruf.
Combinators
Sekarang kita dapat mem-parsing karakter pembuka < , dan kita dapat mem-parsing pengidentifikasi berikutnya, tetapi kita perlu mengurai keduanya . Oleh karena itu, langkah selanjutnya adalah menulis fungsi parser kombinatorial lain, tetapi yang mengambil dua parser sebagai input dan mengembalikan parser baru yang mem-parsing keduanya secara berurutan. Dengan kata lain, parser combinator karena menggabungkan dua parser menjadi yang baru. Mari kita lihat apakah kita bisa melakukan ini.
fn pair<P1, P2, R1, R2>(parser1: P1, parser2: P2) -> impl Fn(&str) -> Result<(&str, (R1, R2)), &str> where P1: Fn(&str) -> Result<(&str, R1), &str>, P2: Fn(&str) -> Result<(&str, R2), &str>, { move |input| match parser1(input) { Ok((next_input, result1)) => match parser2(next_input) { Ok((final_input, result2)) => Ok((final_input, (result1, result2))), Err(err) => Err(err), }, Err(err) => Err(err), } }
Ini menjadi sedikit rumit di sini, tetapi Anda tahu apa yang harus dilakukan: mulai dengan melihat jenis.
Pertama-tama, kami memiliki empat jenis variabel: P1 , P2 , R1 dan R2 . Ini adalah Parser 1 , Parser 2 , Result 1 dan Result 2 . P1 dan P2 adalah fungsi, dan Anda akan melihat bahwa mereka mengikuti pola fungsi parser yang sudah mapan: seperti nilai balik, mereka mengambil &str sebagai input dan mengembalikan Result pasangan input dan hasil yang tersisa, atau kesalahan.
Tapi lihat jenis hasil masing-masing fungsi: P1 adalah parser yang memberikan R1 jika berhasil, dan P2 juga memberikan R2 . Dan hasil parser terakhir yang dikembalikan dari fungsi kami adalah (R1, R2) . Dengan demikian, tugas parser ini adalah pertama-tama memulai analyzer P1 pada input, menyimpan hasilnya, kemudian menjalankan P2 pada input yang mengembalikan P1 , dan jika keduanya bekerja, kami menggabungkan dua hasil menjadi tupel (R1, R2)
Kode tersebut menunjukkan bahwa inilah yang ia lakukan. Kita mulai dengan memulai penganalisis pertama pada input, lalu penganalisis kedua, lalu menggabungkan kedua hasil menjadi tupel dan mengembalikannya. Jika salah satu dari pengurai ini gagal, kami akan segera kembali dengan kesalahan yang dikeluarkannya.
Jadi, kita harus dapat menggabungkan dua parser kami, match_literal dan identifier , untuk benar-benar match_literal fragmen pertama dari tag XML pertama kami. Mari kita menulis tes untuk melihat apakah itu berhasil.
#[test] fn pair_combinator() { let tag_opener = pair(match_literal("<"), identifier); assert_eq!( Ok(("/>", ((), "my-first-element".to_string()))), tag_opener("<my-first-element/>") ); assert_eq!(Err("oops"), tag_opener("oops")); assert_eq!(Err("!oops"), tag_opener("<!oops")); }
Tampaknya bekerja! Tapi lihat jenis hasil ini: ((), String) . Jelas, kami hanya tertarik pada nilai yang benar, String . Ini akan terjadi cukup sering - beberapa parser kami hanya mencocokkan pola pada input tanpa menghasilkan nilai, sehingga outputnya dapat diabaikan dengan aman. Untuk beradaptasi dengan pola ini, kita akan menggunakan kombinator pair kita untuk menulis dua kombinator lainnya: left , yang membuang hasil pengurai pertama dan hanya mengembalikan yang kedua, dan kebalikannya right . Kami menggunakan parser dalam pengujian kami di atas, yang membuang bagian kiri dan hanya menyimpan String kami, bukan pair .
Pendahuluan Functor
Tetapi sebelum kita melangkah sejauh itu, mari kita perkenalkan kombinator lain yang akan sangat menyederhanakan penulisan keduanya: map .
Combinator ini memiliki satu tugas: untuk mengubah jenis hasil. , , , ((), String) , String .
, , . : |(_left, right)| right . , Fn(A) -> B A — , B — .
fn map<P, F, A, B>(parser: P, map_fn: F) -> impl Fn(&str) -> Result<(&str, B), &str> where P: Fn(&str) -> Result<(&str, A), &str>, F: Fn(A) -> B, { move |input| match parser(input) { Ok((next_input, result)) => Ok((next_input, map_fn(result))), Err(err) => Err(err), } }
? P — . A . F — , P , , P , — B A
parser(input) , , result map_fn(result) , A B , .
, , map , Result :
fn map<P, F, A, B>(parser: P, map_fn: F) -> impl Fn(&str) -> Result<(&str, B), &str> where P: Fn(&str) -> Result<(&str, A), &str>, F: Fn(A) -> B, { move |input| parser(input) .map(|(next_input, result)| (next_input, map_fn(result))) }
— , «» Haskell , . A , map , A B , B , . Rust, Option , Result , Iterator Future , . : - Rust, , , , , map .
, , : Fn(&str) -> Result<(&str, Output), &str> . , , , , , , , .
, :
type ParseResult<'a, Output> = Result<(&'a str, Output), &'a str>;
, , , ParseResult<String> . , , Rust . , rustc , , .
'a , , .
. , , . , .
trait Parser<'a, Output> { fn parse(&self, input: &'a str) -> ParseResult<'a, Output>; }
: parse() , : , , .
, , :
impl<'a, F, Output> Parser<'a, Output> for F where F: Fn(&'a str) -> ParseResult<Output>, { fn parse(&self, input: &'a str) -> ParseResult<'a, Output> { self(input) } }
, , , Parser , .
, , . map , .
fn map<'a, P, F, A, B>(parser: P, map_fn: F) -> impl Parser<'a, B> where P: Parser<'a, A>, F: Fn(A) -> B, { move |input| parser.parse(input) .map(|(next_input, result)| (next_input, map_fn(result))) }
: , parser.parse(input) , , P , , Parser , , Parser . , . 'a' , , .
pair , :
fn pair<'a, P1, P2, R1, R2>(parser1: P1, parser2: P2) -> impl Parser<'a, (R1, R2)> where P1: Parser<'a, R1>, P2: Parser<'a, R2>, { move |input| match parser1.parse(input) { Ok((next_input, result1)) => match parser2.parse(next_input) { Ok((final_input, result2)) => Ok((final_input, (result1, result2))), Err(err) => Err(err), }, Err(err) => Err(err), } }
: parser.parse(input) parser(input) .
, pair , map .
fn pair<'a, P1, P2, R1, R2>(parser1: P1, parser2: P2) -> impl Parser<'a, (R1, R2)> where P1: Parser<'a, R1>, P2: Parser<'a, R2>, { move |input| { parser1.parse(input).and_then(|(next_input, result1)| { parser2.parse(next_input) .map(|(last_input, result2)| (last_input, (result1, result2))) }) } }
and_then Result map , , Result , Result . match . and_then , , map , left right .
Left Right
pair map , left right :
fn left<'a, P1, P2, R1, R2>(parser1: P1, parser2: P2) -> impl Parser<'a, R1> where P1: Parser<'a, R1>, P2: Parser<'a, R2>, { map(pair(parser1, parser2), |(left, _right)| left) } fn right<'a, P1, P2, R1, R2>(parser1: P1, parser2: P2) -> impl Parser<'a, R2> where P1: Parser<'a, R1>, P2: Parser<'a, R2>, { map(pair(parser1, parser2), |(_left, right)| right) }
pair , , map , .
, , .
, Parser ParseResult . match_literal :
fn match_literal<'a>(expected: &'static str) -> impl Parser<'a, ()> { move |input: &'a str| match input.get(0..expected.len()) { Some(next) if next == expected => Ok((&input[expected.len()..], ())), _ => Err(input), } }
, , — &'a str , rustc .
identifier , , , :
fn identifier(input: &str) -> ParseResult<String> {
. () . .
#[test] fn right_combinator() { let tag_opener = right(match_literal("<"), identifier); assert_eq!( Ok(("/>", "my-first-element".to_string())), tag_opener.parse("<my-first-element/>") ); assert_eq!(Err("oops"), tag_opener.parse("oops")); assert_eq!(Err("!oops"), tag_opener.parse("<!oops")); }
. < . ? .
, , . , .
, , - , : .
( ) . .
— , <element attribute="value"/> , . , , .
identifier , . , .
fn one_or_more<'a, P, A>(parser: P) -> impl Parser<'a, Vec<A>> where P: Parser<'a, A>, { move |mut input| { let mut result = Vec::new(); if let Ok((next_input, first_item)) = parser.parse(input) { input = next_input; result.push(first_item); } else { return Err(input); } while let Ok((next_input, next_item)) = parser.parse(input) { input = next_input; result.push(next_item); } Ok((input, result)) } }
, , , A , Vec<A> — A .
identifier . , , . , , .
, : ? :
fn zero_or_more<'a, P, A>(parser: P) -> impl Parser<'a, Vec<A>> where P: Parser<'a, A>, { move |mut input| { let mut result = Vec::new(); while let Ok((next_input, next_item)) = parser.parse(input) { input = next_input; result.push(next_item); } Ok((input, result)) } }
, , .
#[test] fn one_or_more_combinator() { let parser = one_or_more(match_literal("ha")); assert_eq!(Ok(("", vec![(), (), ()])), parser.parse("hahaha")); assert_eq!(Err("ahah"), parser.parse("ahah")); assert_eq!(Err(""), parser.parse("")); } #[test] fn zero_or_more_combinator() { let parser = zero_or_more(match_literal("ha")); assert_eq!(Ok(("", vec![(), (), ()])), parser.parse("hahaha")); assert_eq!(Ok(("ahah", vec![])), parser.parse("ahah")); assert_eq!(Ok(("", vec![])), parser.parse("")); }
: one_or_more , , zero_or_more , .
, , . one_or_more zero_or_more , - :
fn one_or_more<'a, P, A>(parser: P) -> impl Parser<'a, Vec<A>> where P: Parser<'a, A>, { map(pair(parser, zero_or_more(parser)), |(head, mut tail)| { tail.insert(0, head); tail }) }
Rust, cons Vec , , Lisp, , . , : .
, : , . : ( ). , , Clone , , , .
. , one_or_more , , , , , - , , RangeBound : range(0..) zero_or_more , range(1..) one_or_more , range(5..=6) , .
. zero_or_more one_or_more .
, — , Rc ?
, one_or_more zero_or_more .
, . , . , , , > /> . , . , , , , .
. .
-. match_literal , . ? - , Unicode, . Rust, , char is_whitespace , is_alphabetic is_alphanumeric .
-. , , is_whitespace , identifier .
-. , . any_char , char , , pred , , : pred(any_char, |c| c.is_whitespace()) . , , : .
any_char , , UTF-8.
fn any_char(input: &str) -> ParseResult<char> { match input.chars().next() { Some(next) => Ok((&input[next.len_utf8()..], next)), _ => Err(input), } }
pred , , . , . , true , . , .
fn pred<'a, P, A, F>(parser: P, predicate: F) -> impl Parser<'a, A> where P: Parser<'a, A>, F: Fn(&A) -> bool, { move |input| { if let Ok((next_input, value)) = parser.parse(input) { if predicate(&value) { return Ok((next_input, value)); } } Err(input) } }
, , :
#[test] fn predicate_combinator() { let parser = pred(any_char, |c| *c == 'o'); assert_eq!(Ok(("mg", 'o')), parser.parse("omg")); assert_eq!(Err("lol"), parser.parse("lol")); }
, whitespace_char :
fn whitespace_char<'a>() -> impl Parser<'a, char> { pred(any_char, |c| c.is_whitespace()) }
, whitespace_char , , , , , . space1 space0 .
fn space1<'a>() -> impl Parser<'a, Vec<char>> { one_or_more(whitespace_char()) } fn space0<'a>() -> impl Parser<'a, Vec<char>> { zero_or_more(whitespace_char()) }
? , , . identifier ( , any_char pred *_or_more ). match_literal("=") = . , . , , .
fn quoted_string<'a>() -> impl Parser<'a, String> { map( right( match_literal("\""), left( zero_or_more(pred(any_char, |c| *c != '"')), match_literal("\""), ), ), |chars| chars.into_iter().collect(), ) }
, , , , .
map - , , , , , : . map right , right — , : match_literal("\"") . .
right — . left , , left , , , match_literal("\"") — . , — .
pred any_char , , , zero_or_more , :
right left .
, . , zero_or_more ? Vec<A> A . any_char char . , , Vec<char> . map : , Vec<char> String , , String Iterator<Item = char> , vec_of_chars.into_iter().collect() , String .
, , , , , , , , .
#[test] fn quoted_string_parser() { assert_eq!( Ok(("", "Hello Joe!".to_string())), quoted_string().parse("\"Hello Joe!\"") ); }
, , , , .
,
, , = . , .
. , Vec<(String, String)> , (String, String) , zero_or_more . , .
fn attribute_pair<'a>() -> impl Parser<'a, (String, String)> { pair(identifier, right(match_literal("="), quoted_string())) }
! : pair , identifier , String , right = , , quoted_string , String .
zero_or_more , , .
fn attributes<'a>() -> impl Parser<'a, Vec<(String, String)>> { zero_or_more(right(space1(), attribute_pair())) }
: ,
. right .
.
#[test] fn attribute_parser() { assert_eq!( Ok(( "", vec![ ("one".to_string(), "1".to_string()), ("two".to_string(), "2".to_string()) ] )), attributes().parse(" one=\"1\" two=\"2\"") ); }
! !
, , rustc , , . , . , rustc, , , #![type_length_limit = "…some big number…"] , . , #![type_length_limit = "16777216"] , . , !
, , , , NP-. element: , , , zero_or_more , ?
, , . , , , : < , . , (String, Vec<(String, String)>) .
fn element_start<'a>() -> impl Parser<'a, (String, Vec<(String, String)>)> { right(match_literal("<"), pair(identifier, attributes())) }
, , .
fn single_element<'a>() -> impl Parser<'a, Element> { map( left(element_start(), match_literal("/>")), |(name, attributes)| Element { name, attributes, children: vec![], }, ) }
, , — Element !
.
#[test] fn single_element_parser() { assert_eq!( Ok(( "", Element { name: "div".to_string(), attributes: vec![("class".to_string(), "float".to_string())], children: vec![] } )), single_element().parse("<div class=\"float\"/>") ); }
… , .
single_element , , , . , , , — , — .
, , ...
- Rust, , , .
. , :
enum List<A> { Cons(A, List<A>), Nil, }
rustc , List<A> , List::<A>::Cons List<A> , . rustc, , , .
, Rust. , Rust, , , , . , .
, . , List::Cons A A , A A . , , , , List::Cons , . , Rust — Box .
enum List<A> { Cons(A, Box<List<A>>), Nil, }
Box , . , , Box<dyn Parser<'a, A>> .
. ? , - , , . : . . , , SIMD ( ).
, Parser Box , .
struct BoxedParser<'a, Output> { parser: Box<dyn Parser<'a, Output> + 'a>, } impl<'a, Output> BoxedParser<'a, Output> { fn new<P>(parser: P) -> Self where P: Parser<'a, Output> + 'a, { BoxedParser { parser: Box::new(parser), } } } impl<'a, Output> Parser<'a, Output> for BoxedParser<'a, Output> { fn parse(&self, input: &'a str) -> ParseResult<'a, Output> { self.parser.parse(input) } }
, , BoxedParser box . BoxedParser ( BoxedParser , ), BoxedParser::new(parser) , , Box . , Parser , .
Box , BoxedParser Parser , . , , , , , , , , . .
, , , .
, ? , , . quoted_string :
fn quoted_string<'a>() -> impl Parser<'a, String> { map( right( match_literal("\""), left( zero_or_more(pred(any_char, |c| *c != '"')), match_literal("\""), ), ), |chars| chars.into_iter().collect(), ) }
, . Parser ?
, , impl Trait , impl Trait .
… BoxedParser . , impl Parser<'a, A> , , BoxedParser<'a, A> .
, , , Parser .
map , Parser :
trait Parser<'a, Output> { fn parse(&self, input: &'a str) -> ParseResult<'a, Output>; fn map<F, NewOutput>(self, map_fn: F) -> BoxedParser<'a, NewOutput> where Self: Sized + 'a, Output: 'a, NewOutput: 'a, F: Fn(Output) -> NewOutput + 'a, { BoxedParser::new(map(self, map_fn)) } }
'a , , . , — , , impl Trait .
quoted_string :
fn quoted_string<'a>() -> impl Parser<'a, String> { right( match_literal("\""), left( zero_or_more(pred(any_char, |c| *c != '"')), match_literal("\""), ), ) .map(|chars| chars.into_iter().collect()) }
, , .map() right() .
pair , left right , , , , pair . , , map , .
— pred . Parser :
fn pred<F>(self, pred_fn: F) -> BoxedParser<'a, Output> where Self: Sized + 'a, Output: 'a, F: Fn(&Output) -> bool + 'a, { BoxedParser::new(pred(self, pred_fn)) }
quoted_string pred , :
zero_or_more(any_char.pred(|c| *c != '"')),
, , , zero_or_more — « any_char », . , zero_or_more one_or_more .
quoted_string , map single_element :
fn single_element<'a>() -> impl Parser<'a, Element> { left(element_start(), match_literal("/>")).map(|(name, attributes)| Element { name, attributes, children: vec![], }) }
element_start , , , . ...
… , . , .
map pred Box — !
. single_element , , > , /> . , , .
fn open_element<'a>() -> impl Parser<'a, Element> { left(element_start(), match_literal(">")).map(|(name, attributes)| Element { name, attributes, children: vec![], }) }
, ? , , , zero_or_more , ? , , — : , , .
, , : , , . , , , . , , , , , , .
fn either<'a, P1, P2, A>(parser1: P1, parser2: P2) -> impl Parser<'a, A> where P1: Parser<'a, A>, P2: Parser<'a, A>, { move |input| match parser1.parse(input) { ok @ Ok(_) => ok, Err(_) => parser2.parse(input), } }
element , , ( open_element , element ).
fn element<'a>() -> impl Parser<'a, Element> { either(single_element(), open_element()) }
. , , , . , ?
fn close_element<'a>(expected_name: String) -> impl Parser<'a, String> { right(match_literal("</"), left(identifier, match_literal(">"))) .pred(move |name| name == &expected_name) }
pred , ?
, :
fn parent_element<'a>() -> impl Parser<'a, Element> { pair( open_element(), left(zero_or_more(element()), close_element(…oops)), ) }
close_element ? , .
. , parent_element , open_element element parent_element , , XML.
, , and_then ? , . and_then : -, , , , . pair , , , , . , and_then Result Option , , , Result Option , , ( , )).
, .
fn and_then<'a, P, F, A, B, NextP>(parser: P, f: F) -> impl Parser<'a, B> where P: Parser<'a, A>, NextP: Parser<'a, B>, F: Fn(A) -> NextP, { move |input| match parser.parse(input) { Ok((next_input, result)) => f(result).parse(next_input), Err(err) => Err(err), } }
, , P , , A . F , map A B , , and_then A NextP , B . — B , , , NextP .
: , , , , f ( A ), , f(result) , B . . , , , B
: P , , f P , NextP , , .
Parser , map , .
fn and_then<F, NextParser, NewOutput>(self, f: F) -> BoxedParser<'a, NewOutput> where Self: Sized + 'a, Output: 'a, NewOutput: 'a, NextParser: Parser<'a, NewOutput> + 'a, F: Fn(Output) -> NextParser + 'a, { BoxedParser::new(and_then(self, f)) }
, , ?
, pair :
fn pair<'a, P1, P2, R1, R2>(parser1: P1, parser2: P2) -> impl Parser<'a, (R1, R2)> where P1: Parser<'a, R1> + 'a, P2: Parser<'a, R2> + 'a, R1: 'a + Clone, R2: 'a, { parser1.and_then(move |result1| parser2.map(move |result2| (result1.clone(), result2))) }
, : parser2.map() parser2 , Fn , FnOnce , parser2 , . , Rust. , , pair .
, Rust, close_element , , .
:
fn parent_element<'a>() -> impl Parser<'a, Element> { pair( open_element(), left(zero_or_more(element()), close_element(…oops)), ) }
, and_then , close_element .
fn parent_element<'a>() -> impl Parser<'a, Element> { open_element().and_then(|el| { left(zero_or_more(element()), close_element(el.name.clone())).map(move |children| { let mut el = el.clone(); el.children = children; el }) }) }
, and_then open_element() , , close_element . , open_element and_then . , Element open_element , , , .
, map , Element ( el ) . clone() , Fn . ( Vec<Element> ) Element , .
, , element , open_element parent_element , , , , !
"" ?
, , map «» Haskell?
and_then — , Rust, , map . flat_map Iterator , , .
— "". Thing<A> , and_then , A Thing<B> , Thing<B> — .
, , Option<A> , , Some(A) None , , Some(A) , Some(B)
. , Future<A> , and_then Future<B> , Future<B> Future<A> , Future<A> . Future<A> , — 1 , Future<B> . , Future , and_then , Future , . , Future , .
, Rust , , , , , , , . .
, Redux
.
, XML, . , ( , , < div / > , ).
.
fn whitespace_wrap<'a, P, A>(parser: P) -> impl Parser<'a, A> where P: Parser<'a, A>, { right(space0(), left(parser, space0())) }
element , element , , , .
fn element<'a>() -> impl Parser<'a, Element> { whitespace_wrap(either(single_element(), parent_element())) }
!
, ! , .
#[test] fn xml_parser() { let doc = r#" <top label="Top"> <semi-bottom label="Bottom"/> <middle> <bottom label="Another bottom"/> </middle> </top>"#; let parsed_doc = Element { name: "top".to_string(), attributes: vec![("label".to_string(), "Top".to_string())], children: vec![ Element { name: "semi-bottom".to_string(), attributes: vec![("label".to_string(), "Bottom".to_string())], children: vec![], }, Element { name: "middle".to_string(), attributes: vec![], children: vec![Element { name: "bottom".to_string(), attributes: vec![("label".to_string(), "Another bottom".to_string())], children: vec![], }], }, ], }; assert_eq!(Ok(("", parsed_doc)), element().parse(doc)); }
, - , , :
#[test] fn mismatched_closing_tag() { let doc = r#" <top> <bottom/> </middle>"#; assert_eq!(Err("</middle>"), element().parse(doc)); }
, . , , , , . , , , , . , , , , , .
: , ! , , , 2 .
, , . !
, , Rust , , - , , , .
, pom , , .
Rust nom , pom ( , ), , .
Rust combine , .
Haskell Parsec .
, « Haskell» , , Haskell.
Bodil Stokke Creative Commons Attribution-NonCommercial-ShareAlike 4.0. , http://creativecommons.org/licenses/by-nc-sa/4.0/ .
1: .
2: , .
andreevlex funkill