Saya masih anak sekolah ketika saya jatuh ke tangan buku "Kursus Pemula C dan C ++" dari penerbit penerbitan Dialog MIFI. Dari buku inilah saya belajar tentang dasar-dasar pemrograman berorientasi objek, dan juga menimbulkan masalah bagi saya yang tidak bisa saya selesaikan untuk waktu yang lama. Pada akhirnya ada program daftar aplikasi, salah satunya disebut kalkulator rekursif. Ini adalah pertemuan pertama saya dengan analisis ekspresi aritmatika menggunakan metode keturunan rekursif. Saya masih ingat jam-jam panjang yang dihabiskan untuk mencoba setidaknya memahami sesuatu dalam kode ini.Artikel ini ditujukan terutama bagi mereka yang dihadapkan dengan tugas mengurai ekspresi untuk pertama kalinya.Jadi, sebelum menulis parser ekspresi aritmatika, kita perlu memahami struktur ekspresi ini. Untuk kesederhanaan, kami tidak akan mempertimbangkan operasi minus unary dan kemungkinan menggunakan fungsi dalam ekspresi untuk saat ini.Untuk menggambarkan struktur, kami menggunakan bentuk Beckus-NaurE -> T + E | T - E | T
T -> F * T | F / t | F
F -> N | (E)
Inilah bilah vertikal "|" berarti operasi logis "atau", dan E, T, F, N - berbagai jenis subekspresi di mana ekspresi asli akan dipisah saat menggunakan kalimat-kalimat ini. N dalam hal ini menunjukkan angka.Kalimat pertama berarti bahwa ekspresi tipe E dapat terdiri dari ekspresi tipe T ditambah ekspresi tipe E, atau ekspresi tipe T minus ekspresi tipe E atau hanya ekspresi tipe T.Untuk kalimat kedua, semuanya serupa, tetapi alih-alih menambahkan dan mengurangi akan ada penggandaan dan divisi.Kalimat ketiga berarti bahwa ekspresi tipe F adalah angka atau ekspresi tipe E yang terlampir dalam tanda kurung.Mari kita coba terapkan tiga kalimat ini pada contoh ekspresi aritmatika2 + 3 * (4 - 5) + 6 - 7
Kami menerapkan kalimat pertama beberapa kaliE (2 + 3 * (4-5) + 6-7) ->
T (2) + E (3 * (4-5) + 6-7) ->
T (2) + T (3 * (4-5)) + E (6-7) ->
T (2) + T (3 * (4-5)) + T (6) - T (7)
Sekarang ekspresi kami hanya terdiri dari subekspresi dari tipe T, jadi kami menerapkan kalimat kedua untuk masing-masing.T (2) -> F (2)
T (3 * (4-5)) -> F (3) * T ((4-5)) -> F (3) * F ((4-5))
T (6) -> F (6)
T (7) -> F (7)
Sudah waktunya untuk kalimat ketigaF (2) -> N (2) -> 2
F (3) -> N (3) -> 3
F ((4-5)) -> E (4-5)
F (6) -> N (6) -> 6
F (7) -> N (7) -> 7
Untuk ekspresi dalam tanda kurung (4-5), kami secara rekursif beralih ke kalimat pertama dan harus mengulangi semua tindakan dengan analogi dengan cara itu selama sisa ekspresi. Jika ekspresi berisi tanda kurung bersarang, maka akan ada lebih banyak transisi rekursif tersebut. Saya akan merekomendasikan agar Anda secara independen mencoba menerapkan ketiga kalimat ke ekspresi yang akan mengandung tingkat tanda kurung, misalnya 2 + 2 * (3 + 4 * (5-6)), untuk memastikan bahwa kalimat itu juga berfungsi untuk itu.Sekarang kita hanya perlu mengimplementasikan tindakan yang dilakukan oleh proposal dalam bentuk kode. Ini akan menjadi analisis ekspresi menggunakan metode turunan rekursif, tetapi sebelum Anda mulai menulis kode, mari sederhanakan kalimatnya dengan menyingkirkan rekursi pada dua yang pertama.Jika kita tanpa henti mengganti kalimat pertama menjadi kalimat itu sendiri, maka kita mengertiE -> T ± T ± T ± T ± ... ± T
Kalimat kedua dapat diubah dengan cara yang sama.T -> F * / F * / F * / * / ... * / F
Bahkan, ini berarti bahwa alih-alih rekursi, kita dapat menggunakan loop di sini. Demikian pula, rekursi tidak dapat dikecualikan dari kalimat ketiga.Kami akan menulis kode di Jawa, karena Ini adalah bahasa pemrograman yang paling akrab bagi saya saat ini. Ucapan terakhir sebelum kita mulai menulis kode - Saya meninggalkan tugas tokenization, yaitu memecah ekspresi menjadi elemen signifikan yang tidak terpisahkan (token) Token tersebut adalah angka, tanda operasi aritmatika dan tanda kurung. Misalkan kita sudah memiliki token array sebagai input dari ekspresi.String[] tokens = {"2", "+", "3", "*", "(", "4", "-", "5", ")", "+", "6", "-", "7"};
Buat kelas parser berikutnya yang akan berisi metode- parse () mulai mem-parsing ekspresi
- ekspresi () untuk menangani ekspresi tipe E
- istilah () untuk memproses ekspresi tipe T
- factor () untuk memproses ekspresi tipe F dan N
public class RecursiveDescentParser {
private final String[] tokens;
private int pos = 0;
public RecursiveDescentParser(String[] tokens) {
this.tokens = tokens;
}
public Double parse() {
Double result = expression();
if (pos != tokens.length) {
throw new IllegalStateException("Error in expression at " + tokens[pos]));
}
return result;
}
private Double expression() {
Double first = term();
while (pos < tokens.length) {
String operator = tokens[pos];
if (!operator.equals("+") && !operator.equals("-")) {
break;
} else {
pos++;
}
Double second = term();
if (operator.equals("+")) {
first += second;
} else {
first -= second;
}
}
return first;
}
private Double term() {
Double first = factor();
while (pos < tokens.length) {
String operator = tokens[pos];
if (!operator.equals("*") && !operator.equals("/")) {
break;
} else {
pos++;
}
Double second = factor();
if (operator.equals("*")) {
first *= second;
} else {
first /= second;
}
}
return first;
}
private Double factor() {
String next = tokens[pos];
Double result;
if (next.equals("(")) {
pos++;
result = expression();
String closingBracket;
if (pos < tokens.length) {
closingBracket = tokens[pos];
} else {
throw new IllegalStateException("Unexpected end of expression");
}
if (pos < tokens.length && closingBracket.equals(")")) {
pos++;
return result;
}
throw new IllegalStateException("')' expected but " + closingBracket);
}
pos++;
return Double.parseDouble(next);
}
}
Itu saja. Jika diinginkan, parser ini dapat diajarkan untuk bekerja dengan minus unary atau berfungsi dalam ekspresi. Hal pertama yang harus dilakukan adalah mengubah kalimat asli sehingga mereka memperhitungkan elemen baru dari struktur ekspresi, dan mungkin ada lebih banyak kalimat dari ini. Begitu mereka benar dimodifikasi, implementasi menjadi hampir formal.