Analisis Sintaks: Jenis Parsing Top Down & Bottom Up Kompiler

Apa itu Analisis Sintaks?

Analisis Sintaks adalah fase kedua dari proses desain kompiler di mana string masukan yang diberikan diperiksa untuk konfirmasi aturan dan struktur tata bahasa formal. Ini menganalisis struktur sintaksis dan memeriksa apakah masukan yang diberikan sesuai dengan sintaks bahasa pemrograman yang benar atau tidak.

Analisis Sintaksis dalam proses Desain Kompiler dilakukan setelah fase analisis Lexical. Analisis ini juga dikenal sebagai Pohon Parse atau Pohon Sintaksis. Pohon Parse dikembangkan dengan bantuan tata bahasa yang telah ditetapkan sebelumnya. Penganalisis sintaksis juga memeriksa apakah program yang diberikan memenuhi aturan yang tersirat dalam tata bahasa bebas konteks. Jika memenuhi, parser kemudian membuat pohon parse dari program sumber tersebut. Jika tidak, parser akan menampilkan pesan kesalahan.

Analisis Sintaks
Proses Penganalisis Sintaks

Mengapa Anda memerlukan Penganalisis Sintaks?

  • Periksa apakah kode tersebut valid secara tata bahasa
  • Penganalisis sintaksis membantu Anda menerapkan aturan pada kode
  • Membantu Anda memastikan bahwa setiap kurung kurawal pembuka memiliki saldo penutup yang sesuai
  • Setiap deklarasi mempunyai tipe dan tipe tersebut harus ada

Terminologi Penganalisis Sintaks Penting

Terminologi penting yang digunakan dalam proses analisis sintaksis:

  • Kalimat: Kalimat adalah sekelompok karakter pada beberapa alfabet.
  • Leksem: Lexeme adalah unit sintaksis tingkat terendah dari suatu bahasa (misalnya total, awal).
  • Token: Token hanyalah sebuah kategori leksem.
  • Kata kunci dan kata-kata khusus – Ini adalah pengidentifikasi yang digunakan sebagai bagian tetap dari sintaksis suatu pernyataan. Ini adalah kata khusus yang tidak dapat Anda gunakan sebagai nama variabel atau pengidentifikasi.
  • Kata-kata kebisingan – Kata-kata berisik bersifat opsional yang disisipkan dalam pernyataan untuk meningkatkan keterbacaan kalimat.
  • komentar – Ini adalah bagian yang sangat penting dari dokumentasi. Sebagian besar ditampilkan dengan, /* */, atau//Kosong (spasi)
  • Pembatas – Ini adalah elemen sintaksis yang menandai awal atau akhir dari beberapa unit sintaksis. Seperti pernyataan atau ekspresi, “begin”…”end”, atau {}.
  • Set karakter – ASCII, Unikode
  • Pengidentifikasi – Ini adalah batasan panjang yang membantu Anda mengurangi keterbacaan kalimat.
  • Operasimbol-simbol – + dan – melakukan dua operasi aritmatika dasar.
  • Elemen sintaksis Bahasa

Mengapa kita perlu Parsing?

Penguraian

Parse juga memeriksa apakah string masukan terbentuk dengan baik, dan jika tidak, tolaklah.

Penguraian

Berikut ini adalah tugas penting yang dilakukan oleh parser dalam desain kompiler:

  • Membantu Anda mendeteksi semua jenis kesalahan Sintaks
  • Temukan posisi di mana kesalahan terjadi
  • Deskripsi kesalahan yang jelas & akurat.
  • Pemulihan dari kesalahan untuk melanjutkan dan menemukan kesalahan lebih lanjut dalam kode.
  • Seharusnya tidak mempengaruhi kompilasi program yang “benar”.
  • Penguraian harus menolak teks yang tidak valid dengan melaporkan kesalahan sintaksis

Teknik Penguraian

Teknik parsing dibagi menjadi dua kelompok berbeda:

  • Penguraian Atas-Bawah,
  • Parsing Bawah-Atas

Parsing Top-Down

Pada parsing top-down konstruksi pohon parsing dimulai dari akar kemudian dilanjutkan ke daun.

Dua jenis penguraian Top-down adalah:

  1. Penguraian Prediktif:

Parse prediktif dapat memprediksi produksi mana yang harus digunakan untuk menggantikan string masukan tertentu. Pengurai prediktif menggunakan titik pandang ke depan, yang menunjuk ke simbol masukan berikutnya. Mundur tidak menjadi masalah dengan teknik penguraian ini. Ini dikenal sebagai LL(1) Parser

  1. Parsing Keturunan Rekursif:

Teknik parsing ini mengurai input secara rekursif untuk membuat pohon prase. Ini terdiri dari beberapa fungsi kecil, satu untuk setiap nonterminal dalam tata bahasa.

Parsing Bawah-Atas

Dalam parsing bottom-up dalam desain compiler, konstruksi pohon parse dimulai dengan daun, dan kemudian diproses menuju akarnya. Ini juga disebut parsing shift-reduce. Jenis parsing dalam desain compiler ini dibuat dengan bantuan penggunaan beberapa perangkat lunak alat.

Kesalahan – Metode Pemulihan

Kesalahan Umum yang Terjadi pada Parsing pada Perangkat Lunak Sistem

  • Leksikal: Nama pengidentifikasi yang salah ketik
  • sintaksis: tanda kurung tidak seimbang atau titik koma hilang
  • semantik: penetapan nilai yang tidak kompatibel
  • logis: Loop tak terbatas dan kode tidak dapat dijangkau

Parser harus mampu mendeteksi dan melaporkan kesalahan yang ditemukan dalam program. Jadi, setiap kali terjadi kesalahan, parser harus mampu mengatasinya dan melanjutkan parsing input yang tersisa. Sebuah program dapat memiliki jenis kesalahan berikut pada berbagai tahap proses kompilasi. Ada lima metode pemulihan kesalahan umum yang dapat diimplementasikan dalam parser.

Pemulihan mode pernyataan

  • Jika parser mengalami kesalahan, ada baiknya Anda mengambil langkah perbaikan. Hal ini memungkinkan masukan dan status lainnya diurai terlebih dahulu.
  • Misalnya, menambahkan titik koma yang hilang dilakukan dalam metode pemulihan mode pernyataan. Namun, perancang parse harus berhati-hati saat melakukan perubahan ini karena satu koreksi yang salah dapat menyebabkan loop tak terbatas.

Pemulihan Mode Panik

  • Jika parser mengalami kesalahan, mode ini mengabaikan sisa pernyataan dan tidak memproses input dari input yang salah hingga pemisah, seperti titik koma. Ini adalah metode pemulihan kesalahan yang sederhana.
  • Dalam metode pemulihan jenis ini, parser menolak simbol input satu per satu hingga ditemukan satu kelompok token sinkronisasi yang ditunjuk. Token sinkronisasi umumnya menggunakan pembatas seperti atau.

Pemulihan Tingkat Frasa

  • Kompiler mengoreksi program dengan memasukkan atau menghapus token. Hal ini memungkinkannya melanjutkan penguraian dari tempatnya semula. Ia melakukan koreksi pada masukan yang tersisa. Itu dapat mengganti awalan input yang tersisa dengan beberapa string, ini membantu parser untuk melanjutkan proses.

Produksi Kesalahan

  • Pemulihan produksi kesalahan memperluas tata bahasa untuk bahasa yang menghasilkan konstruksi yang salah. Parser kemudian melakukan diagnostik kesalahan tentang konstruksi tersebut.

Koreksi Global

  • Kompiler harus membuat perubahan sesedikit mungkin saat memproses string input yang salah. Jika string input a dan tata bahasa c salah, algoritme akan mencari pohon parse untuk string terkait b. Seperti beberapa penyisipan, penghapusan, dan modifikasi token yang diperlukan untuk mengubah a menjadi b sesedikit mungkin.

Tatabahasa

Tata bahasa adalah seperangkat aturan struktural yang menggambarkan suatu bahasa. Tata bahasa menetapkan struktur pada kalimat apa pun. Istilah ini juga mengacu pada studi tentang aturan-aturan ini, dan file ini mencakup morfologi, fonologi, dan sintaksis. Ia mampu menjelaskan banyak sintaksis bahasa pemrograman.

Aturan Tata Bahasa Bentuk

  • Simbol non-terminal harus muncul di sebelah kiri setidaknya satu produksi
  • Simbol tujuan tidak boleh ditampilkan di sebelah kanan::= dari produksi apa pun
  • Suatu aturan bersifat rekursif jika LHS muncul di RHS-nya

Konvensi Notasi

Konvensi notasi simbol dapat ditunjukkan dengan menyertakan elemen dalam tanda kurung siku. Ini adalah urutan sembarang dari contoh elemen yang dapat ditunjukkan dengan menyertakan elemen dalam tanda kurung diikuti oleh simbol asterisk, { … }*.

Merupakan pilihan alternatif yang boleh menggunakan simbol dalam aturan tunggal. Dapat diapit tanda kurung ([,] ) bila diperlukan.

Dua jenis area konvensi Notasi Terminal dan Non-terminal

1.Terminal:

  • Huruf kecil pada alfabet seperti a, b, c,
  • Operasimbol tor seperti +,-, *, dll.
  • Simbol tanda baca seperti tanda kurung, hash, koma
  • 0, 1, …, 9 digit
  • String tebal seperti id atau if, apa pun yang mewakili simbol terminal tunggal

2.Nonterminal:

  • Huruf besar seperti A, B, C
  • Nama miring huruf kecil: ekspresi atau semacamnya

Tata Bahasa Bebas Konteks

CFG adalah tata bahasa rekursif kiri yang memiliki setidaknya satu produksi jenis tersebut. Aturan dalam tata bahasa bebas konteks sebagian besar bersifat rekursif. Penganalisis sintaksis memeriksa apakah program tertentu memenuhi semua aturan tata bahasa bebas konteks atau tidak. Jika memenuhi, penganalisa sintaksis aturan ini dapat membuat pohon parse untuk program tersebut.

expression -> expression -+ term
expression -> expression – term 
expression-> term
term  -> term * factor
term -> expression/ factor
term  -> factor factor
factor ->  ( expression )
factor -> id

Derivasi Tata Bahasa

Derivasi tata bahasa adalah rangkaian aturan tata bahasa yang mengubah simbol awal menjadi string. Derivasi membuktikan bahwa string tersebut milik bahasa tata bahasa.

Derivasi paling kiri

Ketika bentuk masukan sentensial dipindai dan diganti dalam urutan kiri ke kanan, ini dikenal sebagai derivasi paling kiri. Bentuk kalimat yang diturunkan dari turunan paling kiri disebut bentuk kalimat kiri.

Derivasi paling kanan

Derivasi paling kanan memindai dan mengganti input dengan aturan produksi, dari kanan ke kiri, secara berurutan. Ini dikenal sebagai derivasi paling kanan. Bentuk kalimat yang diturunkan dari turunan paling kanan disebut bentuk kalimat kanan.

Sintaks vs. Penganalisis Leksikal

Penganalisis Sintaks Penganalisis Leksikal
Penganalisis sintaksis terutama berkaitan dengan konstruksi bahasa yang rekursif. Penganalisis leksikal memudahkan tugas penganalisis sintaksis.
Penganalisis sintaksis bekerja pada token dalam program sumber untuk mengenali struktur bermakna dalam bahasa pemrograman. Penganalisis leksikal mengenali token dalam program sumber.
Ia menerima masukan, dalam bentuk token, dari penganalisis leksikal. Ini bertanggung jawab atas validitas token yang disediakan oleh

penganalisis sintaksis

Kekurangan menggunakan Syntax Analyzer

  • Itu tidak akan pernah menentukan apakah suatu token valid atau tidak
  • Tidak membantu Anda menentukan apakah operasi yang dilakukan pada jenis token valid atau tidak
  • Anda tidak dapat memutuskan bahwa token dideklarasikan & diinisialisasi sebelum digunakan

Kesimpulan

  • Analisis sintaksis adalah fase kedua dari proses desain kompiler yang dilakukan setelah analisis leksikal
  • Penganalisis sintaksis membantu Anda menerapkan aturan pada kode
  • Kalimat, Leksem, Token, Kata Kunci dan Kata Cadangan, Kata Kebisingan, Komentar, Pembatas, Kumpulan Karakter, Pengidentifikasi adalah beberapa istilah penting yang digunakan dalam Analisis Sintaks dalam konstruksi Kompiler
  • Parse memeriksa apakah string input sudah terbentuk dengan baik, dan jika tidak, tolaklah
  • Teknik parsing dibagi menjadi dua kelompok yang berbeda: Top-Down Parsing, Bottom-Up Parsing
  • Leksikal, Sintaksis, Semantik, dan logis adalah beberapa kesalahan umum yang terjadi selama metode parsing
  • Tata bahasa adalah seperangkat aturan struktural yang menggambarkan suatu bahasa
  • Konvensi notasi simbol dapat ditunjukkan dengan melampirkan elemen dalam tanda kurung siku
  • CFG adalah tata bahasa rekursif kiri yang memiliki setidaknya satu produksi jenis tersebut
  • Derivasi tata bahasa adalah rangkaian aturan tata bahasa yang mengubah simbol awal menjadi string
  • Penganalisis sintaksis terutama berkaitan dengan konstruksi bahasa yang rekursif, sedangkan penganalisis leksikal memudahkan tugas penganalisis sintaksis dalam DBMS
  • Kelemahan dari metode Syntax Analyzer adalah metode ini tidak akan pernah menentukan apakah suatu token valid atau tidak