yang belajar parsing

parsing
dalam ilmu komputer dan linguistik, parsing, atau lebih formalnya di sebut syntactic analysis, adalah proses menganalisa text yang tersusun dari urutan token (sebagai contohnya, kata kata). untuk menentukan apakah struktur gramatikal yang digunakan (lebih atau kurang) memenuhi grammar formal (tepat).parsing juga dapat digunakan sebagai istilah linguistik, terutama dalam kaitannya pada bagaimana frase dibagi dalam kalaimat 'garden path'.
parsing juga merupakan istilah awal untuk 'diagraming of sentences of natural language, dan masih digunakan untuk diagraming of inflected languages, seperti bahasa bahasa roman atau latin. istilah parsing berasal dari pars latin (ōrātiōnis), yang berarti bagian (dari tumpukan kalimat kalimat).
parsing adalah istilah yang umum digunakan dalam psikolinguistik saat menjelaskan pemahaman bahasa, dalam konteks ini parsing mengacu pada bagaimana cara penyampaian manusia, bukan komputer, menganalisa suatu kalimat atau frase (dalam bahasa lisan ataupun text) "dalam istilah konstituen gramatikal, mengidentifikasi bagian bagian dari kata kata, hubungan sintaksis, dll", istilah ini sangat umum saat membahas apakah isyarat linguistik membatu seseorang untuk mem-parse kalimat garden path.

parser
dalam komputasi,parser adalah salah satu komponen dalam interpreter atau kompiler, dimana cara kerjanya adalah mengecek syintak yang benar dan membangun struktur data (seringnya berupa parse tree, pohon sintax abstrak atau struktur hierarki lainnya) yang tersirat dalam input token. parser sering menggunakan penganalisis leksikal terpisah untuk membuat token dari urutan input karakter. parsing dapat diprogram dengan tangan atau mungkin (semi-) pen-generate otomatis (pada beberapa bahasa pemrograman) dengan bantuan tool.

human languages
dalam beberapa penterjemah mesin dan sistem pengolah bahasa alami, bahasa manusia diuraikan dalam program komputer. kalimat kalimat manusia tidak bisa dengan mudah diurailan oleh program, karena ada ambiguitas substansial dalam bahasa manusia, yang penggunaannya adalah untuk menyampaikan makna (atau semantik) diantara berbagai kemungkinan berpotensi tak terbatas tapi hanya beberapa yang erat dengan kasus tertentu. jadi ucapan "man bites dog" vs "dog bites man" adalah memiliki makna yang sama, tapi dalam bahasa lain memiliki kemungkinan akan diucapkan dengan "man dog is bitting" dengan ketergantungan yang lebih besar untuk membedakan antara dua kemungkinan, jika memang perbedaan menjadi perhatian. ini sangat sulit untuk mempersiapkan aturan formal untuk mendeskripsikan prilaku informal walaupun ini sangar jelas bahwa beberapa peraturan sedang digunakan.

dalam rangka untuk mengurai data bahasa alami, pertama tama para peneliti harus setuju pada grammar yang akan digunakan. pemilihan sintax sangatlah dipengaruhi oleh linguistik dan komputasi, misalnya beberapa sistem parsing menggunakan tata bahasa fungsional leksikal, tapi secara umum, parsing untuk tata bahasa jenis ini dikenal sebagai NP-lengkap. frase struktur grammar head-driven adalah linguistik formal lain yang telah populer dikalangan parsing community, namun upaya penelitian lain telah berfokus pada formalisms kurang komplek seperti yang digunakan dalam "penn treebank".parsing dangkal hanya bertujuan untuk menemukan batas batas konstituen besar seperti frase nomina. strategi populer lain untuk menghindari kontroversi linguistik adalah dengan ketergantungan grammar parsing.

parsing paling modern paling tidak berbagian statistik, yaitu mereka bergantung pada bagian pelatihan data yang telah dianotasi (parsed by hand). pendekatan ini memungkinkan sistem untuk mengumpulkan informasi tentang berbagai konstruksi yang terjadi dalam kontek tertentu. pendekatan yang telah digunakan termasuk PCFGs (probabilistic context free grammars), entropi maksimumm, dan jaring syaraf.sebagian sistem yang lebih sukses menggunakan sistem leksikal (yaitu mereka mempertimbangkan identitas dari kata kata yang terlibat, sebagai mana bagian dari kata kata mereka). bagaimanapun juga sistem semacam itu itu lemah untuk lebih pas dan membutuhkan sejenis pelembutan agar bisa efektif.

algoritma parsing untuk bahasa natural tidak bisa mengandalkan pada tata bahasa yang memiliki properti yang menarik sebagaimana tata bahasa pemrograman dengan tata bahasa desain manual. sebagaimana telah dijelaskan sebelumnya bahwa beberapa grammar formalisme sangat sulit untuk mem-parse (mengurai) secara komputerisasi, secara umum bahkan jika struktur yang diinginkan tidak ber-konteks bebas, beberapa jenis pendekatan konteks bebas untuk tata bahasa digunakan untuk menampilkan "a first pass". algoritma yang menggunakan contex-free grammars sering bergantung pada beberapa varian algoritma CKY, bisannya dengan semacam heuristik untung mengurangi analisis kurang tepat untuk menghemat waktu.

programming language
penggunaan parsing paling umum adalah sebagai komponen kompiler dan interpreter. bagian ini menguraikan source code dari bahasa pemrograman komputer untuk menciptakan beberapa bentuk dari representasi internal. bahasa pemrograman cenderung di spesifikasikan kedalam tata bahasa contex free karena parsing yang cepat dan efisien dapat dituliskan disitu. parses dapat ditulis tangan atau di generate melalui parser generator.

tata bahasa contex free dibatasi pada seberapa jauh mereka bisa mengekspresikan semua persyaratan bahasa. informally, alasannya adalah bahwa memory untuk bahasa semacam itu terbatas. tatabahasa tidak dapat mengingat adanya susunan melebihi batas maksimal input, hal ini penting untuk bahasa tersebut, sebagai contoh, sebuah nama harus dideklarasikan dahulu sebelum digunakan sebagai reference. tata bahasa yang lebih kuat yang bisa mengekspresikan masalah batasan ini, bagaimanapun jg tidak dapat di parse secara efisien. dengan demikian ini adalah strategi umum untuk menciptakan a relaxed parser untuk tata bahasa context free yang menerima superset dari pembagun bahasa yang diinginkan (yaitu dimana ini menerima kontruksi yang tidak valid) kemudian konstruksi yang tidak diingikan dapat di saring.

overview of process
contoh berikut mendemonstrasikan masalah umum dari parsing bahasa komputer dengan 2 level grammar, lexical dan syntatic.

tahap pertama adalah token generation, atau lexical analysis, dimana stream input karakter dibagi menjadi simbol simbol yang bermakna yang didefinisikan oleh tata bahasa ekpresi reguler. sebagai contoh sebuah program kalkulator akan malihat input seperti "12*(3+4)^2" dan memecahnya pada token 12,*,(,3,+,4,),^, dan 2, masing masing tersebut adalah symbol yang sangat bermakna pada konteks ekpresi aritmatika. undang undang ini akan berisi aturan atuaran untuk memberitahukan hal tersebut bahwa karakter *,+,^,(, dan ) menandai dimulainnya token baru, jadi tanda tak bermakna seperti "12*" atau "(3" tidak akan sihasilkan.

tahap berikutnya adalah parsing atau syntactic analysis, yang akan mengecek bahwa token token tersebut adalah ekpresi yang diijinkan. hal ini bisannya dilakukan dengan acuan tata bahasa contex free secara rekursif mendefinisikan komponen yang mampu menyusun ekpresi dan mengurutkan mana yang harus muncul. bagamanapun juga tidak semua peraturan mendefinisikan bahasa pemrograman dapat dinyatakan dengan tata bahasa context free saja, sebagai contoh type validitas dan pendeklarasian identitas yang tepat. aturan aturan tersebut dapat secara resmi dinyatakan dengan atribut tata bahasa.

tahap terakhir adalah semantic parsing atau analysis, yang bekerja diluar implikasi dari ekspresion yang baru divalidasi dan mengambil tindakan yang sesuai. dalam kasus kalkulator atau interpreter, tindakan ini adalah untuk mengavaluasi ekpresi atau program, sebuah kompiler pada sisi lain akan menghasilkan semacam kode.atribut tata bahasa juga dapat digunakan untuk mendefinisikan tindakan tindakan ini.


types of parser
tugas parser pada dasarnya adalah untuk menentukan apakah dan bagaimana input dapat diturunkan dari simbol awal tata bahasa. hal ini dapat diselesaikan pada dasarnya dalam 2 cara:

topdown parsing
topdown parsing dapat dilihat sebagai upaya untuk menemukan left-most derivasi dari aliran input dengan mencari parse tree menggunakan perluasan topdown dari aturan tata bahasa formal yang telah diberikan. token token di analisa dari kiri ke kanan, bagian bagian yang dipilih digunakan untuk menampung ambiguitas dengan memperluas semua alternatif right-hand-sides dari aturan tatabahasa.
buttom-up parsing
sebuah parser dapat dimulai dengan input dan mencoba untuk menulis ulang ke simbol awal. intuitively, parser mencoba menemukan elemen paling dasar, kemudian elemen elemen yang mengandung hal hal tersebut, dan seterusnya. LR parser adalah contoh dari buttom up parser,istilah lain yang digunakan untuk parser jenis ini adalah shift reducing parsing.

LL parser dan recursive-descent parser adalah contoh dari top down parser yang mana tidak bisa menampung produksi left rekursive. walaupun ini telah dipercaya implementasi sederhana dari top down parsing tidak bisa menampung langsung maupung tidal langsung left-recursion dan mungkin membutuhkan waktu exponensial ruang yang cukup saat mengurai tatabahasa context free yang ambigu, algoritma yang lebih canggih untuk top down parsing telah diciptakan oleh Frost, Hafiz, dan callaghan yang mampu menampung ambiguitas dan left recursion pada waktu polinomial dan mampu menghasilkan representasi ukuran polinomial dari nomer exponensial yang berpotensi pada parse tree. algoritmannya mampu menghasilkan derivasi left most dan right most pada input yang berkaitan pada CFG yang diberikan.

sebuah perbedaan penting yang berkaitan dengan parsing adalah apakah sebuah parser menghasilkan leftmost derivation ataukah rightmost derivation. LL parser akan menghasilkan sebuah leftmost derivation dan LR parser akan menghasilkan sebuah rightmost derivation (walaupun biasannya secara terbalik).

examples of parser

top down parser

beberapa parser yang menggunakan top down parsing meliputi:
recursive descent parser
LL parser (Left to right, Leftmost derivation)
early parser
X-SAIGA-eXecutable SpecificAtlons of Grammars.
berkaitan dengan algoritma parsing top down yang mendukung left recursion dan ambiguitas dalam waktu polinomial dan ruang publikasi.

buttom up parser

beberapa parser yang menggunakan bottom up parsing meliputi:
precedence parser
operator presedence parser
simple precedence parser
BC (bounded context) parsing
LR parser (left to right, rightmost derivation)
simple LR (SLR) parser
LALR parser
canonical LR (LR(1)) parser
GLR parser
CYK parser

parser development software

beberapa parser development tool yaitu sebagai berikut:
ANTLR
bison
coco/R
GOLD
javaCC
lemon
lex
parboiled
ragel
syntax definition formalism
spirit parser framework
SYNTAX
yacc

2 komentar:

Vostro.Sinaga mengatakan...

Nuhun mas atas info nya ,,,

Sabaku no Nara mengatakan...

senang bisa membantu,,,

Posting Komentar