Tata bahasa (BNF) dan Notasi Polandia Terbalik
| English | Bahasa Indonesia |
|---|---|
| postfix/ˈpəʊstfɪks/ | postfix |
| precedence/ˈpresɪdəns/ | precedence |
| grammar/ˈɡræmə/ | tata bahasa |
| syntax diagram/ˈsɪntæks ˈdaɪəɡræm/ | diagram sintaks |
| Reverse Polish Notation/rɪˈvɜːs ˈpəʊlɪʃ nəʊˈteɪʃn/ | Notasi Polandia Terbalik |
| Backus-Naur Form/ˈbækəs nɔː fɔːm/ | Bentuk Backus-Naur |
| production rules/prəˈdʌkʃn ruːlz/ | aturan produksi |
| terminal/ˈtɜːmɪnl/ | terminal |
| non-terminal/nɒn ˈtɜːmɪnl/ | non-terminal |
| infix/ˈɪnfɪks/ | infix |
Notasi tanpa kurung, dan tanpa ambiguitas
- Tulis
3 + 4 * 2dan Anda mengandalkan konvensi: bahwa perkalian mengikat lebih kuat daripada penjumlahan. Ubah konvensinya dan ekspresi tersebut berarti sesuatu yang lain. - Seorang logikus Polandia, Jan Łukasiewicz, menunjukkan pada tahun 1920-an bahwa jika Anda menempatkan operator sebelum operand-nya, kurung menjadi tidak perlu. Membalikkan posisinya, menempatkan operator setelah, Anda mendapatkan bentuk yang dapat dievaluasi oleh mesin dengan hanya menggunakan tumpukan (stack).
- Itulah sebabnya Virtual Machine Java dan sebagian besar interpreter bytecode bekerja dalam format postfix. Tidak ada tabel prioritas, tidak ada kurung, tidak ada ambiguitas.
- Pelajaran ini menjelaskan bagaimana tata bahasa sebuah bahasa dituliskan dalam BNF dan sebagai diagram sintaks, serta bagaimana Notasi Polish Terbalik dikonversi dan dievaluasi.
Bentuk Backus-Naur
- Sebuah tata bahasa menyatakan sekuens token mana yang merupakan program valid. Bentuk Backus-Naur - (BNF) menuliskannya sebagai aturan produksi:
<symbol> ::= alternative1 | alternative2 | ...
- Simbol terminal adalah teks literal yang muncul dalam program. Simbol non-terminal adalah nama aturan lain, ditulis di dalam tanda sudut.
<digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
<letter> ::= a | b | c | … | z
<identifier> ::= <letter> | <identifier> <letter> | <identifier> <digit>
Dalam BNF, simbol terminal adalah:
Terminal adalah token literal; non-terminal adalah nama aturan produksi lainnya.
Rekursivitas adalah cara BNF berulang
- BNF tidak memiliki simbol "ulang", sehingga pengulangan ditulis dengan mendefinisikan aturan dalam istilah dirinya sendiri.
- Baca
<identifier> ::= <letter> | <identifier> <letter> | <identifier> <digit>sebagai: sebuah identifier adalah satu huruf, atau identifier diikuti oleh huruf, atau identifier diikuti oleh angka. - Keseluruhan alternatif tersebut berarti "huruf diikuti oleh sejumlah huruf atau angka sembarang", yang juga menjelaskan mengapa identifier tidak bisa dimulai dengan angka: tidak ada alternatif yang mengizinkannya.
- Sebuah diagram sintaks, atau diagram rel, mengekspresikan aturan yang sama secara grafis, dengan perulangan di mana BNF menggunakan rekursivitas. Kedua notasi ini ekuivalen.
Perulangan dan rekursivitas mengatakan hal yang sama
Cocokkan setiap istilah tata bahasa/notasi dengan maknanya.
BNF membangun aturan dari terminal dan non-terminal (rekursi memberikan pengulangan); RPN mengurutkan ulang ekspresi untuk menghilangkan kurung.
Mengapa aturan
Alternatif bersama-sama berarti huruf diikuti oleh jumlah huruf atau angka apa pun, dan tidak ada alternatif yang memungkinkannya dimulai dengan angka.
Contoh terpecahkan: uji string terhadap tata bahasa
- Menggunakan aturan di atas, manakah dari
count2,2countdanmy_varyang merupakan identifier valid? count2: valid. Bangun dari bawah:cadalah<letter>, jadi sebuah<identifier>; tambahkano,u,n,tmelalui alternatif kedua; tambahkan2melalui alternatif ketiga.2count: tidak valid. Setiap alternatif dimulai dari<letter>atau dari<identifier>lainnya, dan tidak ada rantai yang dapat dimulai dengan angka.my_var: tidak valid, karena_bukan terminal dalam aturan apa pun di sini. Sebutkan aturan yang gagal, bukan hanya "terlihat salah".
Menggunakan aturan tersebut, string mana yang merupakan identifikasi valid? Pilih semua yang berlaku.
Satu huruf adalah identifikasi berdasarkan alternatif pertama. 2count tidak dapat dimulai dengan angka, dan _ bukan terminal dalam aturan apa pun di sini.
Infix dan postfix
- Infix menempatkan operator di antara operand-nya,
3 + 4 * 2, dan karenanya membutuhkan aturan prioritas dan kurung agar tidak ambigu. - Notasi Polish Terbalik, atau postfix, menempatkan operator setelah operand-nya:
3 4 2 * +. Ia tidak membutuhkan keduanya. - Urutan kemunculan operator dalam bentuk postfix adalah urutan penerapannya, yang merupakan persis apa yang dibutuhkan mesin untuk diberitahu.
Mengonversi infix ke postfix
- Gunakan tumpukan (stack) operator. Pindai dari kiri ke kanan: kirim operand langsung ke output; untuk operator, pop dulu ke output semua operator bertumpuk yang memiliki prioritas lebih tinggi atau sama, lalu push operator tersebut.
- Push kurung buka. Pada kurung tutup, pop ke output hingga menemukan kurung buka yang berpasangan, lalu buang pasangan tersebut.
- Di akhir, pop semua yang tersisa di tumpukan ke output.
Prioritas operator — apa yang dihapus oleh RPN
Dalam matematika infix biasa, × dan ÷ memiliki ikatan lebih kuat daripada + dan −, sehingga Anda harus menerapkan aturan dalam urutan yang benar. Notasi Polandia Terbalik menulis operand terlebih dahulu (3 4 2 × + 1 −), memperbaiki urutan sehingga tidak perlu aturan prioritas.
Apa bentuk RPN (postfix) dari ekspresi infix (3 + 4) * 2?
Kurung memaksa 3+4 terlebih dahulu: 3 4 +, kemudian kalikan dengan 2: 3 4 + 2 *.
Ubah (A + B) * (C - D) menjadi Notasi Polandia Terbalik, menggunakan * untuk perkalian.
Setiap kurung dikonversi satu per satu dan perkalian dipop terakhir, sehingga muncul di akhir. Tidak ada kurung yang tersisa.
Contoh terpecahkan: konversi, lalu evaluasi
- Konversi $(A + B) \times (C - D)$ ke RPN. Push
(; outputA; push+; outputB; pada)pop kembali ke(yang berpasangan, menghasilkanA B +. Push×. Kurung kedua berperilaku identik, menghasilkanC D -. Di akhir pop×. Hasil:A B + C D - ×. - Sekarang evaluasi untuk $A=3, B=4, C=5, D=2$. Push 3, push 4;
+pop keduanya dan push 7. Push 5, push 2;-pop keduanya dan push 3.×pop 7 dan 3 dan push 21. - Operator selalu mengambil dua item teratas, dan item pertama yang dipop adalah operand kanan. Itu penting untuk
-dan/, di mana urutan mengubah jawaban.
Evaluasi ekspresi RPN 3 4 2 * +.
Dorong 3, 4, 2; * mempop 4 dan 2 → 8; + mempop 3 dan 8 → 11.
Notasi Polandia Terbalik tidak memerlukan kurung atau aturan prioritas, dan dapat dievaluasi langsung dengan tumpukan.
Dorong operand; setiap operator mempop operannya dan mendorong hasilnya — yang merupakan persis bagaimana mesin tumpukan berjalan.
Evaluasi dengan tumpukan, langkah demi langkah
- Pindai dari kiri ke kanan: push setiap operand; pada operator, pop dua item teratas, terapkan operator, dan push hasilnya. Di akhir tumpukan berisi satu nilai: jawabannya.
| Token | Tumpukan setelah |
|---|---|
3 |
3 |
4 |
3, 4 |
2 |
3, 4, 2 |
* |
3, 8 |
+ |
11 |
- Ini adalah mesin tumpukan: tidak ada kurung, tidak ada tabel prioritas, tidak ada lookahead. Inilah cara JVM dan banyak interpreter bytecode mengevaluasi setiap ekspresi.
Saat mengevaluasi RPN, item pertama yang dipop dari tumpukan adalah operand sisi kiri dari operator.
Yang pertama dipop adalah operand sisi kanan. Ini tidak berpengaruh untuk + dan *, tetapi membaliknya merusak pengurangan dan pembagian.
Susun langkah-langkah evaluasi 3 4 2 * + dengan tumpukan secara berurutan.
Operand masuk, setiap operator mengonsumsi dua teratas dan meninggalkan hasilnya. Tidak perlu kurung dan tidak perlu tabel prioritas.
⟦⟧ Nilai yang sering terlewat
- Terminal adalah teks literal; non-terminal menamai aturan lain. Jangan menukar keduanya.
- BNF mengekspresikan pengulangan melalui rekursivitas. Jika sebuah aturan merujuk pada dirinya sendiri, sebutkan itu dan jelaskan maknanya.
- Dalam evaluasi, operator mengambil dua item teratas, dan item pertama yang dipop adalah operand kanan. Mendapatkan itu terbalik akan merusak pengurangan dan pembagian.
- RPN tidak memerlukan kurung. Menulis kurung ke dalam jawaban postfix akan kehilangan poin yang sedang diujinya.
Anda telah memahaminya
- BNF aturan produksi menggabungkan terminal (teks literal) dan non-terminal (nama aturan), dan mengekspresikan pengulangan melalui rekursivitas; diagram sintaks adalah bentuk grafis ekuivalennya
- uji string dengan membangunnya dari aturan, dan sebutkan aturan yang gagal ketika string tersebut tidak valid
- infix memerlukan prioritas dan tanda kurung; RPN (postfix) menempatkan operator setelah operand-operandnya dan tidak membutuhkan keduanya
- konversi dengan menggunakan stack operator, dan evaluasi dengan mendorong operand serta menerapkan setiap operator pada dua teratas, yang pertama popped adalah operand sisi kanan