Bisakah Earley Parser dibuat menjadi pengurai fuzzy mirip dengan Levenshtein Automata Algo untuk DFA?

Ada cara untuk melakukan parsing fuzzy (menerima string bahkan dengan kesalahan pengetikan untuk jarak edit tertentu), dengan DFA dan run-time yang dibuat oleh Levenshtein Automata dari kata input. Bisakah hal serupa dilakukan dengan pengurai Earley? Saya merasa sulit untuk memahami algoritma, apalagi menjawab pertanyaan ini.

Jawabannya iya. Namun saya tidak akan melakukan itu dengan parser Earley karena ada yang lebih sederhana dengan kemampuan yang sama.

Pada dasarnya, parser Earley milik keluarga parser bebas konteks umum, yang menghasilkan semua parsing yang mungkin untuk string yang diberikan, ketika tata bahasa ambigu.

Ada dua cara (setidaknya) untuk memahami parser ini:

• sebagai interpretasi pemrograman dinamis dari otomat pushdown yang sesuai dengan tata bahasa pada string input;

• sebagai konstruksi persimpangan tata bahasa dengan otomat keadaan terbatas.

Ketika parsing string tunggal, otomat negara yang terbatas untuk dipertimbangkan adalah robot linear yang hanya mengakui string dapat dipecah, satu simbol pada suatu waktu (jumlah negara adalah | w | + 1 ). Jika Anda menerapkan konstruksi produk silang FA A dan CF garmmar G (Bar Hillel, Perlis, Shamir 1961), Anda mendapatkan tata bahasa CF baru yang merupakan tata bahasa F baru yang menghasilkan L ( A ) ∩ L ( G ) . Hal yang menarik biasanya diabaikan adalah bahwa F menjaga pohon parse yang digunakan oleh $w$$|w|+1$$A$$G$$F$$\mathcal L(A)\cap\mathcal L(G)$$F$$G$, hingga penggantian nama non-terminal (karena produk silang).

Jadi jika FA hanya menghasilkan string input Anda, tata bahasa F hanya akan menghasilkan string tersebut (jika berada dalam L ( G ) , jika tidak maka akan menghasilkan bahasa kosong ∅ ). Selain itu, ia menghasilkannya dengan semua pohon parse yang dapat digunakan G untuk menghasilkannya.$A$$F$$\mathcal L(G)$$\emptyset$$G$

Tata bahasa ini adalah apa yang biasanya disebut hutan parse bersama , dan semua algoritma parsing CF umum adalah versi yang kurang lebih dioptimalkan dari konstruksi produk-silang, apakah CYK, Earley, LR atau LL yang digeneralisasikan, atau yang lainnya. Jadi semua yang saya katakan berlaku untuk mereka juga.$F$

Tetapi, seperti yang Anda lihat, ini bersifat umum untuk mengurai seluruh rangkaian reguler, jika ada yang tertarik untuk melakukan itu.

$w$$w$

$G$$F$

Jika diinginkan, ini dapat digunakan untuk menjaga hanya string dengan jarak minimal.

Namun, ini dapat ditingkatkan sedikit karena komposisi dengan mesin negara hingga asosiatif.

$G$$w$$\Sigma^*$

Akan mudah untuk memangkas konstruksi itu untuk mendapatkan hasil yang sama seperti sebelumnya, tetapi cara terbaik adalah konstruksi persimpangan yang lebih terkontrol, seperti organisasi pemrograman dinamis yang digunakan oleh sebagian besar pengurai dalam literatur, termasuk Earley, dan menggunakannya untuk menghindari menghasilkan aturan yang tidak berguna dengan menghitung jarak dan membatalkan jalur komputasi apa pun ketika melebihi ambang yang diinginkan. Pemrograman dinamis juga dapat digunakan untuk menghitung langsung parse-forest (atau parse-tree) untuk string yang memiliki jarak terpendek ke input.