Teknik Kompilasi - Pertemuan 4 (Top Down Parsing - Brute Force)

00:11:42
https://www.youtube.com/watch?v=O48gZ-z2YUQ

摘要

TLDRVideo ini membahas metode parsing, dengan fokus pada top-down parsing dan backtracking. Top-down parsing dimulai dari simbol awal dan menelusuri hingga mencapai terminal, sedangkan bottom-up parsing dimulai dari terminal dan menarik kembali ke simbol awal. Contoh backtracking dalam parsing dijelaskan, serta kelemahan metode ini seperti waktu eksekusi yang lambat dan penggunaan memori yang tinggi. Video ini juga membahas rekursif kiri dalam grammar dan cara menghilangkannya.

心得

  • 📚 Parsing adalah proses mengubah struktur data.
  • 🔄 Top-down parsing dimulai dari simbol awal.
  • 🔽 Bottom-up parsing dimulai dari terminal.
  • 🔙 Backtracking memungkinkan penelusuran kembali.
  • ⏳ Kelemahan backtracking: waktu eksekusi lambat.
  • 💾 Backtracking memerlukan banyak memori.
  • 🔄 Rekursif kiri dapat menyebabkan masalah dalam parsing.
  • ✂️ Menghilangkan rekursif kiri dengan memisahkan turunan.
  • 📝 Contoh penggunaan backtracking dalam parsing.
  • 🔍 Pentingnya memahami metode parsing dalam pemrograman.

时间轴

  • 00:00:00 - 00:05:00

    Dalam pertemuan ini, kita membahas tentang metode parsing, yang terbagi kepada dua jenis: top-down dan bottom-up. Top-down parsing bermula dari simbol awal dan menelusuri hingga mencapai terminal. Terdapat beberapa teknik dalam top-down parsing seperti backtracking, no backtrack, dan LL(1) yang menggunakan pendekatan prediktif. Contoh yang diberikan adalah backtracking, di mana proses ini memerlukan memori untuk menyimpan langkah-langkah yang telah diambil. Ketika penelusuran tidak berhasil, proses akan kembali ke langkah sebelumnya untuk mencoba alternatif lain.

  • 00:05:00 - 00:11:42

    Proses backtracking melibatkan penyimpanan setiap langkah dalam memori dan kembali ke langkah terakhir jika tidak menemukan string yang diinginkan. Kelemahan dari metode ini termasuk waktu eksekusi yang lambat, kesulitan dalam koreksi kesalahan, penggunaan memori yang banyak, dan masalah dengan grammar yang memiliki rekursif kiri. Untuk mengatasi rekursif kiri, kita perlu memisahkan turunan yang memiliki rekursif kiri dan yang tidak, lalu mengubahnya menjadi bentuk yang tidak memiliki rekursif kiri. Ini melibatkan penggunaan variabel baru dan mendeskripsikan nilai-nilai yang terlibat.

思维导图

视频问答

  • Apa itu parsing?

    Parsing adalah proses mengubah struktur data dari satu bentuk ke bentuk lain, biasanya dari string menjadi struktur yang lebih terorganisir.

  • Apa perbedaan antara top-down dan bottom-up parsing?

    Top-down parsing dimulai dari simbol awal dan menelusuri ke terminal, sedangkan bottom-up parsing dimulai dari terminal dan menarik kembali ke simbol awal.

  • Apa itu backtracking dalam parsing?

    Backtracking adalah metode dalam parsing yang memungkinkan penelusuran kembali ke langkah sebelumnya jika jalur yang diambil tidak menghasilkan hasil yang diinginkan.

  • Apa kelemahan dari metode backtracking?

    Kelemahan metode backtracking termasuk waktu eksekusi yang lambat, kesulitan dalam koreksi kesalahan, dan penggunaan memori yang tinggi.

  • Apa itu rekursif kiri dalam grammar?

    Rekursif kiri adalah kondisi di mana suatu variabel dalam grammar dapat memanggil dirinya sendiri di posisi paling kiri dalam produksinya.

  • Bagaimana cara menghilangkan rekursif kiri?

    Rekursif kiri dapat dihilangkan dengan memisahkan turunan yang memiliki rekursif kiri dan yang tidak, lalu mengubah variabel yang terlibat.

查看更多视频摘要

即时访问由人工智能支持的免费 YouTube 视频摘要！
字幕
id
自动滚动:
  • 00:00:00
    Halo assalamualaikum warahmatullah
  • 00:00:01
    wabarakatuh dalam pertemuan kali ini
  • 00:00:03
    kita akan bahas mengenai metode parsing
  • 00:00:06
    jika di pertemuan sebelumnya itu kita
  • 00:00:09
    sudah membahas mengenai passing itu apa
  • 00:00:11
    dimana pada pertemuan sebelumnya kita
  • 00:00:14
    sudah mempelajari bahwa passing itu
  • 00:00:16
    adalah mengubah dari timbul
  • 00:00:20
    Mbok menjadi sebuah terminal ya di sini
  • 00:00:26
    dapat kita lihat bahwa parsing sendiri
  • 00:00:29
    itu terbagi menjadi dua yang pertama itu
  • 00:00:31
    adalah top-down dan yang kedua itu
  • 00:00:34
    adalah dimana untuk tapi kita akan mulai
  • 00:00:39
    dari sebuah simbol awal atau kemudian
  • 00:00:44
    kita telusuri sampai dia mendapatkan
  • 00:00:49
    terminal
  • 00:00:52
    Hai GB diprosesnya dia dari root dari
  • 00:00:55
    simbol awal menuju ke Terminal nah ini
  • 00:00:59
    yang kita sebut sebagai top-down passing
  • 00:01:02
    nah sebaliknya kalau dia penelusurannya
  • 00:01:06
    mulai dari terminal dan kita tarik ke
  • 00:01:09
    variabel-variabel sebelumnya sampai kita
  • 00:01:12
    dapatkan root atau simbol awal ini kita
  • 00:01:15
    sebut sebagai bertemu Persib jadi mana
  • 00:01:19
    untuk top-down sendiri itu terdiri dari
  • 00:01:21
    backtrack atau backup asing kemudian no
  • 00:01:25
    backtrack atau rekursif desain parser
  • 00:01:27
    dan juga ll16 untuk ll1 ini sudah
  • 00:01:32
    menggunakan prediktif ini akan kita
  • 00:01:37
    pelajari di pertemuan selanjutnya dan
  • 00:01:40
    untuk Batam apa sing itu juga terdiri er
  • 00:01:43
    pasar dimana ini akan terdiri lagi
  • 00:01:46
    menjadi r0sul R1 L1 dan
  • 00:01:52
    Hai juga ada operator precedence parser
  • 00:01:56
    ini juga akan kita pelajari di pertemuan
  • 00:01:59
    selanjutnya mungkin disini kita akan
  • 00:02:01
    lihat dulu salah satu contoh dari
  • 00:02:03
    top-down passing itu adalah untuk di
  • 00:02:06
    backtrack untuk metodenya itu adalah
  • 00:02:09
    metode
  • 00:02:11
    Hai bruteforce game-game kita lihat aja
  • 00:02:14
    di sini nah disini berarti kita akan
  • 00:02:17
    punya ada kata b-track dan juga ada kata
  • 00:02:20
    backup Negeri dimana untuk ini kita
  • 00:02:24
    nanti akan memerlukan suatu memori dan
  • 00:02:28
    backtrack ini gede kita akan penelusuran
  • 00:02:31
    kembali kita lihat contohnya bisa di
  • 00:02:35
    sini ada sebuah cfd kita akan mencari
  • 00:02:38
    string a-b-c-d untuk di blogspot ini
  • 00:02:42
    karena dia merupakan sebuah tapi kita
  • 00:02:46
    akan mulai dari simbol awak sampai kita
  • 00:02:49
    telusuri sehingga dapat terminalnya atau
  • 00:02:53
    disini untuk atau string yang kita punya
  • 00:02:56
    Knuckle disini kita akan mulai dari si
  • 00:02:59
    esnya DCS Ini dia ada dua turunan yang
  • 00:03:03
    kita pilih itu adalah turunan sebelah
  • 00:03:06
    kiri terlebih dahulu sampai di sini akan
  • 00:03:10
    Disimpan dulu dalam sebuah memori
  • 00:03:14
    kemudian gratis esnya ini kita akan
  • 00:03:18
    turunkan menjadi a-a-a-a besar dan Ping
  • 00:03:22
    nah KB di sini di juga akan disimpan di
  • 00:03:25
    sebuah memori kemudian disini kita akan
  • 00:03:28
    telusuri kembali ini sudah tidak bisa
  • 00:03:30
    kita telusuri
  • 00:03:34
    di media ini sama Rio punya dua turunan
  • 00:03:38
    kita pilih itu adalah yang sebelah kiri
  • 00:03:41
    terlebih dahulu kiri dari fajard89 nya
  • 00:03:59
    adalah a-b-d-e sesuai atau enggak yang
  • 00:04:02
    kita mau cewek ini sini dia tidak cocok
  • 00:04:07
    dengan yang kita inginkan nek dari sini
  • 00:04:11
    ia akan melakukan proses backtrack
  • 00:04:14
    batrenya kemana ke memori terakhir
  • 00:04:18
    sebelum proses ini dijalankan Nah di
  • 00:04:22
    sini ada sebuah backtrack dan kita akan
  • 00:04:26
    melakukan backup ke memori yang
  • 00:04:28
    sebelumnya
  • 00:04:29
    Hai jadi proses selanjutnya akan kembali
  • 00:04:32
    lagi ke proses sarang88 Sisi terakhir
  • 00:04:42
    kita akan telusuri lagi dianya tadi kan
  • 00:04:46
    dia punya dua turunan berarti dia akan
  • 00:04:49
    menjadi faacb00k
  • 00:04:58
    Hai SMS ini jadi kita akan dapatkan
  • 00:05:01
    stringnya adalah ac&m sudah sesuai atau
  • 00:05:05
    belum Ini masih belum kredit sama kita
  • 00:05:09
    lakukan backtrack kembali ke posisi
  • 00:05:13
    terakhirnya ini adalah posisi
  • 00:05:16
    terakhirnya tapi dari posisi terakhir
  • 00:05:19
    ini
  • 00:05:20
    Hai dengan Ya kembali keposisi siakads1
  • 00:05:26
    disini lihat ini masih bisa ditelusuri
  • 00:05:30
    lagi nya sia nya udah nggak bisa jadi
  • 00:05:34
    akan kembali lagi ke sebelum proses ini
  • 00:05:38
    jadi akan kembali ke proses
  • 00:05:42
    Kyle kembali ke proses S
  • 00:05:45
    Hai ini dia akan telusuri nilai yang
  • 00:05:48
    kedua kemudian es a&b besar sama ini
  • 00:05:55
    juga akan disimpan kedalam sebuah memori
  • 00:05:58
    kemudian kita akan melakukan penelusuran
  • 00:06:00
    untuk si Dedenya by
  • 00:06:08
    Hai turunan yang pertama itu adalah cc&c
  • 00:06:15
    sampai sini nih selesai kita dapat
  • 00:06:18
    string adalah a c c dan d ini sudah
  • 00:06:22
    sesuai sesuai proses akan berhenti di
  • 00:06:29
    sini pada tahun punya proses backup dan
  • 00:06:34
    juga proses backup
  • 00:06:37
    Hai jadi dari setiap prosesnya ia akan
  • 00:06:39
    disimpan di dalam memori kemudian saat
  • 00:06:43
    dia tidak mencapai string yang kita
  • 00:06:45
    inginkan biarkan kembali ke memori yang
  • 00:06:48
    sebelumnya
  • 00:06:51
    Oke berarti di sini dapat kita simpulkan
  • 00:06:53
    bahwa untuk proses bridport ini dia
  • 00:06:57
    punya beberapa kelemahan yang pertama
  • 00:06:59
    pasti waktu eksekusi akan menjadi lambat
  • 00:07:02
    karena semua aturan produksi kita akan
  • 00:07:05
    cek Kemudian yang kedua kita akan
  • 00:07:08
    sedikit kesulitan dalam melakukan
  • 00:07:10
    koreksi kesalahan kemudian yang ketiga
  • 00:07:14
    itu kita akan memakan banyak memori
  • 00:07:17
    karena saat proses parsing kita akan
  • 00:07:20
    membuat backup memori untuk kita
  • 00:07:24
    melakukan B cracknya
  • 00:07:27
    ndak kemudian yang empat ini jika kita
  • 00:07:32
    punya grammar yang memiliki rekor
  • 00:07:34
    sendiri
  • 00:07:35
    saat ini kita tidak akan bisa priksa
  • 00:07:38
    karena apa yg akan terjadi lumping
  • 00:07:40
    terus-menerus untuk rekursif kiri masih
  • 00:07:43
    inget ya Jadi jika kita punya sebuah
  • 00:07:46
    variabel-variabel ini itu diulang di
  • 00:07:49
    posisi paling kiri
  • 00:07:52
    mbok bisa disini es maka sabartbs5
  • 00:07:58
    posisi paling kiri bisa seperti ini es
  • 00:08:02
    maka asbansub22 ping terus-menerus kita
  • 00:08:39
    sambil inget lagi nih ke
  • 00:08:41
    Hai cara menghilangkan grammar yang
  • 00:08:44
    memiliki rekursif kiri sedikit review
  • 00:08:48
    aja mengenai rekursif kiri semisal di
  • 00:08:51
    sini ada sebuah CFC ini cfd di sini Iya
  • 00:08:55
    punya sebuah rekursif kiri s.ab dan SBD
  • 00:09:01
    disini dia tidak ada tapi ini tetap
  • 00:09:05
    sebuah grammar yang memiliki rekursif
  • 00:09:08
    kiri untuk kita menghilangkan rekursif
  • 00:09:11
    kirinya dan terlengkap pertama kita akan
  • 00:09:15
    pisahkan turunan-turunan yang memiliki
  • 00:09:17
    rekursif kiri dan yang tidak ya berarti
  • 00:09:19
    kan kita punya ss&r FB dan yang tidak
  • 00:09:26
    itu berarti a-b-d-e dan F
  • 00:09:33
    Dairi yang memiliki rekursif nilai
  • 00:09:36
    setelah terjadi rekursif nya Ki berarti
  • 00:09:40
    disini ini kita sebut sebagai Alfa nah
  • 00:09:44
    disini karena ada dua beradik tersebut
  • 00:09:45
    sebagai aparatur dan Alfa
  • 00:09:48
    Hai nah sisanya yang tidak terjadi
  • 00:09:51
    rekursif jadi kita sebut sebagai beta
  • 00:09:54
    ini kita sebut sebagai beta karena ada
  • 00:09:57
    tiga berarti beta beta 2 dan beta3 Nah
  • 00:10:02
    untuk menghilangkannya kita akan ubah
  • 00:10:06
    esnya ini menjadi
  • 00:10:11
    hai cek nilainya ini menjadi Bid'ah
  • 00:10:14
    berarti asd3 FF dengan kita yang kita
  • 00:10:25
    gabung
  • 00:10:26
    Hai dengan variabel yang baru Nah untuk
  • 00:10:29
    variabelnya ini bebas
  • 00:10:31
    Hai nah tapi biasanya jangkar gunakan
  • 00:10:34
    pada CV itu adalah zat walaupun ini
  • 00:10:38
    bebas ya eh di sini kita inginkan si Ice
  • 00:10:44
    dengan Z Dede dengan z&f juga dengan di
  • 00:10:51
    sini kita punya variabel baru variabel
  • 00:10:55
    barunya harus kita Deskripsikan Nah
  • 00:10:59
    untuk pendeskripsiannya itu adalah
  • 00:11:02
    dengan nilai alfanya jadi z sendiri
  • 00:11:06
    adalah Abby dan BD dengan
  • 00:11:12
    Hai Abi dengan kita padankan dengan sih
  • 00:11:16
    variabel baru tadi ambek z&e
  • 00:11:20
    Hai by DJ adalah cara kita menghilangkan
  • 00:11:26
    Gamer yang memiliki rekor shift kiri eh
  • 00:11:31
    mungkin atau pertemuan hari ini cukup
  • 00:11:32
    untuk yang rekursif descriptors Armada
  • 00:11:35
    akan saya jelaskan di video yang
  • 00:11:36
    terpisah ya Terima kasih semoga
  • 00:11:39
    bermanfaat Wassalamualaikum
  • 00:11:40
    warahmatullah wabarakatuh
标签
  • parsing
  • top-down
  • bottom-up
  • backtracking
  • rekursif kiri
  • grammar
  • metode parsing
  • memori
  • waktu eksekusi
  • koreksi kesalahan