I Am { Robi Sahputra }

Parser

Dalam ilmu komputer dan linguistik , parsing, atau lebih formal disebut analisis sintaksis, adalah proses menganalisis teks, terbuat dari urutan token (misalnya, kata-kata), untuk menentukan struktur gramatikal terhadap hal yang diberikan (lebih atau kurang) tata bahasa formal . Parsing juga merupakan istilah awal untuk diagram kalimat dari bahasa alam , dan masih digunakan untuk diagram dari infleksi bahasa, seperti bahasa Romance atau Latin .
Dalam komputasi, parser adalah salah satu komponen dalam sebuah interpreter atau kompiler , yang memeriksa sintaks yang benar dan membangun struktur data (sering beberapa jenis pohon parse , pohon sintaks abstrak atau struktur hirarkis lainnya) tersirat dalam token masukan. Program pendeteksi kombinasi tombol sering menggunakan yang terpisah penganalisa leksikal untuk membuat token dari urutan karakter masukan. Parser dapat diprogram dengan tangan atau mungkin (semi-) otomatis dihasilkan (dalam beberapa bahasa pemrograman) dengan alat (seperti Yacc ) dari tata bahasa yang ditulis dalam bentuk Backus-Naur .
Dalam beberapa terjemahan mesin dan bahasa alami pengolahan sistem, bahasa manusia parsing oleh program komputer.kalimat Manusia tidak mudah diurai oleh program, karena ada substansial ambiguitas di struktur bahasa manusia, yang penggunaannya untuk menyampaikan makna (atau semantik ) di antara rentang terbatas berpotensi kemungkinan tetapi hanya beberapa yang erat dengan kasus tertentu.
Untuk mengurai data bahasa alami, peneliti pertama harus setuju pada tata bahasa untuk digunakan. Pemilihan sintaks dipengaruhi oleh linguistik dan komputasi perhatian, misalnya beberapa sistem parsing menggunakan tata bahasa fungsional leksikal , tetapi secara umum, parsing untuk tata bahasa jenis ini dikenal sebagai NP-lengkap . Kepala berbasis frase struktur tata bahasa linguistik lain formalisme yang telah populer di masyarakat parsing, namun upaya penelitian lain telah terfokus pada formalisms kurang kompleks seperti yang digunakan dalam Penn Treebank . parsing Dangkal hanya bertujuan untuk menemukan batas dari unsur utama seperti frasa nominal. Strategi lain yang populer untuk menghindari kontroversi linguistik adalah ketergantungan tata bahasa parsing.
Sebagian parser modern setidaknya sebagian statistik , yaitu, mereka bergantung pada korpus data pelatihan yang telah dijelaskan (parsing dengan tangan). Pendekatan ini memungkinkan sistem untuk mengumpulkan informasi tentang frekuensi yang berbagai konstruksi terjadi dalam konteks tertentu Lihat. ( mesin belajar .) Pendekatan yang telah digunakan termasuk mudah PCFGs (probabilistik tata bahasa bebas konteks), entropi maksimum , dan jaringan syaraf . Sebagian besar sistem yang lebih sukses menggunakan statistik leksikal (yaitu, mereka mempertimbangkan identitas kata-kata yang terlibat, serta mereka bagian dari pidato ). Namun sistem ini rentan terhadap overfitting dan membutuhkan beberapa jenis smoothing efektif.
Parsing algoritma untuk bahasa alam tidak bisa mengandalkan pada tata bahasa memiliki 'baik' properti sebagai dengan tata bahasa secara manual dirancang untuk bahasa pemrograman. Seperti yang disebutkan sebelumnya beberapa formalisms tata bahasa sangat sulit untuk mengurai komputasi, secara umum, bahkan jika struktur yang diinginkan tidak bebas konteks , semacam aproksimasi bebas konteks untuk tata bahasa digunakan untuk melakukan lulus pertama. Algoritma yang menggunakan tata bahasa bebas konteks seringkali bergantung pada beberapa varian dari algoritma CKY , biasanya dengan beberapa heuristik untuk memangkas pergi analisis tidak mungkin untuk menghemat waktu Lihat. ( parsing grafik .) Namun beberapa sistem perdagangan kecepatan untuk akurasi menggunakan, misalnya, linear-time versi mengurangi pergeseran- algoritma. Sebuah perkembangan yang agak baru-baru ini telah reranking mengurai di mana parser mengusulkan beberapa sejumlah besar analisis, dan kompleks sistem yang lebih memilih pilihan terbaik.
Bahasa Pemrograman
Yang umum menggunakan sebagian besar parser adalah sebagai komponen dari suatu compiler atau interpreter . Hal ini mem-parsing kode sumber dari bahasa pemrograman komputer untuk membuat beberapa bentuk representasi internal.Bahasa Pemrograman cenderung akan ditentukan dalam istilah dari tata bahasa bebas konteks karena cepat dan efisien parser dapat ditulis untuk mereka . Parser yang ditulis oleh tangan atau yang dihasilkan oleh generator parser .
Konteks tata bahasa bebas terbatas sejauh mana mereka bisa mengekspresikan semua persyaratan dari sebuah bahasa.. Informal, alasannya adalah bahwa memori seperti bahasa terbatas. tata bahasa tidak dapat mengingat keberadaan membangun atas masukan sewenang-wenang panjang; ini diperlukan suatu bahasa yang, misalnya, nama harus dinyatakan sebelum dapat dirujuk.. tata bahasa kuat lainnya yang dapat mengungkapkan kendala ini, bagaimanapun, tidak bisa diurai efisien.. Oleh karena itu, strategi umum untuk membuat parser santai untuk tata bahasa bebas konteks yang menerima superset dari bahasa yang dikehendaki konstruksi (yaitu, ia menerima beberapa konstruksi tidak valid), kemudian, konstruksi yang tidak diinginkan dapat disaring.






Sekilas proses

Contoh berikut menunjukkan kasus umum dari penguraian sebuah bahasa komputer dengan dua tingkat tata bahasa: leksikal dan sintaksis.
Tahap pertama adalah generasi token, atau analisis leksikal , di mana aliran input karakter dibagi menjadi simbol bermakna yang didefinisikan oleh tata bahasa dari kalimat biasa . Sebagai contoh, sebuah program kalkulator akan melihat masukan seperti " 12*(3+4)^2 "dan membagi ke dalam token 12 , * , ( , 3 , + , 4 , ) , ^ dan 2 , masing-masing yang merupakan sebuah simbol yang bermakna dalam konteks ekspresi aritmatika. lexer itu akan berisi aturan untuk mengatakan bahwa karakter * , + , ^ , ( dan ) menandai awal dari sebuah token baru, berarti tanda jadi seperti " 12* "atau" (3 "tidak akan dihasilkan.
Tahap berikutnya adalah parsing atau analisa sintaksis , yang memeriksa bahwa bentuk ekspresi token yang diijinkan. Hal ini biasanya dilakukan dengan mengacu pada tata bahasa bebas konteks yang secara rekursif mendefinisikan komponen yang dapat membuat ekspresi dan urutan di mana mereka harus muncul. Namun, tidak semua aturan menentukan bahasa pemrograman dapat dinyatakan dengan tata bahasa bebas konteks saja, untuk jenis validitas dan deklarasi yang tepat contoh pengenal. Aturan-aturan ini dapat dinyatakan secara resmi dengan tata bahasa atribut .
Tahap akhir adalah semantik parsing atau analisis, yang bekerja di luar implikasi dari ungkapan hanya disahkan dan mengambil tindakan yang tepat. Dalam kasus kalkulator atau interpreter, tindakan ini adalah untuk mengevaluasi ekspresi atau program, compiler, di sisi lain, akan menghasilkan semacam kode. Atribut tata bahasa juga dapat digunakan untuk mendefinisikan tindakan tersebut.
Jenis dari parser
Tugas parser pada dasarnya adalah untuk menentukan apakah dan bagaimana input dapat diturunkan dari simbol awal tata bahasa. Hal ini dapat dilakukan pada dasarnya dua cara:
· Top-down parsing - Top-down parsing dapat dilihat sebagai upaya untuk menemukan kiri-derivasi sebagian besar aliran-masukan dengan mencari pohon parse menggunakan-down ekspansi yang diberikan atas tata bahasa formal aturan. Inklusif pilihan digunakan untuk mengakomodasi ambiguitas dengan memperluas semua alternatif tangan kanan-sisi aturan tata bahasa.
· Bottom-up parsing - parser A dapat memulai dengan masukan dan berusaha untuk menulis ulang ke simbol awal. Intuitif, parser upaya untuk menemukan elemen paling dasar, maka unsur-unsur yang mengandung, dan seterusnya. parser LR adalah contoh-up parser bawah. Istilah lain yang digunakan untuk jenis parser ini Shift-Mengurangi parsing.
Parser LL dan keturunan-parser recursive adalah contoh dari top-down parser yang tidak dapat mengakomodasi rekursif kiri produksi. Meskipun telah percaya bahwa implementasi sederhana-down parsing atas tidak dapat mengakomodasi langsung dan tidak langsung kiri rekursi dan mungkin memerlukan waktu eksponensial dan kompleksitas ruang sementara parsing ambigu -bebas tata bahasa konteks , canggih algoritma lebih untuk-down parsing atas telah diciptakan oleh Frost , Hafiz, dan Callaghan yang mengakomodasi ambiguitas dan rekursi kiri dalam waktu polinomial dan yang menghasilkan ukuran representasi polinom-eksponensial dari jumlah potensial pohon parse. algoritma mereka mampu menghasilkan paling baik kiri-dan-yang paling derivasi kanan input sehubungan dengan diberikan CFG .
Sebuah perbedaan penting sehubungan dengan parser adalah apakah sebuah parser menghasilkan derivasi paling kiri atau paling kanan derivasi (lihat tata bahasa bebas konteks ). LL parser akan menghasilkan paling kiri derivasi dan parser LR akan menghasilkan paling kanan derivasi (walaupun biasanya secara terbalik).