Desain Penyusun - Parser Top-Down
Kita telah mempelajari di bab terakhir bahwa teknik parsing top-down mem-parsing input, dan mulai membangun pohon parse dari simpul akar secara bertahap bergerak ke bawah ke simpul daun. Jenis penguraian top-down digambarkan di bawah ini:
Penguraian Penurunan Rekursif
Turunan rekursif adalah teknik penguraian atas-bawah yang menyusun pohon parse dari atas dan input dibaca dari kiri ke kanan. Ia menggunakan prosedur untuk setiap terminal dan entitas non-terminal. Teknik parsing ini mengurai input secara rekursif untuk membuat pohon parse, yang mungkin memerlukan atau tidak memerlukan pelacakan balik. Tetapi tata bahasa yang terkait dengannya (jika tidak dibiarkan) tidak dapat menghindari pelacakan ke belakang. Suatu bentuk penguraian keturunan rekursif yang tidak memerlukan pelacakan balik disebut sebagaipredictive parsing.
Teknik penguraian ini dianggap rekursif karena menggunakan tata bahasa bebas konteks yang bersifat rekursif.
Pelacakan belakang
Parser top-down mulai dari node root (simbol awal) dan mencocokkan string input dengan aturan produksi untuk menggantikannya (jika cocok). Untuk memahaminya, ambil contoh CFG berikut:
S → rXd | rZd
X → oa | ea
Z → ai
Untuk string input: read, parser top-down, akan berperilaku seperti ini:
Ini akan dimulai dengan S dari aturan produksi dan akan mencocokkan hasilnya dengan huruf paling kiri dari input, yaitu 'r'. Produksi S (S → rXd) sangat cocok dengannya. Jadi pengurai top-down maju ke huruf masukan berikutnya (yaitu 'e'). Pengurai mencoba memperluas non-terminal 'X' dan memeriksa produksinya dari kiri (X → oa). Itu tidak cocok dengan simbol masukan berikutnya. Jadi parser top-down backtrack untuk mendapatkan aturan produksi berikutnya dari X, (X → ea).
Sekarang parser mencocokkan semua huruf input secara berurutan. String diterima.
|
|
|
|
Parser Prediktif
Pengurai prediktif adalah pengurai keturunan rekursif, yang memiliki kemampuan untuk memprediksi produksi mana yang akan digunakan untuk menggantikan string input. Pengurai prediktif tidak mengalami kemunduran.
Untuk menyelesaikan tugasnya, pengurai prediktif menggunakan penunjuk lihat ke depan, yang menunjuk ke simbol masukan berikutnya. Untuk membuat pelacakan mundur parser gratis, pengurai prediktif menempatkan beberapa batasan pada tata bahasa dan hanya menerima kelas tata bahasa yang dikenal sebagai tata bahasa LL (k).
Penguraian prediktif menggunakan tumpukan dan tabel penguraian untuk mengurai input dan menghasilkan pohon parse. Baik tumpukan dan masukan berisi simbol akhir$untuk menunjukkan bahwa tumpukan kosong dan masukan dikonsumsi. Pengurai mengacu pada tabel parsing untuk mengambil keputusan apa pun tentang kombinasi elemen tumpukan dan masukan.
Dalam penguraian turunan rekursif, pengurai mungkin memiliki lebih dari satu produksi untuk dipilih untuk satu contoh masukan, sedangkan dalam pengurai prediktif, setiap langkah memiliki paling banyak satu produksi untuk dipilih. Mungkin ada contoh di mana tidak ada produksi yang cocok dengan string input, membuat prosedur penguraian gagal.
LL Parser
Seorang LL Parser menerima tata bahasa LL. Tata bahasa LL adalah bagian dari tata bahasa bebas konteks tetapi dengan beberapa batasan untuk mendapatkan versi yang disederhanakan, untuk mencapai implementasi yang mudah. Tata bahasa LL dapat diimplementasikan dengan menggunakan kedua algoritma yaitu, recursive-descent atau table-driven.
Pengurai LL dilambangkan sebagai LL (k). L pertama di LL (k) mengurai input dari kiri ke kanan, L kedua di LL (k) berarti penurunan paling kiri dan k itu sendiri mewakili jumlah pandangan ke depan. Umumnya k = 1, jadi LL (k) bisa juga ditulis LL (1).
Algoritma Penguraian LL
Kita dapat menggunakan LL deterministik (1) untuk penjelasan parser, karena ukuran tabel tumbuh secara eksponensial dengan nilai k. Kedua, jika tata bahasa yang diberikan bukan LL (1), maka biasanya bukan LL (k), untuk setiap k tertentu.
Diberikan di bawah ini adalah algoritma untuk Parsing LL (1):
Input:
string ω
parsing table M for grammar G
Output:
If ω is in L(G) then left-most derivation of ω,
error otherwise.
Initial State : $S on stack (with S being start symbol)
ω$ in the input buffer
SET ip to point the first symbol of ω$.
repeat
let X be the top stack symbol and a the symbol pointed by ip.
if X∈ Vt or $
if X = a
POP X and advance ip.
else
error()
endif
else /* X is non-terminal */
if M[X,a] = X → Y1, Y2,... Yk
POP X
PUSH Yk, Yk-1,... Y1 /* Y1 on top */
Output the production X → Y1, Y2,... Yk
else
error()
endif
endif
until X = $ /* empty stack */
Tata bahasa G adalah LL (1) jika A → α | β adalah dua produksi G yang berbeda:
karena tidak ada terminal, baik α maupun β mendapatkan string yang dimulai dengan a.
paling banyak satu dari α dan β bisa mendapatkan string kosong.
jika β → t, maka α tidak mendapatkan string apapun yang dimulai dengan terminal di FOLLOW (A).