Programming Language Summary Session 2

• Syntax : bentuk atau struktur dari ekspresi, pernyataan, dan unit program
• Semantic : arti dari ekspresi, pernyataan, dan unit program
• Sentence : kumpulan karakter alphabet
• Language : satu set sentence
• Lexeme : level unit sintaktik terendah
• Token : kategori dari lexeme

Mendefinisi Bahasa secara Formal

• Recognizer
  Untuk mendefinisi suatu bahasa dengan metode recognition, dibutuhkan suatu mekanisme yang dikenal dengan recognition device. Recognition device membaca input string dan menentukan apakah input string tersebut termasuk kedalam bahasa tersebut atau tidak.
• Generator
  Generator merupakan suatu alat (device) yang dapat digunakan untuk menghasilkan (generate) kalimat-kalimat dari suatu bahasa. Seseorang dapat menentukan jika syntax dari kalimat tertentu benar secara sintaktik dengan membandingkannya dengan struktur dari generator.

Mendefinisi Syntax dengan Metode Formal

• Context Free Grammar
  – Dikembangkan oleh Noam Chomsky di pertengahan 1950-an
  – Merupakan language generator, awalnya dimaksudkan untuk menjelaskan syntax dari bahasa natural (bahasa manusia)
  – Mendefinisi sebuah kelas bahasa yang dikenal dengan context-free language
• Backus-Naur Form
  – Ditemukan oleh John Backus untuk menjelaskan syntax dari Algol 58
  – BNF ekuivalen dengan context-free grammarBNF Fundamental
  – BNF merupakan metalanguage, bahasa yang digunakan untuk mendeskripsi bahasa lain, dalam bahasa pemrograman
  – Abstraksi digunakan untuk mewakili kelas-kelas struktur sintaktik

  <assign> →<var> = <expression>

  – Teks yang berada disebelah kiri panah, yang tepatnya bernama left-hand side (LHS), merupakan abstraksi yang didefinisikan. Teks yang berada disebelah kanan panah merupakan definisi dari LHS, atau dikenal dengan right-hand side (RHS). Digabungkan, maka mereka menjadi rule atau production.
  – Abstraksi di suatu deskripsi atau grammar BNF biasa disebut nonterminal symbol, atau singkatnya nonterminal, dan lexeme dan token dari rule dikenal dengan terminal symbol, atau singkatnya terminal. Nonterminal biasa diapit oleh kurung sudut (<>).
  – Grammar merupakan suatu set rule berisi yang terbatas
  – Start symbol merupakan suatu elemen spesial nonterminal dari suatu grammar

• BNF Rule
  – Suatu abstraksi (atau nonterminal symbol) dapat memiliki lebih dari satu RHS
  – Contoh:

  <if_stmt> →if ( <logic_expr> ) <stmt>

• Menjelaskan List
  – Suatu rule dikatakan recursive jika LHS-nya muncul di RHS-nya.
  – Sintaktik list dijelaskan melalui recursion

  <ident_list> →identifier| identifier, <ident_list>

Grammar, Parse Tree, Derivation

• Derivation
  – Derivation merupakan suatu aplikasi rule berulang, dimulai dengan start symbol dan diakhiri dengan suatu sentence (semua terminal symbol)
  – Sentence merupakan sebuah sentential form yang hanya memiliki terminal symbol
  – Tiap string di derivation merupakan sebuah sentential form
  – Leftmost derivation merupakan derivation yang nonterminal paling kiri (leftmost) di tiap sentential formnya yang terganti
  – Suatu derivation bisa saja tidak leftmost ataupun rightmost
  – Contoh:

  <program> => begin <stmt_list> end

  => begin <stmt> ; <stmt_list> end
  => begin <var> = <expression> ; <stmt_list> end
  => begin A = <expression> ; <stmt_list> end
  => begin A = <var> + <var> ; <stmt_list> end
  => begin A = B + <var> ; <stmt_list> end
  => begin A = B + C ; <stmt_list> end
  => begin A = B + C ; <stmt> end
  => begin A = B + C ; <var> = <expression> end
  => begin A = B + C ; B = <expression> end
  => begin A = B + C ; B = <var> end
  => begin A = B + C ; B = C end

• Parse Tree
  – Struktur hirearki sintaktik dari suatu bahasa disebut parse tree
• Grammar
  – Suatu grammar dikatakan ambigu (ambiguous) jika dan hanya jika ia menghasilkan sebuah sentential form yang memiliki dua atau lebih parse tree berbeda
  – Contoh grammar ambigu:

  <expr>  <expr> <op> <expr> | const<op>  / | –

  – Untuk mengatasi keambiguan dalam grammar, maka digunakan precedence level. Operator yang memiliki precedence tertinggi akan dipaksa berada dipaling bawah parse tree, sehingga operator tersebut akan dikerjakan lebih dahulu

  
  – Contoh grammar tak ambigu (unambiguous)

  <expr>  <expr> – <term> | <term><term>  <term> / const| const

  – Ketika suatu operator memiliki precedence level yang sama, maka tingkat pengerjaan akan diselesaikan secara asosiatif, dikenal dengan associativity.

Static Semantic

• Tidak berhubungan dengan arti
• Muncul ketika context-free grammar (CFG) tidak dapat menjelaskan semua syntax dari bahasa pemrograman
• Masalah yang dapat dipecahkan:
  – Context-free, tipe operand di expression
  – Non-context-free, variable harus dideklarasi sebelum digunakan

Attribute Grammar

• Attribute grammar merupakan CFG dengan beberapa tambahan berikut:
  – Untuk tiap grammar simbol x terdapat sebuah himpunan A(x) dari nilai atribut
  – Tiap rule memiliki suatu set function yang mendefinisi atribut tertentu dari nonterminal di rule tersebut
  – Tiap rule memiliki (ada kemungkinan kosong) suatu set predikat untuk memeriksa kekonsistenan atribut
• Atrribute grammar (AG) memiliki penambahan ke CFG untuk membawa beberapa informasi semantic ke node parse tree
• Nilai utama dari AG:
  – Specifikasi static semantic
  – Desain compiler (pengecekan static semantic)
• Contoh:
  – Syntax

  <assign> →<var> = <expr>
  <expr> →<var> + <var>
  | <var>
  <var> →A | B | C

  – actual_type: disintetis untuk <var> dan <expr>
  – expected_type: diturunkan dari <expr>

Semantic

• Tidak ada notasi atau formalisme yang dipakai secara luas untuk menjelaskan semantic
• Beberapa keperluan untuk suatu metodologi dan notasi untuk semantic:
  – Programmer harus mengetahui maksud dari pernyataan
  – Penulis compiler harus tau secara tepat apa yang dilakukan language construct
  – Bukti kebenaran akan mungkin
  – Compiler generator akan mungkin
  – Designer dapat mendeteksi ambiguitas dan ketidak-konsistenan

Operational Semantic

• Menjelaskan arti dari suatu program dengan mengeksekusi pernyataan-pernyataannya di suatu mesin, dengan simulasi ataupun aktual. Perubahan keadaan dari mesin (memori, register, dll) menjelaskan arti dari pernyataan tersebut
• Untuk menggunakan operational semantic di bahasa level-tinggi, diperlukan mesin virtual
• Kegunaan operational semantic:
  – Panduan bahasa dan textbook
  – Mengajar bahasa pemrograman
• Dua level berbeda mengunakan operational semantic:
  – Natural operational semantic
  – Structural operational semantic
• Evaluasi:
  – Baik jika digunakan tidak formal (panduan bahasa,dll)
  – Sangat kompleks jika digunakan secara formal (VDL)

Denotational Semantic

• Metode formal paling dikenal untuk mendeskripsikan maksud dari suatu program
• Diinspirasi dari teori fungsi rekursif
• Metode deskripsi semantic paling abstrak
• Awalnya dikembangkan oleh Scott dan Strachey pada tahun 1970
• Proses membangun spesifikasi denotational untuk suatu bahasa pemrograman membutuhkan pendefinisian objek matematika untuk tiap entitas bahasa
• Disebut detonational karena objek matematika menyatakan (denote) arti dari entitas sintaktik yang sesuai
• Maksud dari language construct didefinisikan hanya oleh nilai dari variable program

Aximoatic Semantic

• Diinspiirasi dari logika formal (predikat kalkulus)
• Merupakan pendekatan paling abstrak ke spesifikasi semantic dari yang sebelumnya telah dibahas
• Awalnya diciptakan untuk memverifikasi program secara formal
• Axiom atau inference rule didefinisikan untuk tiap pernyataan di bahasa tersebut (agar dapat mentransformasi ekspresi logika menjadi ekspresi logika yang lebih formal)
• Ekspresi logika dikenal dengan assertion

Sumber :

• Concept of Programming Languages Tenth Edition / Robert W. Sebesta (Chapter 3) & Describing Syntax and Semantics / Binus Powerpoint Presentation
• Unambigous Parse Tree Picture