Seni parsing atau do-it-yourself DOM

Halo, Habr! Baru-baru ini, saya muncul dengan ide untuk membuat bahasa markup sederhana seperti markdown, yang akan sempurna untuk tugas-tugas saya, yaitu, penulisan cepat kuliah dengan format dan kemampuan untuk memasukkan rumus matematika "on the fly", hanya menggunakan satu keyboard. Untuk menerjemahkan teks yang ditulis dalam format ini ke bentuk yang lebih mudah dimengerti, misalnya, dokumen LibreOffice Writer, Anda memerlukan parser , dengan kata lain, parser . Karena saya biasa membuat sepeda, saya pergi ke mesin pencari dengan pertanyaan "contoh parser", "html ke DOM", "bagaimana mengurai html", dll. Yang mengecewakan saya, pada semua sumber yang ditemukan, baik contoh dasar seperti kalkulator Straustrup dengan rekursif oleh keturunan, atau solusi siap pakai seperti flex, bison, llvm dan yacc digunakan. Bahkan ada lebih banyak perpustakaan yang dirancang untuk mem-parsing bahasa yang didefinisikan secara ketat (gumbo, jsoup, quickjson, alat Qt, dll.) Tidak satu pun yang lain merupakan bagian dari rencana saya untuk menulis parser untuk markup saya di C ++ hanya menggunakan perpustakaan standar, jadi saya alih-alih sumber daya elektronik, manual lembaga teknis menjadi sumber pengetahuan tentang seni parsing. Tentang cara mengambil teks dan membangunnya dari AST (pohon sintaksis abstrak), tentang beberapa jebakan yang saya temui dalam proses, saya akan memberi tahu Anda tentang kemungkinan kesalahan hari ini.

Saya akan segera melakukan reservasi - jika tujuan Anda adalah bahasa skrip Anda sendiri atau bahkan lebih rumit, artikel ini tidak akan cukup untuk implementasinya. Idealnya, Anda perlu tahu betul teori automata dan struktur diskrit. Tetapi untuk saat ini, sebagai titik awal, saya dapat membatasi diri pada pengalaman saya, yang saya bagikan dengan murah hati. Ini bukan apa yang saya maksudkan pada awalnya, tetapi ini ideal sebagai contoh. Kami akan mem-parsing HTML sebagai bahasa yang sederhana dan akrab.

Pertama-tama, parsing, atau parsing, bukan sinonim untuk proses lengkap mengubah teks menjadi model objek. Proses itu sendiri terdiri dari dua tahap:

1. Analisis leksikal teks menjadi token adalah bagian kecil dari teks ini yang memiliki makna sintaksis tertentu.
2. Parsing adalah konstruksi token berdasarkan nilai-nilai mereka dari pohon sintaksis abstrak (AST - pohon sintaksis abstrak), atau model objek dokumen (DOM - model objek dokumen).

Tapi mari kita selesaikan. Sebelum Anda membuka IDE favorit Anda dan menulis kode, Anda perlu mengembangkan tata bahasa untuk masa depan. Dari tata bahasa formal bebas konteks, yang paling terkenal adalah bentuk Backus-Naur (BNF) dan bentuk Backus-Naur yang diperluas . Saya menggunakan simbiosis mereka, mengambil yang terbaik dari kedua bentuk. Ekspresi apa pun dapat didefinisikan melalui ekspresi lain sebagai berikut:

<> = <_1> <_> <_2> 

Di sini satu ekspresi didefinisikan melalui tiga orang lain mengikuti satu demi satu. Mereka, pada gilirannya, juga harus diwakili melalui ekspresi "ketiga", dll.

Kapan harus berhenti?

Deskripsi sintaks bahasa apa pun dalam tata bahasa formal terdiri dari dua jenis token: terminal dan non-terminal . Nonterminals adalah ekspresi yang perlu didefinisikan:

 <_1> = <> (<_> | <_>) <> 

Terminal mandiri, mereka tidak perlu didefinisikan. Contoh di atas dapat ditulis seperti ini:

 <> = <_1> "+" <_2> <_1> = <> ("*" | "/") <> 

di mana "+", "*", "/" adalah terminal.
Anda harus memilih terminal dari tata bahasa segera, Anda bahkan dapat menuliskannya dalam daftar terpisah di bagian bawah definisi utama - mereka akan berguna nanti.

Deskripsi lengkap BNF tersedia di Wikipedia di sini dan di sini . Menyusun tata bahasa adalah tahap penting dalam menciptakan bahasa yang tidak menoleransi kesembronoan. Satu kesalahan di dalamnya dapat menyebabkan kode benar-benar tidak bekerja, yang harus ditulis ulang dari awal. Karena itu, sebelum mengambil langkah berikutnya, pastikan tidak ada masalah kontroversial dalam tata bahasa yang dikompilasi. Jika Anda memiliki dua monitor, akan lebih mudah bagi Anda untuk menempati satu monitor dengan dokumen tata bahasa untuk sisa pekerjaan Anda sehingga Anda dapat dengan cepat memindahkan mata Anda ke sana ketika Anda membuat kode. Percayalah, Anda harus melakukan ini setiap saat. Berikut ini adalah tata bahasa HTML5 BNF yang dikompilasi:

 (* document *) <document> = {<document_part>} <END> <document_part> = <block> | <empty_tag> | <comment> | <macro_tag> | <text> <block> = <opening_tag> {<document_part>} <closing_tag> (* tags *) <opening_tag> = "<" {<ws>} <block_tag_name> [<attributes_list>] {<ws>} ">" <closing_tag> = "<" "/" {<ws>} <block_tag_name> {<ws>} ">" <empty_tag> = "<" "!" {<ws>} <empty_tag_name> [<attributes_list] {<ws>} ["/"] ">" <comment> = "<" "!" "--" <comment_text> "--" ">" <macro_tag> = "<" "?" <macro_text> "?" ">" <block_tag_name> = "a" | "abbr" | "address" | "article" | "aside" | "audio" | "b" | "bdo" | "blockquote" | "body" | "button" | "canvas" | "caption" | "cite" | "code" | "colgroup" | "data" | "datalist" | "dd" | "del" | "details" | "dfn" | "dialog" | "div" | "dl" | "dt" | "em" | "fieldset" | "figcaption" | "figure" | "footer" | "form" | "h1" | "h2" | "h3" | "h4" | "h5" | "h6" | "head" | "header" | "html" | "i" | "iframe" | "ins" | "kbd" | "label" | "legend" | "li" | "main" | "map" | "mark" | "meter" | "nav" | "noscript" | "object" | "ol" | "optgroup" | "option" | "output" | "p" | "picture" | "pre" | "progress" | "q" | "ruby" | "rb" | "rt" | "rtc" | "rp" | "s" | "samp" | "script" | "section" | "select" | "small" | "span" | "strong" | "style" | "sub" | "summary" | "sup" | "table" | "tbody" | "td" | "template" | "textarea" | "tfoot" | "th" | "thead" | "time" | "title" | "tr" | "track" | "u" | "ul" | "var" | "video" <empty_tag_name> = "area" | "base" | "br" | "col" | "embed" | "hr" | "img" | "input" | "link" | "menuitem" | "meta" | "param" | "source" | "track" | "wbr" (* attributes *) <attributes_list> = <ws> {<ws>} <attribute> {<ws> {<ws>} <attribute>} <attribute> = <empty_attribute> | <unquoted_attribute> | <single_quoted_attribute> | <double_quoted_attribute> <empty_attribute> = <attribute_name> <unquoted_attribute> = <attribute_name> {<ws>} "=" {<ws>} <unquoted_attribute_value> <single_quoted_attribute> = <attribute_name> {<ws>} "=" {<ws>} "'" <single_quoted_attribute_value> "'" <double_quoted_attribute> = <attribute_name> {<ws>} "=" {<ws>} "\"" <double_quoted_attribute_value> "\"" <attribute_name> = (<letter> | <digit>) {<letter> | <digit>} {* attribute values *) <unquoted_attribute_value> = /^[\s"'=<>/]/ {/^[\s"'=<>/]/} <single_quoted_attribute_value> = /^[']/ {/^[']/} <double_quoted_attribute_value> = /^["]/ {/^["]/} (* nonterminals *) <text> = {/^[<>]/} <comment_text> = ... <macro_text> = ... <letter> = /[a-zA-Z]/ <digit> = /[0-9]/ <ws> = " " | "\t" | "\n" (* terminals *) "<", ">", "/", "!", "?", " ", "\t", "\n" 

Ketika tata bahasa sudah siap, Anda dapat melanjutkan ke penganalisa leksikal (nama lain untuk pengurai leksikal, karena selain penguraian, ini mengidentifikasi kesalahan leksikal dalam dokumen). Pada pandangan pertama, semuanya sederhana: menyerap karakter, menulis ke buffer, dan ketika terminal kunci terdeteksi, tentukan token yang diterima sebagai token dengan jenis tertentu, bukan? Ya, hanya jenis token di sini yang lebih penting daripada simbol. Saya akan jelaskan sekarang. Tentu saja, prosedur membongkar (ifsteam & file) harus berisi loop yang membaca satu karakter dari aliran input dan mengirimkannya ke prosedur proses (const char & c), di mana karakter ini diproses. Tampaknya prosedur proses harus berisi sakelar ©, di mana setiap simbol kunci memiliki fungsinya sendiri, tergantung pada jenis token saat ini. Faktanya, yang terjadi adalah sebaliknya: lebih baik menggunakan sakelar untuk memeriksa jenis token, dan menentukan fungsi untuk karakter. Selain itu, token saat ini paling sering memiliki jenis yang tidak terbatas, salah satunya. Misalnya, setelah membuka braket sudut, Anda dapat melihat: membuka, menutup, mengosongkan tag, serta komentar gaya HTML atau tag makro (skrip PHP terlampir dalam "<? ...?>". Dan untuk semua serikat pekerja seperti itu, Anda memerlukan kasing sendiri. Bagaimana ini implement? Menggunakan bit flags. Biarkan sejumlah jenis token diberikan (semakin banyak semakin baik, karena tugas penganalisa leksikal adalah meninggalkan sesedikit mungkin pekerjaan ke sintaks). Untuk masing-masing jenis, jumlah unik derajat dua diberikan (1, 2, 4, 8 dll.) Kemudian dalam format biner mereka akan terlihat seperti ini: 0001, 0010, 0 100, dll, dan dengan penambahan bitwise dari jumlah jenis apa pun, nomor unik akan diperoleh.Jika deskripsi teks sulit dipahami, saya akan memberikan kode. Berikut adalah definisi jenis:

 enum Token_type { END = 1, TEXT = 2, OPENING_BLOCK_TAG_NAME = 4, CLOSING_BLOCK_TAG_NAME = 8, EMPTY_TAG_NAME = 16, COMMENT = 32, MACRO_TAG = 64, ATTRIBUTE_NAME = 128, UNQUOTED_ATTRIBUTE_VALUE = 256, SINGLE_QUOTED_ATTRIBUTE_VALUE = 512, DOUBLE_QUOTED_ATTRIBUTE_VALUE = 1024 }; 

Proses prosedur terpotong:

 void Lexer::process (const char &c) { switch (curr_token_type) { case END: { throw string("unexpected ending!"); break; } case TEXT: { if (c == '>') throw string("unexpected symbol: \">\"!"); else if (c == '<') { if (!buffer.empty()) { add(buffer, TEXT); buffer.clear(); } curr_token_type = OPENING_BLOCK_TAG_NAME | CLOSING_BLOCK_TAG_NAME | EMPTY_TAG_NAME | COMMENT | MACRO_TAG; } else buffer.push_back(c); break; } case OPENING_BLOCK_TAG_NAME: { throw string("error!"); break; } case CLOSING_BLOCK_TAG_NAME: { if (c == '<') throw string("unexpected symbol: \"<\"!"); else if (c == '/') throw string("unexpected symbol: \"<\"!"); else if (c == '!') throw string("unexpected symbol: \"!\"!"); else if (c == '?') throw string("unexpected symbol: \"?\"!"); else if (c == ' ') throw string("unexpected symbol: \" \"!"); else if (c == '\t') throw string("unexpected symbol: \"\\t\"!"); else if (c == '\n') throw string("unexpected symbol: \"\\n\"!"); else if (c == '>') { for (unsigned int i(0); i < BLOCK_TAGS_COUNT; i++) if (buffer == block_tags[i]) { add(buffer, CLOSING_BLOCK_TAG_NAME); buffer.clear(); curr_token_type = TEXT; break; } } else buffer.push_back(c); break; } case EMPTY_TAG_NAME: { throw string("error!"); break; } case COMMENT: { ... break; } case MACRO_TAG: { ... break; } case OPENING_BLOCK_TAG_NAME | CLOSING_BLOCK_TAG_NAME | EMPTY_TAG_NAME | COMMENT | MACRO_TAG: { ... break; } case EMPTY_TAG_NAME | COMMENT: { ... break; } case ATTRIBUTE_NAME: { ... break; } case ATTRIBUTE_NAME | UNQUOTED_ATTRIBUTE_VALUE | SINGLE_QUOTED_ATTRIBUTE_VALUE | DOUBLE_QUOTED_ATTRIBUTE_VALUE: { ... break; } case UNQUOTED_ATTRIBUTE_VALUE | SINGLE_QUOTED_ATTRIBUTE_VALUE | DOUBLE_QUOTED_ATTRIBUTE_VALUE: { ... break; } case UNQUOTED_ATTRIBUTE_VALUE: { ... break; } case SINGLE_QUOTED_ATTRIBUTE_VALUE: { ... break; } case DOUBLE_QUOTED_ATTRIBUTE_VALUE: { ... break; } } } 

Kami memeriksa dengan saklar jenis token yang diharapkan (atau token), dan di dalam setiap kasus kami menentukan prosedur untuk masing-masing terminal utama. Tidak ada banyak fungsi, semua orang melakukan tindakan sederhana: baik menambahkan karakter ke buffer, atau membuang buffer ke token berikutnya, atau mengubah jenis token yang diharapkan, atau melempar pengecualian. Sangat mudah untuk menentukan prosedur yang diinginkan menggunakan tata bahasa yang ditulis di atas menggunakan editor teks yang dapat dicari. Cari saja semua inklusi dari token yang diharapkan (token) dalam definisi ekspresi lain, kemudian dimasukkannya ekspresi ini dalam "ketiga", dll. Berikut ini contoh untuk tag pembuka di editor teks gedit:



Pada awalnya, menavigasi tata bahasa itu sulit, tetapi seiring waktu dan pengalaman, itu menjadi tidak lebih rumit daripada membagi kolom. Dan di sini adalah prosedur membongkar:

 void Lexer::disassemble (ifstream &file) { tokens_count = 0; curr_token_type = 0; unsigned long line(1), pos(1); try { char c; curr_token_type = TEXT; while ((c = file.get()) != EOF) { if (c == '\n') { pos = 1; line++; } else pos++; process(c); } if (buffer.size() != 0) { if (!(curr_token_type | TEXT)) throw string("text was expected!"); add(buffer, TEXT); buffer.clear(); } add("", END); } catch (const string &error) { throw string("lexer: " + to_string(line) + "," + to_string(pos) + ": " + error); } } 

Token yang diharapkan pertama jelas diperlukan untuk mengatur tipe ke TEXT, dan pada akhirnya tambahkan token tipe END dengan teks apa pun (atau kosong, seperti di sini).

Sebagai contoh, saya mengambil salah satu templat dokumen HTML saya dengan komentar, menambahkan skrip pseudo-PHP ke dalamnya, memprosesnya dengan lexer, dan menampilkan daftar token dalam format "[" <token_text> ": <token_type>]". Inilah yang terjadi:



Sekarang kita siap untuk memulai bagian kedua - pembangunan pohon sintaks. Karena tag kami memiliki atribut, simpul pohon, selain komunikasi dengan simpul lain, akan berisi larik pasangan nilai kunci. Konstruksi yang dihasilkan dapat secara tepat disebut model objek dokumen DOM yang disebutkan dalam judul artikel.

Berapa banyak kelas yang Anda butuhkan untuk mengimplementasikan semua properti elemen HTML?

Idealnya, ada satu kelas untuk setiap elemen sehingga lembar gaya kaskade dapat didefinisikan untuk mereka, tetapi kami akan membatasi diri kami menjadi tiga - tag "Node" kosong, sebuah blok "Blok" yang diwariskan (konten terlampir di antara dua tag berpasangan) dan diwarisi dari dia dengan akar pohon Root. Kami juga mendefinisikan dalam parser sebuah array tag yang mungkin berisi teks, seperti <p>, <li>, <strong>, dll., Untuk menghilangkan token dengan teks yang tidak ditempatkan. Sekarang terserah kecil. Jika Anda telah bekerja dengan baik pada penganalisis leksikal, maka tugas sintaksis hanyalah untuk menyerap token dan melakukan salah satu dari tiga operasi di simpul terbuka: tambahkan simpul kosong ke dalamnya, buka yang baru atau tutup dengan mengembalikan pointer ke induk. Untuk yang terakhir, diperlukan bahwa semua kelas, dimulai dengan basis Node, mengandung pointer yang diperoleh saat membuat elemen. Proses ini disebut penguraian top-down .

Prosedur Parsing:

 void Parser::parse (const Lexer &lexer) { Block * open_block = (Block*) tree; Node * last_node = (Node*) tree; try { unsigned long long size = lexer.count(); for (unsigned long long i(0); i < size-2; i++) { switch (lexer[i].type) { case Lexer::TEXT: { for (unsigned int j(0); j < TEXT_TAGS_COUNT; j++) if (open_block->get_name() == text_tags[j]) last_node = open_block->add("TEXT", lexer[i].lexeme); break; } case Lexer::OPENING_BLOCK_TAG_NAME: { last_node = open_block = open_block->open(lexer[i].lexeme); break; } case Lexer::CLOSING_BLOCK_TAG_NAME: { if (lexer[i].lexeme != open_block->get_name()) throw string("unexpected closing tag: </" + lexer[i].lexeme + ">"); open_block = open_block->close(); break; } case Lexer::EMPTY_TAG_NAME: { last_node = open_block->add(lexer[i].lexeme); break; } case Lexer::COMMENT: { last_node = open_block->add("COMMENT", lexer[i].lexeme); break; } case Lexer::MACRO_TAG: { last_node = open_block->add("MACRO", lexer[i].lexeme); break; } case Lexer::ATTRIBUTE_NAME: { last_node->add_attr(lexer[i].lexeme, lexer[i].lexeme); break; } case Lexer::UNQUOTED_ATTRIBUTE_VALUE: { last_node->set_last_attr(lexer[i].lexeme); break; } case Lexer::SINGLE_QUOTED_ATTRIBUTE_VALUE: { last_node->set_last_attr(lexer[i].lexeme); break; } case Lexer::DOUBLE_QUOTED_ATTRIBUTE_VALUE: { last_node->set_last_attr(lexer[i].lexeme); break; } case Lexer::END: { if (open_block->get_type() != Node::ROOT) throw string("unexpected ending!"); open_block->close(); } } } } catch (const string &error) { throw string("parser: " + error); } } 

Itu saja! Jika Anda melakukan semuanya dengan benar, pohon yang dihasilkan dapat ditampilkan:

 | 
 + - <ROOT>
   | 
   + - <! DOCTYPE>
   | 
   + - <html>
     | 
     + - <head>
     |  | 
     |  + - <meta>
     |  | 
     |  + - <meta>
     |  | 
     |  + - <meta>
     |  | 
     |  + - <meta>
     |  | 
     |  + - <meta>
     |  | 
     |  + - <meta>
     |  | 
     |  + - <meta>
     |  | 
     |  + - <meta>
     |  | 
     |  + - <meta>
     |  | 
     |  + - <title>
     |  | 
     |  + - <link>
     |  | 
     |  + - <link>
     |  | 
     |  + - <COMMENT>
     | 
     + - <body>
       | 
       + - <header>
       |  | 
       |  + - <div>
       | 
       + - <nav>
       |  | 
       |  + - <ul>
       |  | 
       |  + - <li>
       |  |  | 
       |  |  + - <a>
       |  | 
       |  + - <li>
       |  |  | 
       |  |  + - <a>
       |  | 
       |  + - <li>
       |  | 
       |  + - <a>
       | 
       + - <main>
       |  | 
       |  + - <MACRO>
       | 
       + - <footer>
         | 
         + - <hr>
         | 
         + - <small>

Namun, meskipun pohon yang dihasilkan benar-benar dapat disebut DOM, parser kami jauh dari jQuery, Jsoup, beautifulsoup atau Gumbo, khususnya karena tidak dapat memproses teks yang terletak dengan benar di antara tag <style> dan <script> yang dipasangkan, dan oleh karena itu sumbernya sampai aku membawanya. Tapi saya pasti akan menambahkan jika penduduk Habrovsk menyatakan keinginan seperti itu. Berhasil.

PS Diisi kode sumber dalam akses publik. IMHO, mentah, jadi saya akan merencanakan ke perpustakaan penuh.

PSS Bagian kedua.