Diutamakan fungsi dalam algoritma Shunting-yard

Saya bekerja melalui algoritma Shunting-yard , seperti yang dijelaskan oleh wikipedia.

Deskripsi algoritma ketika berhadapan dengan operator adalah sebagai berikut:

Jika token adalah operator, o1, maka:

sementara ada token operator, o2, di bagian atas tumpukan operator, dan keduanya

o1 is left-associative and its precedence is less than or equal to
that of o2, or

o1 is right associative, and has precedence less than that of o2,

kemudian pop o2 dari stack operator, ke antrian output;

dorong o1 ke tumpukan operator.

Namun, mereka memberikan contoh berikut:

Memasukkan: sin max 2 3 / 3 * 3.1415

Ketika algoritma mengenai /token, deskripsi tentang apa yang harus terjadi adalah sebagai berikut:

Token |        Action       |   Output (in RPN) |   Operator Stack
...
/     | Pop token to output | 2 3 max           | / sin 
...

Mereka bermunculan fungsi tanda maxdari stackdan menempatkan ke dalam queue. Menurut algoritme mereka, ini sepertinya berarti token fungsi keduanya operator, dan memiliki prioritas lebih rendah dari token /operator.

Tidak ada penjelasan apakah ini kasusnya atau tidak. Jadi, untuk Shunting-yardalgoritma, apa yang diutamakan dari suatu fungsi? Apakah fungsinya benar atau kiri asosiatif? Atau apakah wikipedia hanya tidak lengkap / tidak akurat?

Saya percaya jawaban langsungnya adalah bahwa fungsi bukan operator. Dari halaman yang Anda tautkan:

Jika token adalah token fungsi, kemudian dorong ke stack.

Ini yang perlu dikatakan, karena case fungsi (awalan ke postfix) jauh lebih sederhana daripada case operator (infix to postfix).

Untuk pertanyaan selanjutnya: Pengertian tentang presedensi dan asosiatif hanya diperlukan karena ambiguitas bawaan dalam setiap ekspresi dengan beberapa operator infiks. Token fungsi sudah menggunakan notasi awalan, jadi mereka tidak punya masalah itu. Anda tidak perlu tahu apakah sinatau maxmemiliki "prioritas lebih tinggi" untuk mencari tahu yang maxperlu dievaluasi terlebih dahulu; sudah jelas dari urutan token. Itu sebabnya komputer lebih memilih notasi pre / postfix untuk memulai, dan mengapa kita memiliki algoritma ini untuk mengubah infix menjadi pre / postfix.

Anda perlu memiliki semacam aturan untuk di mana argumen fungsi mulai dan berakhir ketika tidak ada tanda kurung, sehingga Anda bisa mengatakan bahwa fungsi "diutamakan" di atas operator atau sebaliknya. Tetapi tidak seperti operator infiks, aturan tunggal yang konsisten untuk semua fungsi sudah cukup untuk membuat komposisi mereka sepenuhnya ambigu.

Ada dua kasus berbeda yang perlu dipertimbangkan, tergantung pada sintaksis bahasa Anda. Jika bahasa Anda menggunakan tanda kurung untuk menunjukkan aplikasi fungsi (misalnya f(2+1)) maka prioritas tidak relevan. Fungsi harus didorong ke tumpukan dan muncul setelah (untuk contoh di atas, hasilnya adalah 2 1 + f). Sebagai alternatif, Anda dapat memperlakukan fungsi sebagai nilai dan mengeluarkannya segera, dan mengeluarkan operasi pemanggilan fungsi setelah tanda kurung tutup (yang seharusnya diperlakukan sama dengan tanda kurung lainnya), misalnya f 2 1 + $, di mana $operasi pemanggilan fungsi.

Jika bahasa Anda, bagaimanapun, tidak menggunakan tanda kurung untuk menunjukkan pemanggilan fungsi, tetapi sebaliknya menempatkan argumen langsung setelah fungsi tanpa tanda baca khusus (misalnya f 2 + 1), seperti yang terjadi pada contoh Wikipedia, maka hal-hal sedikit lebih rumit. Perhatikan bahwa ungkapan yang baru saja saya berikan adalah contoh yang ambigu: apakah f diterapkan pada 2 dan 1 ditambahkan ke hasilnya, atau apakah kita menambahkan 2 dan 1 bersamaan dan kemudian memanggil f dengan hasilnya?

Sekali lagi, ada dua pendekatan. Anda cukup mendorong fungsi ke tumpukan operator ketika Anda menjumpainya dan menetapkannya prioritas apa pun yang Anda inginkan. Ini adalah pendekatan yang paling sederhana, dan tampaknya apa yang telah dilakukan oleh contoh yang dikutip. Namun, ada masalah praktis. Pertama, bagaimana Anda mengidentifikasi suatu fungsi? Jika Anda memiliki set yang terbatas itu mudah, tetapi jika Anda memiliki fungsi yang ditentukan pengguna, ini berarti parser Anda perlu memberi umpan balik ke lingkungan Anda, yang dapat menjadi berantakan dengan cepat. Dan bagaimana Anda menangani fungsi dengan banyak argumen?

Perasaan saya adalah bahwa untuk gaya sintaksis ini, menggunakan fungsi sebagai nilai yang lebih handier oleh operator aplikasi fungsi jauh lebih masuk akal. Kemudian, Anda bisa menyuntikkan operator aplikasi setiap kali Anda membaca nilai dan hal terakhir yang Anda baca juga merupakan nilai, sehingga Anda tidak perlu cara khusus untuk mengetahui pengidentifikasi mana yang berfungsi. Anda juga dapat bekerja dengan ekspresi yang mengembalikan fungsi (yang sulit atau tidak mungkin dengan gaya fungsi-sebagai-operasi). Dan ini berarti Anda dapat menggunakan currying untuk menangani beberapa fungsi argumen, yang merupakan penyederhanaan besar untuk mencoba menanganinya secara langsung.

Satu-satunya hal yang perlu Anda putuskan adalah apa yang menjadi prioritas aplikasi fungsi. Pilihannya terserah Anda, tetapi dalam setiap bahasa yang saya gunakan yang berfungsi seperti ini, ia telah menjadi operator yang paling kuat dalam bahasa tersebut, dan telah diasosiasikan dengan benar. (Satu-satunya variasi yang menarik adalah Haskell, yang selain memiliki versi pengikatan yang sangat jelas, juga memiliki sinonim dengan simbol $yang merupakan operator pengikat yang paling lemah dalam bahasa tersebut, yang memungkinkan ekspresi seperti f 2 + 1menerapkan f ke 2 dan f $ 2 + 1untuk menerapkan ke seluruh sisa ekspresi)

Saya menerapkan "fungsi di halaman shunting" yang diminta setelah membaca pemikiran asli Dijkstra (Halaman 7-11 dalam makalah kompiler Algol 60, https://ir.cwi.nl/pub/9251 ), dan membutuhkan solusi yang kuat, saya lakukan hal berikut:

parsing:

• Dorong deskriptor fungsi
• Dorong braket kiri start-of-args "[" sama seperti dimulainya kurung subekspresi.
• Baca urutan daftar argumen seimbang "(" hingga ")" dari input
• Dorong ini ke aliran token output
• Dorong braket kanan end-of-args "]" sama seperti "bracket penutupan kompensasi"

Infix-to-postfix (halaman shunting):

• Tambahkan tumpukan lain, tumpukan fungsi, sama seperti tumpukan operator
• Saat memindai nama fungsi, dorong info fungsi ke tumpukan fungsi
• Ketika braket kanan akhir-arg-terlihat, pop fungsi stack untuk output

Berfungsi sempurna dalam pengujian yang kuat dan skenario yang rumit. Dalam aplikasi saya (expander argumen yang berisi ekspresi baris perintah), saya mendukung fungsi multi argumen dan tanda "," tanda untuk memisahkan mereka, dan ini mengalir melalui seluruh proses.

Contohnya terlihat seperti "sqrt (3 ^ 2 + 4 ^ 2)" yang menjadi "3 2 ^ 4 2 ^ + sqrt" dan akhirnya "5" yang merupakan argumen program. Itu bignum, jadi "" binomial (64, 32) / gcd (binomial (64, 32), binomial (63, 31)) "==> hal-hal besar ==>" 2 "sangat membantu." 123456 ^ 789 " adalah 40.173 digit dan waktunya menunjukkan "evaluasi = 0,000390 detik" di MacBookPro saya, begitu cepat.

Saya juga menggunakan ini untuk memperluas data dalam tabel, dan menemukan itu berguna. Bagaimanapun, ini tip saya tentang cara saya dengan hati-hati menangani panggilan fungsi, banyak argumen, dan bersarang dalam konteks halaman shunting-halaman Dijkstra. Lakukan saja hari ini dari pemikiran mandiri. Tidak tahu apakah mungkin ada cara yang lebih baik.