Menghapus rekursi kiri dalam tata bahasa sambil mempertahankan asosiasi kiri operator

Saya punya masalah dengan latihan ini:

Biarkan G menjadi tata bahasa ambigu berikut untuk kalkulus λ:

E → v | λv.E | EE | (E)

di mana E adalah simbol non-terminal tunggal, λv.E mewakili abstraksi dari variabel v di E, dan EE mewakili aplikasi.

1. Definisikan tata bahasa LL (1) G ′ sedemikian rupa sehingga L (G ′) = L (G) dan ambiguitas G diselesaikan dengan memaksakan konvensi biasa berikut:
   1. abstraksi adalah asosiatif yang benar;
   2. aplikasi dibiarkan asosiatif;
   3. aplikasi memiliki prioritas lebih tinggi daripada abstraksi.
2. Perlihatkan tabel penguraian LL (1) untuk G ′ dan pohon pengurai yang diperoleh saat mengurai string λv1. λv2. v1v2v1.

Saya menghilangkan prioritas ambiguitas pengaturan dan asosiasi, mendapatkan tata bahasa ini:

E -> EF | F
F -> λv.G | G
G -> (E) | v

yang bukan LL (1), karena produksi E -> EFdibiarkan rekursif. Namun, menghilangkan rekursi kiri dari produksi itu saya dapatkan:

E -> FE¹
E¹-> FE¹ | ɛ
F -> λv.G | G
G -> (E) | v

yang tidak memenuhi persyaratan 1.2.

Saya mencari solusi di Internet, tetapi sepertinya tidak mungkin untuk menghilangkan rekursi kiri yang menjaga asosiatif kiri.

Namun, latihan ini muncul pada ujian kompiler beberapa tahun yang lalu, jadi harus ada jawaban yang benar.

Terima kasih untuk bantuannya.

Kompatibilitas asosiasi kiri dan penguraian LL (1)

Anda baru saja menekan salah satu inkonsistensi utama dalam penggunaan sintaks bebas konteks (CF). Orang ingin memilih tata bahasa sehingga parse-tree akan mencerminkan struktur kalimat yang dimaksudkan, dekat dengan semantiknya, terutama dalam hal operator non asosiatif, seperti aplikasi . Ini cukup banyak maksud asli tata bahasa CF dalam linguistik. Tetapi pada saat yang sama mereka membatasi diri pada teknologi parsing yang hanya akan mentolerir beberapa jenis tata bahasa.

Memang, jika parse-tree adalah untuk merefleksikan asosiasi kiri dari operator, maka tata bahasa tentu saja bersifat rekursif kiri, karena simpul aplikasi teratas dalam parse-tree perlu menambahkan istilah paling kanan dari aplikasi berturut-turut yang tidak dipisah-pisah. Jadi penguraian LL tidak mungkin. Kamu benar.

Ada dua jalan keluar dari ini. Seseorang tidak harus bergantung pada parser untuk memberikan "parse-tree" yang kuat untuk digunakan pada tahap pemrosesan selanjutnya (seperti mengurangi ekspresi lambda, di sini). Ini mengarah pada konsep Abstract Syntax Trees (AST) yang dapat dibangun dari parse-tree, tetapi dengan struktur yang berbeda.

Solusi lainnya adalah menggunakan Teknik parsing yang lebih umum yang akan menerima tata bahasa CF, dan parsing sesuai dengannya. Pengurai CF umum adalah teknologi yang dikembangkan dengan baik (dan saya tidak berhenti bertanya-tanya mengapa LL tetap begitu populer).

Saya tidak tahu apa yang bisa dianggap sebagai jawaban yang tepat untuk persyaratan yang bertentangan ini.

Apa yang akan saya lakukan adalah menunjukkan bahwa mereka bertentangan dengan persyaratan. Berikan tata bahasa pertama yang memenuhi asosiasi dan batasan prioritas, lalu ubah tata bahasa menjadi dan tata bahasa LL (1) untuk penguraian.

Fakta bahwa sesuatu muncul dalam jurnal atau ujian bukanlah jaminan total bahwa itu benar. Dan saya mungkin salah juga ... tapi saya melakukan pengecekan, di samping pengetahuan saya sendiri tentang masalah ini.

Tentang contoh spesifik ini

Ini dikatakan, tata bahasa pertama yang Anda sarankan tampaknya tidak sepenuhnya benar. Itu tidak memiliki cara menghasilkan λu.λv.v.

Satu trik yang perlu diketahui adalah memulai dengan operator (abstraksi atau aplikasi) dengan prioritas terendah (abstraksi). Ini sama untuk ekspresi aritmatika.

Usaha saya:

E  -> A | λv.E
A  -> FA'
A' -> A | ɛ
F  -> (E) | v

Tata bahasa ini adalah LL (1) dan harus menghormati properti yang diperlukan.