Pertemuan 2: Describing Syntax and Semantics

Pertemuan 2: Describing Syntax and Semantics

  October 09, 2017    michael

---

Pada pertemuan hari Sabtu tanggal 7 Oktober 2017, Bu Yanfi menjelaskan tentang materi kedua kami di mata kuliah PLC yaitu "Describing Syntax and Semantics"

Ada beberapa topik dalam materi "Describing Syntax and Semantics" hari ini, yaitu

1. Introduction
2. The General Problem of Describing Syntax
3. Formal Definition of Languages
4. Attribute Grammars
5. Semantics

Topik pertama memperkenalkan tentang pengertian syntax dan semantics. Pengertian syntax adalah struktur dari ekspresi, pernyataan, dan unit program. Sedangkan semantics adalah arti dari ekspresi, pernyataan, dan unit program.

Topik kedua memaparkan masalah umum saat mengdeskripsikan syntax. Masalahnya adalah sebagai berikut:

1. Kalimat adalah serangkaian karakter yang terdiri atas alfabet.
2. Bahasa adalah kumpulan dari kalimat.
3. Lexeme adalah unit syntax tingkat terendah dari sebuah bahasa (mis., *, sum, begin).
4. Token adalah kategori lexeme (mis., identifier).

Topik ketiga menjelaskan definisi formal dari bahasa. Definisinya adalah:

1. Recognizers 
• Perangkat pengenal membaca string masukan lalu membandingkannya dengan alfabet bahasa dan menentukan apakah string masukan termasuk dalam bahasa.
2. Generators
• Perangkat yang menghasilkan kalimat dari bahasa.
• Sebuah perangkat dapat menentukan apakah syntax kalimat tertentu benar secara syntax dengan membandingkannya dengan struktur generator.  

 Topik keempat menjelaskan tentang atribut dalam grammar. Atribut dalam grammar adalah:

1. Context-Free Grammars
• Dikembangkan oleh Noam Chomsky di pertengahan 1950an.
• Perangkat penghasil bahasa, ditujukan untuk mendeskripsikan syntax dari bahasa natural.
• Mengartikan beberapa bahasa yang disebut bahasa bebas konteks.
  
2. Backus-Naur Form (1959)
1. Ditemukan oleh John Backus untuk mengartikan syntax dari Algol 58.
2. BNF setara dengan bahasa bebas konteks.

Ada aturan dalam BNF, yaitu:
Simbol nonterminal bisa memiliki lebih dari satu RHS (Right-Hand side)
     <stmt> → <single_stmt>
             | begin <stmt_list> end 

List sintaksis dideskripsikan dengan pengulangan rekursiSyntactic lists are described using recursion
    <ident_list> →ident
                | ident, <ident_list>

Turunan adalah pengulangan dari aplikasi rumus, dimulai dari simbol mulai dan diakhiri dengan kalimat (semua simbol terminal).

Contoh grammar adalah:
   <program> → <stmts>
   <stmts> → <stmt> | <stmt> ; <stmts>
   <stmt> → <var> = <expr>
   <var> → a | b | c | d
   <expr> → <term> + <term> | <term> - <term>
   <term> → <var> | const

Contoh turunan adalah:
    <program> => <stmts> => <stmt>
                      => <var> = <expr>
                      => a = <expr>
                      => a = <term> + <term>
                      => a = <var> + <term>
                      => a = b + <term>
                      => a = b + const

Pengertian dari turunan adalah:

1. Setiap kumpulan dari simbol dalam turunan adalah bentuk sentensial.
2. Kalimat adalah bentuk sentensial yang hanya memiliki simbol terminal.
3. Turunan yang dimulai dari kiri adalah turunan yang di mana non terminal paling kiri terlebih dahulu yang dibuka, begitu juga sebaliknya.
4. Turunan bisa saja bukan leftmost/rightmost.

Ambiguitas dalam grammar:
Grammar menjadi ambigu jika dan hanya jika ia menghasilkan bentuk sentensial yang meiliki 2 atau lebih parse tree.

Berikut adalah contoh dari grammar ambigu dan tidak ambigu:

Topik kelima atau terkahir berisi tentang semantics. Ada berbagai jenis semantics, yaitu:

1. Statics semantics
2. Operational semantics
3. Denotational semantics
4. Axiomatic semantics

Pengertian static semantics: 

1. Tak ada hubungannya dengan arti.
2. CFG tidak dapat mendeskripsikan semua syntax dalam bahasa
3. Kategori dari konstruksi yang merupakan masalah:
• Bebas-konteks, tapi tidak praktis (mis., tipe dari operands dalam ekspresi).
• Tidak bebas-konteks, (mis., variabel harus dideklarasikan sebelum digunakan).

Pengertian operational semantics:

1. Mendeskripsikan pengertian dari program dengan cara mengeksekusi statementnya dalam mesin, disimulasikan ataupun secara aktual. Perubahan dari kondisi mesin (memori, register, dll) mendefinisikan arti dari statement.
2. Untuk menggunakan operational semantics untuk bahasa tingkat tinggi, dibutuhkan mesin virtual.
3. Kegunaan
• Petunjuk bahasa dan buku cetak   
• Teaching programming languages 
4. Dua tingkat berbeda untuk kegunaan operational semantics:   
• Natural operational semantics
• Structural operational semantics

Pengertian denotational semantics: 

1. Berdasarkan teori fungsi pengulangan rekursi
2. Metode deskripsi semantics yang paling abstrak
3. Awalnya dikembangkan oleh Scott dan Strachey (1970).

Pengertian axiomatic semantics:

1. Berdasarkan logika formal (kalkulus predikat)
2. Tujuan awal: verifikasi program formal
3. Axioms atau Aksioma atau aturan inferensi didefinisikan untuk setiap jenis pernyataan dalam bahasa (untuk memungkinkan transformasi ekspresi logika menjadi ekspresi logika yang lebih formal)
4. Ekspresi logika disebut assertions/pernyataan.

 Itulah materi kedua PLC yang kami pelajari.