Mengapa rekursi buruk?

Dalam desain kompiler, mengapa rekursi kiri dihilangkan dalam tata bahasa? Saya membaca bahwa itu karena dapat menyebabkan rekursi yang tak terbatas, tetapi apakah itu tidak benar untuk tata bahasa rekursif yang tepat juga?

Tata bahasa rekursif kiri tidak selalu merupakan hal yang buruk. Tata bahasa ini mudah diurai menggunakan tumpukan untuk melacak frasa yang sudah diuraikan, seperti halnya dalam pengurai LR .

Ingat bahwa aturan rekursif kiri tata bahasa CF adalah dalam bentuk:$G = (V,\Sigma,R,S)$

$\alpha \rightarrow \alpha \beta$

dengan elemen dan elemen . (Lihat definisi formal lengkap untuk tupel sana ).$\alpha$$V$$\beta$$V \cup \Sigma$$(V,\Sigma,R,S)$

Biasanya, sebenarnya adalah urutan terminal dan non terminal, dan ada aturan lain untuk mana tidak muncul di sisi kanan.$\beta$$\alpha$$\alpha$

Setiap kali terminal baru diterima oleh pengurai tata bahasa (dari lexer), terminal ini didorong di atas tumpukan: operasi ini disebut shift .

Setiap kali sisi kanan aturan dicocokkan oleh sekelompok elemen berturut-turut di bagian atas tumpukan, grup ini digantikan oleh elemen tunggal yang mewakili frasa yang baru cocok. Penggantian ini disebut pengurangan .

Dengan tata bahasa rekursif yang tepat, tumpukan dapat tumbuh tanpa batas hingga pengurangan terjadi, sehingga membatasi kemungkinan penguraian secara dramatis. Namun, yang rekursif kiri akan membiarkan kompiler menghasilkan pengurangan lebih awal (pada kenyataannya, sesegera mungkin). Lihat entri wikipedia untuk informasi lebih lanjut.

Pertimbangkan aturan ini:

example : 'a' | example 'b' ;

Sekarang pertimbangkan parser LL yang mencoba mencocokkan string yang tidak cocok 'b'dengan aturan ini. Karena 'a'tidak cocok, itu akan mencoba mencocokkan example 'b'. Tetapi untuk melakukannya, itu harus cocok example... yang merupakan apa yang coba dilakukan di tempat pertama. Bisa macet mencoba selamanya untuk melihat apakah bisa cocok, karena selalu berusaha mencocokkan aliran token yang sama dengan aturan yang sama.

Untuk mencegah hal itu, Anda harus mengurai dari kanan (yang jarang terjadi, sejauh yang saya lihat, dan akan membuat rekursi yang tepat sebagai gantinya), secara artifisial membatasi jumlah sarang yang diizinkan, atau mencocokkan tanda sebelum rekursi dimulai sehingga selalu ada kasus dasar (yaitu, di mana semua token telah dikonsumsi dan masih belum ada kecocokan lengkap). Karena aturan rekursif kanan sudah melakukan yang ketiga, itu tidak memiliki masalah yang sama.

(Saya tahu pertanyaan ini sudah sangat tua sekarang, tetapi kalau-kalau orang lain memiliki pertanyaan yang sama ...)

Apakah Anda bertanya dalam konteks parser keturunan rekursif? Misalnya, untuk tata bahasa expr:: = expr + term | term, mengapa sesuatu seperti ini (dibiarkan rekursif):

// expr:: = expr + term
expr() {
   expr();
   if (token == '+') {
      getNextToken();
   }
   term();
}

bermasalah, tetapi bukankah ini (benar rekursif)?

// expr:: = term + expr
expr() {
   term();
   if (token == '+') {
      getNextToken();
      expr();
   }
}

Sepertinya kedua versi expr()panggilan itu sendiri. Tetapi perbedaan penting adalah konteks - yaitu token saat ini ketika panggilan rekursif dibuat.

Dalam kasus rekursif kiri, expr()terus-menerus menyebut dirinya sendiri dengan token yang sama dan tidak ada kemajuan yang dibuat. Dalam kasus rekursif yang tepat, ia mengkonsumsi beberapa input dalam panggilan ke term()dan token PLUS sebelum mencapai panggilan ke expr(). Jadi pada titik ini, panggilan rekursif dapat memanggil term dan kemudian mengakhiri sebelum mencapai tes if lagi.

Sebagai contoh, pertimbangkan untuk mem-parsing 2 + 3 + 4. Parser rekursif kiri memanggil expr()tanpa batas saat menempel pada token pertama, sedangkan parser rekursif kanan mengkonsumsi "2 +" sebelum memanggil expr()lagi. Panggilan kedua untuk expr()mencocokkan "3 +" dan panggilan expr()dengan hanya 4 yang tersisa. 4 cocok dengan istilah dan parsing berakhir tanpa panggilan lagi expr().

Dari manual Bison:

"Setiap jenis urutan dapat didefinisikan menggunakan rekursi kiri atau rekursi kanan, tetapi Anda harus selalu menggunakan rekursi kiri , karena dapat menguraikan urutan sejumlah elemen dengan ruang stack yang dibatasi. Rekursi kanan menggunakan ruang pada stack Bison di sebanding dengan jumlah elemen dalam urutan, karena semua elemen harus dipindahkan ke tumpukan sebelum aturan dapat diterapkan sekali saja. Lihat Algoritma Bison Parser, untuk penjelasan lebih lanjut tentang ini. "

http://www.gnu.org/software/bison/manual/html_node/Recursion.html

Jadi itu tergantung pada algoritma parser, tetapi seperti yang dinyatakan dalam jawaban lain, beberapa parser mungkin tidak bekerja dengan rekursi kiri