ne ada, top-down parsing

top-down parsing
parsing top-down merupakan strategi untuk menganalisa hubungan unknown data dengan hipotesis struktur umum parse tree dan kemudian mempertimbangkan apakah struktur foundamental yang dikenal kompatibel dengan hipotesisnya. hal ini terjadi pada analisa dari natural languages dan komputer languages.

parsing top-down dapat dilihat sebagai upaya untuk menemukan leftmost derivasi dari aliran input dengan cara mencari parse tree menggunakan perluasan top-down dari aturan tata bahasa formal yang diberikan. token token dianalisa dari kiri ke kanan. pilihan inklusif digunakan untuk menampung ambiguitas dengan memperluas semua alternatif right hand sides dari aturan tata bahasa.

implementasi sederhana dari top down parsing tidak menghentikan tata bahasa left recursve, dan top down parsing backtraking kompleksitas waktu eksponensial yang berhubungan dengan panjangnya input yang ambigu.


aplikasi bahasa pemrograman
sebuah kompiler mem-parsing input daro bahasa pemrograman ke bahasa assembly atau representasi internal dengan cara mencocokkan simbol yang masuk ke aturan produksi bentuk backus-naur. sebuah LL parser juga disebut top-bottom parser atau top-down parser, berlaku pada setiap aturan prduksi pada simbol simbol yang masuk dengan mengerjakannya dari leftmost symbol yang dihasilkan pada aturan produksi dan kemudian di proses ke aturan priduksi berikutnya untuk setiap simbil non termunal yang ditemui. dengan cara ini parsing mulai dari kiri dari sisi hasil (sisi kanan) aturan produksi dan mengevaluasi susunan non terminal dari kiri dulu dan dengan demikian proses turunnya parse tree untuk setiap non terminal baru sebelum melanjutkan ke simbol berikutnya untuk aturan produksi.

sebagai contoh;
    * A \ rightarrow aBC
    * B \ rightarrow c | cd
    * C \ rightarrow df | eg
akan mencocokkan A \ rightarrow aBC dan akan kemudian mencoba mencocokkan B \ rightarrow c | cd lalu akan mencoba C \ rightarrow df | eg. sebagai salah satu bisa berharap bahwa beberapa bahasa lebih ambigu dibanding yang lainnya. untuk bahasa yang tidak ambigu dalam semua produksi non terminal menghasilkan string yang berbeda; string yang dihasilkan oleh salah satu produksi tidak akan mulai dengan simbol yang sama pada produksi yang lain. bahasa yang tidak ambigu bisa di parsing dengan tata bahasa LL dimana menandakan bahwa parser membaca satu token pada satu waktu. untuk bahasa ambigu jika di parse dengan parser LL, maka parser harus membacanya lebih dari satu simbol.

solusi umum adalah dengan menggunakan LR parser (juga biasa disebut sebagai bottom up, atau shift reduce parser).

menampung rekursi kiri pada top-down parsing

tata bahasa formal yang mengandung rekursi kiri tidal bisa di parsing dengan turunan parser rekursif standar kecuali jika di konversi ke bentuk yang sama lemah pada rekursif kanan. namun penelitian terbaru menunjukkan bahwa ada kemungkinan untuk menampung tata bahasa rekursif kiri (bersama dengan segala bentuk lain dari CFGs umum) dalam parser top-down yang lebih canggih dengan menggunakan pembatasan. sebuah pengakuan algoritma dimana menampung tata bahasa ambigu dan membatasi perkembangan langsung parser left rekursif dengan menerapkan kedalaman pembatasan pada panjang dan posisi input saat ini, telah digambarkan oleh Frost dan Hafiz pada 2006. algoritma itu telah diperpanjang untuk melengkapi algoritma parsing untuk menampung secara tidak langsung (dengan membandingkan konteks komputerisasi sebelumnya dengan konteks sekarang) sebagaimana baiknya dengan left rekursif pada waktu polinomial secara langsung, dan untuk menghasilkan tampilan ukuran padat pada ukuran polinomial dari potensi angka eksponen dari parse tree untuk tingkat keambiguan yang sangat tinggi, oleh Frost, Hafiz dan callagham pada 2007. algoritma telah diimplementasikan sebagai satu kelengkapan parser kombinator sejak saat itu dan kemudian ditulis dalam bahasa pemrigraman Haskel.

waktu dan kompleksitas ruang dari top-down parsing
pada saat top-down parser mencoba untuk memparsing input ambigu berkenaan dengan suatu CFG ambigu  mungkin ini membutuhkan nomor exponensial dari suatu cara untuk mencoba semua alternatif dari CFG dalam rangka untuk menghasilkan semua kemungkinan parse tree, yang pada akhrnya akan membutuhkan ruang memori eksponensial. masalah dari kompleksitas waktu eksponensial pada top-down parser dibangun sebagai set fungsi saling rekursif telah dipecahkan oleh Norvig 1991. tekniknya sama dengan penggunaan programming dinamis dan serupa dengan algoritma Earleys (1970).
ide utamanya adalah untuk menyimpan hasil dari penerapan parser p pada posisi j dalam data dan untuk menggunakan kembali hasil setiap kali situasi yang sama muncul. Frost, Hafiz, dan callagham juga menggunakan pengenal data untuk menahan kelipatan data berkomputer untuk menampung berbagai macam CFG pada waktu polinomial. (untuk tata bahasa rekkursif left rekuesif dan non left rekursif). algoritma parsing mereka juga membutuhkan ruang polinomial untuk kemungkinan adanya parse tree eksponensial ambigu tampilan padat dan pengelompokan ambiguitas local, Representasi padat mereka sebanding dengan representasi padat Tomita tentang parsing bottom-up

0 komentar:

Posting Komentar