Analisis Leksikal
Analisis leksikal adalah proses memecah input program atau ekspresi matematika menjadi unit-unit kecil yang disebut token. Setiap token merupakan representasi dari suatu konstruksi yang ditemukan dalam input, seperti operator, angka, atau variabel. Proses analisis leksikal ini penting karena token-token tersebut nantinya akan digunakan dalam proses analisis sintaksis.
Dalam Bahasa pemrograman dikenal sebagai token yaitu identifiers, keywoards, operators, literals, punctuation
1. Identifier: mengidentifikasi sebuah variable atau nama- nama yang memiliki fungsi tertentu.Contohnya: variable yag diawal identifikasi A,B,C kemudian seperti #include<>
2. Keyword : sebuah kata kunci, dimana fungsinya sudah tidak bisa dirubah contoh seperti if, else, then, while, do
3. Operators : berhubungan dengan operasi aritmatika seperti + - / * =
4. Lierals : nilai constant atau nilai yang saat kita berikan dari awal tidak mengalami perubahan atau tetap digunakan Ketika hasilnya keluar, contoh rumus lingkaran yang bernilai phi yaitu 22/7 atau 3,14 itu nilainya konstan
5. Punctuation: tanda baca seperti , . : ; ()
Analisis Sintaksis
Analisis sintaksis adalah proses untuk memeriksa apakah suatu program atau ekspresi matematika memenuhi sintaks yang telah ditentukan atau tidak. Proses analisis sintaksis ini penting karena dapat memastikan bahwa program atau ekspresi matematika tersebut dapat dijalankan dengan benar.
Contoh Kode C++ dengan Perulangan
Berikut adalah contoh kode C++ sederhana dengan perulangan untuk menunjukkan bagaimana analisis leksikal & analisa sintaks dapat diterapkan:
Pada code tersebut, kita menggunakan loop for untuk mengiterasi setiap karakter dalam input dan melakukan analisis leksikal dengan fungsi is_number() dan is_operator(). Selanjutnya, kita menggunakan analisis sintaksis untuk melakukan operasi penjumlahan atau pengurangan pada token-token yang terdapat pada input. Terakhir, kita mencetak hasil operasi pada layar.
Pohon Urai
Pohon urai (parse tree) adalah struktur data berupa pohon yang merepresentasikan struktur sintaksis dari suatu rangkaian simbol dalam bahasa pemrograman atau bahasa formal lainnya. Pohon urai digunakan dalam teknik kompilasi untuk menganalisis sintaksis dari sebuah program dan membangun struktur data yang merepresentasikan program tersebut.
Untuk membangun pohon urai, dibutuhkan aturan sintaksis atau grammar yang mendefinisikan struktur sintaksis dari bahasa pemrograman atau bahasa formal yang digunakan. Grammar adalah aturan formal yang digunakan untuk menentukan struktur sintaksis dari sebuah rangkaian simbol.
Pohon urai tersebut dapat dibaca dari atas ke bawah sebagai:
- Tambahkan 2 ke 0 (nilai awal).
- Kali 4 dengan 3 dan tambahkan hasilnya ke nilai sebelumnya (2).
- Kurangi nilai sebelumnya (14) dengan 1.
Sehingga hasil akhirnya adalah 13.
Otomata
Otomata adalah sebuah model matematis yang digunakan untuk mengenali atau memproses rangkaian simbol dalam sebuah bahasa formal. Otomata digunakan dalam teknik kompilasi untuk melakukan analisis leksikal dan sintaksis dari sebuah program.
Dalam teknik kompilasi, terdapat beberapa jenis otomata yang digunakan, di antaranya adalah otomata berhingga deterministik (deterministic finite automata/ DFA) dan otomata berhingga nondeterministik (nondeterministic finite automata/ NFA).
Dalam teknik kompilasi, otomata digunakan untuk melakukan analisis leksikal, yaitu proses mengenali token atau kata dalam sebuah program. Setiap token dalam bahasa pemrograman memiliki pola atau aturan tertentu yang dapat dijelaskan menggunakan otomata. Misalnya, untuk mengenali token angka dalam bahasa pemrograman, dapat digunakan otomata berhingga deterministik yang menerima simbol angka (0-9) pada state awal dan berakhir pada state akhir setelah menerima sejumlah simbol angka yang memadai.
Selain itu, otomata juga digunakan dalam analisis sintaksis untuk memvalidasi struktur sintaksis dari sebuah program. Otomata digunakan untuk mengenali urutan simbol atau token yang mengikuti aturan produksi dari grammar yang telah didefinisikan. Misalnya, sebuah grammar untuk bahasa pemrograman mungkin memiliki aturan produksi seperti if_statement -> IF ( condition ) statement yang menentukan struktur sintaksis dari sebuah statement if. Otomata digunakan untuk mengenali urutan token yang mengikuti aturan produksi tersebut, sehingga dapat memvalidasi struktur sintaksis dari sebuah program.
Dalam pengembangan kompiler, otomata digunakan sebagai dasar dalam pembuatan parser. Parser digunakan untuk melakukan analisis sintaksis secara lebih kompleks, dengan mengintegrasikan beberapa otomata yang saling berhubungan. Salah satu teknik parser yang menggunakan otomata sebagai dasarnya adalah parser LL(1) atau parser recursive-descent.
Parser LL(1) menggunakan otomata untuk mengenali simbol-simbol yang sesuai dengan aturan produksi dari grammar, dengan mempertimbangkan satu simbol maju ke depan (lookahead symbol) dalam proses parsing. Parser recursive-descent menggunakan otomata dalam bentuk fungsi-fungsi rekursif yang menerapkan aturan produksi dari grammar secara berurutan.
Selain itu, otomata juga digunakan dalam analisis semantik dan optimasi kode dalam proses kompilasi. Pada tahap analisis semantik, otomata digunakan untuk melakukan validasi terhadap penggunaan variabel, tipe data, dan aturan lain dalam program. Pada tahap optimasi kode, otomata digunakan untuk mengenali pola-pola tertentu dalam kode yang dapat dioptimalkan.
Dalam teknik kompilasi, otomata menjadi dasar penting dalam analisis leksikal dan sintaksis dari sebuah program. Dengan menggunakan otomata, kompiler dapat melakukan analisis secara lebih efektif dan akurat, sehingga dapat menghasilkan program yang lebih baik dan efisien.
Untuk membuat otomata dari source code tersebut, kita perlu memahami alur program terlebih dahulu. Program tersebut melakukan analisis sintaksis dan leksikal untuk menjumlahkan atau mengurangkan bilangan dalam input yang diberikan.
Kita dapat membuat otomata untuk program di atas dengan menggunakan diagram alir berikut:
Berikut adalah keterangan untuk setiap state dan transisi pada otomata di atas:
- Start (S): State awal, program dimulai dari sini.
- State (N): State bilangan, karakter saat ini adalah angka.
- State (O): State operator, karakter saat ini adalah operator.
- State (N, O): State bilangan setelah operator, karakter saat ini adalah angka setelah operator.
- State (R): State reset, karakter saat ini bukan angka atau operator, atau sudah mencapai akhir input.
- Finish: State akhir, program selesai.
Berikut adalah penjelasan untuk transisi pada otomata di atas:
- - Dari state Start (S), program memeriksa karakter saat ini. Jika karakter tersebut adalah angka, program akan berpindah ke state State (N), dan jika karakter tersebut adalah operator, program akan berpindah ke state State (O). Jika karakter tersebut bukan angka atau operator, program akan tetap berada di state Start (S).
- - Dari state State (N), program akan memeriksa karakter saat ini. Jika karakter tersebut adalah angka, program akan tetap berada di state State (N), dan jika karakter tersebut adalah operator, program akan berpindah ke state State (O). Jika karakter tersebut bukan angka atau operator, program akan berpindah ke state State (R).
- - Dari state State (O), program akan memeriksa karakter saat ini. Jika karakter tersebut adalah angka, program akan berpindah ke state State (N, O), dan jika karakter tersebut adalah operator, program akan tetap berada di state State (O). Jika karakter tersebut bukan angka atau operator, program akan berpindah ke state State (R).
- Dari state State (N, ...), akan ada dua kemungkinan transisi tergantung pada karakter input. Jika karakter input adalah angka, maka transisi yang diambil adalah menuju state State (N, X), dimana X adalah angka yang sedang diinput. Sedangkan jika karakter input adalah operator, maka transisi yang diambil adalah menuju state State (O, Y), dimana O adalah operator yang sedang diinput dan Y adalah angka terakhir yang terdeteksi sebelumnya.
Berikut adalah implementasi otomata untuk analisis sintaksis pada program kalkulator sederhana:
Detail Anggota :
1. Rahmad Darmawan.S (201931012)
2. Nur Alfrida (201931106)
3. Yusni Yahdian (201931140)
4. Janri Melano (201931209)
Tidak ada komentar:
Posting Komentar